Surpassing gradient descent provably: a cyclic incremental method with linear convergence rate

SIAM Journal on Optimization, 28(2), pp. 1420–1447, 2018.

Publisher (DOI)arXiv:1611.00347

An incremental method that provably beats full gradient descent. DIAG aggregates both the gradients and the iterates of the component functions in a fixed cyclic order, converges linearly, and does so at a rate that is strictly better than gradient descent’s for the same amount of gradient computation — the first such guarantee for a cyclic incremental method.

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)
• A double incremental aggregated gradient method with linear convergence rate for large-scale optimization (ICASSP, 2017)