A Stochastic Newton Method for Nonlinear Equations (Journal of Computational Mathematics, 2023)
In this paper, we study a stochastic Newton method for nonlinear equations, whoseexact function information is difficult to obtain while only stochastic approximations areavailable. At each iteration of the proposed algorithm, an inexact Newton step is firstcomputed based on stochastic zeroth- and first-order oracles. To encourage the possiblereduction of the optimality error, we then take the unit step size if it is acceptable by aninexact Armijo line search condition. Otherwise, a small step size will be taken to helpinduce desired good properties. Then we investigate convergence properties of the proposedalgorithm and obtain the almost sure global convergence under certain conditions. We alsoexplore the computational complexities to find an approximate solution in terms of calls tostochastic zeroth- and first-order oracles, when the proposed algorithm returns a randomlychosen output. Furthermore, we analyze the local convergence properties of the algorithmand establish the local convergence rate in high probability. At last we present preliminarynumerical tests and the results demonstrate the promising performances of the proposedalgorithm.
Keywords: Nonlinear equations; Stochastic approximation; Line search; Global convergence; Computational complexity; Local convergence rate.