PaperlayerView exact revision on arXiv

Source-linked AI summary

The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime

Andrea Montanari, Feng Ruan, Youngtak Sohn, Jun Yan

arXiv:1911.01544v3math.STstat.ML

TL;DR

The paper asks how max-margin classifiers generalize in overparametrized, high-dimensional settings where separability emerges despite moderate signal-to-noise ratios. It analyzes Gaussian features under proportional asymptotics and transfers the results to certain nonlinear random features. The theory yields exact limiting generalization errors, benign-overfitting conditions, and decreasing random-feature test error as width grows.

  • Problem

    Existing rigorous analyses of overparametrized generalization largely focus on ridge or least-squares regression, leaving max-margin classification less characterized.

  • Method

    The paper studies Gaussian features with covariance Σ in proportional asymptotics, then uses universality to analyze max-margin classification with random one-layer neural features.

  • Results

    The empirical margin and prediction error converge to explicitly characterized limits; the theory also identifies benign-overfitting sequences and shows random-feature test error decreases with width.

  • Takeaways & Limitations

    High-dimensional dimensionality blow-up can produce analyzable max-margin generalization behavior beyond ridge regression, including benign overfitting and favorable large-width random-feature asymptotics.

  • Takeaways & Limitations

    The analysis requires assumptions such as tightness for convergence statements, and several mathematical questions remain unsolved.

Abstract

from arXiv · show

Modern machine learning classifiers often exhibit vanishing classification error on the training set. They achieve this by learning nonlinear representations of the inputs that maps the data into linearly separable classes. Motivated by these phenomena, we revisit high-dimensional maximum margin classification for linearly separable data. We consider a stylized setting in which data $(y_i,{\boldsymbol x}_i)$, $i\le n$ are i.i.d. with ${\boldsymbol x}_i\sim\mathsf{N}({\boldsymbol 0},{\boldsymbol Σ})$ a $p$-dimensional Gaussian feature vector, and $y_i \in\{+1,-1\}$ a label whose distribution depends on a linear combination of the covariates $\langle {\boldsymbol θ}_*,{\boldsymbol x}_i \rangle$. While the Gaussian model might appear extremely simplistic, universality arguments can be used to show that the results derived in this setting also apply to the output of certain nonlinear featurization maps. We consider the proportional asymptotics $n,p\to\infty$ with $p/n\to ψ$, and derive exact expressions for the limiting generalization error. We use this theory to derive two results of independent interest: $(i)$ Sufficient conditions on $({\boldsymbol Σ},{\boldsymbol θ}_*)$ for `benign overfitting' that parallel previously derived conditions in the case of linear regression; $(ii)$ An asymptotically exact expression for the generalization error when max-margin classification is used in conjunction with feature vectors produced by random one-layer neural networks.

1 Introduction

The paper studies max-margin classification when high-dimensional overparametrization makes moderately noisy, non-linearly separable data linearly separable, focusing on dimensionality blow-up rather than learned representations. It derives asymptotic margin and prediction-error formulas, characterizes benign overfitting, and applies the theory to random one-layer features.

  • 1.1 Background: The paper focuses on dimensionality blow-up from feature representations, rather than data-dependent feature learning, because it is more amenable to rigorous analysis.The scope includes neural tangent and lazy regimes, kernels, and random-feature approximations.
  • 1.1 Background: Moderate signal-to-noise data that are not population-linearly separable become separable through high-dimensional overparametrization.This setting differs from classical strong-signal separability and motivates analyzing separability as a high-dimensional phenomenon.
  • 1.2 Overview of results: The theory characterizes the limiting maximum margin κ∗(µ, ψ) and generalization error Err∗(µ, ψ) in proportional high-dimensional asymptotics.The empirical maximum margin and prediction error converge in probability to non-random limits that are explicitly characterized.
  • 1.2 Overview of results: The limiting error formula characterizes sequences of (Σ, θ∗) achieving benign overfitting, extending prior benign-overfitting results beyond ridge regression.The criterion concerns prediction error approaching within ε of Bayes error while n and p grow proportionally.
  • 1.2 Overview of results: For random one-layer neural features, universality transfers the Gaussian theory to non-Gaussian features, and test error decreases with width, minimizing at p/n ≫1.The construction generates nonlinear random features and fits a max-margin separating hyperplane.
  • 1.2 Overview of results: The analysis uses Gordon’s Gaussian comparison inequality and an infinite-dimensional convex formulation to establish uniqueness of the nonlinear-equation solution.The convex problem’s KKT conditions are equivalent to the nonlinear equations governing the asymptotics.

2 Benign overfitting and the role of overparametrization

The paper identifies conditions under which max-margin classification can approach Bayes error despite interpolation, and shows that overparameterization is necessary for this behavior. The relevant conditions involve overparameterization, covariance eigenvalue decay, and how the signal aligns with low-variance directions.

  • Conditions for benign overfitting: The excess error is small when p/n is large, covariance eigenvalues decay slowly, and the signal has little projection onto eigenvectors with small eigenvalues.These terms play roles analogous to bias and variance terms, although classification error lacks an exact bias-variance decomposition.
  • Main result: Theorem 1 shows that overparameterization is necessary for the max-margin estimator to achieve near-Bayes risk in the high-dimensional setting.The result is established for sequences with p_n/n approaching a finite positive ratio and under the stated assumptions on the covariance and link function.
  • Example 1: In a bilevel covariance model, choosing sufficiently large overparameterization and sufficiently weak junk-feature variance makes the excess error at most ε with probability tending to one.The construction separates a subset of powerful covariates from lower-variance junk covariates.
  • Example 2: With eigenvalues λ_i approximately j^-1(log j)^-α for α > 1, benign overfitting persists when max-margin classification replaces ridgeless regression.The example is motivated by a covariance-decay regime previously studied for benign overfitting in regression.
  • Example 2: For the decaying-eigenvalue example, sufficiently large p/n followed by sufficiently small signal-support ratio yields excess error at most ε with probability tending to one.The bounds are order one in proportional asymptotics but expose dependence on (Σ, θ_*), enabling ε-consistency conclusions.

3 A random features model

The paper analyzes random-feature max-margin classification through an equivalent Gaussian model and universality, obtaining asymptotically exact margin and test-error predictions. In the wide limit, the nonlinear lifted classifier is equivalent to a linear soft-margin classifier in the original covariates.

  • Random features construction: The classifier generates nonlinear features with fixed random first-layer weights and learns max-margin second-layer weights.Features are ˜x_ij = σ(⟨w_j, z_i⟩), with w_j sampled uniformly on the unit sphere.
  • Equivalent Gaussian model and universality: Random features have the same asymptotic margin and test error as an equivalent Gaussian model with matching second-order statistics.The universality result transfers the Gaussian theory to nonlinear random-feature models.
  • Numerical experiments: As overparameterization increases, the margin becomes positive beyond an interpolation threshold, while test error decreases and is minimized at large p/n.The margin vanishes linearly as p/n approaches the threshold, whereas the test error is monotonically decreasing in p/n.
  • Numerical experiments: The predicted margin and test error depend on the activation through γ1 and γ∗, with a different activation producing nearly indistinguishable results from ReLU.The numerical comparison matches activations selected to have the same γ1 and γ∗ values.
  • Wide network asymptotics: In the wide high-dimensional limit, the random-feature max-margin classifier behaves like a linear classifier with a soft margin in the original covariates.The random-feature classifier remains nonlinear in the underlying covariates and has vanishing training error, while the equivalent soft-margin classifier is linear in d dimensions.

4 Further related work

The paper situates its contribution within noisy high-dimensional statistics, max-margin classification, overparametrized learning, and asymptotic analyses using general covariance structures.

  • The paper builds on proportional-regime asymptotics developed for problems including Lasso and regularized linear regression, and on earlier statistical-physics analyses of maximum margins.
  • The analysis extends prior separability thresholds by treating general covariance structures rather than only isotropic covariates, which is necessary for random-features models.
  • Unlike prior overparametrized-learning theory focused mainly on least-squares or ridge regression, this work analyzes max-margin classification.
  • Earlier max-margin results established benign overfitting under separated mixtures and feature-independent label noise, with extensions to two-layer ReLU networks.
  • The paper is the first, within proportional asymptotics, to characterize covariance and parameter sequences yielding benign overfitting in classification accuracy.

5 Main results

The paper derives asymptotic formulas for maximum margin, separability, and generalization error in Gaussian max-margin classification with general covariance and signal structure. These formulas yield a separability threshold and support benign-overfitting results.

  • The main theorem characterizes the asymptotic maximum margin κ∗(µ, ψ) and generalization error Err∗(µ, ψ) under proportional asymptotics.
  • Analytical characterization: The paper uses a nonlinear-equation characterization whose well-definedness relies on existence and uniqueness of the relevant solution.
  • Threshold for linear separability: Data are asymptotically linearly separable with high probability when ψ exceeds ψ∗(0), and non-separable when ψ is below it.
  • Threshold for linear separability: The theory generalizes the separability threshold previously obtained for logistic labels by Candès and Sur [CS18] and also characterizes the overparametrized margin.

6 Proofs

The proofs reduce Gaussian max-margin problems through Gordon comparison inequalities to tractable asymptotic optimization problems. They establish threshold behavior, margin convergence, classifier limits, and generalization-error formulas.

  • Gordon’s Gaussian comparison inequality reduces the original convex-concave minimax problem to a simpler Gaussian process whose asymptotics can be analyzed.
  • Technical limitations: The asymptotic passage is technically difficult because the finite-dimensional problem grows with p while its limit is infinite-dimensional, so elementary empirical-process arguments do not apply.
  • For κ above κ∗(ψ), the margin-feasibility event occurs with probability tending to one, while below κ∗(ψ) it collapses to zero.
  • The proof establishes convergence of the empirical distribution of covariance, signal, and max-margin coordinates to Lψ,κ∗(ψ) in W2 distance.
  • Non-separability below the threshold follows by applying the same comparison method to a covariance-normalized optimization problem.

B.2 Properties of the function F: Proof of Lemma 6.3

The proof establishes structural properties of Fκ that support the asymptotic optimization analysis, including strict convexity, monotonicity, continuity, and uniqueness of minimizers.

  • For κ > 0, Fκ is strictly convex in (c1, c2), ensuring strong control of the associated optimization problem.
  • For fixed c1, Fκ is strictly increasing in c2 over c2 ≥ 0, while Fκ is strictly increasing in κ.
  • Fκ is continuously differentiable, with continuity justified through dominated convergence and positivity of the underlying hinge-loss expectation.
  • Strict convexity of the induced functional yields a unique minimizer in the infinite-dimensional optimization problem.
  • The proof uses convexity, monotonicity, continuity, compactness, and dominated convergence to establish existence and uniqueness results for the limiting optimization problem.

C Analysis of the Gordon’s optimization problem: Proof of Proposition 6.4

The proof establishes convergence of the finite-dimensional Gordon optimization parameters to their limiting values, then uses this convergence to derive the stated distributional and Wasserstein limits.

  • Parameter convergence: (c1,n, c2,n, sn) converges to (c1,∞, c2,∞, s∞) as n,p→∞ with p/n→ψ.The argument shows every limit point satisfies the limiting system, whose solution is unique.
  • Wasserstein convergence: The target Wasserstein convergence is reduced by triangle inequality to separate convergence of the input distributions and replacement of Hn,ψ,κ by H∞,ψ,κ.These are the two intermediate claims labeled (a) and (b).
  • Assumptions: The proof assumes ψ>ψ↓(κ), s∞>0, and an almost-sure bounded feature variable X<C.These conditions ensure the limiting expressions are well behaved and denominators remain controlled.
  • Wasserstein convergence: Hn,ψ,κ is linear in G, W, and ⟨G,W⟩QnG, whereas H∞,ψ,κ is linear only in G and W.Convergence of the coefficients follows from convergence of (c1,n,c2,n,sn) and uniform lower bounds on the relevant denominator.
  • Parameter convergence: Uniform convergence of the defining expectation equations on a compact parameter set controls the finite-n solutions.The proof combines compactness, continuity, and uniqueness of the limiting system.

D.2 Proof of Lemma 6.2

The proof of Lemma 6.2 establishes uniform convergence by combining concentration, Lipschitz or equicontinuity control, and compactness arguments.

  • Limiting distributions: The label-generating distributions are specified by Gaussian variables with P(y=1|u)=f(∥θ*,n∥Σ·u) and P(Y=1|U)=f(ρ·U).The convergence ∥θ*,n∥Σ→ρ permits passage from the finite-n to limiting expectations.
  • Concentration: Bernstein concentration applies because the relevant hinge-type variables are uniformly subgaussian and their squares are subexponential.The resulting bounds hold uniformly over the parameter set after a covering argument.
  • Concentration: The empirical functions are Lipschitz in the parameters, with n,ψ,κ(ν,q) having Lipschitz constant 3ψ^-1/2.This controls deviations between covering-net points and arbitrary parameter values.
  • Uniform convergence: Uniform convergence follows from pointwise convergence plus equicontinuity on the compact parameter set.For one function class, monotonicity replaces equicontinuity; Arzelà–Ascoli and Dini’s theorem then complete the argument.

E Asymptotics of the prediction error: Proof of Proposition 6.5

The proof analyzes the asymptotic prediction-error quantities through continuity, convexity, and convergence of the maximum-margin parameters and margin.

  • Optimization structure: Strict convexity and continuity of Fκ ensure positive separation through the gap function whenever compared parameters differ.This positivity is used to control deviations from the limiting optimizer.
  • Prediction-error limits: The prediction-error limits follow from Proposition 6.4, Lemmas 6.1–6.2, and convergence of the empirical margin and classifier parameters.The proof transfers finite-sample quantities to their limiting counterparts through the established asymptotic characterization.
  • Margin convergence: The margin estimator κ̂n converges in probability to κ*(ψ), while ξn,ψ,κ is uniformly Lipschitz in κ.These properties extend fixed-κ asymptotics to the random empirical margin.
  • Classifier distribution: The maximum-margin classifier is characterized through its empirical distribution Lp(θ) and a Wasserstein neighborhood around Lψ,κ*(ψ).The section’s goal is to show the empirical distribution of the learned classifier belongs asymptotically to every such neighborhood.

F.2 Main content of the analysis

The analysis proves that maximum-margin solutions concentrate around the limiting distribution by combining Wasserstein convergence, a gap bound, and a three-step exclusion argument.

  • Main convergence result: For every ε>0, the empirical distribution Lp(θ̂MMn) eventually lies within Wasserstein distance ε of Lψ,κ*(ψ).The proof reduces this claim to three intermediate steps controlling the optimizer, its complement, and a positive objective gap.
  • Step 1: The first step establishes convergence of the empirical distribution at the maximum-margin solution using Lemmas 6.1–6.2 and Proposition 6.4.The relevant objective is uniformly Lipschitz in κ, which supports the convergence argument.
  • Step 2: The second step shows that parameters outside the Wasserstein neighborhood are eventually separated from the limiting distribution.This uses W2(Lp(θ1),Lp(θ2))≤∥θ1−θ2∥2 and convergence of the empirical law at the maximum-margin solution.
  • Step 3: The third step derives a positive objective gap η(ψ;ε) from strict convexity and monotonicity of Fκ.The gap is quantified as η(ψ;ε)=ψ^-1·gapκ*(ψ)(ε/2).
  • Step 3: Lemma F.1 supplies the technical comparison bound needed to extend the gap argument uniformly over pairs of unit-norm parameters.Its proof combines elementary inequalities, convexity, and bounds on the covariance-related quantities.

G Data Separability

The section establishes a Gaussian-comparison-based route to the desired separability result. Under ψ < ψ∗(0), the relevant quantity converges in probability, completing Lemma 6.7.

  • The section begins by reducing the claim to a two-step proof of Lemma 6.7.
  • The proof proceeds through a Gaussian comparison inequality and introduces Ξ(2) after the resulting chain of inequalities.
  • ψ < ψ∗(0) yields the stated convergence in probability for some Ξ∗(ψ) > 0, completing Lemma 6.7.
  • The argument uses homogeneity of F0 and positivity on the unit constraint set to establish the needed strict inequality.

H Proof of Theorem 1

The section proves Theorem 1 by connecting the asymptotic prediction error to an explicit variational characterization and analyzing its gap from Bayes error. It derives lower and upper bounds showing that exact Bayes error is unattainable at fixed proportional dimension, although near-Bayes performance can occur for sufficiently large ψ.

  • Theorem 3 identifies the limiting prediction error as Err∗(µ, ψ) and provides its explicit formula through Γ and the optimizer quantities.
  • Proposition H.1 supplies both lower and upper error bounds with constants depending only on ρ, λM, and the link function f.
  • Err⋆(µ, ψ) cannot equal the Bayes error in the proportional regime, but can approach it when ψ is sufficiently large.
  • The gap from Bayes error is analyzed through Γ, whose behavior near zero is controlled by monotonicity and Γ′(0+) = 0, Γ′′(0+) > 0.
  • The proof controls the surrogate gap through the ratio |c∗_2/c∗_1| + 1/c∗_1≤0 and establishes bounds on the associated optimization quantities.
  • The technical proof combines KKT conditions, homogeneity, concentration, and deterministic derivative bounds for the convex optimization problem.

I Some technical results

This section develops technical foundations for the variational analysis, including KKT characterizations and random-feature asymptotics. It relates the optimization quantities to asymptotic margin and prediction-error formulas.

  • A minimizer of the constrained optimization problem is characterized exactly by the KKT conditions, with uniqueness inherited from the underlying problem.
  • The KKT proof handles separately interior and boundary minimizers, using convex subgradient arguments and a separation result for closed convex sets.
  • Random features: In the random-features model, ψ = ψ1/ψ2, so fixing ψ2 makes ψ → ∞ equivalent to the wide-feature limit ψ1 → ∞.
  • Random features: The random-feature construction uses Gaussian variables and the Marchenko–Pastur law to define the limiting joint distribution and variational problem.
  • Random features: The variational quantities determine asymptotic maximum margin and prediction error through the optimizer h∗ and the associated c∗ quantities.

J.2 Proof of Proposition 3.1

The proof of Proposition 3.1 approximates the wide random-feature variational problem by a limiting optimization as ψ1 grows. It then establishes convergence of the asymptotic margin and prediction error through uniqueness and continuity properties.

  • The limiting function T∞ is strictly increasing and has a unique zero, which determines the wide-limit asymptotic margin.
  • The proof relies on uniform approximation of the variational coefficients, conditioning on zero and nonzero feature events, and bounds that vanish with increasing ψ1.
  • As ψ1 → ∞, the random-feature optimization is approximated by a limiting problem whose optimizer is uniquely characterized by first-order stationarity.
  • The finite-width margin converges to the unique zero of the limiting function because the finite-width functions converge pointwise and preserve the relevant monotonicity and continuity.
  • The prediction-error limit follows by letting τ(ψ1) tend to zero and transferring the finite-width optimizer to the limiting variational problem.
  • Strict convexity and symmetry properties ensure uniqueness and restrict the limiting optimizer to the interior of the feasible set.

K Proof of Proposition 3.2

The proof derives asymptotic limits by reducing the optimization to a lower-dimensional characterization and establishing convergence and uniqueness properties.

  • K Proof of Proposition 3.2: The proof tracks the optimizer through equivalent optimization formulations to establish the claimed asymptotic characterization.The derivation uses explicit optimization over auxiliary variables and retains the minimizer to obtain the final claim.
  • K Proof of Proposition 3.2: Convergence in probability is established using preceding lemmas and uniform convergence over compact ranges of the tuning parameter.Monotonicity and Lipschitz continuity provide the uniform-over-compacts step.
  • K Proof of Proposition 3.2: The limiting equation has a unique zero because the relevant function is strictly decreasing in the margin parameter.This uniqueness identifies the asymptotic margin value.
  • K Proof of Proposition 3.2: The section also situates the argument within Gordon-inequality methods for high-dimensional classification and contrasts it with underparametrized logistic-regression analyses.Earlier applications include compressed sensing and Lasso, while the closest logistic-regression results focus on the underparametrized regime.

L.1 Isotropic well specified model

For isotropic Gaussian features, the theory predicts when max-margin classification becomes separable and accurately matches simulations, while test error can worsen as overparameterization increases. In misspecified models, adding features can initially reduce error by lowering approximation noise, but excessive overparameterization reverses that improvement.

  • L.1 Isotropic well specified model: Test error decreases as ψ decreases until crossing the interpolation threshold, below which the data are no longer separable.The maximum margin has a strictly positive limit exactly above the threshold ψ∗.
  • L.1 Isotropic well specified model: Theoretical predictions for maximum margin and test error agree closely with numerical results in the isotropic well-specified model.Figure 6 compares Corollary L.1 predictions with simulations, while Figure 5 reports the underlying margin and error curves.
  • L.1 Isotropic well specified model: As ψ decreases, both margin and classification error decrease, contradicting the classical expectation that smaller margins imply larger test error.The paper attributes this behavior to non-concentration of the margin in the high-dimensional regime.
  • L.1 Isotropic well specified model: The classical margin-based estimate has the wrong dependence on ψ and is never non-trivial in the isotropic setting.Even after discarding the factor 4, the bound remains at least 1.
  • L.2 Isotropic misspecified models: The misspecified construction captures approximation benefits more effectively than the well-specified model, yet remains too simple to represent unbounded modern overparameterization benefits.Its optimum overparameterization ratio ψ is bounded.
  • L.2 Isotropic misspecified models: In the misspecified model, test error decreases for ψ∗_miss < ψ < ψ0 but increases again for ψ > ψ0 as added features first reduce approximation error and then overshoot the optimum.The misspecified distribution is independent of the number of features, but its optimal overparameterization ratio remains bounded.
Loading 1911.01544v3…