Convergence rate of incremental gradient and incremental Newton methods

SIAM Journal on Optimization, 29(4), pp. 2542–2565, 2019.

Publisher (DOI)

Pins down how fast the incremental gradient method — a fixed pass over the component functions with a diminishing stepsize — converges on strongly convex problems: with stepsize proportional to 1/k^s the rate is of order 1/k^s in the distance to the optimum, with the 1/k rate attainable when the constant is chosen correctly, and the incremental Newton method achieves the 1/k rate without that tuning.

The playground Why random reshuffling beats SGD lets you try the ideas of this paper in the browser.

The research note Why random reshuffling beats SGD explains the paper informally.

Incremental methods & data ordering

• Why random reshuffling beats stochastic gradient descent (Math. Program., 2021)
• Randomness and permutations in coordinate descent methods (Math. Program., 2020)
• 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)
• A double incremental aggregated gradient method with linear convergence rate for large-scale optimization (ICASSP, 2017)