mlsanityData to 14 Oct 2026

Fast Margin Maximization via Dual Acceleration

arXiv 2107.00595 ↗First posted 1 Jul 2021cs.LG math.OC stat.MLcited by 33

Not on the map. Why?

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.

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

20 of 34 references.

References · 20

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  2. 2016Understanding deep learning requires rethinking generalizationcited by 1,674
  3. 2017Spectrally-normalized margin bounds for neural networkscited by 686
  4. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 659
  5. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 655
  6. 2014In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learningcited by 342
  7. 2019Gradient Descent Maximizes the Margin of Homogeneous Neural Networkscited by 320
  8. 2020Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Losscited by 268
  9. 2018Characterizing Implicit Bias in Terms of Optimization Geometrycited by 266
  10. 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 261
  11. 2018Implicit Bias of Gradient Descent on Linear Convolutional Networkscited by 251
  12. 2020Directional convergence and alignment in deep learningcited by 178
8 more
  1. 2018Convergence of Gradient Descent on Separable Datacited by 110
  2. 2018Risk and parameter convergence of logistic regressioncited by 85
  3. 2014Global convergence of the Heavy-ball method for convex optimizationcited by 61
  4. 2014Linear Coupling: An Ultimate Unification of Gradient and Mirror Descentcited by 58
  5. 2013Margins, Shrinkage, and Boostingcited by 35
  6. 2021Properties of the After Kernelcited by 27
  7. 2014Towards A Deeper Geometric, Analytic and Algorithmic Understanding of Marginscited by 4
  8. 2020Linear Separation via Optimismcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 1; 2022: 7; 2023: 8; 2024: 11; 2025: 5; 2026: 1.

33 papers.

Sort:

  1. 2022On the Implicit Bias in Deep-Learning Algorithmscited by 86
  2. 2023Transformers as Support Vector Machinescited by 74
  3. 2023Max-Margin Token Selection in Attention Mechanismcited by 58
  4. 2023Implicit Bias of Gradient Descent for Logistic Regression at the Edge of Stabilitycited by 42
  5. 2025Implicit Bias of Spectral Descent and Muon on Multiclass Separable Datacited by 41
  6. 2022Implicit Bias of Gradient Descent on Reparametrized Models: On Equivalence to Mirror Descentcited by 39
  7. 2024Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiencycited by 35
  8. 2024Implicit Bias and Fast Convergence Rates for Self-attentioncited by 31
  9. 2023A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Timecited by 30
  10. 2023Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximizationcited by 29
  11. 2022Mirror Descent Maximizes Generalized Margin and Can Be Implemented Efficientlycited by 26
  12. 2021Does Momentum Change the Implicit Regularization on Separable Data?cited by 22
21 more
  1. 2024Implicit Regularization of Gradient Flow on One-Layer Softmax Attentioncited by 19
  2. 2024Large Stepsize Gradient Descent for Non-Homogeneous Two-Layer Networks: Margin Improvement and Fast Optimizationcited by 17
  3. 2023A Unified Approach to Controlling Implicit Regularization via Mirror Descentcited by 14
  4. 2024Implicit Optimization Bias of Next-Token Prediction in Linear Modelscited by 14
  5. 2024Transformers Learn Low Sensitivity Functions: Investigations and Implicationscited by 14
  6. 2024Improving Generalization and Convergence by Enhancing Implicit Regularizationcited by 14
  7. 2024Non-asymptotic Convergence of Training Transformers for Next-token Predictioncited by 13
  8. 2025The Rich and the Simple: On the Implicit Bias of Adam and SGDcited by 13
  9. 2024The Implicit Bias of Gradient Descent on Separable Multiclass Datacited by 11
  10. 2025How Transformers Learn Regular Language Recognition: A Theoretical Study on Training Dynamics and Implicit Biascited by 11
  11. 2024Optimizing Attention with Mirror Descent: Generalized Max-Margin Token Selectioncited by 9
  12. 2022On Generalization of Decentralized Learning with Separable Datacited by 8
  13. 2025Minimax Optimal Convergence of Gradient Descent in Logistic Regression via Large and Adaptive Stepsizescited by 7
  14. 2022On Accelerated Perceptrons and Beyondcited by 6
  15. 2023Achieving Margin Maximization Exponentially Fast via Progressive Norm Rescalingcited by 4
  16. 2024The Oracle Complexity of Simplex-based Matrix Gamescited by 4
  17. 2025Constant Stepsize Local GD for Logistic Regression: Acceleration by Instabilitycited by 2
  18. 2022On the Optimization of Margin Distributioncited by 0
  19. 2022Iterative regularization in classification via hinge loss diagonal descentcited by 0
  20. 2023Faster Margin Maximization Rates for Generic and Adversarially Robust Optimization Methodscited by 0
  21. 2026On the Rate of Convergence of GD in Non-linear Neural Networks: An Adversarial Robustness Perspectivecited by 0