# Fastest Rates for Stochastic Mirror Descent Methods

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Mar 2018.

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

- [Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize](https://mlsanity.com/paper/2110.15412/) (2021)
- [Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergence](https://mlsanity.com/paper/2402.17722/) (2024)
- [Understanding Stochastic Natural Gradient Variational Inference](https://mlsanity.com/paper/2406.01870/) (2024)
- [Nonconvex Stochastic Bregman Proximal Gradient Method with Application to Deep Learning](https://mlsanity.com/paper/2306.14522/) (2023)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [Stochastic Mirror Descent for Low-Rank Tensor Decomposition Under Non-Euclidean Losses](https://mlsanity.com/paper/2104.14562/) (2021)
- [Natural Gradient VI: Guarantees for Non-Conjugate Models](https://mlsanity.com/paper/2510.19163/) (2025)
- [Fast Minimization of Expected Logarithmic Loss via Stochastic Dual Averaging](https://mlsanity.com/paper/2311.02557/) (2023)
- [Sinkhorn Flow: A Continuous-Time Framework for Understanding and Generalizing the Sinkhorn Algorithm](https://mlsanity.com/paper/2311.16706/) (2023)
- [Shuffling the Stochastic Mirror Descent via Dual Lipschitz Continuity and Kernel Conditioning](https://mlsanity.com/paper/2603.16042/) (2026)
- [Convergence of projected stochastic natural gradient variational inference for various step size and sample or batch size schedules](https://mlsanity.com/paper/2604.00683/) (2026)
- [Convergence Rates for the MAP of an Exponential Family and Stochastic Mirror Descent -- an Open Problem](https://mlsanity.com/paper/2111.06826/) (2021)
- [Mitigating Divergence of Latent Factors via Dual Ascent for Low Latency Event Prediction Models](https://mlsanity.com/paper/2111.07866/) (2021)
- [SPIRAL: A superlinearly convergent incremental proximal algorithm for nonconvex finite sum minimization](https://mlsanity.com/paper/2207.08195/) (2022)

## Abstract (arXiv)

Relative smoothness - a notion introduced by Birnbaum et al. (2011) and rediscovered by Bauschke et al. (2016) and Lu et al. (2016) - generalizes the standard notion of smoothness typically used in the analysis of gradient type methods. In this work we are taking ideas from well studied field of stochastic convex optimization and using them in order to obtain faster algorithms for minimizing relatively smooth functions. We propose and analyze two new algorithms: Relative Randomized Coordinate Descent (relRCD) and Relative Stochastic Gradient Descent (relSGD), both generalizing famous algorithms in the standard smooth setting. The methods we propose can be in fact seen as a particular instances of stochastic mirror descent algorithms. One of them, relRCD corresponds to the first stochastic variant of mirror descent algorithm with linear convergence rate.