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

arXiv: https://arxiv.org/abs/2110.15412 · HTML: https://mlsanity.com/paper/2110.15412/

## Key facts

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

## Builds on (most cited first, 30 of 30)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes](https://mlsanity.com/paper/1805.08114/) (2018)
- [The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning](https://mlsanity.com/paper/1712.06559/) (2017)
- [Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron](https://mlsanity.com/paper/1810.07288/) (2018)
- [Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence](https://mlsanity.com/paper/2002.10542/) (2020)
- [Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates](https://mlsanity.com/paper/1905.09997/) (2019)
- [Relatively-Smooth Convex Optimization by First-Order Methods, and Applications](https://mlsanity.com/paper/1610.05708/) (2016)
- [Scale-Free Online Learning](https://mlsanity.com/paper/1601.01974/) (2016)
- [SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation](https://mlsanity.com/paper/2006.10311/) (2020)
- [Revisiting the Polyak step size](https://mlsanity.com/paper/1905.00313/) (2019)
- [Momentum and Stochastic Momentum for Stochastic Gradient, Newton, Proximal Point and Subspace Descent Methods](https://mlsanity.com/paper/1712.09677/) (2017)
- [Training Neural Networks for and by Interpolation](https://mlsanity.com/paper/1906.05661/) (2019)
- [Stochastic Mirror Descent on Overparameterized Nonlinear Models: Convergence, Implicit Regularization, and Generalization](https://mlsanity.com/paper/1906.03830/) (2019)
- [Subgradient methods for sharp weakly convex functions](https://mlsanity.com/paper/1803.02461/) (2018)
- [Stochastic Gradient/Mirror Descent: Minimax Optimality and Implicit Regularization](https://mlsanity.com/paper/1806.00952/) (2018)
- [L4: Practical loss-based stepsize adaptation for deep learning](https://mlsanity.com/paper/1802.05074/) (2018)
- [Fast Stochastic Bregman Gradient Methods: Sharp Analysis and Variance Reduction](https://mlsanity.com/paper/2104.09813/) (2021)
- [A general class of surrogate functions for stable and efficient reinforcement learning](https://mlsanity.com/paper/2108.05828/) (2021)
- [Fastest Rates for Stochastic Mirror Descent Methods](https://mlsanity.com/paper/1803.07374/) (2018)
- [Dual-Free Stochastic Decentralized Optimization with Variance Reduction](https://mlsanity.com/paper/2006.14384/) (2020)
- [Primal-dual subgradient methods for minimizing uniformly convex functions](https://mlsanity.com/paper/1401.1792/) (2014)
- [Stochastic Gradient Descent with Polyak's Learning Rate](https://mlsanity.com/paper/1903.08688/) (2019)
- [Mirror Descent and Convex Optimization Problems With Non-Smooth Inequality Constraints](https://mlsanity.com/paper/1710.06612/) (2017)
- [Convergence Analysis of Inexact Randomized Iterative Methods](https://mlsanity.com/paper/1903.07971/) (2019)
- [Improved Complexities for Stochastic Conditional Gradient Methods under Interpolation-like Conditions](https://mlsanity.com/paper/2006.08167/) (2020)
- [Adaptive Stochastic Mirror Descent for Constrained Optimization](https://mlsanity.com/paper/1705.02031/) (2017)
- [Randomized Bregman Coordinate Descent Methods for Non-Lipschitz Optimization](https://mlsanity.com/paper/2001.05202/) (2020)

## Built on by (most cited first, 22 of 22)

- [Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variance](https://mlsanity.com/paper/2202.11632/) (2022)
- [Low-rank Optimal Transport: Approximation, Statistics and Debiasing](https://mlsanity.com/paper/2205.12365/) (2022)
- [Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditions](https://mlsanity.com/paper/2302.14043/) (2023)
- [Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performance](https://mlsanity.com/paper/2406.04142/) (2024)
- [Remove that Square Root: A New Efficient Scale-Invariant Version of AdaGrad](https://mlsanity.com/paper/2403.02648/) (2024)
- [Locally Adaptive Federated Learning](https://mlsanity.com/paper/2307.06306/) (2023)
- [New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Results](https://mlsanity.com/paper/2505.20219/) (2025)
- [SANIA: Polyak-type Optimization Framework Leads to Scale Invariant Stochastic Algorithms](https://mlsanity.com/paper/2312.17369/) (2023)
- [Generalized Exponentiated Gradient Algorithms and Their Application to On-Line Portfolio Selection](https://mlsanity.com/paper/2406.00655/) (2024)
- [Primal-dual algorithm for contextual stochastic combinatorial optimization](https://mlsanity.com/paper/2505.04757/) (2025)
- [Decision-Aware Actor-Critic with Function Approximation and Theoretical Guarantees](https://mlsanity.com/paper/2305.15249/) (2023)
- [Bias-Optimal Bounds for SGD: A Computer-Aided Lyapunov Analysis](https://mlsanity.com/paper/2505.17965/) (2025)
- [Taking the Road Less Scheduled with Adaptive Polyak Steps](https://mlsanity.com/paper/2511.07767/) (2025)
- [Safeguarded Stochastic Polyak Step Sizes for Non-smooth Optimization: Robust Performance Without Small (Sub)Gradients](https://mlsanity.com/paper/2512.02342/) (2025)
- [Fast Minimization of Expected Logarithmic Loss via Stochastic Dual Averaging](https://mlsanity.com/paper/2311.02557/) (2023)
- [Implicit Bias and Convergence of Matrix Stochastic Mirror Descent](https://mlsanity.com/paper/2602.18997/) (2026)
- [Shuffling the Stochastic Mirror Descent via Dual Lipschitz Continuity and Kernel Conditioning](https://mlsanity.com/paper/2603.16042/) (2026)
- [Adaptive Sharpness-Aware Minimization with a Polyak-type Step size: A Theory-Grounded Scheduler](https://mlsanity.com/paper/2606.01827/) (2026)
- [Convergence Rates for the MAP of an Exponential Family and Stochastic Mirror Descent -- an Open Problem](https://mlsanity.com/paper/2111.06826/) (2021)
- [Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation](https://mlsanity.com/paper/2404.02378/) (2024)
- [Mirror Descent Beyond Euclidean Stability: An Exponential Separation in Initialization Sensitivity](https://mlsanity.com/paper/2606.11431/) (2026)
- [Polyak-Type Extragradient Methods for Monotone Root-Finding Problems](https://mlsanity.com/paper/2609.26581/) (2026)

## 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.