PaperlayerView exact revision on arXiv

Source-linked AI summary

A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Models

Lijia Zhou, Frederic Koehler, Pragya Sur, Danica J. Sutherland, Nathan Srebro

arXiv:2210.12082v1stat.MLcs.LGmath.STstat.TH

TL;DR

Uniform-convergence analyses of interpolation have often used restrictive, well-specified linear-model assumptions. This paper develops non-asymptotic Moreau-envelope generalization bounds for Gaussian-feature linear predictors, combining training loss with complexity. It recovers optimistic-rate results in regression and extends the analysis to misspecification and classification.

  • Problem

    Prior uniform-convergence work has mostly focused on linear regression with a well-specified linear conditional mean and constant residual variance, limiting its coverage of broader loss and label settings.

    Source: §1 · p. 2

  • Method

    The paper bounds test error through Moreau envelopes of continuous losses, combining training error with complexity and optimizing the smoothing parameter.

    Source: §1 · p. 2, §4 · pp. 4–5

  • Results

    The bounds recover the optimistic rate for square-loss linear regression, extend it to misspecified labels, and yield analogous squared-hinge results and max-margin consistency.

    Source: §1 · p. 2, §5.2 · p. 6

  • Takeaways & Limitations

    Localized Gaussian-width bounds are reported to be asymptotically sharp for empirical risk minimizers, extending generalization analysis beyond proportional-scaling regimes.

    Source: §1 · p. 2, §8 · p. 10

    The framework's applicability is limited by its Gaussian-data assumption.

    Source: §8 · p. 10

Abstract

from arXiv · show

We prove a new generalization bound that shows for any class of linear predictors in Gaussian space, the Rademacher complexity of the class and the training error under any continuous loss $\ell$ can control the test error under all Moreau envelopes of the loss $\ell$. We use our finite-sample bound to directly recover the "optimistic rate" of Zhou et al. (2021) for linear regression with the square loss, which is known to be tight for minimal $\ell_2$-norm interpolation, but we also handle more general settings where the label is generated by a potentially misspecified multi-index model. The same argument can analyze noisy interpolation of max-margin classifiers through the squared hinge loss, and establishes consistency results in spiked-covariance settings. More generally, when the loss is only assumed to be Lipschitz, our bound effectively improves Talagrand's well-known contraction lemma by a factor of two, and we prove uniform convergence of interpolators (Koehler et al. 2021) for all smooth, non-negative losses. Finally, we show that application of our generalization bound using localized Gaussian width will generally be sharp for empirical risk minimizers, establishing a non-asymptotic Moreau envelope theory for generalization that applies outside of proportional scaling regimes, handles model misspecification, and complements existing asymptotic Moreau envelope theories for M-estimation.

1 Introduction

Uniform-convergence explanations of interpolation have largely relied on well-specified linear models and restrictive noise assumptions, leaving broader losses and misspecified labels less addressed. The paper develops Moreau-envelope bounds for high-dimensional GLMs, extending optimistic-rate results and analyzing a broader range of losses and settings.

1 Introduction

  • Uniform-convergence analyses of interpolation have mostly assumed a linear conditional label expectation and constant residual variance, unlike classical agnostic guarantees for broader losses and classes.Srebro et al. (2010) give optimistic-rate bounds for smooth, nonnegative losses, but their hidden logarithmic factor is too loose to explain noisy interpolation; Zhou et al. (2021) address this for well-specified linear regression.Source: §1 · p. 2
  • The Moreau-envelope bound extends the optimistic rate for square-loss linear regression to misspecified models, including nonlinear trends and heteroskedasticity.The squared hinge loss has the same envelope-scaling property, supporting an analogous rate argument and a consistency result for max-margin classifiers.Source: §1 · p. 2
  • Localized Gaussian-width bounds are reported to be asymptotically sharp for empirical risk minimizers even when overfitting is not necessarily benign.The paper also reports numerical simulations across varied feature distributions and label-generating processes.Source: §1 · p. 2

2 Related Work

Prior Moreau-envelope work focuses on asymptotic estimation and inference, while uniform-convergence studies of interpolation have often depended on well-specified linear models. This paper positions its contribution as a non-asymptotic generalization analysis that also covers misspecification and classification settings.

2 Related Work

  • Existing Moreau-envelope theory for M-estimators focuses on estimation and inference under proportional asymptotics and gives no non-asymptotic results.The cited work includes linear models and logistic regression.Source: §2 · p. 2
  • Earlier uniform-convergence analyses of linear regression generally assume a well-specified linear label model, whereas this theory relaxes the label-generation assumption but retains Gaussian features.Shamir (2022) also studies misspecification while allowing non-Gaussian features, and shows benign overfitting need not occur in the most general setting.Source: §2 · p. 3
  • For classification, the analysis uses the squared hinge loss's shared Moreau-envelope transformation with square loss, while cited asymptotic max-margin results assume proportional scaling.The paper instead uses the Gaussian Minimax Theorem for uniform convergence and a non-asymptotic bound.Source: §2 · p. 3
  • The paper contrasts its norm-based bound, which applies to all predictors and outside benign-overfitting conditions, with prior classification analyses.It compares Corollary 3 with Shamir (2022), whose Gaussian-setting result requires bounded data norm, while the paper states its result permits o(n) covariance eigenvalues to grow arbitrarily quickly.Source: §2 · p. 3

3 Problem Formulation

The paper studies learning linear predictors from i.i.d. data under a continuous loss, with labels generated by a Gaussian-feature multi-index model. This setup includes linear regression as well as nonlinear and heteroskedastic label mechanisms.

3 Problem Formulation

  • Given i.i.d. sample pairs and a continuous loss, the learning objective is empirical loss minimization for a linear model, with the goal of small population loss.The population loss is the expected loss over the data distribution.Source: §3 · p. 3
  • The model assumes centered Gaussian features with unknown covariance and labels formed from a link function of k signal directions and independent noise.The covariance-scaled signal vectors are assumed orthonormal; the noise need not be Gaussian.Source: §3 · p. 4
  • The multi-index model includes well-specified linear regression and permits nonlinear trends, heteroskedasticity, and binary labels.These cases arise by changing the link function, which need not be continuous.Source: §3 · p. 4

4 Moreau Envelope Generalization Theory

The theory bounds generalization using Moreau-smoothed losses, combining low-dimensional concentration with a predictor-complexity term. A VC-theory route supplies low-dimensional concentration under specified tail and dimension conditions.

4 Moreau Envelope Generalization Theory

  • A Moreau envelope smooths the original loss, with smaller λ corresponding to more smoothing; for square and squared hinge losses, the envelope is proportional to the original loss.For Lipschitz losses, the theory bounds the difference between the original and smoothed losses; optimizing λ balances approximation and generalization errors.Source: §4 · pp. 4–5
  • The generalization bound controls population Moreau-envelope loss against training loss using a low-dimensional concentration term and a predictor-complexity term.The low-dimensional component is tied to the k meaningful directions, while the dimension-free component can be controlled by predictor norm and typically absorbs noise-fitting complexity.Source: §4 · p. 4
  • The theorem combines concentration on a low-dimensional surrogate distribution with a complexity bound to control test error uniformly over predictors.The result is non-asymptotic and holds with probability at least 1 − δ under its stated assumptions.Source: §4 · pp. 4–5

4.1 VC Theory for Low-dimensional Concentration

  • VC theory yields low-dimensional concentration when a norm-equivalence condition and a bounded VC dimension hold, with the paper's settings typically giving h = O(k).The section also points to alternative concentration results based on fourth moments or Rademacher complexity.Source: §4.1 · pp. 5–6
  • Combining the general bound with VC concentration gives a uniform bound over constrained predictors when the surrogate distribution meets the stated condition and the associated loss class has bounded VC dimension.Uniformity over λ additionally requires the assumptions and VC-dimension bound to hold across λ.Source: §4.1 · pp. 5–6

5 Applications

The Moreau-envelope bound recovers optimistic rates for square-loss regression and extends them to squared-hinge classification and other losses. Further applications include improved contraction bounds and uniform convergence for smooth-loss interpolators.

5.1 Linear Regression with Square Loss

  • The square-loss Moreau envelope is proportional to the loss, enabling an optimized generalization bound that recovers optimistic rates for regression, including under model misspecification.The stated guarantee specializes to interpolators and establishes ℓ2 benign overfitting with misspecification.Source: §5.1 · p. 6

5.2 Classification with Squared Hinge Loss

  • The squared-hinge Moreau envelope is proportional to the loss, so the square-loss argument gives the same optimistic-rate bound for max-margin classification.In some settings, including noisy ones, minimizing squared hinge loss also minimizes zero-one misclassification loss.Source: §5.2 · p. 6

5.3 Further applications

  • For L1 loss, the Moreau envelope is a rescaled Huber loss, and its population risk is controlled by empirical L1 loss.As λ tends to zero, the Huber loss becomes the squared loss; the hinge-loss envelope likewise rescales the Huber hinge loss.Source: §5.3 · pp. 6–7
  • For an M-Lipschitz loss, the Moreau-envelope argument improves the standard contraction bound, whose symmetrization-and-contraction form loses a factor of two.For L1 loss, M = 1; this bound is not as tight as the version using Huber test loss.Source: §5.3 · p. 7
  • For smooth losses with zero minimum, interpolators have uniform convergence when k/n = o(1), extending Koehler et al. (2021) to arbitrary smooth losses.The passage assumes the loss is nonnegative and H-smooth.Source: §5.3 · p. 8

6 ℓ2 Benign Overfitting

The section combines norm bounds for interpolators with generalization bounds to establish benign-overfitting consistency results. Its results cover misspecified square-loss regression, squared-hinge classification, and a range of regularization strengths.

ℓ2 benign overfitting

  • Combining the norm-based generalization bound with an interpolator norm bound gives a sufficient route to consistency.The norm analysis supplies a high-probability bound on the radius B containing a zero-training-error predictor.Source: §6 · pp. 8–9
  • The square-loss benign-overfitting result does not require a well-specified linear model and holds under the paper’s more general model assumption.The section derives consistency under the stated ℓ2 benign-overfitting conditions.Source: §6 · pp. 8–9
  • The analogous classification result uses squared hinge loss, because its Moreau envelope is proportional to the loss just as for square loss.The argument is the same for both losses, which are squares of Lipschitz functions.Source: §6 · p. 8
  • Under the stated distributional and hypercontractivity assumptions, the corollary concerns squared-loss or squared-hinge minimum-norm interpolators across a sequence of distributions.The setup defines the interpolator using n i.i.d. samples and the population-loss minimizer.Source: §6 · p. 9
  • Consistency also holds uniformly along the constrained regularization path when the norm bound is at least the population minimizer’s norm, so the predictor need not be over-regularized.The passage states this uniformly over all such sequences of bounds.Source: §6 · p. 9

7 Training Error and Local Gaussian Width

A dual result bounds the training error of a constrained ERM using a Moreau envelope and a complexity term. With localized Gaussian width, the resulting generalization bound can be asymptotically sharp even when overfitting is not necessarily benign.

Training error and local Gaussian width

  • A dual theorem bounds constrained-ERM training error by a Moreau envelope and complexity term, supplying the norm bound used for interpolators.The bound applies to bounded convex sets and a loss convex in the prediction.Source: §7 · p. 9
  • With the appropriate localized Gaussian-width complexity, the generalization bound is asymptotically sharp for ERMs even when overfitting is not necessarily benign.The result provides a non-asymptotic analogue of existing asymptotic Moreau-envelope theory and recovers the well-specified linear-model case.Source: §7 · p. 10

8 Discussion

The discussion presents a broader localized uniform-convergence framework while noting that its current theory relies on Gaussian data. The appendix adds simulations, including tests beyond Gaussian covariates, and compares risk bounds along ridge regression paths.

8 Discussion

  • The authors extend localized uniform convergence to any loss and label-generating process under mild conditions, while the theory remains non-asymptotic and applies across overparameterized settings.They identify the Gaussian-data assumption as a significant restriction and note that the GMT formulation does not cover multiclass classification or two-layer networks.Source: §8 · p. 10

A Organization of the Appendices

  • The appendix organization assigns simulations to B, the main-result proof to D, and consistency applications to G.Appendix E handles low-dimensional concentration and linear-regression and classification guarantees; Appendix F proves Theorem 4.Source: A Organization of the Appendices · p. 14

B Additional Numerical Simulations

B.1 Linear Regression

  • The linear-regression simulations fit square-loss models with ℓ1 and ℓ2 penalties and use features x = Σ^1/2z, where z has independent, mean-zero, unit-variance coordinates.They also include a misspecified model with a nonlinear conditional mean and residual variance depending on x4.Source: §B.1 · pp. 14, 16

B.1.1 Speculative Risk Bounds for Non-Gaussian Features

  • The appendix conjectures that Rademacher complexity can extend the Gaussian-feature theory to broader distributions and uses simulations to test this conjecture.The simulations use synthetic data and are intended to confirm the theory beyond Gaussian covariates.Source: B Additional Numerical Simulations · p. 14, §B.1.1 · p. 16

Ridge Regression

  • For ridge regression, bound (18) uses the smaller projected norm, while bound (19) is sufficient to establish minimal-ℓ2-norm interpolator consistency in the junk-feature setting.The authors expect bound (19) to be tight throughout the ridge path, but report no experiments confirming tightness in the non-benign setting.Source: Ridge Regression · p. 16

B.1.2 Experimental Results

The experiments broadly support the risk bounds across ridge and LASSO regression, while illustrating differences in their tightness and behavior across feature settings. The section also describes population-risk calculations and experiments with squared-hinge linear classifiers.

B.1.2 Experimental Results

  • Ridge bounds closely track test error, while LASSO bounds are valid but less tight across the full regularization path.For LASSO, localized Gaussian width can yield sharp bounds across the path, at the cost of finer analysis than bounds (20) and (21).Source: §B.1.2 · pp. 17–18

B.1.3 Note on Computing the Optimal Linear Predictor and Population Risk

  • For square loss, population risk is computed from the optimal linear predictor, with expectations estimated using large samples for one-dimensional feature quantities.The predictor is obtained from a first-order condition, with separate treatments for well-specified and misspecified models.Source: §B.1.3 · p. 18
  • In junk-feature settings, ridge test error is nearly flat after fitting the signal, but over-regularization harms prediction risk.For non-benign features, optimally tuned ridge nearly achieves optimal risk, whereas the minimal-norm interpolator is inconsistent despite overparameterization.Source: Figure 4 · p. 20, Figure 5 · p. 21
  • Regularized LASSO can achieve nearly optimal risk through sparsity, but minimal-norm interpolation is not consistently benign across feature settings.In isotropic data the minimal-ℓ1 interpolator's population risk exceeds null risk; in non-benign settings its ℓ1 norm rises faster than with junk features.Source: Figure 6 · p. 22, Figure 8 · p. 24

B.2 Linear Classification

  • Squared-hinge linear classifiers use logistic-generated labels, so the learned model may be misspecified; the regression risk bounds also apply to ℓ1 and ℓ2 margin classifiers.The experiments use proportional and overparameterized sample-dimension settings; junk-feature paths are essentially flat when under-regularized, while the non-benign U-shaped curve is narrower near optimal regularization.Source: §B.2 · p. 25

B.2.1 Experimental Results

The margin-classifier experiments find that risk bounds track test error across feature distributions, with different limitations for ℓ2 and ℓ1 classifiers. The appendix also describes Gaussian-feature risk estimation, population optimization, and Gaussian minimax preliminaries.

B.2.1 Experimental Results

  • For ℓ2 max-margin classifiers, risk bounds tightly control test error across feature distributions, although overfitting can make isotropic-feature risk worse than the null risk.The bound-to-error gap is larger for heavy-tailed features, where confidence intervals are also wider because of the relatively small sample size.Source: §B.2.1 · p. 25, Figure 9 · p. 26
  • For ℓ1 max-margin classifiers, bounds establish consistency of optimally tuned predictors in junk and non-benign settings, but can loosen near interpolation as the ℓ1 norm grows.The isotropic and junk-feature population risks can also exceed the null risk, and non-benign features show multiple descent.Source: §B.2.1 · p. 25, Figure 10 · p. 27

B.2.2 Note on Computing the Population Risk with Gaussian Features

  • For Gaussian features, the appendix estimates population risk without drawing a new high-dimensional dataset, instead sampling from a two-dimensional distribution.The calculation conditions on the signal index and uses the resulting conditional Gaussian representation.Source: §B.2.2 · pp. 25, 28

B.2.3 Note on Computing the Optimal Linear Predictor

  • The population squared-hinge-loss minimizer is found by SGD; the example reduces to one dimension because labels are independent of features outside the first coordinate.The appendix sets w* = (5, 0, ..., 0) and b* = 3, then uses one-pass SGD on (x_i,1, y_i).Source: §B.2.3 · p. 28

C Preliminaries

  • Appendix C introduces signal-span and orthogonal covariance projections, whose design-matrix parts are independent, and states the Gaussian minimax theorem used as a key technique.Under its assumptions, the theorem bounds the primary optimization's lower tail by twice the auxiliary optimization's lower tail.Source: C Preliminaries · pp. 28–29

D Proof of Theorem 1

This section proves Theorem 1 through a truncated primary optimization and Gaussian min-max comparison, deriving uniform bounds under concentration and complexity conditions for regression and classification. It specializes the framework to square-loss regression, including polynomial misspecification and noise, and to squared-hinge classification, while establishing conditions for uniform guarantees.

D Proof of Theorem 1

  • Theorem 1 gives a uniform generalization bound with probability at least 1 − δ when surrogate training loss and Gaussian projection satisfy the stated concentration conditions.The proof uses truncation and Gaussian min-max comparison; the training-loss condition requires only one-sided concentration.Source: D Proof of Theorem 1 · pp. 30, 35, 36

E.1 Low-Dimensional Concentration

  • VC-dimension concentration yields a uniform bound over the predictor class, and the corollary extends uniformly over λ when the concentration and joint class-complexity conditions hold.The low-dimensional result applies when the surrogate loss has the required one-sided concentration and the associated threshold-indicator class has bounded VC-dimension.Source: §E.1 · p. 36

E.2 Linear Regression

  • For square loss, the threshold-indicator class has VC-dimension O(k), enabling a uniform generalization corollary under the surrogate-distribution concentration condition.The VC bound follows by relating the class to a union of two nonhomogeneous halfspaces.Source: §E.2 · p. 37
  • Gaussian hypercontractivity is used to obtain the required concentration parameter for misspecified polynomial regression with polynomial signal and scale and noise having finite eighth moment.The stated example assumes the signal and scale polynomials have degree at most l.Source: §E.2 · p. 38
  • The expected squared regression error decomposes into a term involving the conditional mean m and a separate noise term involving s and ξ.The separation uses independence of x and ξ.Source: §E.2 · p. 38
  • Finite eighth moments for ξ can be relaxed, but heavier tails may increase the constant multiplying τ or slow the low-dimensional concentration rate in n.The passage notes a Vapnik (1982) version of Theorem 2 that replaces the exponent 4 with 1 + ϵ.Source: §E.2 · p. 38

E.3 Linear Classification

  • The squared-hinge threshold class has VC-dimension at most k + 3, by reducing shattering to nonhomogeneous halfspaces in R^(k+2).The proof uses that the squared hinge loss is nonnegative and that nonhomogeneous halfspaces in R^(k+2) cannot shatter more than k + 4 points.Source: §E.3 · pp. 38–39
  • Corollary 4 gives a high-probability guarantee uniform over w and b for squared hinge loss when the surrogate distribution satisfies assumption (9) uniformly.Source: §E.3 · p. 39
  • Under a positive lower bound on both label probabilities, including random classification noise, the Gaussian-prediction moment argument verifies hypercontractivity condition (9).The argument bounds the eighth moment of the hinge margin using Gaussian moments.Source: §E.3 · p. 39
  • If labels are noisy on a positive-probability subset of x, Theorem 10 ensures hypercontractivity; examples include logistic regression and multi-index models with a not-always-large link function.The theorem assumes pη > 0, the probability that both conditional label probabilities are at least η.Source: §E.3 · pp. 39–40

E.3.1 Squared Hinge Loss and Zero-One Loss

For convex margin losses, removing predictor components orthogonal to the ground-truth direction cannot increase population loss. The section relates squared-hinge minimization to zero-one performance under specific conditions and examines the sharpness of the Lipschitz contraction bound.

E.3.1 Squared Hinge Loss and Zero-One Loss

  • In the realizable setting, a near-minimizer of squared hinge test loss has near-optimal zero-one loss by the general margin-loss comparison.The section also discusses a noisy setting where minimizing squared hinge test loss minimizes zero-one test loss, while noting that linear functions need not contain the measurable squared-hinge minimizer under label noise.Source: §E.3.1 · p. 40
  • For convex margin losses in the single-index model, any near-minimizer has an orthogonal component with covariance norm approaching zero, aligning it with the ground-truth direction.The loss difference is nonnegative and, for nonconstant losses, is zero only when that orthogonal component vanishes.Source: §E.3.1 · pp. 40–41
  • With zero bias and the stated condition, every squared-hinge-loss global optimum points along the positive ground-truth direction, and near-minimizers approach optimal zero-one loss.The section notes that alignment alone need not suffice in more general settings: predictor scale and bias must also match the ground truth.Source: §E.3.1 · pp. 41–42
  • When the ground-truth halfspace is Bayes-optimal, near-minimizers of squared hinge test loss are near-minimizers of zero-one loss.The text identifies logistic regression as a standard model for which the stated condition holds.Source: §E.3.1 · p. 42

E.4 Sharpness of Improved Lipschitz Contraction

  • The Lipschitz contraction bound has sharp constants for the L1 loss in the junk-feature setting, so further tightening requires a different bound form.The text identifies the Moreau-envelope bound with Huber test loss as one alternative and says it is more useful for interpolators.Source: §E.4 · p. 42

F Proof of Theorem 4

The proof of Theorem 4 recasts training loss as a min-max problem and compares its primary optimization with a Gaussian auxiliary optimization. A Gaussian minimax argument transfers a probability bound, after which the auxiliary problem is related back to the theorem's conclusion.

F Proof of Theorem 4

  • Theorem 4 assumes bounded convex sets and a loss convex in the prediction, with a high-probability condition on samples from the surrogate distribution.The theorem statement supplies the assumptions and probability premise for its conclusion.Source: F Proof of Theorem 4 · p. 43
  • The proof writes minimum training loss as a primary min-max optimization using the prediction variable and Lagrange multipliers, then defines a Gaussian auxiliary optimization and truncated versions.The auxiliary problem depends on independent standard Gaussian vectors.Source: F Proof of Theorem 4 · p. 43
  • The Gaussian minimax theorem transfers a tail bound from the primary optimization to the auxiliary one, and the proof rewrites the auxiliary problem to obtain the conclusion.The final equivalence uses the law of a projected predictor plus Gaussian noise under the mapped predictor.Source: F Proof of Theorem 4 · pp. 43–44

F.1 Geometric Interpretation

This section interprets the generalization bound geometrically through a summary functional, deriving a tight constrained-ERM bound from local Gaussian width and establishing convexity properties and results for sqrt-Lipschitz losses and ℓ2 benign overfitting. It also characterizes the maximizer of g over λ ≥ 0 in terms of the ratio a/b.

F.1 Geometric Interpretation

  • For constrained ERM, choosing complexity from the local Gaussian width of the projected set QK yields an essentially tight generalization bound.The projection removes the span on which the true regression function depends.Source: §F.1 · p. 44
  • With local Gaussian-width complexity and the optimal envelope parameter, Theorem 1’s training-error lower bound is tight for constrained ERM, so the bound predicts its actual generalization error.The summary functional ψ captures the lower bound; Theorem 4 establishes tightness, while combining it with Theorem 13 yields the generalization conclusion.Source: §F.1 · p. 45
  • The summary functional ψ is convex in (φ(w), b) when the loss is convex in its prediction and K and B are convex; the finite-sample version may be only approximately convex.The local-width complexity C is concave in φ(w), supporting the convexity result.Source: §F.1 · p. 47
  • In the well-specified example, constrained ERM has excess test loss r(w)=σ²(d/n)/(1−d/n), and the summary functional reduces to that of Zhou et al. (2021) after optimizing over λ.For misspecified models under the general assumptions, the calculation generalizes with w* as the population squared-loss minimizer (the oracle), and excess test loss measured as the gap to w*.Source: §F.1 · p. 48

G.1 Properties of Sqrt-Lipschitz Functions

  • Any H-smooth, nonnegative function is H-sqrt-Lipschitz, and convex L-sqrt-Lipschitz functions are closed under convex combinations.For convex L-sqrt-Lipschitz losses, the paper also derives a deterministic local bound on training loss in terms of predictor displacement.Source: §G.1 · pp. 48–49

G.2 Norm Bounds

  • For squared or squared-hinge loss, under the stated assumptions, with probability at least 1 − δ there is an interpolator with norm at most B, where B² = ||w♯||₂² + (1 + ρ₂)n Tr(Σ⊥)(Lf(w♯, b♯) + ρ₁).The result requires the covariance and probability conditions in the lemma and assumes Qw♯ = 0.Source: §G.2 · p. 49
  • For a,b > 0, g has a unique critical point at 1 + λ = a/b; over λ ≥ 0, its maximum is there if a/b > 1 and at λ = 0 otherwise.The critical point is the global maximum on (−1, ∞).Source: §G.2 · p. 51

G.3 Consistency

The section formalizes bounds for minimum-ℓ2-norm zero-training-error predictors and relates finite-sample conditions to asymptotically negligible error terms.

G.3 Consistency

  • Theorem 3 addresses the minimum-ℓ2-norm predictor with zero training error in the setting of Lemma 2.Source: §G.3 · p. 52
  • Corollary 3 considers sequences of distributions under the model assumptions, with labels depending on kn indices and either squared or squared hinge loss.Source: §G.3 · p. 53
  • The minimum-ℓ2-norm predictor is defined as a zero-training-error predictor minimizing ℓ2 norm, with training error measured on n i.i.d. samples from Dn.Source: §G.3 · p. 53
  • The proof uses asymptotic conditions to make the error term negligible relative to population loss and to send ρ2 and ρ3 to zero.It invokes kn/n → 0 for the error term and Chebyshev’s inequality when taking ρ1 → 0.Source: §G.3 · p. 53

Related papers

Loading 2210.12082v1…