# Linear Convergence of Generalized Mirror Descent with Time-Dependent Mirrors

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Sep 2020.

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

- [Mask in the Mirror: Implicit Sparsification](https://mlsanity.com/paper/2408.09966/) (2024)
- [Mirror, Mirror of the Flow: How Does Regularization Shape Implicit Bias?](https://mlsanity.com/paper/2504.12883/) (2025)
- [Differentiable Bilevel Programming for Stackelberg Congestion Games](https://mlsanity.com/paper/2209.07618/) (2022)
- [A Mirror Descent Perspective of Smoothed Sign Descent](https://mlsanity.com/paper/2410.14158/) (2024)
- [Configurable Mirror Descent: Towards a Unification of Decision Making](https://mlsanity.com/paper/2405.11746/) (2024)

## Abstract (arXiv)

The Polyak-Lojasiewicz (PL) inequality is a sufficient condition for establishing linear convergence of gradient descent, even in non-convex settings. While several recent works use a PL-based analysis to establish linear convergence of stochastic gradient descent methods, the question remains as to whether a similar analysis can be conducted for more general optimization methods. In this work, we present a PL-based analysis for linear convergence of generalized mirror descent (GMD), a generalization of mirror descent with a possibly time-dependent mirror. GMD subsumes popular first order optimization methods including gradient descent, mirror descent, and preconditioned gradient descent methods such as Adagrad. Since the standard PL analysis cannot be extended naturally from GMD to stochastic GMD, we present a Taylor-series based analysis to establish sufficient conditions for linear convergence of stochastic GMD. As a corollary, our result establishes sufficient conditions and provides learning rates for linear convergence of stochastic mirror descent and Adagrad. Lastly, for functions that are locally PL*, our analysis implies existence of an interpolating solution and convergence of GMD to this solution.