# Stochastic Mirror Descent on Overparameterized Nonlinear Models: Convergence, Implicit Regularization, and Generalization

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

## Key facts

- Cited by 40 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jun 2019.

## Built on by (most cited first, 30 of 40)

- [Transformers as Support Vector Machines](https://mlsanity.com/paper/2308.16898/) (2023)
- [Max-Margin Token Selection in Attention Mechanism](https://mlsanity.com/paper/2306.13596/) (2023)
- [Implicit Bias of Spectral Descent and Muon on Multiclass Separable Data](https://mlsanity.com/paper/2502.04664/) (2025)
- [Adaptive-Control-Oriented Meta-Learning for Nonlinear Systems](https://mlsanity.com/paper/2103.04490/) (2021)
- [Sketching Curvature for Efficient Out-of-Distribution Detection for Deep Neural Networks](https://mlsanity.com/paper/2102.12567/) (2021)
- [Continual Learning with Recursive Gradient Optimization](https://mlsanity.com/paper/2201.12522/) (2022)
- [A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time](https://mlsanity.com/paper/2309.07418/) (2023)
- [Mirror Descent Maximizes Generalized Margin and Can Be Implemented Efficiently](https://mlsanity.com/paper/2205.12808/) (2022)
- [Implicit Geometry of Next-token Prediction: From Language Sparsity Patterns to Model Representations](https://mlsanity.com/paper/2408.15417/) (2024)
- [Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize](https://mlsanity.com/paper/2110.15412/) (2021)
- [Control-oriented meta-learning](https://mlsanity.com/paper/2204.06716/) (2022)
- [A Unified Approach to Controlling Implicit Regularization via Mirror Descent](https://mlsanity.com/paper/2306.13853/) (2023)
- [Implicit Optimization Bias of Next-Token Prediction in Linear Models](https://mlsanity.com/paper/2402.18551/) (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)
- [Peer-to-Peer Learning Dynamics of Wide Neural Networks](https://mlsanity.com/paper/2409.15267/) (2024)
- [Tractable Uncertainty-Aware Meta-Learning](https://mlsanity.com/paper/2210.01881/) (2022)
- [Synaptic Weight Distributions Depend on the Geometry of Plasticity](https://mlsanity.com/paper/2305.19394/) (2023)
- [Primal-dual algorithm for contextual stochastic combinatorial optimization](https://mlsanity.com/paper/2505.04757/) (2025)
- [Probabilistic Forecasting for Building Energy Systems using Time-Series Foundation Models](https://mlsanity.com/paper/2506.00630/) (2025)
- [Adaptive Consensus Optimization Method for GANs](https://mlsanity.com/paper/2304.10317/) (2023)
- [A Mirror Descent Perspective of Smoothed Sign Descent](https://mlsanity.com/paper/2410.14158/) (2024)
- [Sparse Training of Neural Networks based on Multilevel Mirror Descent](https://mlsanity.com/paper/2602.03535/) (2026)
- [Explicit Regularization via Regularizer Mirror Descent](https://mlsanity.com/paper/2202.10788/) (2022)
- [Mirror descent of Hopfield model](https://mlsanity.com/paper/2211.15880/) (2022)
- [Mirror Descent on Reproducing Kernel Banach Spaces](https://mlsanity.com/paper/2411.11242/) (2024)
- [Adaptive Pruning of Pretrained Transformer via Differential Inclusions](https://mlsanity.com/paper/2501.03289/) (2025)
- [SYNTHESIS: A Semi-Asynchronous Path-Integrated Stochastic Gradient Method for Distributed Learning in Computing Clusters](https://mlsanity.com/paper/2208.08425/) (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)

## Abstract (arXiv)

Most modern learning problems are highly overparameterized, meaning that there are many more parameters than the number of training data points, and as a result, the training loss may have infinitely many global minima (parameter vectors that perfectly interpolate the training data). Therefore, it is important to understand which interpolating solutions we converge to, how they depend on the initialization point and the learning algorithm, and whether they lead to different generalization performances. In this paper, we study these questions for the family of stochastic mirror descent (SMD) algorithms, of which the popular stochastic gradient descent (SGD) is a special case. Our contributions are both theoretical and experimental. On the theory side, we show that in the overparameterized nonlinear setting, if the initialization is close enough to the manifold of global minima (something that comes for free in the highly overparameterized case), SMD with sufficiently small step size converges to a global minimum that is approximately the closest one in Bregman divergence. On the experimental side, our extensive experiments on standard datasets and models, using various initializations, various mirror descents, and various Bregman divergences, consistently confirms that this phenomenon happens in deep learning. Our experiments further indicate that there is a clear difference in the generalization performance of the solutions obtained by different SMD algorithms. Experimenting on a standard image dataset and network architecture with SMD with different kinds of implicit regularization, ℓ1 to encourage sparsity, ℓ2 yielding SGD, and ℓ10 to discourage large components in the parameter vector, consistently and definitively shows that ℓ10-SMD has better generalization performance than SGD, which in turn has better generalization performance than ℓ1-SMD.