# Stochastic Gradient/Mirror Descent: Minimax Optimality and Implicit Regularization

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

## Key facts

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

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

- [On the Implicit Bias in Deep-Learning Algorithms](https://mlsanity.com/paper/2208.12591/) (2022)
- [Label-Imbalanced and Group-Sensitive Classification under Overparameterization](https://mlsanity.com/paper/2103.01550/) (2021)
- [Max-Margin Token Selection in Attention Mechanism](https://mlsanity.com/paper/2306.13596/) (2023)
- [Adaptive-Control-Oriented Meta-Learning for Nonlinear Systems](https://mlsanity.com/paper/2103.04490/) (2021)
- [Mirror Descent Maximizes Generalized Margin and Can Be Implemented Efficiently](https://mlsanity.com/paper/2205.12808/) (2022)
- [Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize](https://mlsanity.com/paper/2110.15412/) (2021)
- [Implicit Regularization of Gradient Flow on One-Layer Softmax Attention](https://mlsanity.com/paper/2403.08699/) (2024)
- [Control-oriented meta-learning](https://mlsanity.com/paper/2204.06716/) (2022)
- [Automatic Gradient Descent: Deep Learning without Hyperparameters](https://mlsanity.com/paper/2304.05187/) (2023)
- [A Unified Approach to Controlling Implicit Regularization via Mirror Descent](https://mlsanity.com/paper/2306.13853/) (2023)
- [A Universal Class of Sharpness-Aware Minimization Algorithms](https://mlsanity.com/paper/2406.03682/) (2024)
- [ORFit: One-Pass Learning via Bridging Orthogonal Gradient Descent and Recursive Least-Squares](https://mlsanity.com/paper/2207.13853/) (2022)
- [Optimizing Attention with Mirror Descent: Generalized Max-Margin Token Selection](https://mlsanity.com/paper/2410.14581/) (2024)
- [Implicit Regularization of Bregman Proximal Point Algorithm and Mirror Descent on Separable Data](https://mlsanity.com/paper/2108.06808/) (2021)
- [Synaptic Weight Distributions Depend on the Geometry of Plasticity](https://mlsanity.com/paper/2305.19394/) (2023)
- [Improving Implicit Regularization of SGD with Preconditioning for Least Square Problems](https://mlsanity.com/paper/2403.08585/) (2024)
- [A Mirror Descent Perspective of Smoothed Sign Descent](https://mlsanity.com/paper/2410.14158/) (2024)
- [Explicit Regularization via Regularizer Mirror Descent](https://mlsanity.com/paper/2202.10788/) (2022)
- [Diagonalizing the Softmax: Hadamard Initialization for Tractable Cross-Entropy Dynamics](https://mlsanity.com/paper/2512.04006/) (2025)
- [Implicit Regularization Properties of Variance Reduced Stochastic Mirror Descent](https://mlsanity.com/paper/2205.00058/) (2022)
- [SketchOGD: Memory-Efficient Continual Learning](https://mlsanity.com/paper/2305.16424/) (2023)
- [One-Bit Quantization and Sparsification for Multiclass Linear Classification with Strong Regularization](https://mlsanity.com/paper/2402.10474/) (2024)
- [Optimal Implicit Bias in Linear Regression](https://mlsanity.com/paper/2506.17187/) (2025)
- [Implicit Bias and Convergence of Matrix Stochastic Mirror Descent](https://mlsanity.com/paper/2602.18997/) (2026)
- [The Generalization Error of Stochastic Mirror Descent on Over-Parametrized Linear Models](https://mlsanity.com/paper/2302.09433/) (2023)
- [Distributed Linear Solvers and Data Heterogeneity](https://mlsanity.com/paper/2304.10640/) (2023)
- [Gaussian Universality for Diffusion Models](https://mlsanity.com/paper/2501.07741/) (2025)
- [Dual Space Preconditioning for Gradient Descent in the Overparameterized Regime](https://mlsanity.com/paper/2603.10485/) (2026)
- [The Implicit Bias of Depth: From Neural Collapse to Softmax Codes](https://mlsanity.com/paper/2605.23087/) (2026)

## Abstract (arXiv)

Stochastic descent methods (of the gradient and mirror varieties) have become increasingly popular in optimization. In fact, it is now widely recognized that the success of deep learning is not only due to the special deep architecture of the models, but also due to the behavior of the stochastic descent methods used, which play a key role in reaching "good" solutions that generalize well to unseen data. In an attempt to shed some light on why this is the case, we revisit some minimax properties of stochastic gradient descent (SGD) for the square loss of linear models---originally developed in the 1990's---and extend them to general stochastic mirror descent (SMD) algorithms for general loss functions and nonlinear models. In particular, we show that there is a fundamental identity which holds for SMD (and SGD) under very general conditions, and which implies the minimax optimality of SMD (and SGD) for sufficiently small step size, and for a general class of loss functions and general nonlinear models. We further show that this identity can be used to naturally establish other properties of SMD (and SGD), namely convergence and implicit regularization for over-parameterized linear models (in what is now being called the "interpolating regime"), some of which have been shown in certain cases in prior literature. We also argue how this identity can be used in the so-called "highly over-parameterized" nonlinear setting (where the number of parameters far exceeds the number of data points) to provide insights into why SMD (and SGD) may have similar convergence and implicit regularization properties for deep learning.