# The Statistical Complexity of Early-Stopped Mirror Descent

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Feb 2020.

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

- [Implicit Bias of SGD for Diagonal Linear Networks: a Provable Benefit of Stochasticity](https://mlsanity.com/paper/2106.09524/) (2021)
- [(S)GD over Diagonal Linear Networks: Implicit Regularisation, Large Stepsizes and Edge of Stability](https://mlsanity.com/paper/2302.08982/) (2023)
- [A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergence](https://mlsanity.com/paper/2301.13139/) (2023)
- [Stochastic linear optimization never overfits with quadratically-bounded losses on general data](https://mlsanity.com/paper/2202.06915/) (2022)
- [Implicit Regularization in Matrix Sensing via Mirror Descent](https://mlsanity.com/paper/2105.13831/) (2021)
- [Sobolev Acceleration and Statistical Optimality for Learning Elliptic Equations via Gradient Descent](https://mlsanity.com/paper/2205.07331/) (2022)
- [Exponential Tail Local Rademacher Complexity Risk Bounds Without the Bernstein Condition](https://mlsanity.com/paper/2202.11461/) (2022)
- [Thinking Outside the Ball: Optimal Learning with Gradient Descent for Generalized Linear Stochastic Convex Optimization](https://mlsanity.com/paper/2202.13328/) (2022)
- [From inexact optimization to learning via gradient concentration](https://mlsanity.com/paper/2106.05397/) (2021)
- [On Optimal Early Stopping: Over-informative versus Under-informative Parametrization](https://mlsanity.com/paper/2202.09885/) (2022)
- [Towards Data-Algorithm Dependent Generalization: a Case Study on Overparameterized Linear Regression](https://mlsanity.com/paper/2202.06054/) (2022)
- [Guarantees for Nonlinear Representation Learning: Non-identical Covariates, Dependent Data, Fewer Samples](https://mlsanity.com/paper/2410.11227/) (2024)
- [Optimization Insights into Deep Diagonal Linear Networks](https://mlsanity.com/paper/2412.16765/) (2024)
- [Iterative regularization for low complexity regularizers](https://mlsanity.com/paper/2202.00420/) (2022)
- [Implicit Regularization Properties of Variance Reduced Stochastic Mirror Descent](https://mlsanity.com/paper/2205.00058/) (2022)
- [Hard labels sampled from sparse targets mislead rotation invariant algorithms](https://mlsanity.com/paper/2603.20967/) (2026)
- [Accelerated Gradient Flow: Risk, Stability, and Implicit Regularization](https://mlsanity.com/paper/2201.08311/) (2022)
- [GRADSTOP: Early Stopping of Gradient Descent via Posterior Sampling](https://mlsanity.com/paper/2508.19028/) (2025)
- [Statistical Benefits of Fine-Tuning from Pretrained Initialization in Diagonal Linear Networks](https://mlsanity.com/paper/2609.34756/) (2026)

## Abstract (arXiv)

Recently there has been a surge of interest in understanding implicit regularization properties of iterative gradient-based optimization algorithms. In this paper, we study the statistical guarantees on the excess risk achieved by early-stopped unconstrained mirror descent algorithms applied to the unregularized empirical risk with the squared loss for linear models and kernel methods. By completing an inequality that characterizes convexity for the squared loss, we identify an intrinsic link between offset Rademacher complexities and potential-based convergence analysis of mirror descent methods. Our observation immediately yields excess risk guarantees for the path traced by the iterates of mirror descent in terms of offset complexities of certain function classes depending only on the choice of the mirror map, initialization point, step-size, and the number of iterations. We apply our theory to recover, in a clean and elegant manner via rather short proofs, some of the recent results in the implicit regularization literature, while also showing how to improve upon them in some settings.