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

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

## Key facts

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

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

- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [The generalization error of random features regression: Precise asymptotics and double descent curve](https://mlsanity.com/paper/1908.05355/) (2019)
- [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)
- [Two models of double descent for weak features](https://mlsanity.com/paper/1903.07571/) (2019)
- [Just Interpolate: Kernel "Ridgeless" Regression Can Generalize](https://mlsanity.com/paper/1808.00387/) (2018)
- [Directional convergence and alignment in deep learning](https://mlsanity.com/paper/2006.06657/) (2020)
- [Benign overfitting in ridge regression](https://mlsanity.com/paper/2009.14286/) (2020)
- [Harmless interpolation of noisy data in regression](https://mlsanity.com/paper/1903.09139/) (2019)
- [Convergence of Gradient Descent on Separable Data](https://mlsanity.com/paper/1803.01905/) (2018)
- [Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate](https://mlsanity.com/paper/1806.05161/) (2018)
- [On the Optimal Weighted ℓ2 Regularization in Overparameterized Linear Regression](https://mlsanity.com/paper/2006.05800/) (2020)
- [Classification vs regression in overparameterized regimes: Does the loss function matter?](https://mlsanity.com/paper/2005.08054/) (2020)
- [Benign Overfitting in Two-layer Convolutional Neural Networks](https://mlsanity.com/paper/2202.06526/) (2022)
- [On the Implicit Bias in Deep-Learning Algorithms](https://mlsanity.com/paper/2208.12591/) (2022)
- [Risk and parameter convergence of logistic regression](https://mlsanity.com/paper/1803.07300/) (2018)
- [Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Bias](https://mlsanity.com/paper/2110.13905/) (2021)
- [Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime](https://mlsanity.com/paper/2004.12019/) (2020)
- [Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Data](https://mlsanity.com/paper/2202.05928/) (2022)
- [Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Rate](https://mlsanity.com/paper/1806.01796/) (2018)
- [Gradient descent follows the regularization path for general losses](https://mlsanity.com/paper/2006.11226/) (2020)
- [Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting](https://mlsanity.com/paper/2106.09276/) (2021)
- [Implicit Regularization Towards Rank Minimization in ReLU Networks](https://mlsanity.com/paper/2201.12760/) (2022)
- [Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixtures](https://mlsanity.com/paper/2104.13628/) (2021)
- [Implicit Bias in Leaky ReLU Networks Trained on High-Dimensional Data](https://mlsanity.com/paper/2210.07082/) (2022)
- [Consistency of Interpolation with Laplace Kernels is a High-Dimensional Phenomenon](https://mlsanity.com/paper/1812.11167/) (2018)

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

- [Max-Margin Token Selection in Attention Mechanism](https://mlsanity.com/paper/2306.13596/) (2023)
- [Benign Overfitting and Grokking in ReLU Networks for XOR Cluster Data](https://mlsanity.com/paper/2310.02541/) (2023)
- [Feature emergence via margin maximization: case studies in algebraic tasks](https://mlsanity.com/paper/2311.07568/) (2023)
- [Implicit Bias and Fast Convergence Rates for Self-attention](https://mlsanity.com/paper/2402.05738/) (2024)
- [Vanishing Gradients in Reinforcement Finetuning of Language Models](https://mlsanity.com/paper/2310.20703/) (2023)
- [Selective Underfitting in Diffusion Models](https://mlsanity.com/paper/2510.01378/) (2025)
- [From Tempered to Benign Overfitting in ReLU Neural Networks](https://mlsanity.com/paper/2305.15141/) (2023)
- [Learning a Neuron by a Shallow ReLU Network: Dynamics and Implicit Bias for Correlated Inputs](https://mlsanity.com/paper/2306.06479/) (2023)
- [Trained Transformer Classifiers Generalize and Exhibit Benign Overfitting In-Context](https://mlsanity.com/paper/2410.01774/) (2024)
- [Provable Guarantees for Neural Networks via Gradient Feature Learning](https://mlsanity.com/paper/2310.12408/) (2023)
- [Noisy Interpolation Learning with Shallow Univariate ReLU Networks](https://mlsanity.com/paper/2307.15396/) (2023)
- [Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionality](https://mlsanity.com/paper/2409.03891/) (2024)
- [Universality of max-margin classifiers](https://mlsanity.com/paper/2310.00176/) (2023)
- [Benign overfitting in leaky ReLU networks with moderate input dimension](https://mlsanity.com/paper/2403.06903/) (2024)
- [A PAC-Bayesian Perspective on the Interpolating Information Criterion](https://mlsanity.com/paper/2311.07013/) (2023)
- [Provable Tempered Overfitting of Minimal Nets and Typical Nets](https://mlsanity.com/paper/2410.19092/) (2024)
- [Implicit Bias of Policy Gradient in Linear Quadratic Control: Extrapolation to Unseen Initial States](https://mlsanity.com/paper/2402.07875/) (2024)
- [When Are Bias-Free ReLU Networks Effectively Linear Networks?](https://mlsanity.com/paper/2406.12615/) (2024)
- [Provable Privacy Attacks on Trained Shallow Neural Networks](https://mlsanity.com/paper/2410.07632/) (2024)
- [Precise Asymptotic Generalization for Multiclass Classification with Overparameterized Linear Models](https://mlsanity.com/paper/2306.13255/) (2023)
- [Quantifying Overfitting along the Regularization Path for Two-Part-Code MDL in Supervised Classification](https://mlsanity.com/paper/2503.02110/) (2025)
- [Harmful Overfitting in Sobolev Spaces](https://mlsanity.com/paper/2602.00825/) (2026)
- [Sufficient Conditions for Stability of Minimum-Norm Interpolating Deep ReLU Networks](https://mlsanity.com/paper/2602.13910/) (2026)
- [Frequency maps reveal the correlation between Adversarial Attacks and Implicit Bias](https://mlsanity.com/paper/2305.15203/) (2023)
- [Demolition and Reinforcement of Memories in Spin-Glass-like Neural Networks](https://mlsanity.com/paper/2403.02537/) (2024)
- [Gradient Descent Robustly Learns the Intrinsic Dimension of Data in Training Convolutional Neural Networks](https://mlsanity.com/paper/2504.08628/) (2025)
- [Embedding principle of homogeneous neural network for classification problem](https://mlsanity.com/paper/2505.12419/) (2025)
- [Directional Convergence, Benign Overfitting of Gradient Descent in leaky ReLU two-layer Neural Networks](https://mlsanity.com/paper/2505.16204/) (2025)
- [Deep Exploration of Epoch-wise Double Descent in Noisy Data: Signal Separation, Large Activation, and Benign Overfitting](https://mlsanity.com/paper/2601.08316/) (2026)

## 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.