# Mirror Descent Maximizes Generalized Margin and Can Be Implemented Efficiently

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 50 references that are in the map.
- First posted on arXiv 25 May 2022.

## Builds on (most cited first, 30 of 31)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [MobileNetV2: Inverted Residuals and Linear Bottlenecks](https://mlsanity.com/paper/1801.04381/) (2018)
- [Zero-Shot Text-to-Image Generation](https://mlsanity.com/paper/2102.12092/) (2021)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Designing Network Design Spaces](https://mlsanity.com/paper/2003.13678/) (2020)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Deep Double Descent: Where Bigger Models and More Data Hurt](https://mlsanity.com/paper/1912.02292/) (2019)
- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1412.6614/) (2014)
- [Gradient Descent Maximizes the Margin of Homogeneous Neural Networks](https://mlsanity.com/paper/1906.05890/) (2019)
- [Characterizing Implicit Bias in Terms of Optimization Geometry](https://mlsanity.com/paper/1802.08246/) (2018)
- [The Marginal Value of Adaptive Gradient Methods in Machine Learning](https://mlsanity.com/paper/1705.08292/) (2017)
- [Convergence of Gradient Descent on Separable Data](https://mlsanity.com/paper/1803.01905/) (2018)
- [Relatively-Smooth Convex Optimization by First-Order Methods, and Applications](https://mlsanity.com/paper/1610.05708/) (2016)
- [Gradient descent follows the regularization path for general losses](https://mlsanity.com/paper/2006.11226/) (2020)
- [The Implicit Bias for Adaptive Optimization Algorithms on Homogeneous Neural Networks](https://mlsanity.com/paper/2012.06244/) (2020)
- [Stochastic Mirror Descent on Overparameterized Nonlinear Models: Convergence, Implicit Regularization, and Generalization](https://mlsanity.com/paper/1906.03830/) (2019)
- [Margins, Shrinkage, and Boosting](https://mlsanity.com/paper/1303.4172/) (2013)
- [Fast Margin Maximization via Dual Acceleration](https://mlsanity.com/paper/2107.00595/) (2021)
- [Stochastic Gradient/Mirror Descent: Minimax Optimality and Implicit Regularization](https://mlsanity.com/paper/1806.00952/) (2018)
- [Fast Rates for Noisy Interpolation Require Rethinking the Effects of Inductive Bias](https://mlsanity.com/paper/2203.03597/) (2022)
- [Implicit Regularization of Bregman Proximal Point Algorithm and Mirror Descent on Separable Data](https://mlsanity.com/paper/2108.06808/) (2021)

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

- [Transformers as Support Vector Machines](https://mlsanity.com/paper/2308.16898/) (2023)
- [Implicit Bias of Spectral Descent and Muon on Multiclass Separable Data](https://mlsanity.com/paper/2502.04664/) (2025)
- [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)
- [Implicit Geometry of Next-token Prediction: From Language Sparsity Patterns to Model Representations](https://mlsanity.com/paper/2408.15417/) (2024)
- [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)
- [Implicit Optimization Bias of Next-Token Prediction in Linear Models](https://mlsanity.com/paper/2402.18551/) (2024)
- [Mirror, Mirror of the Flow: How Does Regularization Shape Implicit Bias?](https://mlsanity.com/paper/2504.12883/) (2025)
- [Implicit Bias of Mirror Flow on Separable Data](https://mlsanity.com/paper/2406.12763/) (2024)
- [Optimizing Attention with Mirror Descent: Generalized Max-Margin Token Selection](https://mlsanity.com/paper/2410.14581/) (2024)
- [Nonconvex Stochastic Bregman Proximal Gradient Method with Application to Deep Learning](https://mlsanity.com/paper/2306.14522/) (2023)
- [On Accelerated Perceptrons and Beyond](https://mlsanity.com/paper/2210.09371/) (2022)
- [Achieving Margin Maximization Exponentially Fast via Progressive Norm Rescaling](https://mlsanity.com/paper/2311.14387/) (2023)
- [Never Saddle for Reparameterized Steepest Descent as Mirror Flow](https://mlsanity.com/paper/2603.02064/) (2026)
- [A Mirror Descent Perspective of Smoothed Sign Descent](https://mlsanity.com/paper/2410.14158/) (2024)
- [Mirror Descent on Reproducing Kernel Banach Spaces](https://mlsanity.com/paper/2411.11242/) (2024)
- [Diagonalizing the Softmax: Hadamard Initialization for Tractable Cross-Entropy Dynamics](https://mlsanity.com/paper/2512.04006/) (2025)
- [Stability Annealing Selects the Implicit Bias of Smoothed Sign Descent: A Rate-Indexed Barrier Path on Separable Data](https://mlsanity.com/paper/2607.06013/) (2026)
- [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)
- [Faster Margin Maximization Rates for Generic and Adversarially Robust Optimization Methods](https://mlsanity.com/paper/2305.17544/) (2023)
- [Mirror Descent on Riemannian Manifolds](https://mlsanity.com/paper/2603.17527/) (2026)
- [HORST: Composing Optimizer Geometries for Sparse Transformer Training](https://mlsanity.com/paper/2605.21104/) (2026)
- [The Implicit Bias of Depth: From Neural Collapse to Softmax Codes](https://mlsanity.com/paper/2605.23087/) (2026)
- [Mirror Descent Beyond Euclidean Stability: An Exponential Separation in Initialization Sensitivity](https://mlsanity.com/paper/2606.11431/) (2026)
- [From Parallel to Sequential: Small-Batch Noise Restores Simplicity Bias of Muon](https://mlsanity.com/paper/2610.16868/) (2026)

## Abstract (arXiv)

Driven by the empirical success and wide use of deep neural networks, understanding the generalization performance of overparameterized models has become an increasingly popular question. To this end, there has been substantial effort to characterize the implicit bias of the optimization algorithms used, such as gradient descent (GD), and the structural properties of their preferred solutions. This paper answers an open question in this literature: For the classification setting, what solution does mirror descent (MD) converge to? Specifically, motivated by its efficient implementation, we consider the family of mirror descent algorithms with potential function chosen as the p-th power of the ℓp-norm, which is an important generalization of GD. We call this algorithm p-textsfGD. For this family, we characterize the solutions it obtains and show that it converges in direction to a generalized maximum-margin solution with respect to the ℓp-norm for linearly separable classification. While the MD update rule is in general expensive to compute and perhaps not suitable for deep learning, p-textsfGD is fully parallelizable in the same manner as SGD and can be used to train deep neural networks with virtually no additional computational overhead. Using comprehensive experiments with both linear and deep neural network models, we demonstrate that p-textsfGD can noticeably affect the structure and the generalization performance of the learned models.