PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Spencer Frei, Gal Vardi, Peter L. Bartlett, Nathan Srebro

arXiv:2303.01462v1cs.LGstat.ML

TL;DR

Benign overfitting asks how a model can fit noisy training labels perfectly yet generalize well to unseen data. This paper analyzes gradient-flow solutions satisfying margin-maximization KKT conditions and proves benign-overfitting results for linear classifiers and two-layer leaky ReLU networks in specified settings. The key mechanism is that near-orthogonality makes these classifiers behave like nearly uniform averages of training examples.

  • Problem

    Benign overfitting is the phenomenon of perfectly fitting noisy training data while still generalizing well, contrary to longstanding intuition that fitting noise harms out-of-sample prediction.

    Source: §1 · p. 1

  • Method

    The paper analyzes margin-maximization KKT points, using their nearly balanced weighted-sum representation on nearly orthogonal data to study linear classifiers and leaky ReLU networks.

    Source: §3 · p. 5

  • Results

    The paper proves benign overfitting for linear classifiers and two-layer leaky ReLU networks in specified settings, including noisy sub-Gaussian and nearly orthogonal-cluster distributions.

    Source: §1 · p. 2

  • Takeaways & Limitations

    In the studied settings, the implicit structure of gradient-flow solutions helps explain how interpolating classifiers can generalize despite noisy labels.

    Source: §6 · p. 12, §7 · p. 13

    The proof covers settings where two-layer leaky ReLU networks have linear decision boundaries; benign overfitting with nonlinear learned boundaries remains an open direction.

    Source: §7 · p. 13

Abstract

from arXiv · show

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.

1 Introduction

The paper studies when interpolating noisy labels can coexist with good test performance, extending benign-overfitting results to two-layer leaky ReLU networks and new data distributions. Its proof strategy connects gradient flow’s KKT implicit bias to nearly balanced averages of training examples.

1 Introduction

  • Benign overfitting concerns fitting noisy training data perfectly while still generalizing well to unseen data, contrary to the longstanding intuition that fitting noise harms test prediction.The phenomenon drew attention following initial experiments by Zhang et al. [Zha+17].Source: §1 · p. 1
  • The results establish benign overfitting for linear classifiers and two-layer leaky ReLU networks in new distributional settings, including noisy sub-Gaussian and nearly orthogonal-cluster data.In the cluster setting, the results essentially generalize prior findings for linear classification [CL21] [WT21] and networks with smooth leaky activations [FCB22].Source: §1 · p. 2
  • Gradient flow’s implicit bias toward margin-maximization KKT points underlies the proof that nearly balanced training-example weights yield benign overfitting.The paper states that every KKT point in its settings has a linear decision boundary, including for leaky ReLU networks.Source: §1 · p. 2

Related work

  • Prior work proves benign overfitting in linear classification for high-dimensional sub-Gaussian mixtures [CL21] [WT21], while Frei, Chatterji, and Bartlett show it in two-layer networks with smooth leaky ReLU activations on high-dimensional sub-Gaussian mixtures [FCB22].Source: Related work · pp. 2–3
  • The paper situates its analysis among work on gradient-flow implicit bias, including maximum-margin directions for linear classifiers [Sou+18] and KKT points for homogeneous networks [LL20] [JT20].Its leaky ReLU analysis builds on work about nearly orthogonal data [Fre+23].Source: Related work · p. 3

2 Preliminaries

The preliminaries define the linear and neural-network margin problems and explain how KKT points arise in gradient-flow training. In the settings studied, generalization by feasible KKT points yields benign overfitting because feasibility interpolates the training data.

2 Preliminaries

  • The paper studies maximum-margin linear classifiers and two-layer leaky ReLU networks with a trained first layer and fixed second-layer weights.The fixed output weights are initialized with equal numbers of positive and negative signs.Source: §2 · p. 4
  • The linear max-margin classifier minimizes the Euclidean norm of w subject to each signed training margin yi⟨w, xi⟩ being at least 1.The paper states that gradient descent on exponentially tailed losses such as logistic loss is implicitly biased toward these solutions [Sou+18].Source: §2 · p. 4
  • The preliminaries introduce the Clarke subdifferential for locally Lipschitz objectives and define KKT points using feasibility and nonnegative multipliers.For continuously differentiable functions, the Clarke subdifferential reduces to the gradient.Source: §2 · p. 4
  • Any feasible KKT point of the neural-network margin problem interpolates the training data, so its generalization implies benign overfitting even with a constant fraction of uniformly random labels.The paper states that it will show such KKT points generalize well in several settings.Source: §2 · p. 5
  • For the 1-homogeneous neural network, gradient flow on exponential or logistic loss converges in direction to a KKT point when the empirical loss becomes sufficiently small.This convergence result is attributed to Lyu and Li [LL20] and Ji and Telgarsky [JT20]; the resulting KKT point need not be a global maximum-margin solution [VSS21] [Lyu+21].Source: §2 · p. 5

3 Properties of KKT Points for Nearly Orthogonal Data

For nearly orthogonal training data, KKT classifiers have decision boundaries represented by positively weighted, approximately balanced sums of training examples. This characterization connects linear max-margin solutions and gradient-flow-trained leaky ReLU networks to nearly uniform sample averages used to establish benign overfitting.

3 Properties of KKT Points for Nearly Orthogonal Data

  • Nearly orthogonal data make both linear max-margin and leaky ReLU KKT decision boundaries representable as positively weighted sums with weights of the same order.The resulting estimator is a nearly uniform average of the signed training examples.Source: §3 · p. 5
  • P-orthogonality includes exactly orthogonal data and can also hold for i.i.d. samples from a broad class of distributions.The paper introduces p-orthogonality and τ-uniform classifiers to formalize the conditions and representation used in this section.Source: §3 · p. 5
  • As p-orthogonality increases and training-example norm ratios approach one, the linear max-margin classifier becomes proportional to the classical signed sample average.The linear result follows from analysis of the max-margin KKT conditions.Source: §3 · p. 6
  • For leaky ReLU networks, p-orthogonality with p ≥ 3γ^-3 yields a KKT decision boundary represented by a linear classifier.The proposition states that gradient flow on logistic or exponential loss converges in direction to such a KKT point for any initialization.Source: §3 · p. 6
  • The leaky ReLU characterization requires no assumptions on network width or initialization, and as p increases, norm ratios approach one, and γ approaches one, its decision boundary approaches the sample-average direction.The proposition thereby covers networks in the feature-learning regime.Source: §3 · p. 6
  • Analyzing τ-uniform classifiers captures both linear max-margin estimators and nearly orthogonal leaky ReLU networks trained by gradient flow.In the paper’s distributional settings, this estimator can have zero training error on noisy data and test error near the noise rate.Source: §3 · p. 6

4 Benign Overfitting for Sub-Gaussian Marginals

For noisy sub-Gaussian data, the paper shows that linear max-margin classifiers and leaky ReLU networks can interpolate noisy training data while generalizing well, under conditions on signal variance and covariance rank. Near-orthogonality connects KKT solutions to nearly uniform linear classifiers, and the results also cover a Gaussian setting.

4 Benign Overfitting for Sub-Gaussian Marginals

  • As the assumptions’ constant C grows, the training examples become more orthogonal, enabling the max-margin linear classifier to approach a 1-uniform estimator.The resulting τ-uniform estimators exhibit benign overfitting, with tolerated noise levels approaching 1/2 as τ approaches one.Source: §4 · pp. 7–8
  • Under the stated sub-Gaussian assumptions, sufficiently high covariance rank and a sufficiently strong first-coordinate signal yield benign overfitting for linear classifiers and leaky ReLU networks.The labels follow the sign of the first coordinate, with flips at rate η; the result also assumes an anti-concentration bound near zero for that coordinate.Source: §4 · pp. 7–8
  • Leaky ReLU KKT points also exhibit benign overfitting, but smaller leaky parameter γ means less tolerated label noise; as γ approaches one, their behavior recovers the linear predictor’s.The data conditions and the comparison with the linear predictor are stated in the corollary discussion.Source: §4 · pp. 8–9
  • The setting requires both sufficiently high covariance rank and first-coordinate variance large relative to the remaining coordinates, constraints that can be in tension.The paper gives a Gaussian covariance example with ρ in (1/2, 1) satisfying both conditions.Source: §4 · p. 9
  • For Gaussian covariates with covariance diag(d^ρ, 1, …, 1), ρ in (1/2, 1), and d = ˜Ω(n^(1/(1−ρ))), KKT points of the leaky ReLU margin problem exhibit benign overfitting.The result holds with probability at least 1 − 9δ under the stated sample-size and distributional conditions.Source: §4 · p. 9
  • For any initialization, gradient flow converges in direction to a network satisfying the stated benign-overfitting result for leaky ReLU networks.The generalization bound in the corresponding corollary does not depend on the number of neurons m.Source: §4 · p. 9

5 Benign Overfitting for Clustered Data

For clustered data with noisy labels, near-orthogonality lets linear and leaky ReLU margin solutions behave like nearly uniform averages of training examples. Under the paper’s cluster assumptions, both can exhibit benign overfitting, including in specified orthogonal-cluster settings.

5 Benign Overfitting for Clustered Data

  • The clustered model samples a cluster uniformly, adds independent mean-zero sub-Gaussian noise to its mean, and flips the cluster’s clean label with probability η.The cluster means are assumed nearly orthogonal, alongside the stated sample-size and dimension conditions.Source: §5 · p. 10
  • Under the cluster assumptions, the training data are linearly separable with high probability, and increasing C makes them more orthogonal while bringing example norms closer together.These properties support applying the paper’s results relating near-orthogonality to nearly uniform margin solutions.Source: §5 · p. 10
  • If n min_q ||µ(q)||^4 = ω(k^2d), the linear classifier exhibits benign overfitting under the clustered-data assumptions.The theorem allows noise η ≤ 1/(1+τ) − ∆ for constants τ ≥ 1 and ∆ > 0.Source: §5 · p. 10
  • One covered case has orthogonal clusters with ||µ(q)|| = Θ(d^β), β in (1/4, 1/2), and k = O(1), under the stated dimension condition.For this setting, the supplied passage bounds test error by η plus an exponential term, but does not provide that term’s full expression.Source: §5 · p. 11
  • The paper distinguishes this setting from one where clean labels depend on a linear classifier over k = Θ(d^0.05) components.The latter is described as quite different from settings where labels depend on a constant number of high-variance directions.Source: §5 · p. 11
  • Under the same cluster assumptions and signal-strength condition, leaky ReLU KKT points exhibit benign overfitting, and gradient flow converges in direction to a network satisfying the result.The corresponding result applies to any KKT point of the stated network margin problem.Source: §5 · p. 11
  • The analysis does not explicitly cover two opposing clusters, though the authors say it can be extended to that distribution by a small proof modification.Their comparison notes that their analysis gives an explicit upper bound on tolerated noise for constant-probability label flips, unlike the cited smooth-activation results.Source: §5 · pp. 11–12

6 Proof intuition

The proof intuition is that a nearly uniform average of training examples can both fit noisy labels and retain a signal useful for test prediction. In the opposing-cluster example, the signal and noise components play different roles in those outcomes.

6 Proof intuition

  • The paper’s intuition uses a 1-uniform estimator, the sum of signed training examples, as a simple instance of the nearly orthogonal max-margin form.The authors identify clean and noisy examples according to whether observed labels match the clean labels.Source: §6 · p. 12
  • The estimator’s noise component helps fit noisy training labels but contributes little to prediction on fresh test examples.The paper contrasts it with µ, the linear classifier that achieves optimal accuracy for the distribution.Source: §6 · p. 12
  • The noise component has a larger effect on training than on test performance when d ≫ √n, according to the supplied comparison.The passage states this dimensional condition while omitting logarithmic factors in the preceding concentration discussion.Source: §6 · pp. 12–13
  • In the opposing-cluster setting, benign overfitting requires the signal to be weak enough not to prevent fitting noisy labels but strong enough to support accurate test predictions.The paper summarizes the setting as requiring both sufficiently high dimension and an appropriately sized underlying signal.Source: §6 · p. 13

7 Discussion

The paper characterizes new settings for benign overfitting in linear classifiers and two-layer neural networks, using gradient flow’s implicit bias to understand generalization by interpolating models with noisy labels.

7 Discussion

  • The work identifies new settings where linear classifiers and two-layer neural networks exhibit benign overfitting.It uses gradient flow’s implicit bias to connect model structure with generalization by interpolating models despite noisy labels.Source: §7 · p. 13
  • The proofs do not yet cover nonlinear decision boundaries for two-layer leaky ReLU networks.The paper identifies deeper ReLU networks and nonlinear learned boundaries as future research directions.Source: §7 · p. 13

A Proof of Proposition 3.3

The proof uses KKT multipliers to represent the linear max-margin classifier as a weighted sum of training examples, then bounds those multipliers under p-orthogonality.

A Proof of Proposition 3.3

  • The KKT representation expresses the max-margin classifier as a sum of training examples with nonnegative multipliers, zero for examples not on the margin.The proof then seeks upper and lower bounds on these multipliers under p-orthogonality.Source: A Proof of Proposition 3.3 · pp. 14–15

B Proof of Proposition 3.4

The proof shows that KKT points of leaky ReLU max-margin training act like weighted averages on p-orthogonal data, then uses concentration properties to establish the needed sub-Gaussian setting.

B Proof of Proposition 3.4

  • For p-orthogonal data, a leaky ReLU KKT point has a decision boundary equivalent to a weighted sum of labeled examples.Gradient flow on logistic or exponential loss converges in direction to such a KKT point.Source: B Proof of Proposition 3.4 · pp. 17, 21

C Proofs for Sub-Gaussian Marginals

  • Under the sub-Gaussian assumptions, a classifier’s test error is near the noise rate when its first component is positive and its remaining covariance-weighted components are small.The proof reduces this condition to properties of a nearly uniform weighted average of the training examples.Source: §C.1 · p. 22, C Proofs for Sub-Gaussian Marginals · p. 22

C.1 Preliminary concentration inequalities

  • With high probability, the sub-Gaussian training samples have similar norms and sufficiently small pairwise correlations to be p-orthogonal.These sample properties provide the conditions needed to apply the max-margin results.Source: §C.1 · p. 24, §C.2 · pp. 26–27

C.2 Proof of Lemma 4.1

  • The concentration bounds imply p-orthogonality and a sample-norm ratio approaching one as the assumptions’ constant grows.The proof establishes these as consequences of a high-probability event.Source: §C.2 · pp. 26–27

C.3 Proof of Theorem 4.2

The proof establishes benign overfitting for a τ-uniform classifier under the stated sub-Gaussian assumptions: it interpolates the training data and has generalization error close to the noise rate.

C.3 Proof of Theorem 4.2

  • The proof controls the classifier’s first component using the balance between clean and noisy examples, with the noise rate bounded by η ≤ 1/(2τ) − ∆.It also bounds the remaining covariance-weighted components using sample concentration and the stable-rank assumption.Source: §C.3 · pp. 27, 29, 30
  • Under the theorem’s stated conditions, including Assumptions (SG1) through (SG3), with constant τ ≥ 1 and δ ∈ (0, 1/7), the classifier x ↦ sign(⟨u, x⟩) exhibits benign overfitting with probability at least 1 − 7δ.Source: §C.3 · p. 31

C.4 Proof of Corollary 4.3, Corollary 4.4, and Corollary 4.5

The appendix verifies benign-overfitting corollaries for sub-Gaussian and Gaussian data, then develops the concentration and near-orthogonality facts used to analyze clustered data. These properties support generalization bounds and the later corollaries for clustered distributions.

C.4 Proof of Corollary 4.3, Corollary 4.4, and Corollary 4.5

  • Under the stated assumptions, max-margin linear classifiers and KKT points for leaky ReLU networks exhibit benign overfitting in the sub-Gaussian setting; gradient flow converges in direction to a network satisfying the stated condition.The appendix also establishes the corresponding KKT-point result for the Gaussian setting and convergence from any initialization.Source: §C.4 · pp. 32–33

D Proofs for clustered data

  • The clustered-data proof reduces small test error to positive projections onto each signed cluster mean, then uses τ-uniformity and sample-to-cluster correlations to establish the needed bounds.Propositions 3.3 and 3.4 connect max-margin solutions to τ-uniform classifiers when the training data is p-orthogonal.Source: D Proofs for clustered data · p. 34

D.1 Preliminary concentration inequalities

  • The preliminary concentration results control sample norms and inner products with other samples or cluster means, providing inputs to a generalization bound for classifiers over Pclust.The section also tracks clean and noisy examples within each cluster.Source: §D.1 · pp. 35–37

D.2 Proof of Lemma 5.1

  • Under assumptions CL1–CL4, the clustered training data is C/C2-orthogonal with high probability, and sample squared norms are close in ratio.The probability is at least 1 − 7δ.Source: §D.2 · p. 40

D.3 Proof of Theorem 5.2

For clustered data, the proof establishes benign overfitting for τ-uniform linear classifiers under stated assumptions. It derives the result by showing these classifiers align positively with signed cluster means and have controlled norm.

D.3 Proof of Theorem 5.2

  • The proof bounds each classifier’s projection onto a signed cluster mean and its norm, using within-cluster clean/noisy contributions and near-orthogonality between clusters.These bounds feed a generalization bound for classifiers of the form Σ_i s_i y_i x_i.Source: §D.3 · pp. 42, 46, 47
  • Under Theorem 5.2’s conditions, if n min_q ||μ(q)||^4 = ω(k^2d), then the linear classifier x ↦ sign(⟨u,x⟩) exhibits benign overfitting.The conditions include constant τ ≥ 1, η ≤ 1/(1 + τ) − Δ for absolute constants η, Δ > 0, and Assumptions (CL1) through (CL4).Source: §D.3 · p. 47

D.4 Proof of Corollary 5.3 and Corollary 5.4

The clustered-data corollaries transfer the τ-uniform classifier result to max-margin linear classifiers and KKT points of the leaky ReLU network problem. The network result also gives directional convergence of gradient flow from any initialization.

D.4 Proof of Corollary 5.3 and Corollary 5.4

  • Under CL1–CL4, the max-margin linear classifier and KKT points of Problem (3) satisfy the stated benign-overfitting bounds; when n min_q ||μ(q)||^4 = ω(k^2d), they exhibit benign overfitting.For the network, gradient flow converges in direction from any initialization to a network satisfying the stated condition.Source: §D.4 · pp. 48–49

Related papers

Loading 2303.01462v1…