PaperlayerView exact revision on arXiv

Source-linked AI summary

Universality Laws for High-Dimensional Learning with Random Features

Hong Hu, Yue M. Lu

arXiv:2009.07669v3cs.IT

TL;DR

High-dimensional nonlinear random feature models are difficult to analyze because their regressors are non-Gaussian. This paper proves, using Lindeberg interpolation, leave-one-out analysis, and a central limit theorem, that their training and generalization errors are asymptotically equivalent to those of a surrogate linear Gaussian model. The result establishes the Gaussian equivalence conjecture under stated assumptions while leaving extensions beyond odd activations and Gaussian or random feature matrices as scope boundaries.

  • Problem

    Nonlinear random feature regressors prevent direct application of Gaussian analytical tools, especially for non-quadratic losses and regularizers without closed-form solutions.

  • Method

    The proof combines the classical Lindeberg principle with leave-one-out analysis and techniques handling correlations among nonlinear feature regressors.

  • Results

    The paper proves asymptotic equivalence between nonlinear random feature models and surrogate linear Gaussian models in training and generalization errors.

  • Takeaways & Limitations

    Learning performance of high-dimensional random feature models can be characterized through linear Gaussian counterparts that are more amenable to theoretical analysis.

  • Takeaways & Limitations

    The main results assume an odd activation function and Gaussian feature vectors; extensions to broader activations and deterministic matrices remain outside the current proof.

Abstract

from arXiv · show

We prove a universality theorem for learning with random features. Our result shows that, in terms of training and generalization errors, a random feature model with a nonlinear activation function is asymptotically equivalent to a surrogate linear Gaussian model with a matching covariance matrix. This settles a so-called Gaussian equivalence conjecture based on which several recent papers develop their results. Our method for proving the universality theorem builds on the classical Lindeberg approach. Major ingredients of the proof include a leave-one-out analysis for the optimization problem associated with the training process and a central limit theorem, obtained via Stein's method, for weakly correlated random variables.

I. INTRODUCTION

The paper studies high-dimensional random feature models, whose nonlinear regressors complicate analysis, and proves their asymptotic equivalence to a surrogate linear Gaussian model for training and generalization errors.

  • Model setting: Random feature models use nonlinear activations applied to fixed random first-layer features, with learning performed through the second-layer weights.This setup can also be viewed as a two-layer neural network with a fixed first layer.
  • Motivation: Nonlinear regressors prevent direct use of analytical tools developed for Gaussian vectors, especially beyond quadratic losses and regularizers with closed-form solutions.This motivates replacing the nonlinear feature model with a tractable Gaussian surrogate.
  • Gaussian equivalence: The Gaussian equivalence conjecture states that the nonlinear and linear Gaussian models have asymptotically matching training and generalization errors as p →∞.The surrogate uses Gaussian regressors with parameters defined from the nonlinear model.
  • Evidence: Numerical experiments show close training and generalization errors for nonlinear and Gaussian models in both regression and binary classification.The experiments use ReLU with quadratic loss for regression and tanh with logistic loss for classification, with d = 200 and n = 600.
  • Main contribution: The paper proves the Gaussian equivalence conjecture under stated assumptions, with Theorem 1 and related results establishing asymptotic agreement for the models.A special case with τ1 = τ2 = 0 gives the same asymptotic limit for the training errors.
  • Scope: The analysis assumes an odd activation and Gaussian feature vectors, although the authors expect extensions to more general activations and sub-Gaussian or deterministic feature matrices.The odd-activation assumption implies µ0 = 0, while ReLU is shown numerically to exhibit the phenomenon.

D. Related Work

The paper situates its universality proof within prior Gaussian-equivalence and central-limit results, then develops a Lindeberg and leave-one-out strategy to overcome correlated random-feature regressors. The proof interpolates between nonlinear and Gaussian models and controls each replacement uniformly over admissible feature matrices.

  • Prior work and gap: Prior work established Gaussian-equivalence conjectures and central-limit results, but those results did not by themselves control optimization-defined training and generalization errors.The unresolved challenge involves comparing statistics associated with different optimized weight vectors.
  • Proof strategy: The proof uses Lindeberg’s principle and leave-one-out analysis to compare nonlinear and Gaussian random-feature models despite correlated regression-vector entries.The interpolation replaces regressors one at a time, while leave-one-out problems isolate each replacement.
  • Related techniques: The paper also uses Stein’s method to provide an alternative proof of the central limit theorem for the nonlinear feature model.Technical details are deferred to the appendices, while the main text emphasizes central ideas and intermediate results.
  • Admissible feature matrices: The analysis defines an admissible set of feature matrices and reduces the proof to establishing the interpolation bound and showing its complement has probability O(polylog p/√p).The admissible-set construction includes high-probability events controlling the relevant optimization quantities.
  • Proof strategy: The interpolation path starts at ΦA and ends at ΦB, so uniformly small neighboring differences yield the target comparison by the triangle inequality.There are n = O(p) pairwise comparisons, and the resulting bound is uniform over F ∈ A and k ∈ [n].

D. Proof of Theorem 1

The proof constructs a suitable test function and applies the main theorem to establish the desired asymptotic characterization. Figure 2 illustrates that the empirical distributions are generally non-Gaussian, while Lemmas 15 and 16 provide the correct limiting distributions.

  • A suitable test function is constructed to complete the proof after applying the preceding result.
  • Figure 2 compares empirical distributions across three values of λ for fixed d = 600, p = 900, and n = 1800.
  • The empirical distributions are not Gaussian, with the discrepancy becoming more noticeable as λ decreases.
  • Lemmas 15 and 16 yield the correct limit distributions shown in Figure 2.
  • The proof obtains the stated conclusion for ε ∈ (0, 1) and p ≥ 1/ε^2, with the analogous argument applying symmetrically to ΦA and ΦB.

E. Proof of Proposition 1

The proposition is proved in three parts: Gaussian-model quantities converge to deterministic limits, the nonlinear model has the same limits by universality, and its generalization error is characterized through a Gaussian comparison function. The proof combines Gaussian representations, continuity, and a leave-one-out-based central limit theorem.

  • Part (a): The Gaussian generalization error is represented by G(ρB, πB), because the relevant variables are jointly Gaussian and determined by their covariance matrix.
  • Part (a): The Gaussian-model parameters ρB and πB converge to derivatives of the limit function q∗ at the origin.
  • Part (b): The nonlinear-model parameters ρA and πA have the same limits as ρB and πB by the universality laws of Theorem 1.
  • Part (c): The nonlinear generalization error converges to G(ρA, πA) with high probability after applying the central limit theorem and controlling exceptional events.
  • Part (c): The central limit theorem applies to weakly correlated nonlinear features under assumptions on feature vectors, activations, and differentiable test functions.
  • Part (c): The proof requires bounding the leave-one-out optimal solution in ℓ∞, which is identified as a nontrivial challenge.

A. A Reduced Form of Theorem 2

The reduced theorem proves that a nonlinear feature inner product is asymptotically Gaussian by comparing it with a Gaussian surrogate. Stein’s method reduces the claim to controlling mean, variance, Taylor-remainder, and derivative terms.

  • The reduced theorem characterizes aTβ/√p through a Gaussian comparison involving bTβ/√p and a test function.
  • The reduced result imposes stronger conditions than the full theorem, including compact support for σp and boundedness for the test function and its derivatives.
  • The proof uses Stein’s method and a Stein transform to compare the nonlinear quantity with its Gaussian counterpart.
  • The main error decomposition separates terms whose control reduces to showing Eχ → 1 and var(χ) → 0.
  • Taylor expansions, compact support, bounded derivatives, and feature-correlation bounds control the remainder terms.
  • Gaussian Poincaré inequalities bound the variance of the auxiliary gradient function Γ(g).

B. Joint Distributions

The joint-distribution result extends the one-dimensional Gaussian approximation to the pair involving the nonlinear feature statistic and the teacher projection. Conditioning creates an independence structure that permits reuse of the reduced theorem.

  • The one-dimensional Gaussian limit extends to joint Gaussianity of aTβ/√p and gTξ.
  • The proof rewrites the correlated Gaussian variables using an independent scalar s and Gaussian vector eg.
  • This representation makes egTefi independent of s, allowing expectations to be computed by conditioning on s.
  • Taylor expansion of the activation separates the principal term from remainder terms involving Δ1 and Δ2.
  • The argument uses bounded derivatives and Gaussian Poincaré control to show the additional terms are small.
  • The reduced theorem is applied conditionally to the projected feature vectors after verifying that they retain the required feature bounds.

C. Proof of Theorem 2

The proof extends the central-limit characterization from truncated, smooth functions to broader activations and test functions, using truncation and smoothing while controlling approximation errors. It also identifies technical assumptions and unresolved extensions involving feature matrices, losses, and activations.

  • Removing smoothness and support assumptions: The proof removes compact-support and bounded-derivative assumptions through standard truncation, preserving the central-limit characterization.The truncation argument relaxes both restrictions simultaneously.
  • Removing smoothness and support assumptions: O(polylog p/√p) is the approximation cost of replacing the original test function with a smoothly truncated version.The same truncation strategy is applied to the activation function.
  • Covariance comparison: The resulting covariance comparison reaches Theorem 2's bound using Lemma 3 and |µ2 − µ2,p| ≤ polylog p/√p.The proof combines the truncated-function estimate with the discrepancy between the corresponding constants.
  • Piecewise smooth test functions: Piecewise differentiable test functions are handled by smoothing around finitely many nondifferentiable points, enabling applications where the output function is nonsmooth.This extension is needed for generalization errors using functions such as sign(y).
  • Assumptions and rates: The proof assumes κp ≤ polylog p, ∥β∥∞ ≤ polylog p, and ν2 ≥ c > 0, while higher moments could improve the convergence rate.The stated rate can improve from O(p^-1/8 polylog p) to O(p^-1/4 polylog p) under stronger moment assumptions.
  • Scope and extensions: The theorem currently assumes differentiable losses and odd activations, although smoothing can extend the analysis to hinge loss and non-differentiable activations or regularizers.For hinge loss, smoothing yields convergence at a slower rate than the differentiable setting.
  • Scope and extensions: A remaining challenge is proving the needed ℓ∞ bound for optimal weights with deterministic feature matrices satisfying the admissibility conditions.The bound is required by the central limit theorem.

APPENDIX

The appendix develops mollification, truncation, covariance comparison, and concentration tools used throughout the proof. These tools control approximation errors and establish the Gaussian and covariance estimates needed for universality.

  • Smoothing and truncation: A compactly supported mollifier produces smooth approximations of piecewise-smooth functions, while a smoothed window equals one inside a threshold region and vanishes outside an expanded region.The transition band preserves values between zero and one.
  • Smoothing and truncation: The truncation event has probability at least 1 − 2p^-CT/C, allowing the proof to replace unbounded functions by controlled approximations.A sufficiently large CT makes the exceptional event sufficiently rare.
  • Piecewise differentiable functions: Choosing δp = p^-1/4 optimizes the smoothing error and yields the stated convergence rate for piecewise differentiable test functions.The smoothed function has derivative bounded by C/δp.
  • Covariance comparison: The appendix compares the nonlinear covariance matrix with its Gaussian surrogate by decomposing entrywise Taylor errors and bounding the resulting matrix terms.The bounds combine feature-vector assumptions, Gaussian tails, and remainder control.
  • Covariance comparison: For smoothly truncated activations, the covariance discrepancy is controlled at a polylogarithmic-over-√p scale.The proof bounds the decomposition terms and substitutes them into the covariance estimate.

E. Some Concentration Results

This section establishes concentration and moment bounds for Gaussian and nonlinear random-feature quantities, often conditional on a fixed admissible feature matrix. These estimates support later leave-one-out and optimization arguments.

  • Gaussian concentration: Gaussian concentration for Lipschitz functions supplies tail and moment bounds for feature responses, Gaussian surrogate variables, and linear forms.The relevant Lipschitz constants depend on ∥σ′∥∞, ∥F∥, and ∥β∥.
  • Uniform auxiliary bounds: The concentration estimates apply to both nonlinear regressors and Gaussian surrogates, enabling uniform control of the auxiliary quantities used in the proof.The bounds are derived for fixed admissible feature matrices.
  • Random-feature concentration: The nonlinear regressors inherit concentration because g ↦ σ(F^Tg) and g ↦ ∥σ(F^Tg)∥ are Lipschitz when σ has bounded derivative.These bounds yield moment estimates used throughout the proof.
  • Leave-one-out quantities: Conditioned on the feature matrix, leave-one-out Hessian quantities concentrate using independence of the omitted regressor and strong convexity.The Hessian inverse is controlled through the regularization lower bound.

3) The Spectral Norm of Random Matrices:

The appendix bounds spectral norms and analyzes the original, leave-one-out, and quadratic-approximation optimization problems. Strong convexity and concentration connect these auxiliary problems to the theorem's asymptotic analysis.

  • Spectral norm bounds: Spectral norms of the nonlinear and Gaussian design matrices are bounded with high probability using ε-nets and sub-Gaussian concentration.The argument reduces operator-norm control to finitely many bilinear forms.
  • Optimization problems: The optimization analysis distinguishes the original, leave-one-out, and quadratic-approximation problems used along the Lindeberg interpolation path.The leave-one-out problem replaces one regressor, while the quadratic approximation enables closed-form analysis.
  • Quadratic approximation: The quadratic approximation is expressed through Moreau envelopes, proximal operators, and leave-one-out quadratic terms.These representations provide tractable formulas for the approximate optimizer and objective.
  • Quadratic approximation: Strong convexity converts gradient control into distance bounds between the true optimizer and the quadratic-approximation optimizer.The proof uses the optimality condition of the true solution and controls the approximate gradient.
  • Optimizer bounds: The appendix derives probabilistic bounds on optimal weights and scalar leave-one-out terms under the admissible feature-matrix conditions.The bounds rely on strong convexity, Gaussian concentration, and moment estimates.

5) The ℓ∞Boundedness of Optimal Solutions:

The proof bounds the optimal solution by reducing to a single coordinate, controlling it through strong convexity and Gaussian concentration, and then using symmetry and a union bound to obtain an ℓ∞ bound with high probability.

  • Coordinate reduction: The argument studies a (p+1)-dimensional problem and focuses without loss of generality on the last coordinate u∗ of the optimal solution.The added feature column is denoted f_{p+1}; symmetry later extends the coordinatewise bound to the full vector.
  • High-probability events: The required intermediate conditions hold with probability at least 1−2e^(−cp), while additional terms are bounded with high probability.Several bounds are established by conditioning on high-probability events and applying Gaussian tail estimates.
  • Objective control: Strong convexity of G and h supplies lower bounds for the objective, which are combined with the first-order optimality condition to control u∗.The proof also uses the constraint on τ_1 and compares the optimum with L(0).
  • Concentration bounds: Gaussian and conditional concentration bounds control the stochastic terms appearing in the objective comparison, including √p ξ^T f_{p+1} and f^T⋅.The proof separately treats terms indexed by t and uses independence of f_{p+1} from the relevant optimizer quantities.
  • From coordinates to ℓ∞: A union bound converts the coordinatewise estimate into an ℓ∞ bound because all coordinates of the optimal vector have the same marginal distribution.The resulting probability estimate is adjusted for sufficiently large p using a logarithmic-exponential tail bound.

6) Proof of Proposition 2:

The proof of Proposition 2 establishes the required high-probability event by intersecting previously defined events and then applying a union bound over k.

  • Event construction: For each k, the proof defines a set of feature matrices whose membership is sufficient to establish the desired event A_{3,k}.The argument begins from the set A_2 and introduces B_k before showing A_2∩B_k⊂A_{3,k}.
  • Probability control: The probability of A_{3,k} is controlled by combining the bounds for A_2 and B_k, yielding a logarithmic-exponential failure probability uniformly over k.The proof chooses constants large enough to absorb the resulting probability bound.
  • Conclusion: Applying the union bound over k completes the proof of the proposition.

7) Proof of Lemma 1:

The proof of Lemma 1 compares leave-one-out and full optimization quantities, expands the relevant remainder, and controls the resulting expectations using concentration, inverse-Hessian bounds, and moment estimates.

  • Optimization comparison: The proof compares optimal solutions associated with Φ_k(r) and Ψ_k(r), taking r to be either a_k or b_k.This comparison is used to establish the first claimed bound of the lemma.
  • Remainder expansion: Taylor expansion expresses the remainder R_k(w;r) through intermediate points between the reference and optimal coordinates.The expansion is combined with the definitions of S_k(w;r) and L_S.
  • Expectation bounds: The proof bounds each expectation in the resulting decomposition using concentration inequalities and moment estimates for the leave-one-out terms.These estimates include polynomial-in-log p bounds and powers of p for terms indexed by t≠k.
  • Matrix control: Inverse-Hessian control provides uniform bounds on H^{-1}_k and its columns, which are then inserted into the expectation estimates.For F∈A, the proof uses ∥H^{-1}_k∥≤2/λ and derives corresponding column bounds.
  • Conclusion: Combining the component bounds yields the stated claim of Lemma 1.

8) Two Auxiliary Lemmas for Proving Theorem 1:

The auxiliary lemmas establish polylogarithmic-over-square-root-p bounds and finite-moment controls needed for the main theorem’s proof.

  • Bounds on Δ_1 and Δ_2: Lemma 24 bounds Δ_1 by polylog p/√p and obtains an analogous bound for Δ_2.The Δ_2 estimate is concluded after controlling the terms in its decomposition and applying the cited inequalities.
  • Role in the theorem: The resulting estimates support the auxiliary claims used in proving Theorem 1.
  • Moment control: Lemma 25 constructs a function B(s) whose fourth moment under a standard normal input is finite and uses it to establish the required bound uniformly over k.The construction takes B as the maximum of two auxiliary functions with finite fourth moments.
  • Proof ingredients: The proof of the auxiliary bounds relies on the proximal operator, loss-function inequalities, Gaussian concentration, and Assumption (A.4).These ingredients control the terms involving γ_k, z, and the associated derivatives.
Loading 2009.07669v3…