Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize

By Ryan D'Orazio, Nicolas Loizou, Issam Hadj Laradji, Ioannis Mitliagkas. 2021

42 citations recorded by the source corpus.

We investigate the convergence of stochastic mirror descent (SMD) under interpolation in relatively smooth and smooth convex optimization. In relatively smooth convex optimization we provide new convergence guarantees for SMD with a constant stepsize. For smooth convex optimization we propose a new adaptive stepsize scheme -- the mirror stochastic Polyak stepsize (mSPS). Notably, our convergence results in both settings do not make bounded gradient assumptions or bounded variance assumptions, and we show convergence to a neighborhood that vanishes under interpolation. Consequently, these results correspond to the first convergence guarantees under interpolation for the exponentiated gradient algorithm for fixed or adaptive stepsizes. mSPS generalizes the recently proposed stochastic Polyak stepsize (SPS) (Loizou et al. 2021) to mirror descent and remains both practical and efficient for modern machine learning applications while inheriting the benefits of mirror descent. We complement our results with experiments across various supervised learning tasks and different instances of SMD, demonstrating the effectiveness of mSPS.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research, 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 Artificial Intelligence

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

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 Management Science and Operations Research

1. Simon Lacoste-Julien
2. Nicolas Loizou
3. Antonio Orvieto
4. Peter Richtárik

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, methodology): “, 2020), and include Adam (Kingma and Ba, 2014), Adagrad (Duchi et al., 2011), and RMSprop (Tieleman and Hinton, 2012). Ideally, a theoretically grounded adaptive method should yield fast convergence to X ∗ without knowledge of problem dependent parameters, such as the gradient Lipshitz constant or ”