A simple proof for the iteration complexity of the proximal gradient algorithm

Nuri Denizcan Vanli; Mert Gürbüzbalaban; Asuman Ozdaglar

Publications · Conference paper · OPT@NeurIPS 2016

A simple proof for the iteration complexity of the proximal gradient algorithm

Nuri Denizcan Vanli, Mert Gürbüzbalaban, Asuman Ozdaglar

OPT 2016: NeurIPS Workshop on Optimization for Machine Learning, 2016.

In brief

A short, self-contained proof that the proximal gradient method converges at the rate O(1/k) in function value for composite convex problems — a smooth term plus a nonsmooth regularizer handled through its proximal map — built on one elementary inequality rather than the usual machinery, so the argument fits in a page and is easy to teach.

Topics

Incremental methods & data ordering

Cite

@inproceedings{vanli2016simpleproof,
  title   = {A simple proof for the iteration complexity of the proximal gradient algorithm},
  author  = {Nuri Denizcan Vanli and Mert Gürbüzbalaban and Asuman Ozdaglar},
  year    = {2016},
  booktitle = {OPT 2016: NeurIPS Workshop on Optimization for Machine Learning},
}

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