A Stochastic Newton Method for Nonlinear Equations

Source 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.