On the convergence rate of incremental aggregated gradient algorithms

Mert Gürbüzbalaban; Asuman Ozdaglar; Pablo A. Parrilo

doi:10.1137/15M1049695

Publications · Journal article · SIAM J. Optim. 2017

On the convergence rate of incremental aggregated gradient algorithms

Mert Gürbüzbalaban, Asuman Ozdaglar, Pablo A. Parrilo

SIAM Journal on Optimization, 27(2), pp. 1035–1048, 2017.

Publisher (DOI)

In brief

Establishes the first linear convergence rate guarantees for incremental aggregated gradient methods — the deterministic-order counterparts of SAG-type algorithms — with explicit dependence on the problem conditioning and the delay in gradient information.

Topics

Incremental methods & data ordering

Cite

@article{gurbuzbalaban2017iag,
  title   = {On the convergence rate of incremental aggregated gradient algorithms},
  author  = {Mert Gürbüzbalaban and Asuman Ozdaglar and Pablo A. Parrilo},
  year    = {2017},
  journal = {SIAM Journal on Optimization},
  volume  = {27(2)},
  pages   = {1035--1048},
  doi     = {10.1137/15M1049695},
}

Relatedsame topics

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)

← All publications · Research program · Mert Gürbüzbalaban