mlsanityData to 13 Oct 2026

Achieving Margin Maximization Exponentially Fast via Progressive Norm Rescaling

arXiv 2311.14387 ↗First posted 24 Nov 2023cs.LG math.OCcited by 4

Not on the map. Why?

Abstract (arXiv)

In this work, we investigate the margin-maximization bias exhibited by gradient-based algorithms in classifying linearly separable data. We present an in-depth analysis of the specific properties of the velocity field associated with (normalized) gradients, focusing on their role in margin maximization. Inspired by this analysis, we propose a novel algorithm called Progressive Rescaling Gradient Descent (PRGD) and show that PRGD can maximize the margin at an em exponential rate. This stands in stark contrast to all existing algorithms, which maximize the margin at a slow em polynomial rate. Specifically, we identify mild conditions on data distribution under which existing algorithms such as gradient descent (GD) and normalized gradient descent (NGD) em provably fail in maximizing the margin efficiently. To validate our theoretical findings, we present both synthetic and real-world experiments. Notably, PRGD also shows promise in enhancing the generalization performance when applied to linearly non-separable datasets and deep neural networks.

Key facts. Cited by 4 papers in the map (data through 13 Oct 2026). Builds on 49 of its 63 references that are in the map. First posted on arXiv 24 Nov 2023.

Builds on

49 of 63 references.

References · 49

  1. 2014Very Deep Convolutional Networks for Large-Scale Image Recognitioncited by 15,321
  2. 2016Understanding deep learning requires rethinking generalizationcited by 1,666
  3. 2020Sharpness-Aware Minimization for Efficiently Improving Generalizationcited by 1,411
  4. 2016On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minimacited by 1,344
  5. 2017Spectrally-normalized margin bounds for neural networkscited by 681
  6. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 652
  7. 2014Convex Optimization: Algorithms and Complexitycited by 570
  8. 2019Fantastic Generalization Measures and Where to Find Themcited by 510
  9. 2021Gradient Descent on Neural Networks Typically Occurs at the Edge of Stabilitycited by 419
  10. 2014In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learningcited by 340
  11. 2019Gradient Descent Maximizes the Margin of Homogeneous Neural Networkscited by 312
  12. 2020Kernel and Rich Regimes in Overparametrized Modelscited by 305
37 more
  1. 2020Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Losscited by 268
  2. 2018Characterizing Implicit Bias in Terms of Optimization Geometrycited by 263
  3. 2018Implicit Bias of Gradient Descent on Linear Convolutional Networkscited by 251
  4. 2018Gradient descent aligns the layers of deep linear networkscited by 182
  5. 2020Directional convergence and alignment in deep learningcited by 174
  6. 2020The Break-Even Point on Optimization Trajectories of Deep Neural Networkscited by 150
  7. 2019Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like processcited by 123
  8. 2018Convergence of Gradient Descent on Separable Datacited by 109
  9. 2021Implicit Bias of SGD for Diagonal Linear Networks: a Provable Benefit of Stochasticitycited by 109
  10. 2021What Happens after SGD Reaches Zero Loss? --A Mathematical Frameworkcited by 107
  11. 2022Understanding the Generalization Benefit of Normalization Layers: Sharpness Reductioncited by 86
  12. 2018Risk and parameter convergence of logistic regressioncited by 84
  13. 2022On the Implicit Bias in Deep-Learning Algorithmscited by 84
  14. 2021Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Biascited by 82
  15. 2023Why Do We Need Weight Decay in Modern Deep Learning?cited by 71
  16. 2022The alignment property of SGD noise and how it helps select flat minima: A stability analysiscited by 64
  17. 2018Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Ratecited by 63
  18. 2021On Linear Stability of SGD and Input-Smoothness of Neural Networkscited by 62
  19. 2020Reconciling Modern Deep Learning with Traditional Optimization Analyses: The Intrinsic Learning Ratecited by 59
  20. 2020Gradient descent follows the regularization path for general lossescited by 58
  21. 2023Saddle-to-Saddle Dynamics in Diagonal Linear Networkscited by 56
  22. 2019Lexicographic and Depth-Sensitive Margins in Homogeneous and Non-Homogeneous Deep Modelscited by 53
  23. 2023The Implicit Regularization of Dynamical Stability in Stochastic Gradient Descentcited by 44
  24. 2022Beyond the Quadratic Approximation: the Multiscale Structure of Neural Network Loss Landscapescited by 42
  25. 2023Implicit Bias of Gradient Descent for Logistic Regression at the Edge of Stabilitycited by 42
  26. 2023Sharpness Minimization Algorithms Do Not Only Minimize Sharpness To Achieve Better Generalizationcited by 39
  27. 2022Implicit Bias of Gradient Descent on Reparametrized Models: On Equivalence to Mirror Descentcited by 38
  28. 2021On Margin Maximization in Linear and ReLU Networkscited by 34
  29. 2021Fast Margin Maximization via Dual Accelerationcited by 33
  30. 2023The Crucial Role of Normalization in Sharpness-Aware Minimizationcited by 26
  31. 2022Mirror Descent Maximizes Generalized Margin and Can Be Implemented Efficientlycited by 25
  32. 2022The Asymmetric Maximum Margin Bias of Quasi-Homogeneous Neural Networkscited by 25
  33. 2019Implicit Regularization and Convergence for Weight Normalizationcited by 20
  34. 2023Sharpness-Aware Minimization and the Edge of Stabilitycited by 17
  35. 2023Understanding Multi-phase Optimization Dynamics and Rich Nonlinear Behaviors of ReLU Networkscited by 15
  36. 2022On Accelerated Perceptrons and Beyondcited by 6
  37. 2023The Inductive Bias of Flatness Regularization for Deep Matrix Factorizationcited by 6

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2024: 2; 2025: 1; 2026: 1.

4 papers.

  1. 2025Grokking at the Edge of Numerical Stabilitycited by 44
  2. 2024The Implicit Bias of Adam on Separable Datacited by 33
  3. 2024Improving Generalization and Convergence by Enhancing Implicit Regularizationcited by 14
  4. 2026On the Rate of Convergence of GD in Non-linear Neural Networks: An Adversarial Robustness Perspectivecited by 0