Sequential convergence of AdaGrad algorithm for smooth convex optimization

By Cheik Traoré, Edouard Pauwels. 2020

30 citations recorded by the source corpus.

We prove that the iterates produced by, either the scalar step size variant, or the coordinatewise variant of AdaGrad algorithm, are convergent sequences when applied to convex objective functions with Lipschitz gradient. The key insight is to remark that such AdaGrad sequences satisfy a variable metric quasi-Fej\'er monotonicity property, which allows to prove convergence.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Numerical Analysis, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

1. Nicolas Loizou
2. Simon Lacoste-Julien
3. Peter Richtárik
4. Antonio Orvieto
5. Gauthier Gidel
6. Sebastian U. Stich
7. Francis R. Bach
8. Martin Takác

In Computational Theory and Mathematics

1. Nicolas Loizou
2. Simon Lacoste-Julien
3. Antonio Orvieto
4. Peter Richtárik
5. Zeyuan Allen-Zhu
6. Jakub Konecný
7. Francis R. Bach
8. Filip Hanzely

In Numerical Analysis

1. Simon Lacoste-Julien
2. Nicolas Loizou
3. Antonio Orvieto
4. Sebastian U. Stich

In Optimization & Training

1. Nicolas Loizou
2. Simon Lacoste-Julien
3. Peter Richtárik
4. Antonio Orvieto
5. Gauthier Gidel
6. Sebastian U. Stich
7. Martin Jaggi
8. Francis R. Bach

Citations in the corpus

• Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution (2022, background): “To the best of our knowledge, no such result exist for AdaGrad — except [30], for the deterministic case.”