mlsanityData to 7 Oct 2026

Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximization

arXiv 2303.01462 ↗First posted 2 Mar 2023cs.LG stat.MLcited by 29

Not on the map. Why?

Abstract (arXiv)

Linear classifiers and leaky ReLU networks trained by gradient flow on the logistic loss have an implicit bias towards solutions which satisfy the Karush--Kuhn--Tucker (KKT) conditions for margin maximization. In this work we establish a number of settings where the satisfaction of these KKT conditions implies benign overfitting in linear classifiers and in two-layer leaky ReLU networks: the estimators interpolate noisy training data and simultaneously generalize well to test data. The settings include variants of the noisy class-conditional Gaussians considered in previous work as well as new distributional settings where benign overfitting has not been previously observed. The key ingredient to our proof is the observation that when the training data is nearly-orthogonal, both linear classifiers and leaky ReLU networks satisfying the KKT conditions for their respective margin maximization problems behave like a nearly uniform average of the training examples.

Key facts. Cited by 29 papers in the map (data through 7 Oct 2026). Builds on 52 of its 65 references that are in the map. First posted on arXiv 2 Mar 2023.

Builds on

52 of 65 references.

References · 52

  1. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  2. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 649
  3. 2019Benign Overfitting in Linear Regressioncited by 544
  4. 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 508
  5. 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 410
  6. 2019Gradient Descent Maximizes the Margin of Homogeneous Neural Networkscited by 308
  7. 2020Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Losscited by 267
  8. 2018Characterizing Implicit Bias in Terms of Optimization Geometrycited by 259
  9. 2019Two models of double descent for weak featurescited by 194
  10. 2018Just Interpolate: Kernel "Ridgeless" Regression Can Generalizecited by 190
  11. 2020Directional convergence and alignment in deep learningcited by 172
  12. 2020Benign overfitting in ridge regressioncited by 152
38 more
  1. 2019Harmless interpolation of noisy data in regressioncited by 121
  2. 2018Convergence of Gradient Descent on Separable Datacited by 108
  3. 2018Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolatecited by 99
  4. 2020Classification vs regression in overparameterized regimes: Does the loss function matter?cited by 97
  5. 2020On the Optimal Weighted ℓ2 Regularization in Overparameterized Linear Regressioncited by 97
  6. 2022Benign Overfitting in Two-layer Convolutional Neural Networkscited by 90
  7. 2022On the Implicit Bias in Deep-Learning Algorithmscited by 84
  8. 2021Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Biascited by 82
  9. 2018Risk and parameter convergence of logistic regressioncited by 81
  10. 2020Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regimecited by 81
  11. 2022Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Datacited by 74
  12. 2018Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Ratecited by 63
  13. 2020Gradient descent follows the regularization path for general lossescited by 57
  14. 2021Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfittingcited by 54
  15. 2022Implicit Regularization Towards Rank Minimization in ReLU Networkscited by 53
  16. 2021Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixturescited by 48
  17. 2022Implicit Bias in Leaky ReLU Networks Trained on High-Dimensional Datacited by 46
  18. 2018Consistency of Interpolation with Laplace Kernels is a High-Dimensional Phenomenoncited by 44
  19. 2019In Defense of Uniform Convergence: Generalization via derandomization with an application to interpolating predictorscited by 44
  20. 2021Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolationcited by 41
  21. 2022The Implicit Bias of Benign Overfittingcited by 38
  22. 2022Benign, Tempered, or Catastrophic: A Taxonomy of Overfittingcited by 36
  23. 2021On Margin Maximization in Linear and ReLU Networkscited by 34
  24. 2021Fast Margin Maximization via Dual Accelerationcited by 33
  25. 2020On the proliferation of support vectors in high dimensionscited by 32
  26. 2020Theoretical Insights Into Multiclass Classification: A High-dimensional Asymptotic Viewcited by 32
  27. 2020Gradient Methods Never Overfit On Separable Datacited by 29
  28. 2020Binary Classification of Gaussian Mixtures: Abundance of Support Vectors, Benign Overfitting and Regularizationcited by 27
  29. 2022Gradient Methods Provably Converge to Non-Robust Networkscited by 27
  30. 2020Failures of model-dependent generalization bounds for least-norm interpolationcited by 26
  31. 2022The Asymmetric Maximum Margin Bias of Quasi-Homogeneous Neural Networkscited by 25
  32. 2021Interpolating Classifiers Make Few Mistakescited by 22
  33. 2022Fast Rates for Noisy Interpolation Require Rethinking the Effects of Inductive Biascited by 21
  34. 2022On the Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Biascited by 21
  35. 2021Towards Understanding Learning in Neural Networks with Linear Teacherscited by 19
  36. 2021The Interplay Between Implicit Bias and Benign Overfitting in Two-Layer Linear Networkscited by 18
  37. 2021Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noisecited by 17
  38. 2021Tight bounds for minimum l1-norm interpolation of noisy datacited by 16

50 most cited of 52 All 52 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 12; 2024: 9; 2025: 5; 2026: 3.

29 papers.

Sort:

By area:

  1. 2023Max-Margin Token Selection in Attention Mechanismcited by 57
  2. 2023Feature emergence via margin maximization: case studies in algebraic taskscited by 33
  3. 2023Benign Overfitting and Grokking in ReLU Networks for XOR Cluster Datacited by 32
  4. 2024Implicit Bias and Fast Convergence Rates for Self-attentioncited by 31
  5. 2023Vanishing Gradients in Reinforcement Finetuning of Language Modelscited by 26
  6. 2025Selective Underfitting in Diffusion Modelscited by 17
  7. 2023From Tempered to Benign Overfitting in ReLU Neural Networkscited by 16
  8. 2023Learning a Neuron by a Shallow ReLU Network: Dynamics and Implicit Bias for Correlated Inputscited by 16
  9. 2024Trained Transformer Classifiers Generalize and Exhibit Benign Overfitting In-Contextcited by 14
  10. 2023Provable Guarantees for Neural Networks via Gradient Feature Learningcited by 13
  11. 2023Noisy Interpolation Learning with Shallow Univariate ReLU Networkscited by 11
  12. 2024Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionalitycited by 7
17 more
  1. 2024Benign overfitting in leaky ReLU networks with moderate input dimensioncited by 5
  2. 2024Provable Tempered Overfitting of Minimal Nets and Typical Netscited by 5
  3. 2023Universality of max-margin classifierscited by 4
  4. 2023A PAC-Bayesian Perspective on the Interpolating Information Criterioncited by 4
  5. 2024Implicit Bias of Policy Gradient in Linear Quadratic Control: Extrapolation to Unseen Initial Statescited by 4
  6. 2024Provable Privacy Attacks on Trained Shallow Neural Networkscited by 4
  7. 2023Precise Asymptotic Generalization for Multiclass Classification with Overparameterized Linear Modelscited by 3
  8. 2024When Are Bias-Free ReLU Networks Effectively Linear Networks?cited by 3
  9. 2025Quantifying Overfitting along the Regularization Path for Two-Part-Code MDL in Supervised Classificationcited by 2
  10. 2023Frequency maps reveal the correlation between Adversarial Attacks and Implicit Biascited by 0
  11. 2024Demolition and Reinforcement of Memories in Spin-Glass-like Neural Networkscited by 0
  12. 2025Gradient Descent Robustly Learns the Intrinsic Dimension of Data in Training Convolutional Neural Networkscited by 0
  13. 2025Embedding principle of homogeneous neural network for classification problemcited by 0
  14. 2025Directional Convergence, Benign Overfitting of Gradient Descent in leaky ReLU two-layer Neural Networkscited by 0
  15. 2026Deep Exploration of Epoch-wise Double Descent in Noisy Data: Signal Separation, Large Activation, and Benign Overfittingcited by 0
  16. 2026Harmful Overfitting in Sobolev Spacescited by 0
  17. 2026Sufficient Conditions for Stability of Minimum-Norm Interpolating Deep ReLU Networkscited by 0