Limitations of Lazy Training of Two-layers Neural Networks

Behrooz Ghorbani; Song Mei; Theodor Misiakiewicz; Andrea Montanari

Source-linked AI summary

Limitations of Lazy Training of Two-layers Neural Networks

Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, Andrea Montanari

arXiv:1906.08899v1Jun 21, 2019stat.MLcs.LGmath.ST

TL;DR

The paper asks how efficiently neural networks can learn functions beyond the tractable random-feature and neural-tangent approximations. It analyzes quadratic and Gaussian-mixture models across RF, NT, and fully trained NN regimes, finding a potentially unbounded risk gap below the dimension threshold and vanishing NT and NN risk above it for quadratic targets.

Problem
The paper investigates which functions can be learned efficiently by neural networks and whether RF and NT adequately describe that learnable class.
Method
The paper compares random features, neural tangent linearization, and fully trained two-layer networks with quadratic activations on quadratic-function and Gaussian-mixture models.
Results
For quadratic targets with N<d, the three regimes can have a potentially unbounded prediction-risk gap; for N>d, NT and NN achieve vanishing risk.
Takeaways & Limitations
Full training can learn principal eigendirections and outperform RF and NT, which remain limited by fixed or random representations.
Takeaways & Limitations
The NT–NN separation is established only for N≤d, and NN SGD convergence is not proved for the Gaussian-mixture model.

Abstract

from arXiv · show

We study the supervised learning problem under either of the following two models: (1) Feature vectors ${\boldsymbol x}_i$ are $d$-dimensional Gaussians and responses are $y_i = f_*({\boldsymbol x}_i)$ for $f_*$ an unknown quadratic function; (2) Feature vectors ${\boldsymbol x}_i$ are distributed as a mixture of two $d$-dimensional centered Gaussians, and $y_i$'s are the corresponding class labels. We use two-layers neural networks with quadratic activations, and compare three different learning regimes: the random features (RF) regime in which we only train the second-layer weights; the neural tangent (NT) regime in which we train a linearization of the neural network around its initialization; the fully trained neural network (NN) regime in which we train all the weights in the network. We prove that, even for the simple quadratic model of point (1), there is a potentially unbounded gap between the prediction risk achieved in these three training regimes, when the number of neurons is smaller than the ambient dimension. When the number of neurons is larger than the number of dimensions, the problem is significantly easier and both NT and NN learning achieve zero risk.

1 Introduction

The paper asks which functions neural networks can learn efficiently and compares random-feature, neural-tangent, and fully trained regimes on quadratic and Gaussian-mixture problems. It finds that full training can substantially outperform linearized approaches when the neuron count is below dimension, while NT and NN achieve vanishing risk above dimension for quadratic targets.

1 Introduction: RF and NT are tractable finite-dimensional inner bounds of fully trained neural networks, obtained by fixing or linearizing first-layer weights.RF and NT optimize over linear spaces, whereas NN trains all weights.
1 Introduction: The paper studies which subset of functions can be learned efficiently by neural networks using stochastic gradient descent, focusing on quadratic functions and mixtures of Gaussians.The supervised-learning objective is to minimize prediction risk for an unknown target function.
1.1 Summary of main results: For N>d, both neural tangent and fully trained networks achieve vanishing risk on quadratic functions, while RF risk remains bounded away from zero at finite N/d.RF does not capture quadratic functions effectively unless N/d tends to infinity.
1.1 Summary of main results: For quadratic targets with N/d below one, RF and NT retain nonzero risk, whereas fully trained networks achieve strictly lower risk by fitting principal eigendirections.The NN improvement is quantified by a positive GAP(ρ) relative to NT.
1.1 Summary of main results: The results suggest that neural networks can outperform linearized models because full training learns a data-aligned representation rather than remaining confined to random directions.The paper explicitly limits the demonstrated NT–NN separation to N≤d and presents broader extensions as expectations or partial evidence.
1.1 Summary of main results: The study establishes analogous RF and NT behavior for Gaussian mixtures but does not prove an NN stochastic-gradient-descent convergence result in that model.It does show that the minimum NN prediction risk is strictly smaller than the minima achieved by RF and NT.

2 Main results: quadratic functions

For quadratic targets with Gaussian features, the paper derives asymptotic risks for random features, neural tangent, and fully trained networks, showing that NT becomes exact when N ≥ d while NN can outperform it for N < d.

2 Main results: quadratic functions: The results analyze Gaussian quadratic targets with quadratic activations in the high-dimensional limit N, d →∞ with N/d →ρ.The RF and NT analyses use random first-layer weights, while the NN analysis considers SGD and B ⪰ 0.
2.1 Random features: RF risk can remain bounded away from zero even as N/d diverges, unless the feature covariance Γ is aligned with the target matrix B.For isotropic features, the asymptotic risk depends on the spectral structure of B and can be no better than the trivial predictor in a trace-zero case.
2.3 Neural network: NN risk is characterized after one-pass SGD, where the number of SGD steps also equals the sample size and the reported error is test prediction risk.The theorem averages over initialization and samples and orders the target directions through the eigenvalues of B.
2.3 Neural network: The neural-network population-risk landscape is strict saddle on every sub-level set under the stated quadratic, positive-semidefinite assumptions.Near points with small gradient, the Hessian has a strictly negative minimum eigenvalue.
2.3 Neural network: NN learns the most important eigendirections of the quadratic target, whereas RF and NT do not.The comparison is made for positive-semidefinite target matrices B and quadratic activations.

3 Main results: mixture of Gaussians

In the mixture-of-Gaussians model, the paper characterizes prediction risk for RF, NT, and NN regimes under spectral assumptions and compares them with simulations. NT and NN do not achieve Bayes error even for very wide networks.

The model assigns equal class probabilities and uses centered Gaussians with covariances Σ − ∆ and Σ + ∆.
The mixture assumptions bound Σ between positive multiples of the identity and scale ∆ so the signal-to-noise ratio remains order one.If ∆ is too large, the classes become asymptotically mutually singular; if its operator norm is o(1/sqrt(d)), no non-trivial classifier exists.
Even when N/d is much larger than one, neither NT nor NN achieves the Bayes error in the mixture-of-Gaussians model.
Random features: For RF, the asymptotic risk is expressed through ζ1(d), ζ2(d), the quadratic activation’s Hermite coefficient, and the neuron-to-dimension ratio.
For NT and NN, theorems characterize risk under general covariance and Gaussian initialization, with a special asymptotic statement when Σ = I and N/d tends to ρ.
Comparison of regimes: Across the three regimes, NN learns the most important directions of ∆, whereas RF and NT do not.

4 Numerical Experiments

The experiments evaluate analytical predictions and empirical risks for quadratic-activation networks across RF, NT, and NN settings. They use high-dimensional synthetic problems, Gaussian initializations, and SGD-based training for NT and NN.

Experiments use d = 450 and N from 45 to 4500, with NT and NN trained by SGD and RF fitted directly.The reported training uses 2.0 × 10^5 steps for quadratic-function models and 1.4 × 10^5 steps for mixture-of-Gaussians models.
The experiments compare analytical predictions with empirical results under the specified synthetic settings and SGD procedures.
The quadratic-function experiments choose diagonal B with independent standard-exponential diagonal entries, while mixture experiments use diagonal ∆ with specified random diagonal elements.
Random features: The RF risk is obtained by solving the second-layer optimization through its KKT conditions, yielding a = U^-1V.
The analysis uses Hermite expansions of the activation and concentration arguments for Gaussian weight matrices to control the relevant risk terms.
Neural tangent and neural network: The NT and NN analyses compare risks using Gaussian projections, matrix decompositions, and asymptotic bounds as N/d approaches ρ.

B.1.4 Calculating 1TU −1

This appendix section derives asymptotic control of the quantity 1^T U^-1 1 using covariance approximations, concentration, and random-matrix arguments. The proof combines several lemmas covering discretized spectra and Gaussian quadratic forms.

The proof reduces the target expression to a sequence of lemmas controlling covariance block approximations, inverse matrices, and Gaussian quadratic forms.
The covariance is first handled under a finite-block spectral decomposition, then extended to a continuous limiting spectrum by eigenvalue binning.
The final argument combines bounds on auxiliary matrices and spectral transforms to establish the desired asymptotic expression.
The matrix U^0 is decomposed as A^0 + zz^T + μμ^T, after which the Sherman-Morrison-Woodbury formula relates U^0^-1 to A^0^-1.
Concentration and Hanson-Wright bounds show that the relevant deviations vanish exponentially fast in N and d.

B.2 Neural Tangent model: proof of Theorem 2

The neural-tangent proof rewrites the quadratic-activation model in a basis aligned with the random weights and evaluates the resulting Gaussian projection terms. The analysis distinguishes the cases N ≥ d and N < d.

The NT model with σ(x) = x^2 is rewritten using the weight matrix W and coefficient matrix A, then analyzed through the singular-value decomposition of W.
When N ≥ d, the weight span can cover the full feature space, whereas N < d requires separating components inside and orthogonal to that span.
The proof evaluates moments of coordinates of uniform spherical vectors and their conditional projections onto orthogonal complements.
Cross-moment calculations and dominated-convergence arguments provide the limits needed to assemble the NT risk expression.
The resulting comparison supports the broader conclusion that NN learns the most important directions of the quadratic target, unlike RF and NT.

B.3.2 Landscape: proof of Proposition 1

The section characterizes the critical-point landscape of L(W, c) and shows that every nonglobal critical point is a strict saddle. Consequently, gradient-based dynamics avoid nonglobal stationary points for almost every initialization.

Risk geometry: The risk admits an explicit expansion in c and W through traces and the discrepancy W W^T − B.The gradient and Hessian calculations use this representation to identify negative-curvature directions at nonglobal critical points.
Critical-point landscape: Critical points align W_0W_0^T with selected eigendirections of the positive-semidefinite matrix B.The active directions correspond to eigenvectors of B, with the relevant singular-value structure determined by the stationary conditions.
Critical-point landscape: Every stationary point that is not a global minimizer is a strict saddle point.This is established by analyzing the Hessian in rank-deficient and eigenvalue-misaligned cases.
Gradient dynamics: The set of initializations whose gradient flow converges to a strict saddle has Lebesgue measure zero.The proof applies stable-manifold arguments on compact sublevel sets and then takes a countable union over bounded regions.

B.3.4 Proof of Theorem 3

The proof connects gradient-flow convergence with stochastic-gradient dynamics for the analytic risk. With absolutely continuous initialization, the limiting solution is a global minimizer, and suitably scaled SGD tracks the flow over finite horizons.

Gradient-flow convergence: With an absolutely continuous random initialization, gradient flow converges almost surely to a global minimizer of L(W, c).This follows because all nonglobal critical points are strict saddles and strict-saddle convergence occurs only from a measure-zero set.
SGD approximation: The SGD iterates are identified with the jump process at its jump times.The jump direction is given by a stochastic gradient step, linking the discrete algorithm to the continuous-time process.
SGD approximation: As the step-scale parameter tends to zero, suitably rescaled SGD remains uniformly close to the gradient-flow trajectory over every fixed finite horizon.The approximation is stated for arbitrary fixed T > 0 and δ > 0.

C.1 Random Features model: proof of Theorem 4

The random-features proof analyzes the optimized second-layer problem through kernel-like matrices and asymptotic concentration under the Gaussian-mixture model. Several interpolation and concentration bounds control the resulting risk expression as N/d approaches a fixed ratio.

RF optimization: The RF optimum is obtained by solving the KKT conditions, yielding second-layer weights a = U^-1V.The risk is thereby represented using the matrices U and V induced by the random features.
Asymptotic analysis: As N/d = ρ and d →∞, the random-feature matrix quantities concentrate around their asymptotic forms under the stated assumptions.The proof uses Hermite coefficients, Gaussian transformations, and bounds on centered quadratic forms.
Asymptotic analysis: The proof bounds differences among three interpolating variables and combines the resulting estimates to obtain the desired RF asymptotics.The comparisons use high-probability bounds, expectation estimates, and dominated-convergence arguments.

C.1.4 Proof of Theorem 4

This proof reduces the optimized RF risk to a formula involving Γ, Σ, and Δ, then uses the model assumptions to control the signal-dependent correction. The resulting bound shows that this correction is asymptotically negligible under the stated scaling.

Risk optimization: The proof substitutes the RF representation and asymptotic estimates from the preceding lemmas into the risk expression.Proposition 2 and the two lemmas provide the quantities used in the final comparison.
Risk optimization: After optimizing over a and c with Γ fixed, the risk equals 2^2 + ⟨Γ, Δ⟩^2/[Tr(ΓΣΓΣ) + Tr(ΓΔΓΔ)].This formula is obtained by successive minimization over the second-layer coefficient and offset.
Final bound: Under M1 and M2, the correction term is bounded using Σ ⪰ cI_d and ∥Δ∥op ≤ C/√d, yielding o_d(1).The final bound is obtained from 1 + C^2/(dc^2) raised to the inverse-power form shown in the proof.

C.2.2 Proof of Theorem 5

The proof analyzes the NT model separately for neuron-to-dimension ratios above and below one, reducing optimization to a matrix problem and deriving a high-probability risk formula. For N<d, the optimum is characterized through the leading singular directions of the target matrix.

Matrix reduction: The NT optimization is reduced, via the SVD of W, to an equivalent optimization over G when W has rank min(d,N) almost surely.The reduction uses W=P_1SV^T and G=SV^TA.
Case split: When N≥d, the minimizer is G=∆, while N<d requires maximizing a trace expression over the lower-dimensional parameterization.The proof treats the two regimes separately according to N/d→ρ.
Case N/d<1: For N<d, the constrained optimization is rewritten as a convex problem in the P=[P_1,P_2] basis and solved through a Lagrangian.The variables are decomposed into G_1=GP_1 and G_2=GP_2.
Optimizer characterization: The stationary condition and substitutions identify the symmetric optimizer and its associated minimizer for the NT objective.The proof proceeds by imposing the stationary condition, rewriting the constraint in the P basis, and substituting the resulting expressions.
Risk bound: A gradient bound combined with concentration on the Stiefel manifold yields the final high-probability risk formula for the NT model.The displayed bound controls the gradient using operator and Frobenius norms of ∆.

C.3 Neural Network model: proof of Theorem 6

The neural-network proof rewrites the quadratic two-layer model as a rank-constrained optimization over symmetric matrices. Cauchy–Schwarz reduces the solution to choosing eigendirections associated with the largest singular values of ∆.

Model parameters: The network risk is optimized jointly over neuron coefficients, weights, and the offset c.The risk function is defined for the complete parameter set and optimized over (a_i,w_i) and c.
Neural network reformulation: The fully trained quadratic network induces a symmetric matrix Γ=WAW^T whose rank is at most min(N,d), so risk minimization becomes a rank-constrained matrix problem.The proof assumes Σ=Id after rescaling and defines Γ through the neuron weights and coefficients.
Optimization: Cauchy–Schwarz characterizes the optimal eigenvalues of Γ as the diagonal of U^T∆U for an eigendecomposition Γ=USU^T.Equality holds when S*=ddiag(U^T∆U).
Subspace selection: The remaining problem selects r orthonormal columns of U to maximize the squared norm of ddiag(U^T∆U).Here r=min(N,d), inherited from the rank constraint.
Optimal directions: The maximizing directions are the eigendirections corresponding to the r largest singular values of ∆.The optimum is expressed using the singular values λ_i in descending order.