A globally convergent incremental Newton method

Mathematical Programming, 151(1), pp. 283–313, 2015.

Publisher (DOI)

An incremental Newton method that processes the component functions one at a time with second-order information and, unlike earlier incremental Newton schemes, is proved to converge from any starting point. With a constant stepsize it converges linearly on strongly convex problems, and with diminishing stepsizes it converges at an explicit sublinear rate.

Incremental methods & data ordering

• Why random reshuffling beats stochastic gradient descent (Math. Program., 2021)
• Randomness and permutations in coordinate descent methods (Math. Program., 2020)
• Convergence rate of incremental gradient and incremental Newton methods (SIAM J. Optim., 2019)
• Global convergence rate of proximal incremental aggregated gradient methods (SIAM J. Optim., 2018)
• Surpassing gradient descent provably: a cyclic incremental method with linear convergence rate (SIAM J. Optim., 2018)