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 when high-dimensional overparameterization makes the training data separable despite a nonseparable population. It develops asymptotic theory for Gaussian and random one-layer features, deriving explicit limits for margin and prediction error.

  • Problem

    The open question is max-margin generalization when separability arises from overparameterization despite a non-linearly-separable population, a regime where classical margin bounds miss qualitative behavior.

    Source: §1.1 · p. 5

  • Method

    The paper characterizes asymptotic margin and error for max-margin classifiers and applies its Gaussian theory to nonlinear random features through universality.

    Source: §1.2 · p. 7, §5 · p. 18

  • Results

    Margin and prediction error converge to explicitly characterized deterministic limits; benign-overfitting sequences are characterized, and random-feature test error decreases with width, reaching a minimum at large overparameterization.

    Source: §1.2 · p. 7

  • Takeaways & Limitations

    For characterized covariance-signal sequences, max-margin classification can achieve prediction error within ε of Bayes error as n and p grow proportionally.

    Source: §1.2 · p. 7

    The proof setup pairs a p-dimensional problem with an infinite-dimensional convex problem, so elementary empirical-process arguments do not apply.

    Source: §6 · p. 26

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 generalization when overparameterization makes data separable, deriving asymptotic prediction-error and margin characterizations, benign-overfitting conditions, and results for random features.

1.1 Background

  • The paper focuses on dimensionality blow-up, where separability arises through overparameterization despite moderate signal-to-noise and a population distribution that is not linearly separable.This regime is distinct from analyses premised on strong signal-to-noise and approximately separable data.Source: §1.1 · pp. 3, 5

1.2 Overview of results

  • The maximum margin converges in probability to a deterministic limit, yielding an interpolation threshold above which data are separable with positive margin and below which they are non-separable.The threshold generalizes a recent result of [CS18].Source: §1.2 · p. 7
  • Under proportional asymptotics, the test error converges in probability to an explicitly characterized deterministic limit for Gaussian features with covariance Σ.The analysis assumes the feature covariance and true parameter sequence satisfy conditions ensuring the limit is well defined.Source: §1.2 · pp. 5–7
  • The asymptotic test-error formula characterizes sequences (Σ, θ*) that achieve benign overfitting with prediction error within ε of Bayes error when p ≍ n.The paper presents this as the first generalization of [TB20] beyond ridge regression.Source: §1.2 · p. 7
  • For one-layer random neural networks, test error decreases monotonically with width and is minimal as p/n ≫ 1, giving exact asymptotics beyond simple ridge regression.Universality results allow the Gaussian theory to apply to these non-Gaussian random features.Source: §1.2 · p. 7
  • Gordon’s Gaussian comparison approach reduces the optimization to a nearly separable problem, while an infinite-dimensional convex formulation proves uniqueness of its characterizing equations.The approach builds on convex-concave optimization methods.Source: §1.2 · p. 8

2 Benign overfitting and the role of overparametrization

The section gives conditions under which max-margin classification can approach Bayes error, including a necessity result for overparameterization. Two examples show ε-consistency under different covariance and signal structures.

2 Benign overfitting and the role of overparametrization

  • Overparameterization is necessary for the max-margin classifier to attain near-Bayes error, and excess error is small when overparameterization is sufficient, covariance eigenvalues decay slowly, and the signal has little mass in small-eigenvalue directions.The theorem’s bounds have a bias- and variance-like structure, though classification error has no exact bias-variance decomposition.Source: §2 · pp. 8–9
  • In the bilevel example, choosing ψ large and φ and λs small makes the excess error at most ε with probability tending to one.The setup has kn predictive covariates and pn − kn junk covariates; ψφ < ε and ψλs ≪ ε are sufficient choices stated in the passage.Source: §2 · pp. 9–10
  • With eigenvalues λi ≍ i^-1(log i)^-α for α > 1, choosing ψ large and φ small makes the excess error at most ε with probability tending to one.This example shows benign overfitting for classification under a covariance decay rate motivated by ridgeless regression.Source: §2 · p. 10
  • The theorem’s and examples’ bounds remain order one in proportional asymptotics, while their constants depend only on λM and f, allowing ε-consistency conclusions.The bounds expose how excess risk depends on Σ and θ∗.Source: §2 · p. 10

3 A random features model

The section studies max-margin classification on nonlinear random features and develops an equivalent Gaussian perspective for its asymptotics, simulations, and wide-network behavior.

3.1 Classification using random features

  • The classifier maps covariates through nonlinear features generated by random unit-sphere first-layer weights, then chooses second-layer weights to maximize the margin.This is a two-layer network with fixed, non-optimized first-layer weights.Source: §3.1 · p. 11

3.2 Asymptotics via equivalent Gaussian model and universality

  • The Gaussian-equivalent construction replaces nonlinear feature residuals with independent noise, yielding a usable noisy linear feature map even for potentially non-separable data.The residuals have zero mean and unit variance, and are orthogonal to the linear component by construction.Source: §3.2 · pp. 12–13
  • As p, n, d → ∞ with p/d → ψ1 and n/d → ψ2, random-feature max margin and test error coincide with predictions from the equivalent Gaussian model.The model’s asymptotics match those of a Gaussian model with matching second-order statistics.Source: §3 · p. 10, §3.2 · p. 13

3.3 Numerical experiments

  • Above the interpolation threshold, the margin is strictly positive with high probability and appears to vanish linearly at the threshold, while test error decreases with overparameterization and is minimized at large ratios.The simulations compare ReLU random features with predictions from the Gaussian covariates model.Source: Figure 1 · p. 13, §3.3 · p. 14, Figure 2 · p. 14
  • The standard margin-based generalization bound is vacuous here, while simulations with a different activation matched on γ1 and γ∗ produce results hardly distinguishable from ReLU.The theory predicts that margin and test error depend on the activation only through γ1 and γ∗.Source: §3.3 · pp. 14–15, Figure 3 · p. 15

3.4 Wide network asymptotics

  • In the wide, high-dimensional limit, the random-features max-margin classifier is equivalent in margin and classification error to a linear soft-margin classifier in the original covariates.The random-features classifier is linear in the lifted space, nonlinear in the original space, and has vanishing training error; the equivalent soft-margin classifier is linear in the original space.Source: §3.4 · p. 16

4 Further related work

This section situates the paper among work on noisy high-dimensional statistics and overparametrized generalization, emphasizing its analysis of max-margin classification with general covariance. It also relates the paper’s results to separability thresholds, prior methods, and subsequent extensions.

4 Further related work

  • In the noisy high-dimensional regime, proportional sample and parameter counts yield non-trivial asymptotic limits, studied across regression, classification, and matrix estimation using several mathematical techniques.This regime has roots in statistical physics; Gardner computed the isotropic, random-label maximum-margin threshold κ*(ψ).Source: §4 · p. 17
  • The analysis uses Gordon’s inequality and addresses uniqueness of the optimization minimizer, unlike [SAH19], in the overparametrized regime with general covariance.Earlier logistic-regression analyses [CS18] [SAH19] focus on the underparametrized regime and assume isotropic covariates; general covariance is needed to capture random-feature behavior.Source: §4 · p. 17
  • Earlier mathematical studies of overparametrized generalization focused on least-squares or ridge regression, with proportional-asymptotic ridge results in [MM19].Moving beyond ridge regression requires tools beyond random matrix theory; the motivating literature includes interpolation in deep networks [ZBH+16], broader interpolation behavior [BMM18], and phase transitions [GJS+19].Source: §4 · pp. 17–18
  • For p/n → ψ, the paper generalizes the separability threshold in [CS18] and characterizes the margin for ψ > ψ*; Cover’s special-case threshold is ψ* = 1/2.The margin is more challenging to characterize because it depends on all entries of (Σ, θ*), whereas separability does not.Source: §4 · p. 18
  • Subsequent work generalized the results, including max ℓ1-margin analysis; independent work treated isotropic covariates, while non-asymptotic studies established benign-overfitting guarantees [FVBS23] [ZKS+22].The setting assumes separated mixture components and feature-independent label noise; [FVBS23] extend that analysis to two-layer ReLU networks, and [ZKS+22] uses Gaussian comparison inequalities in generalized linear models.Source: §4 · p. 18
  • The paper is the first to characterize covariance and parameter sequences (Σ, θ*) under which max-margin classification exhibits benign overfitting in classification accuracy.This result is limited to proportional asymptotics.Source: §4 · p. 18

5 Main results

The section introduces asymptotic predictions for maximum margin and generalization error, then states a theorem characterizing these quantities and the separability threshold in the proportional high-dimensional regime.

5.2 Main statement

  • The main theorem characterizes asymptotic maximum margin and generalization error for Gaussian features and labels generated under the paper’s stated assumptions.It considers i.i.d. data with p/n tending to a positive finite limit.Source: §5 · p. 18, §5.2 · pp. 20–21

5.1 Introducing the asymptotic predictions

  • The asymptotic predictions are well-defined through a unique solution, and κ∗(µ, ψ) increases strictly with ψ and diverges as ψ grows.The proposition also states continuity and monotonicity properties of the auxiliary prediction functions.Source: §5.1 · pp. 19–20

5.2 Main statement

  • Data are asymptotically linearly separable when ψ exceeds ψ∗(0), and non-separable when ψ is below that threshold.The stated result concerns probability tending to one in the high-dimensional limit.Source: §5.2 · p. 20, §5.3 · p. 22
  • The theorem’s margin, error, and distributional characterizations extend beyond the previously characterized isotropic, purely random-label case, which confirmed Gardner’s non-rigorous result.The paper identifies that isotropic case as the only previously characterized case it knows of.Source: §5.2 · p. 21

5.3 Proof technique

  • The proof analyzes a convex-concave Gaussian minimax problem using Gordon’s comparison inequality and a refinement by Thrampoulidis, Oymak, and Hassibi.For non-separability below ψ∗(0), it applies the same approach to a related minimax quantity.Source: §5.3 · pp. 21–22

6 Proofs … B.1 Definitions

The proofs reduce the max-margin analysis to simpler Gaussian and asymptotic optimization problems, then establish threshold and limiting-distribution results. The appendices contain many technical steps.

6 Proofs

  • The proof diagonalizes Σ without loss of generality and uses Gordon’s comparison inequality to replace a complicated Gaussian-process minimax problem with a simpler one.The joint distribution and Theorem 3 are basis-independent; the inequality is stated for convenience.Source: §6 · p. 23
  • For κ>0, Fκ is strictly convex; it is also strictly increasing in c2≥0 and in κ.These properties support the convex optimization arguments in the proof.Source: §6 · p. 24
  • The finite-dimensional optimizer has a unique minimum with almost-sure convergence, but proving its limit is nontrivial because its dimension grows while the limiting problem is infinite-dimensional.The text notes that elementary empirical-process arguments do not apply to this gap.Source: §6 · p. 26
  • For κ>κ*(ψ), P(ξ_n,ψ,κ>0)→1, while for κ<κ*(ψ), P(ξ_n,ψ,κ=0)→1.These are the stated proportional-asymptotic limits for ξ_n,ψ,κ.Source: §6 · p. 26
  • For ψ>ψ*(0), Proposition 6.5 gives max-margin classifier asymptotics, while Proposition 6.6 shows its coordinate empirical law converges in probability in W2 to L_ψ,κ*(ψ).The empirical law is that of the feature coordinates, weights, and scaled classifier coordinates.Source: §6 · p. 27

A Notations

  • The paper’s notation establishes scalar, vector, and matrix conventions, defines W2, and treats p/n→ψ as the standing proportional-asymptotic limit.The limit is understood even when not written explicitly.Source: A Notations · p. 27

B Properties of the asymptotic optimization problem

  • The asymptotic optimization problem determining maximum margin and prediction error has both a three-parameter formulation and an infinite-dimensional formulation.The formulations use (c1,c2,s) and the optimization in Eq. (6.13), respectively.Source: B Properties of the asymptotic… · p. 28

B.1 Definitions

  • B.1 defines L2(P) and its orthogonal projection, then specifies the (g,x,w) coordinates, Q∞=N(0,1)⊗μ, and an Fκ-based optimization with minimum R*.The projection is onto the orthogonal complement of W in L2(P).Source: §B.1 · p. 28

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

This section establishes analytic properties of the function and variational objective, using them to characterize the optimization problem’s minimizer and prove uniqueness and properties of the defining systems and parameters. It also proves continuity and monotonicity results and rules out zero values of c₂ and s under the stated condition on ψ.

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

  • Fκ is strictly convex, strictly increasing in c2 for c2 ≥ 0 and in κ, and continuously differentiable.The arguments use Assumption 3 for strictness and dominated convergence for differentiability.Source: §B.2 · pp. 29–30

B.3 Properties of Rψ,κ,P

  • Under Lemma B.3’s assumptions, Rψ,κ,P is weakly lower semicontinuous and strictly convex, so (B.3) has a unique minimizer h* up to almost-sure equality.The proof obtains existence using weak compactness of the constraint set and uniqueness from strict convexity.Source: §B.3 · p. 31

Then the following hold

  • The results characterize the unique minimizer h* through the unique solution of Eq. (B.13) and state a bound on that solution.The supplied passages do not provide the equations or the bound’s explicit form.Source: Then the following hold · p. 32

B.3.1 Proof of Lemma B.3

  • The proof of Lemma B.3 establishes lower semicontinuity from continuity and monotonicity properties, then proves strict convexity to obtain uniqueness.Weak compactness of the unit constraint set yields existence of a minimizer.Source: §B.3.1 · pp. 32–33

B.3.2 Proof of Lemma B.4

  • The proof of Lemma B.4 treats the three cases A1, A2, and A3, using convexity and Cauchy–Schwarz in its bounds.The proof also invokes the strict increase of Fκ in κ.Source: §B.3.2 · pp. 33–34

B.3.3 Proof of Lemma B.5

  • The proof of Lemma B.5 uses KKT conditions to characterize the minimizer and establishes that the associated scalar s is positive.The minimizer is unique by strict convexity; the proof derives the positivity conclusion by contradiction.Source: §B.3.3 · pp. 35–36
  • The proof of Lemma B.5 establishes uniqueness of the solution (c1, c2, s) to Eq. (B.49) and uses it to characterize R*.The characterization follows from Eq. (B.50), with (c1, c2, s) given by the unique solution.Source: §B.3.3 · p. 37

B.4 Consequences for P = Qn and P = Q∞

  • For ψ > ψ↓(κ), Corollary B.7 gives a unique system solution for P = Q∞ and sufficiently large n for P = Qn, with the Q∞ system equivalent to Eq. (5.6).It also identifies the Q∞ solution with (c1(ψ, κ), c2(ψ, κ), s(ψ, κ)).Source: §B.4 · p. 38
  • For P = Q∞ and sufficiently large n for P = Qn, Corollary B.7 also states a representation and bounds for the system’s solution.The supplied passages do not expose the formulas for that representation or those bounds.Source: §B.4 · p. 39

B.5 Proof of Proposition 5.1

  • The map T(ψ, κ) is continuous, strictly increasing in κ, and strictly decreasing in ψ.The solution functions c1, c2, and s are also continuous on the stated domain ψ > ψ↓(κ).Source: §B.5 · p. 40

B.5.1 Proof of Lemma B.8

  • For ψ > ψ*(0), every solution of Eq. (B.49) with P = Q∞ has c2 ≠ 0 and s ≠ 0.The proof rules out c2 = 0 and then, using ∂2Fκ(c1, c2) > 0, rules out s = 0.Source: §B.5 · p. 41, §B.5.1 · p. 42

C Analysis of the Gordon’s optimization problem: Proof of Proposition 6.4 … D.1 Proof of Lemma 6.1

These sections establish the convergence and uniform-convergence results used in the analysis of the Gordon parameters, including reductions of distributional limits to Wasserstein-2 limits. They also prove claims in Lemma C.1 and handle label dependence in Lemma 6.1 by decomposing the Gaussian design and conditioning.

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

  • Every limit point of (c1,n, c2,n, sn) solves the limiting system, whose unique solution is (c1,∞, c2,∞, s∞), so the parameter triple converges.The proof obtains the limiting equations using uniform convergence on a compact set, then applies uniqueness to identify every limit point.Source: C Analysis of the Gordon’s… · pp. 43, 45
  • Equation (6.16) is reduced to two Wasserstein-2 convergence claims: one for the limiting function under changing inputs and one for the finite- versus limiting-parameter functions.The proof uses the triangle inequality; the second claim is strengthened to convergence of the functions evaluated at the same random inputs.Source: C Analysis of the Gordon’s… · pp. 43–44

C.1 Proof of Lemma C.1

  • Lemma C.1 establishes uniform convergence of the expected functions on a compact set using pointwise convergence and equicontinuity, with monotonicity in s for i = 3.For i = 1, 2 the functions are equicontinuous on the set; for i = 3 they are equicontinuous in (c1, c2) at fixed s.Source: C Analysis of the Gordon’s… · p. 45, §C.1 · p. 46
  • Claim 6 follows from uniform moment bounds and estimates that reduce the i = 2 case to i = 1.The proof uses a uniform lower bound on V↓1 and the identity V↓2 = (V↓1)^2.Source: §C.1 · p. 49
  • A direct evaluation yields zero, and E[|(G2 + W2)/X|] is uniformly bounded over n ∈ N; using Eq. (C.30) and Eq. (C.31), Claim 7 follows.Source: §C.1 · p. 50

D.1 Proof of Lemma 6.1

  • The proof addresses dependence between y and the Gaussian design by decomposing X̄ along w and its orthogonal complement, which is independent of (u, y).Here w parallels θ̄*, where θ̄* = Λ^1/2θ*; X is rewritten as X̄Λ^1/2.Source: §D.1 · p. 50
  • Conditioning on (u, y) permits applying Theorem 4 for Θp = Bp(1), after which the proof takes expectations over (u, y).The resulting statement is given for any t ∈ R.Source: §D.1 · p. 50

D.2 Proof of Lemma 6.2

The proof reduces Lemma 6.2 to a uniform convergence claim, established through concentration, covering, and compactness arguments.

D.2 Proof of Lemma 6.2

  • The uniform convergence claim (D.5), together with the Lipschitz property of the positive-part map, implies Lemma 6.2 for parameters with norm at most one.Source: §D.2 · p. 51
  • Bernstein’s inequality [Ver18b, Thm 2.8] gives exponential concentration because the variables are subgaussian and their squares are subexponential.Source: §D.2 · p. 52
  • The relevant empirical quantity is Lipschitz in its parameters, using high-probability Gaussian norm bounds and Minkowski’s inequality.Source: §D.2 · p. 53
  • An n^-1/4 covering and a union bound yield events with summable failure probabilities, so Borel–Cantelli establishes almost sure uniform convergence.Source: §D.2 · p. 53
  • Dominated convergence gives pointwise convergence as ∥θ*,n∥Σ approaches ρ, and Arzelà–Ascoli upgrades it to uniform convergence.Source: §D.2 · p. 54

E Asymptotics of the prediction error: Proof of Proposition 6.5 … F.1 Notation

The appendix completes the prediction-error proof using separation properties of a gap function and convergence bounds. It then turns to the coordinate distribution of the maximum-linear classifier, introducing empirical-distribution notation for that analysis.

E Asymptotics of the prediction error: Proof of Proposition 6.5

  • Strict convexity and continuity of Fκ yield a lower-semicontinuous gap that is positive when its two arguments differ.The proof identifies Lemma E.1 as the crucial observation for establishing the target claim.Source: E Asymptotics of the prediction error:… · p. 55
  • The proof completes Proposition 6.5 by combining a high-probability bound with Lipschitz continuity and convergence of the estimated margin to κ*(ψ).The proof states that these steps establish its target claim at Eq. (E.9).Source: E Asymptotics of the prediction error:… · p. 56

E.1 Proof of Lemma E.1

  • Lemma E.1 supplies an auxiliary step in the prediction-error proof, using that Fκ increases in its second argument.The proof concludes that its preceding inequalities give the desired lemma.Source: §E.1 · p. 57

F Asymptotics of the Coordinate Distribution of √pˆθ

F.1 Notation

  • The notation in F.1 defines an empirical distribution for θ and a Wasserstein ball around Lψ,κ*(ψ), along with its complement in the unit ball.These definitions frame the section’s stated goal of establishing an ε-dependent claim.Source: §F.1 · p. 57

F.2 Main content of the analysis · F.3 Proof of Lemma F.1

The analysis proves Proposition 6.6 through three steps: a convergence result, containment of the relevant set, and a positive gap bound. It uses Lemma F.1 for the third step and proves that lemma in the following subsection.

F.2 Main content of the analysis

  • The proof is based on three steps, whose three facts are proved in the following three paragraphs and imply Eq. (F.2), yielding Proposition 6.6.Source: §F.2 · p. 58
  • The first step establishes a stronger convergence result, using comparison lemmas and uniform Lipschitz continuity to obtain convergence in probability.The variational characterization gives a (ψ)^-1/2-Lipschitz mapping, uniformly in n, ψ, and ε.Source: §F.2 · pp. 58–59
  • The second step uses Wasserstein continuity and Proposition 6.4(b) to establish the stated eventual containment of Θc_p(ε) in Bc(ε/2).The argument combines the bound W2(Lp(θ1), Lp(θ2)) ≤ ∥θ1 − θ2∥2 with convergence from Proposition 6.4(b).Source: §F.2 · pp. 58–59
  • The third step obtains a positive gap because Fκ is continuous, strictly convex in (c1, c2), and strictly increasing in c2 for fixed c1.This gives η(ψ; ε) = ψ^-1 · gapκ(ε/2) > 0.Source: §F.2 · p. 59
  • Lemma F.1 is the technical tool for the third step’s second fact, which is used to establish Eq. (F.5) with a positive η.The proof invokes the lemma to support the lower bound over Θc_p(ε).Source: §F.2 · p. 60

F.3 Proof of Lemma F.1

  • Lemma F.1 is reduced to three elementary bounds; (a) follows from the triangle inequality, while (c) is verified by calculation and identities.The proof states that these bounds imply the lemma.Source: §F.3 · pp. 61–62

G Data Separability · G.1 A comparison result · G.2 Typical value is positive

The appendix proves Lemma 6.7 in two steps, including a comparison argument and a positivity result. For ψ < ψ*(0), the typical value converges in probability to a positive Ξ*(ψ).

G Data Separability

G.1 A comparison result

  • The comparison argument invokes the Gaussian comparison inequality (Theorem 4) and states an almost-sure relation involving n and ψ.Source: §G.1 · p. 62
  • The comparison setup specifies independent g ~ N(0, I_p), h ~ N(0, I_n), and u ~ N(0, I_n).Source: §G.1 · p. 62
  • After the inequality chain, the proof introduces Ξ^(2).Source: §G.1 · p. 62

G.2 Typical value is positive

  • For ψ < ψ*(0), the typical value converges in probability to some Ξ*(ψ) > 0.This convergence establishes the desired Lemma 6.7.Source: §G.2 · p. 63
  • The positivity argument uses homogeneity of F0 and F0 > 0 on the set c1^2 + c2^2 = 1, under ψ < ψ*(0).Source: §G.2 · p. 63

H Proof of Theorem 1 … H.2.4 Control on the derivative ∂2F

This section proves Theorem 1 by bounding limiting prediction error under the stated assumptions, including showing it cannot equal Bayes error in the proportional regime. It also develops technical bounds to complete Proposition H.7 and control ∂2F, yielding Proposition H.8.

H Proof of Theorem 1

  • Theorem 3 gives the limit of Errn(y, X) as Err*(µ, ψ) under Assumptions 1–3, reducing the proof of Theorem 1 to Proposition H.1.Proposition H.1 additionally assumes that f is almost everywhere differentiable, increasing, and satisfies f(0) = 1/2 and f′(0) > 0.Source: H Proof of Theorem 1 · p. 63

H.1 Lower bound in Proposition H.1

  • The limiting error cannot equal Bayes error in the proportional regime, and can achieve near Bayes error only when ψ is large enough.The lower bound in Proposition H.1 uses a constant depending only on ρ, λM, and f.Source: H Proof of Theorem 1 · p. 63

H.2 Upper bound in Proposition H.1

  • For any λ > 0, Proposition H.1 gives an upper error bound with a constant depending only on ρ, λM, and f.The bound is stated using B(λ, µ, ψ) and V(λ, µ, ψ).Source: H Proof of Theorem 1 · p. 63

H.2.2 Controls on the implicit regularization term λ◦

  • For sufficiently small cρ,f, the implicit regularization term satisfies λ◦ ≲ρ,f λs.The argument bounds λ◦ using controls on ∂2F and the optimizer quantities.Source: §H.2.2 · pp. 67–68

H.2.3 Order equivalence between the ratio |c*2/c*1| and the derivative ∂2F

  • The proof establishes c*1 > 0 and |c*2/c*1| ≍ρ ∂2Fκ*(c*1, c*2).These relations connect the coefficient ratio to the derivative at the optimizing parameters.Source: §H.2.3 · p. 68

H.2.3 Order equivalence between the ratio |c∗ 2/c∗ 1| and the derivative ∂2F

  • The proof establishes κ* ≲ρ,f c1* and concludes the proof of Proposition H.7 on order equivalence between |c2*/c1*| and ∂2F.Source: §H.2.3 · p. 69

H.2.4 Control on the derivative ∂2F

  • For sufficiently small cρ,f, bounds on γ − α^2 and ν in terms of Λ yield the control on |∂2F| stated in Proposition H.8.The proof gives |γ − α^2| ≲ρ,f Λ and ν ≤ Λ; Lemma H.9 establishes the technical bound used for ν.Source: §H.2.4 · pp. 70–71

I Some technical results … J.1 Setup

The appendix establishes the KKT characterization and uniqueness of the optimizer, then sets up the random-features wide-limit analysis through variational expressions for margin and prediction error.

I.1 Proof of KKT conditions (B.33)

  • The optimizer of (B.4) is unique, and it is optimal exactly when it satisfies the KKT conditions (B.33).The proof establishes sufficiency and necessity of the conditions.Source: §I.1 · pp. 73–74
  • The KKT proof handles both interior solutions, with norm below 1, and boundary solutions, with norm equal to 1.For a boundary minimizer, a separation argument shows the subgradient intersects the cone of vectors −sh* for some s ≥ 0.Source: §I.1 · p. 74

J Large width asymptotics for the random features model: Proof of Proposition 3.1

J.1 Setup

  • With ψ2 fixed and ψ = ψ1/ψ2, taking ψ → ∞ is equivalent to taking ψ1 → ∞.Source: §J.1 · p. 75
  • The setup defines μψ1 as the joint distribution of (X, W), using independent variables drawn from the Marchenko–Pastur law and a standard normal distribution.The passage identifies the Marchenko–Pastur law as μ̃ψ1 and the independent standard normal variable as G̃.Source: §J.1 · p. 75
  • The asymptotic maximum rescaled margin and prediction error are formulated through a variational characterization, with the prediction error expressed using its unique optimizer.The setup identifies T(ψ, κ) with R*ψ1(κψ−1/2, τ) and introduces quantities used to express the prediction error.Source: §J.1 · pp. 75–76

J.2 Proof of Proposition 3.1 · J.3 Proof of Lemma J.1, J.2,J.3 and J.4

This section proves Proposition 3.1 and supporting lemmas by reducing the large-ψ₁ variational problem to a limiting optimization and establishing supporting properties. It also characterizes the feasible coefficient set for ψ₁>1 and simplifies the expression for R*.

J.2 Proof of Proposition 3.1

  • The limiting optimization has a unique interior minimizer characterized by first-order stationarity, and its value function is strictly increasing with a unique zero.That zero coincides with κ̄*_wide(ψ2, γ1, γ*).Source: §J.2 · p. 76
  • The proof shows finite-ψ1 margin roots converge to the unique zero of the limiting variational function.For the prediction-error claim, it uses τ(ψ1)→0 and establishes the required optimizer limit using coefficient estimates and margin convergence.Source: §J.2 · pp. 78–79

J.3 Proof of Lemma J.1, J.2,J.3 and J.4

  • The cited bound establishes that, as ψ1→∞, sup over κ>0 and h with Eψ1[h²]≤1 of |Eψ1,κ(h)| converges to exactly zero.Source: §J.3 · p. 83
  • The cited passage states that Tψ1 is the same for all ψ1 > 1, but the supplied excerpt ends before giving the value to which it equals.Source: §J.3 · p. 84
  • The proof simplifies R* by optimizing d3 and d4 for fixed d1 and d2, whose feasible pairs satisfy d1^2+d2^2≤1 and d2≥0.The resulting expression completes the proof of Eq. (J.23).Source: §J.3 · pp. 84–85
  • For any h with Eψ1[h2]≤1, the proof shows its coefficient tuple (di,ψ1(h)) lies in T.Source: §J.3 · p. 85

K Proof of Proposition 3.2 · L Special examples and numerical illustrations

Appendix K derives Proposition 3.2 by reducing its optimization and establishing asymptotic limits; Appendix L introduces special parameter and covariance sequences to illustrate the main results and their statistical insights.

K Proof of Proposition 3.2

L Special examples and numerical illustrations

L.1 Isotropic well specified model · L.2 Isotropic misspecified models

In isotropic well-specified models, test error rises with overparameterization above the interpolation threshold, while in a misspecified model it first falls as added features reduce approximation error and then rises. In both settings, the maximum margin does not reliably reflect test-error behavior.

L.1 Isotropic well specified model

  • For isotropic well-specified data, test error increases with ψ when ψ > ψ*, and its value at ψ* lies between 0 and 1/2.The analytical predictions agree with numerical results.Source: Figure 5 · p. 87, §L.1 · p. 88
  • In the well-specified isotropic setting, both test error and margin decrease as ψ decreases, contrary to the expectation that decreasing margin raises test error.The margin does not concentrate near its population value in this regime.Source: Figure 5 · p. 87, §L.1 · pp. 88–89
  • For well-specified isotropic data, increasing p/n also increases target complexity, so this setting does not capture the benefits of overparametrization.The covariates are isotropic, and rotational invariance makes margin and prediction error independent of the unit-norm θ* vector.Source: §L.1 · pp. 87, 89
  • The classical margin-based estimate has the wrong qualitative dependence on ψ and is never non-trivial in the well-specified isotropic setting.Figure 6 compares the estimate with analytical predictions and numerical test errors.Source: Figure 6 · p. 89, §L.1 · p. 89

L.2 Isotropic misspecified models

  • In the misspecified model, test error decreases for ψ*_miss < ψ < ψ0, then increases for ψ > ψ0.The example’s error curve reflects the reduction in approximation error as features are added.Source: Figure 7 · p. 90, §L.2 · p. 91
  • In the misspecified model, omitted signal features act as label noise, and adding features reduces that noise and the approximation error.The feature distribution of this model is independent of the number of features used for learning.Source: §L.2 · pp. 90–91
  • The misspecified distribution is richer than the well-specified one, but its optimal overparameterization ratio is bounded.For the example with signal mass across the first p0 features, γ(ψ) = ψ/ψ0 for ψ ≤ ψ0 and γ(ψ) = 1 for ψ > ψ0.Source: §L.2 · p. 91
  • In the misspecified example, the maximum margin increases monotonically with ψ, but its margin-based bound is always larger than one and misses test-error behavior.Here κ*(ψ)/√ψ < 1.Source: §L.2 · p. 91

Related papers

Loading 1911.01544v3…