mlsanityData to 7 Oct 2026

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

arXiv 2110.15412 ↗First posted 28 Oct 2021math.OC cs.LGcited by 22

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 22 papers in the map (data through 7 Oct 2026). Builds on 30 of its 81 references that are in the map. First posted on arXiv 28 Oct 2021.

Builds on

30 of 81 references.

References · 30

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2014Convex Optimization: Algorithms and Complexitycited by 569
  3. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
  4. 2019SGD: General Analysis and Improved Ratescited by 206
  5. 2018On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizescited by 155
  6. 2017The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learningcited by 150
  7. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  8. 2020Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergencecited by 137
  9. 2019Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Ratescited by 119
  10. 2016Relatively-Smooth Convex Optimization by First-Order Methods, and Applicationscited by 108
  11. 2016Scale-Free Online Learningcited by 83
  12. 2020SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolationcited by 66
18 more
  1. 2019Revisiting the Polyak step sizecited by 55
  2. 2017Momentum and Stochastic Momentum for Stochastic Gradient, Newton, Proximal Point and Subspace Descent Methodscited by 49
  3. 2019Training Neural Networks for and by Interpolationcited by 45
  4. 2019Stochastic Mirror Descent on Overparameterized Nonlinear Models: Convergence, Implicit Regularization, and Generalizationcited by 40
  5. 2018Subgradient methods for sharp weakly convex functionscited by 33
  6. 2018Stochastic Gradient/Mirror Descent: Minimax Optimality and Implicit Regularizationcited by 29
  7. 2018L4: Practical loss-based stepsize adaptation for deep learningcited by 26
  8. 2021Fast Stochastic Bregman Gradient Methods: Sharp Analysis and Variance Reductioncited by 19
  9. 2021A general class of surrogate functions for stable and efficient reinforcement learningcited by 16
  10. 2018Fastest Rates for Stochastic Mirror Descent Methodscited by 14
  11. 2020Dual-Free Stochastic Decentralized Optimization with Variance Reductioncited by 12
  12. 2014Primal-dual subgradient methods for minimizing uniformly convex functionscited by 11
  13. 2019Stochastic Gradient Descent with Polyak's Learning Ratecited by 11
  14. 2017Mirror Descent and Convex Optimization Problems With Non-Smooth Inequality Constraintscited by 10
  15. 2019Convergence Analysis of Inexact Randomized Iterative Methodscited by 8
  16. 2020Improved Complexities for Stochastic Conditional Gradient Methods under Interpolation-like Conditionscited by 2
  17. 2017Adaptive Stochastic Mirror Descent for Constrained Optimizationcited by 1
  18. 2020Randomized Bregman Coordinate Descent Methods for Non-Lipschitz Optimizationcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 2; 2023: 5; 2024: 4; 2025: 5; 2026: 5.

22 papers.

Sort:

  1. 2022Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variancecited by 22
  2. 2022Low-rank Optimal Transport: Approximation, Statistics and Debiasingcited by 21
  3. 2023Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditionscited by 14
  4. 2024Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performancecited by 13
  5. 2024Remove that Square Root: A New Efficient Scale-Invariant Version of AdaGradcited by 8
  6. 2023Locally Adaptive Federated Learningcited by 7
  7. 2025New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Resultscited by 6
  8. 2023SANIA: Polyak-type Optimization Framework Leads to Scale Invariant Stochastic Algorithmscited by 5
  9. 2024Generalized Exponentiated Gradient Algorithms and Their Application to On-Line Portfolio Selectioncited by 5
  10. 2025Primal-dual algorithm for contextual stochastic combinatorial optimizationcited by 4
  11. 2023Decision-Aware Actor-Critic with Function Approximation and Theoretical Guaranteescited by 3
  12. 2025Bias-Optimal Bounds for SGD: A Computer-Aided Lyapunov Analysiscited by 2
10 more
  1. 2025Taking the Road Less Scheduled with Adaptive Polyak Stepscited by 2
  2. 2025Safeguarded Stochastic Polyak Step Sizes for Non-smooth Optimization: Robust Performance Without Small (Sub)Gradientscited by 2
  3. 2023Fast Minimization of Expected Logarithmic Loss via Stochastic Dual Averagingcited by 1
  4. 2026Implicit Bias and Convergence of Matrix Stochastic Mirror Descentcited by 1
  5. 2026Shuffling the Stochastic Mirror Descent via Dual Lipschitz Continuity and Kernel Conditioningcited by 1
  6. 2026Adaptive Sharpness-Aware Minimization with a Polyak-type Step size: A Theory-Grounded Schedulercited by 1
  7. 2021Convergence Rates for the MAP of an Exponential Family and Stochastic Mirror Descent -- an Open Problemcited by 0
  8. 2024Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolationcited by 0
  9. 2026Mirror Descent Beyond Euclidean Stability: An Exponential Separation in Initialization Sensitivitycited by 0
  10. 2026Polyak-Type Extragradient Methods for Monotone Root-Finding Problemscited by 0