# The Generalization Error of Stochastic Mirror Descent on Over-Parametrized Linear Models

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 26 references that are in the map.
- First posted on arXiv 18 Feb 2023.

## Builds on (most cited first, 13 of 13)

- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Implicit Regularization in Matrix Factorization](https://mlsanity.com/paper/1705.09280/) (2017)
- [Characterizing Implicit Bias in Terms of Optimization Geometry](https://mlsanity.com/paper/1802.08246/) (2018)
- [Implicit Bias of Gradient Descent on Linear Convolutional Networks](https://mlsanity.com/paper/1806.00468/) (2018)
- [Generalization error in high-dimensional perceptrons: Approaching Bayes error with convex optimization](https://mlsanity.com/paper/2006.06560/) (2020)
- [Precise Statistical Analysis of Classification Accuracies for Adversarial Training](https://mlsanity.com/paper/2010.11213/) (2020)
- [A framework to characterize performance of LASSO algorithms](https://mlsanity.com/paper/1303.7291/) (2013)
- [Stochastic Mirror Descent on Overparameterized Nonlinear Models: Convergence, Implicit Regularization, and Generalization](https://mlsanity.com/paper/1906.03830/) (2019)
- [The Impact of Regularization on High-dimensional Logistic Regression](https://mlsanity.com/paper/1906.03761/) (2019)
- [Stochastic Gradient/Mirror Descent: Minimax Optimality and Implicit Regularization](https://mlsanity.com/paper/1806.00952/) (2018)
- [Fundamental Limits of Ridge-Regularized Empirical Risk Minimization in High Dimensions](https://mlsanity.com/paper/2006.08917/) (2020)
- [The Performance Analysis of Generalized Margin Maximizer (GMM) on Separable Data](https://mlsanity.com/paper/2010.15379/) (2020)
- [Explicit Regularization via Regularizer Mirror Descent](https://mlsanity.com/paper/2202.10788/) (2022)

## Abstract (arXiv)

Despite being highly over-parametrized, and having the ability to fully interpolate the training data, deep networks are known to generalize well to unseen data. It is now understood that part of the reason for this is that the training algorithms used have certain implicit regularization properties that ensure interpolating solutions with "good" properties are found. This is best understood in linear over-parametrized models where it has been shown that the celebrated stochastic gradient descent (SGD) algorithm finds an interpolating solution that is closest in Euclidean distance to the initial weight vector. Different regularizers, replacing Euclidean distance with Bregman divergence, can be obtained if we replace SGD with stochastic mirror descent (SMD). Empirical observations have shown that in the deep network setting, SMD achieves a generalization performance that is different from that of SGD (and which depends on the choice of SMD's potential function. In an attempt to begin to understand this behavior, we obtain the generalization error of SMD for over-parametrized linear models for a binary classification problem where the two classes are drawn from a Gaussian mixture model. We present simulation results that validate the theory and, in particular, introduce two data models, one for which SMD with an ℓ2 regularizer (i.e., SGD) outperforms SMD with an ℓ1 regularizer, and one for which the reverse happens.