arrow
Volume 41, Issue 6
A Stochastic Newton Method for Nonlinear Equations

Jiani Wang, Xiao Wang & Liwei Zhang

J. Comp. Math., 41 (2023), pp. 1192-1221.

Published online: 2023-11

Export citation
  • Abstract

In this paper, we study a stochastic Newton method for nonlinear equations, whose exact function information is difficult to obtain while only stochastic approximations are available. At each iteration of the proposed algorithm, an inexact Newton step is first computed based on stochastic zeroth- and first-order oracles. To encourage the possible reduction of the optimality error, we then take the unit step size if it is acceptable by an inexact Armijo line search condition. Otherwise, a small step size will be taken to help induce desired good properties. Then we investigate convergence properties of the proposed algorithm and obtain the almost sure global convergence under certain conditions. We also explore the computational complexities to find an approximate solution in terms of calls to stochastic zeroth- and first-order oracles, when the proposed algorithm returns a randomly chosen output. Furthermore, we analyze the local convergence properties of the algorithm and establish the local convergence rate in high probability. At last we present preliminary numerical tests and the results demonstrate the promising performances of the proposed algorithm.

  • AMS Subject Headings

49M37, 65K05, 90C30

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{JCM-41-1192, author = {Wang , JianiWang , Xiao and Zhang , Liwei}, title = {A Stochastic Newton Method for Nonlinear Equations}, journal = {Journal of Computational Mathematics}, year = {2023}, volume = {41}, number = {6}, pages = {1192--1221}, abstract = {

In this paper, we study a stochastic Newton method for nonlinear equations, whose exact function information is difficult to obtain while only stochastic approximations are available. At each iteration of the proposed algorithm, an inexact Newton step is first computed based on stochastic zeroth- and first-order oracles. To encourage the possible reduction of the optimality error, we then take the unit step size if it is acceptable by an inexact Armijo line search condition. Otherwise, a small step size will be taken to help induce desired good properties. Then we investigate convergence properties of the proposed algorithm and obtain the almost sure global convergence under certain conditions. We also explore the computational complexities to find an approximate solution in terms of calls to stochastic zeroth- and first-order oracles, when the proposed algorithm returns a randomly chosen output. Furthermore, we analyze the local convergence properties of the algorithm and establish the local convergence rate in high probability. At last we present preliminary numerical tests and the results demonstrate the promising performances of the proposed algorithm.

}, issn = {1991-7139}, doi = {https://doi.org/10.4208/jcm.2112-m2021-0072}, url = {http://global-sci.org/intro/article_detail/jcm/22109.html} }
TY - JOUR T1 - A Stochastic Newton Method for Nonlinear Equations AU - Wang , Jiani AU - Wang , Xiao AU - Zhang , Liwei JO - Journal of Computational Mathematics VL - 6 SP - 1192 EP - 1221 PY - 2023 DA - 2023/11 SN - 41 DO - http://doi.org/10.4208/jcm.2112-m2021-0072 UR - https://global-sci.org/intro/article_detail/jcm/22109.html KW - Nonlinear equations, Stochastic approximation, Line search, Global convergence, Computational complexity, Local convergence rate. AB -

In this paper, we study a stochastic Newton method for nonlinear equations, whose exact function information is difficult to obtain while only stochastic approximations are available. At each iteration of the proposed algorithm, an inexact Newton step is first computed based on stochastic zeroth- and first-order oracles. To encourage the possible reduction of the optimality error, we then take the unit step size if it is acceptable by an inexact Armijo line search condition. Otherwise, a small step size will be taken to help induce desired good properties. Then we investigate convergence properties of the proposed algorithm and obtain the almost sure global convergence under certain conditions. We also explore the computational complexities to find an approximate solution in terms of calls to stochastic zeroth- and first-order oracles, when the proposed algorithm returns a randomly chosen output. Furthermore, we analyze the local convergence properties of the algorithm and establish the local convergence rate in high probability. At last we present preliminary numerical tests and the results demonstrate the promising performances of the proposed algorithm.

Wang , JianiWang , Xiao and Zhang , Liwei. (2023). A Stochastic Newton Method for Nonlinear Equations. Journal of Computational Mathematics. 41 (6). 1192-1221. doi:10.4208/jcm.2112-m2021-0072
Copy to clipboard
The citation has been copied to your clipboard