# Fast Margin Maximization via Dual Acceleration

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 34 references that are in the map.
- First posted on arXiv 1 Jul 2021.

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

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [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)
- [Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss](https://mlsanity.com/paper/2002.04486/) (2020)
- [Characterizing Implicit Bias in Terms of Optimization Geometry](https://mlsanity.com/paper/1802.08246/) (2018)
- [Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data](https://mlsanity.com/paper/1808.01204/) (2018)
- [Implicit Bias of Gradient Descent on Linear Convolutional Networks](https://mlsanity.com/paper/1806.00468/) (2018)
- [Directional convergence and alignment in deep learning](https://mlsanity.com/paper/2006.06657/) (2020)
- [Convergence of Gradient Descent on Separable Data](https://mlsanity.com/paper/1803.01905/) (2018)
- [Risk and parameter convergence of logistic regression](https://mlsanity.com/paper/1803.07300/) (2018)
- [Global convergence of the Heavy-ball method for convex optimization](https://mlsanity.com/paper/1412.7457/) (2014)
- [Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent](https://mlsanity.com/paper/1407.1537/) (2014)
- [Margins, Shrinkage, and Boosting](https://mlsanity.com/paper/1303.4172/) (2013)
- [Properties of the After Kernel](https://mlsanity.com/paper/2105.10585/) (2021)
- [Towards A Deeper Geometric, Analytic and Algorithmic Understanding of Margins](https://mlsanity.com/paper/1406.5311/) (2014)
- [Linear Separation via Optimism](https://mlsanity.com/paper/2011.08797/) (2020)

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

- [On the Implicit Bias in Deep-Learning Algorithms](https://mlsanity.com/paper/2208.12591/) (2022)
- [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 Gradient Descent for Logistic Regression at the Edge of Stability](https://mlsanity.com/paper/2305.11788/) (2023)
- [Implicit Bias of Spectral Descent and Muon on Multiclass Separable Data](https://mlsanity.com/paper/2502.04664/) (2025)
- [Implicit Bias of Gradient Descent on Reparametrized Models: On Equivalence to Mirror Descent](https://mlsanity.com/paper/2207.04036/) (2022)
- [Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency](https://mlsanity.com/paper/2402.15926/) (2024)
- [Implicit Bias and Fast Convergence Rates for Self-attention](https://mlsanity.com/paper/2402.05738/) (2024)
- [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)
- [Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximization](https://mlsanity.com/paper/2303.01462/) (2023)
- [Mirror Descent Maximizes Generalized Margin and Can Be Implemented Efficiently](https://mlsanity.com/paper/2205.12808/) (2022)
- [Does Momentum Change the Implicit Regularization on Separable Data?](https://mlsanity.com/paper/2110.03891/) (2021)
- [Implicit Regularization of Gradient Flow on One-Layer Softmax Attention](https://mlsanity.com/paper/2403.08699/) (2024)
- [Large Stepsize Gradient Descent for Non-Homogeneous Two-Layer Networks: Margin Improvement and Fast Optimization](https://mlsanity.com/paper/2406.08654/) (2024)
- [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)
- [Transformers Learn Low Sensitivity Functions: Investigations and Implications](https://mlsanity.com/paper/2403.06925/) (2024)
- [Improving Generalization and Convergence by Enhancing Implicit Regularization](https://mlsanity.com/paper/2405.20763/) (2024)
- [Non-asymptotic Convergence of Training Transformers for Next-token Prediction](https://mlsanity.com/paper/2409.17335/) (2024)
- [The Rich and the Simple: On the Implicit Bias of Adam and SGD](https://mlsanity.com/paper/2505.24022/) (2025)
- [The Implicit Bias of Gradient Descent on Separable Multiclass Data](https://mlsanity.com/paper/2411.01350/) (2024)
- [How Transformers Learn Regular Language Recognition: A Theoretical Study on Training Dynamics and Implicit Bias](https://mlsanity.com/paper/2505.00926/) (2025)
- [Optimizing Attention with Mirror Descent: Generalized Max-Margin Token Selection](https://mlsanity.com/paper/2410.14581/) (2024)
- [On Generalization of Decentralized Learning with Separable Data](https://mlsanity.com/paper/2209.07116/) (2022)
- [Minimax Optimal Convergence of Gradient Descent in Logistic Regression via Large and Adaptive Stepsizes](https://mlsanity.com/paper/2504.04105/) (2025)
- [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)
- [The Oracle Complexity of Simplex-based Matrix Games](https://mlsanity.com/paper/2412.06990/) (2024)
- [Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability](https://mlsanity.com/paper/2506.13974/) (2025)
- [On the Optimization of Margin Distribution](https://mlsanity.com/paper/2204.14118/) (2022)

## Abstract (arXiv)

We present and analyze a momentum-based gradient method for training linear classifiers with an exponentially-tailed loss (e.g., the exponential or logistic loss), which maximizes the classification margin on separable data at a rate of widetildeO(1/t2). This contrasts with a rate of O(1/log(t)) for standard gradient descent, and O(1/t) for normalized gradient descent. This momentum-based method is derived via the convex dual of the maximum-margin problem, and specifically by applying Nesterov acceleration to this dual, which manages to result in a simple and intuitive method in the primal. This dual view can also be used to derive a stochastic variant, which performs adaptive non-uniform sampling via the dual variables.