PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep learning: a statistical viewpoint

Peter L. Bartlett, Andrea Montanari, Alexander Rakhlin

arXiv:2103.09177v1math.STcs.LGstat.ML

TL;DR

Deep learning predicts well despite near-perfect fits to noisy data and no explicit complexity control, leaving important theoretical gaps. This review surveys theory on interpolation in linear-feature settings and reports that model complexity in random-feature and neural-tangent models grows with sample size but saturates at the number of network parameters.

  • Problem

    Theoretical accounts remain incomplete for why deep networks predict well despite near-perfect noisy-data fits without explicit complexity control.

    Source: §1 · p. 3

  • Method

    The review examines when interpolation can be near-optimal with noisy data, focusing on models linear in data-independent feature spaces.

    Source: §7 · p. 51

  • Results

    In random-feature and neural-tangent models, the simple model's complexity grows with sample size but saturates at the number of network parameters.

    Source: §7 · p. 53

  • Takeaways & Limitations

    Overparametrization is motivated primarily by computation, with empirical evidence indicating that it can make global optimization tractable.

    Source: §7 · p. 53

    Some analyses assume isotropic covariates, so the ambient dimension matches the data's intrinsic dimension.

    Source: §6.2 · p. 43

Abstract

from arXiv · show

The remarkable practical success of deep learning has revealed some major surprises from a theoretical perspective. In particular, simple gradient methods easily find near-optimal solutions to non-convex optimization problems, and despite giving a near-perfect fit to training data without any explicit effort to control model complexity, these methods exhibit excellent predictive accuracy. We conjecture that specific principles underlie these phenomena: that overparametrization allows gradient methods to find interpolating solutions, that these methods implicitly impose regularization, and that overparametrization leads to benign overfitting. We survey recent theoretical progress that provides examples illustrating these principles in simpler settings. We first review classical uniform convergence results and why they fall short of explaining aspects of the behavior of deep learning methods. We give examples of implicit regularization in simple settings, where gradient methods lead to minimal norm functions that perfectly fit the training data. Then we review prediction methods that exhibit benign overfitting, focusing on regression problems with quadratic loss. For these methods, we can decompose the prediction rule into a simple component that is useful for prediction and a spiky component that is useful for overfitting but, in a favorable setting, does not harm prediction accuracy. We focus specifically on the linear regime for neural networks, where the network can be approximated by a linear model. In this regime, we demonstrate the success of gradient flow, and we consider benign overfitting with two-layer networks, giving an exact asymptotic analysis that precisely demonstrates the impact of overparametrization. We conclude by highlighting the key challenges that arise in extending these insights to realistic deep learning settings.

1 Introduction

The paper surveys early theoretical explanations for deep learning’s ability to optimize overparameterized models and generalize despite fitting noisy training data. It examines implicit regularization and benign overfitting in simpler settings, then highlights open challenges in extending these insights to realistic deep learning.

1 Introduction

  • The paper frames two puzzles: overparameterization may make non-convex optimization tractable, while implicit regularization and benign overfitting may allow interpolating models to predict well.The authors conjecture that sufficient overparameterization makes optimization under-constrained, and that interpolating models can combine a low-complexity predictive component with a high-complexity fitting component that does not significantly harm accuracy.Source: §1 · pp. 3–4
  • The reviewed results do not establish optimization or generalization benefits from increasing network depth, though depth may aid expressive, parsimonious representations of natural functions.Extending the specific theoretical results to realistic deep learning remains an open challenge.Source: §1 · p. 4

1.1 Overview

  • Classical uniform-convergence bounds explain generalization for complexity-controlled classes but face specific barriers when analyzing interpolating predictors.The overview reviews risk-versus-empirical-risk bounds, complexity hierarchies, and applications to classification, large-margin classification, regression, and feed-forward networks; analyzing benign overfitting requires stronger assumptions about data generation.Source: §1.1 · p. 4
  • In examples with linear parameterizations and convex losses, suitably initialized gradient methods return empirical-risk minimizers with minimal parameter norms.The paper also connects this linear/convex perspective to non-convex optimization problems in neural networks.Source: §1.1 · pp. 4–5
  • Benign overfitting examples decompose interpolating predictors into a useful simple component and a spiky fitting component that can be harmless for prediction.For high-dimensional linear regression, the split follows covariance eigenvalues: benign overfitting occurs when the high-variance subspace is low-dimensional and the low-variance subspace has high effective dimension and suitably low energy. Related RKHS examples show that it may fail at fixed input dimension or occur as input dimension increases; singular-kernel smoothing can also interpolate while attaining minimax rates with a suitable bandwidth.Source: §1.1 · p. 5
  • In a neural-network linear regime, suitable parameterization and initialization let gradient methods stay near the linearization, converge linearly in empirical risk, and produce predictions approximated by that linearization.For two-layer networks, sufficiently large overparameterization and initialization suffice; the mean-field limit with smaller initialization behaves essentially differently.Source: §1.1 · p. 5
  • For random-features and neural-tangent two-layer models, low-degree polynomial components predict while orthogonal complex components permit interpolation without significantly harming accuracy.The random-features model keeps randomly initialized first-layer parameters fixed, whereas the neural-tangent model corresponds to linearization about a random initialization.Source: §1.1 · p. 5
  • The review identifies mechanisms, dimensionality, prediction–overfitting decompositions, data-adaptive decompositions, and overparameterization’s tractability benefits as directions for future work.It considers how these insights might extend to realistic deep learning settings.Source: §1 · p. 4, §1.1 · p. 6

2 Generalization and uniform convergence … 2.4 Complexity regularization

The section develops a prediction-focused account under weak assumptions on the data, using uniform convergence to control estimation error and complexity regularization to balance fit against model complexity. It also explains when faster rates are possible and how complexity hierarchies yield oracle guarantees.

2.1 Preliminaries

  • With only i.i.d. data assumed, excess risk separates into approximation error and estimation error, which trade off as the function class becomes more complex.The prediction goal is to perform well on future examples without assuming a functional relationship between inputs and outputs.Source: §2.1 · pp. 6–7

2.2 Uniform laws of large numbers

  • Uniform deviation bounds control empirical-risk estimation despite its data-dependent selection, with Rademacher complexity measuring the loss class’s contribution to the bound.The empirical risk of the selected predictor is a biased estimate of its true risk, so a uniform bound over the class is used.Source: §2.2 · pp. 7–8

2.3 Faster rates

  • For bounded losses, the classical worst-case Rademacher bound cannot improve faster than n^-1/2 when loss variance is positive, even if the empirical minimizer can converge faster.This limitation motivates conditions and bounds beyond the general uniform-deviation approach.Source: §2.3 · p. 8
  • When a bounded quadratic-loss problem has a perfect predictor in the class, a sufficiently simple class can yield risk of ˜O(1/n) for an empirical minimizer with zero training loss.The faster-rate result relies on quadratic-loss smoothness and is related to variance conditions such as the Bernstein property.Source: §2.3 · p. 8

2.4 Complexity regularization

  • Complexity regularization selects among nested classes to balance empirical fit and complexity, as in SVMs with RKHS-norm classes and Lasso with ℓ1-norm classes.Choosing class complexity from the data manages the approximation-estimation tradeoff.Source: §2.4 · p. 9
  • Penalized empirical risk minimization over a complexity hierarchy gives oracle inequalities under either uniform deviation bounds or suitable relative deviation bounds.These guarantees achieve the best corresponding bound in the hierarchy, as if an oracle knew which complexity level was best.Source: §2.4 · pp. 9–10
  • The framework also applies to neural-network classes indexed by network properties such as parameter size, where trading training fit against complexity can yield an oracle inequality.The section points to such network-indexed estimation bounds as later examples.Source: §2.4 · p. 10

2.5 Computational complexity of empirical risk minimization · 2.6 Classification · 2.7 Large margin classification

These sections contrast tractable convex empirical-risk problems with hard discrete classification, then show how VC dimension and convex surrogate losses shape statistical guarantees. They also explain why surrogate-based analyses can be less sensitive to a model class’s full thresholded complexity.

2.5 Computational complexity of empirical risk minimization

  • Classical ERM is efficiently solvable when the class is linearly parameterized and the loss and complexity penalty are convex; SVM and Lasso penalized problems reduce to quadratic programs.The SVM example uses an RKHS function class and convex loss; Lasso uses linear functions on Rd and quadratic loss.Source: §2.5 · p. 10
  • ERM for thresholded linear functions is NP-hard, but when a function in the class correctly classifies all training data, finding an empirical risk minimizer is equivalent to solving a linear program efficiently.Replacing the discrete loss with a convex surrogate allows computational efficiency even when no thresholded linear function correctly classifies all training data.Source: §2.5 · pp. 10–11

2.6 Classification

  • VC dimension governs classification uniform convergence and worst-case excess risk: ERM has an upper bound, and every method predicting within F has a matching-order worst-case lower bound [VC71, VC74].When F contains a perfect prediction rule, the bounds improve to ˜Θ(dVC(F)/n).Source: §2.6 · p. 11
  • Neural-network VC dimension grows at least linearly with parameter count, so small excess risk or uniform convergence for discrete losses requires sample size large relative to that count.The cited bounds cover networks with piecewise-polynomial nonlinearities.Source: §2.6 · p. 12
  • VC analysis can be infinitely sensitive to tiny activation perturbations, while the authors suggest convex-loss optimization may avoid such fine-grained capacity and help explain gains from increasing parameters.A one-parameter two-layer network with a perturbed ReLU has infinite VC dimension; the paper notes that deep networks often predict well with more parameters than training examples and that performance can improve after training examples are classified.Source: §2.6 · p. 12

2.7 Large margin classification

  • For a c-Lipschitz loss with ℓ(0, y) = 0, the loss-class Rademacher complexity is at most 2c times that of the real-valued function class [LT91, Theorem 4.12].The hinge and logistic losses are examples of convex, 1-Lipschitz classification surrogates.Source: §2.7 · p. 13
  • For a convex surrogate φ, Theorem 2.8 relates excess classification risk to excess surrogate risk through ψφ.When φ is differentiable at zero with φ′(0) < 0, ψφ(θi) → 0 implies θi → 0; for 1-Lipschitz φ, the paper also gives a high-probability classification-risk bound involving Rademacher complexity and surrogate approximation error.Source: §2.7 · pp. 13–14
  • Every classification-calibrated convex surrogate scaled so φ(0) = 1 upper-bounds discrete classification loss, yielding a risk bound when it is also 1-Lipschitz.Classification-calibrated means that any surrogate-risk minimizer also minimizes classification risk.Source: §2.7 · p. 14

2.8 Real prediction · 2.9 The mismatch between benign overfitting and uniform convergence

The sections develop complexity-based generalization bounds for real-valued neural networks, then show that uniform-convergence bounds can explain minimum-complexity interpolation in noiseless settings but become vacuous under noise. This mismatch motivates analyses that use additional information about the prediction problem.

2.8 Real prediction

  • For real-valued neural-network classes, direct Rademacher-complexity bounds transfer to Lipschitz losses, including absolute loss and bounded-range quadratic loss, whereas pseudodimension bounds still require sample size large relative to parameter count.The transfer uses the contraction result for losses that are Lipschitz in the prediction.Source: §2.8 · p. 14
  • For two-layer networks on X=[−1, 1]^d with bounded 1-Lipschitz σ:R→[−1, 1] and σ(0)=0, the Rademacher-complexity result gives high-probability surrogate-loss guarantees, including classification guarantees when the surrogate upper-bounds ℓ01.Source: §2.8 · pp. 14–15
  • For networks with Lipschitz activations that need not be bounded, Theorem 2.10 bounds classification risk using parameter deviations from fixed centers and covering numbers to control intermediate vector scales [BFT17].The bound assumes 1-Lipschitz activations and a Lipschitz surrogate upper bound on classification loss.Source: §2.8 · p. 15
  • For 1-homogeneous activations such as ReLU, Theorem 2.11 gives a direct Frobenius-norm complexity bound, but it is worse than Theorem 2.10 unless the Frobenius-to-spectral norm ratios are near one [GRS18].The L factor can be removed at the cost of worse dependence on n [NTS15].Source: §2.8 · pp. 15–16

2.9 The mismatch between benign overfitting and uniform convergence

  • These bounds are meaningful only when an interpolant exists whose complexity grows sufficiently slowly with sample size for the excess-risk bound to converge to zero.This condition follows from the bounds’ dependence on network-parameter scale or complexity.Source: §2.9 · p. 16
  • When a fixed-complexity function achieves zero risk, a minimum-complexity interpolant has risk converging to zero; in this noiseless case, Theorem 2.2 gives a faster rate of O((log n)^4 R̄_n^2(F_r)).A zero-risk function in F_r implies there is no noise: y = f*(x) almost surely.Source: §2.9 · p. 16
  • With noise, uniform-convergence excess-risk bounds for interpolants cannot fall below a constant, because they also apply in fixed-design settings where excess risk is at least the noise level.Thus these bounds can be vacuous regardless of sample size.Source: §2.9 · pp. 16–17
  • Examples of benign overfitting despite loose uniform-convergence bounds, and the apparent inapplicability of stability approaches in the interpolation regime, motivate analyses that exploit additional information.The complexity notion minimized by an interpolant is crucial to such analyses.Source: §2.9 · p. 17

3 Implicit regularization

When overparametrization creates many empirical minimizers, optimization and parametrization implicitly bias which solution is selected. These biases can select minimum-norm or margin solutions, with properties that may support generalization.

Implicit regularization

  • When an empirical objective has multiple minimizers, optimization method and parametrization shape the selected solution, whose properties may support generalization through mechanisms beyond uniform convergence.Implicit regularization is the bias introduced by an iterative method as a by-product rather than an explicitly enforced property.Source: §3 · p. 17
  • For d > n, gradient descent converges to the minimum ℓ_2-norm interpolant, which is also the ridgeless limit of ridge regression.The iterates remain in the row span of X; from an arbitrary initialization, convergent gradient descent selects the interpolating solution closest to that initialization in ℓ_2 norm.Source: §3 · pp. 17–18
  • On separable data, AdaBoost’s coordinate descent approaches the maximizing ℓ_1-margin direction [ZY05] [Tel13], while gradient descent approaches the max-ℓ_2-margin direction [SHN+18] [JT18].AdaBoost’s margin distribution was observed to keep shifting positively after classification error reaches zero.Source: §3 · pp. 18–19
  • For separable data, logistic-loss gradient descent satisfies θ_t = bθ log t + ρ_t, where bθ is the ℓ_2 max-margin solution and ||ρ_t|| = O(log log t) [SHN+18].The result also holds for suitable smooth losses with exponential-like tails, including exponential loss [SHN+18] [JT18].Source: §3 · p. 19
  • Implicit-bias analyses extend to fully connected and convolutional networks without nonlinearities [GLSS18b], and to mirror descent, steepest descent, and AdaGrad [GLSS18a].The latter analyses cover cases where a global minimum is attained and classification cases where minimizers lie at infinity.Source: §3 · p. 19
  • With infinitesimal initialization, gradient flow on the reparametrized least-squares problem can select a minimum-ℓ_1-norm interpolant; matrix analogues yield minimum nuclear-norm solutions under additional assumptions [GWB+17].The ℓ_1 conclusion requires the limiting solution to exist and interpolate the data.Source: §3 · p. 19

4 Benign overfitting

This section examines benign overfitting under square loss, asking how interpolating estimators can generalize despite noise beyond what uniform-convergence mechanisms explain. It considers local smoothing, overparameterized linear regression, and minimum-norm interpolation in reproducing-kernel Hilbert spaces across dimension regimes, including how a spiky component can enable interpolation without hurting prediction accuracy.

4.1 Local methods: Nadaraya-Watson

  • With noiseless data, 1-nearest neighbor can be consistent under smoothness conditions, but it is generally inconsistent with noise; k-neighbor averaging addresses its insufficient averaging.Even when inconsistent, its asymptotic risk is at most 2L(f*).Source: §4.1 · pp. 20–21
  • [BRT19] show that a truncated singular-kernel Nadaraya–Watson estimator achieves minimax-optimal estimation rates while interpolating for every bandwidth.The stated theorem assumes a β-Hölder regression function and a marginal density bounded above and away from zero; the result extends to β > 1.Source: §4.1 · p. 21
  • The Nadaraya–Watson estimator can add small spikes at training points to a smooth predictive estimate, decoupling exact fit from the bandwidth-controlled bias–variance trade-off.When the added component has vanishing L2(P) norm, it enables interpolation without harming prediction; the singularity determines exact fit, while bandwidth determines smoothing.Source: §4.1 · p. 21

4.2 Linear regression in the interpolating regime

  • Minimum-norm linear interpolation separates prediction from overfitting, with data-dependent self-induced regularization governing their bias–variance trade-off.The prediction component uses the leading k coordinates, while the interpolation component uses the tail; the bounds match up to constants, and the latter’s variance can be small when tail eigenvalues decay slowly and d − k ≫ n.Source: §4.2 · pp. 22, 25

4.3 Linear regression in Reproducing Kernel Hilbert Spaces

  • Kernel regression uses a feature map and kernel function to form an RKHS estimate; as the ridge parameter tends to zero, kernel ridge regression yields a minimum-norm interpolant.The section analyzes these interpolants through random kernel matrices, extending beyond the overparametrized linear-regression setting.Source: §4.3 · p. 26

4.3.1 The Laplace kernel with constant dimension

  • For the Laplace kernel in fixed dimension, the minimum-norm interpolant is inconsistent for every bandwidth choice, including data-dependent choices.In one dimension, the interpolant ranges from piecewise linear as σ grows to spikes at data points as σ shrinks; neither limit is consistent. For smooth signals, bounded density, and Rademacher noise, the result extends to fixed odd dimensions.Source: §4.3.1 · p. 27

4.3.2 Kernels on Rd with d ≍nα

  • With independent coordinates and d ≍ n^α, kernel eigenvalues form a staircase, while interpolation variance has multiple-descent valleys that deepen as dimension grows.Degree-bounded kernel components capture low-frequency signal directions; variance is at most d^-1/2 at n = d^(ι+1/2).Source: §4.3.2 · pp. 27–29

4.3.3 Kernels on Rd with d ≍n

  • When d ≍ n, the kernel matrix is approximated by a linear kernel plus an identity term, whose curvature implicitly regularizes the minimum-norm interpolant.The interpolant separates into a simple component and a small-in-L2(P) overfitting component; Theorem 4.13 characterizes bias and variance under stated conditions, with an equivalent sequence-model interpretation.Source: §4.3.3 · pp. 29–31
  • Each interpolating solution separates into a simple prediction component and a spiky overfitting component.The spiky component ensures interpolation without reducing prediction accuracy.Source: §4.3.3 · p. 32

5 Efficient optimization

This section surveys how overparametrization and different training regimes shape optimization, from tractable interpolation and linearized versus mean-field dynamics to conditions determining those regimes. It also covers approaches beyond linearized evolution, including higher-order kernel approximations and parametrizations with purely nonlinear gradient-flow dynamics.

5 Efficient optimization

  • When a linear classifier can interpolate the data, finding an interpolator reduces to solving linear inequalities in polynomial time; this motivates the hypothesis that overparametrization makes neural networks tractable.Random constraint satisfaction problems, though NP-hard in the worst case, are observed to become tractable when free parameters sufficiently outnumber constraints; a satisfactory theory for neural networks remains lacking outside the linear regime.Source: §5 · pp. 32–33

5.1 The linear regime

  • In the linear regime, gradient flow can stay close to its initialization and its linearized flow, with Jacobian singular values and Lipschitz variation governing sufficient conditions.When the initialization Jacobian has full row rank, the linearized flow converges to an interpolator minimizing its ℓ2 distance from initialization.Source: §5.1 · pp. 33–34

Further define

  • For two-layer networks, α = Θ(1) requires md ≫ n² for the stated guarantees, while suitable initialization and increasing α allow them under md ≫ n log n.In the latter case, the linear model approximates the network with L2(P) error O(1/α); when the approximation bound is negligible, the network's generalization is approximated by min-norm interpolation in the initialization's feature map.Source: Further define · p. 36

5.2 Beyond the linear regime?

  • In the mean-field limit, neuron-weight distributions follow a PDE and weights move nontrivially; the prediction kernel changes during training, although short-time evolution recovers the linearized dynamics.For the stated mean-field scaling, first-layer weight changes do not vanish as width grows, so both linear and nonlinear regimes can arise at infinite width under different normalization scalings.Source: §5.2 · pp. 37–38
  • In mean-field gradient flow, a distribution is a global minimizer exactly when ψ vanishes for every weight vector, whereas a fixed point requires this only on its support.For analytic activations, a stationary distribution whose support contains distinct weights with an accumulation point is therefore a global minimum; non-global local minima must have isolated-point support.Source: §5.2 · p. 39

5.3 Other approaches

  • Higher-order Taylor approximations evolve the kernel through an order-3 tensor contracted with the residual; retaining its initialization value yields a hierarchy of increasingly complex, more accurate approximations [HY20].The linearized approximation instead replaces the order-3 kernel with zero.Source: §5.3 · p. 39
  • Other proposals construct Taylor expansions around linearized evolutions [DGA20] and [HN20].Source: §5.3 · p. 39
  • When a network parametrization makes the initialization Jacobian vanish, the first nontrivial Taylor term is quadratic and gradient flow is purely nonlinear [BL20a].Source: §5.3 · p. 39

6 Generalization in the linear regime

This section examines generalization in linearized models, where uniform-convergence bounds do not explain overparameterized models, and reviews gradient-based implicit bias in random-feature and neural-tangent models. It covers random-feature behavior under proportional scaling—including double descent, benign high-overparameterization risk, and noisy-feature universality—and related neural-tangent generalization at equal parameter counts.

6.1 The implicit regularization of gradient-based training

  • Gradient descent in the linear regime selects the minimum-ℓ2-norm interpolator, corresponding to a minimum-norm fit in the linearized neural network’s function space.That function-space norm is an RKHS norm. Outside the linear regime, gradient flow can induce a different bias: [CB20] show a total-variation norm that promotes functions depending on a small number of directions.Source: §6.1 · pp. 40–41

6.2 Ridge regression in the linear regime

  • Ridge regression in random-feature and neural-tangent linearized models includes minimum-norm interpolation as the vanishing-regularization limit, while positive regularization approximates gradient flow with early stopping.The stated setup uses isotropic covariates; if data lie in a lower-dimensional subspace, the ambient dimension should be replaced by the intrinsic dimension.Source: §6.2 · pp. 41, 43

6.3.1 Polynomial scaling

  • In polynomial scaling, when width and sample size are well separated, random-feature test error is governed by the smaller of the two and exhibits a sharp transition across polynomial degrees.When m ≪ n, approximation error dominates; when n ≪ m, statistical error dominates. For d^ℓ ≪ min(m,n) ≪ d^(ℓ+1), the fit approximates the target’s projection onto degree-ℓ polynomials, even for sufficiently small regularization including min-norm interpolation.Source: §6.3.1 · pp. 43–44
  • Increasing random-feature width improves test error up to roughly m ≈ n, with limited gains beyond m ≥ nd^δ, where the error matches the associated kernel method.The feature model is essentially kernel ridge regression with a polynomial kernel whose degree depends on the smaller of m and n; higher-degree activation components behave like noise in the regressors.Source: §6.3.1 · pp. 44–45

6.3.2 Proportional scaling

  • The proportional regime m ≍ n can have high variance when the feature matrix is nearly square, motivating simulations across the overparametrization ratio.The reported simulations use small regularization λ = 10^-3(m/d) and show test and training error, but the supplied passages do not state their outcomes.Source: §6.3.2 · p. 45
  • Train error becomes very small for m/n ≥ 1, while test error peaks—and for λ = 0+ diverges—at m/n = 1 before decreasing as m/n grows.For m/n ≫ 1 and n/d ≫ 1, test error converges to ∥P>1f∗∥L2.Source: §6.3.2 · pp. 45–46, Figure 1 · p. 46
  • With m/n ≫ 1 and n/d ≫ 1, test error is asymptotically ∥P>1f∗∥L2: degree-one target components are fitted perfectly, while higher-degree components remain unlearned.This suggests m/n ≫ 1 can suffice for risk to be dominated by statistical error, rather than the larger separation assumed in Theorem 6.1.Source: §6.3.2 · pp. 46–47
  • In proportional asymptotics, the risk has effective bias and variance terms plus ∥P>1f∗∥2L2, with higher-degree target components acting like added noise.The random-features risk is asymptotically equivalent to that of a simpler noisy-features model.Source: §6.3.2 · pp. 47–48
  • Above a critical signal-to-noise ratio, λ = 0+ is optimal; below it, the risk decreases for small positive regularization, so near-interpolation is optimal only at high signal-to-noise.The result concerns the limiting risk as dimension grows.Source: §6.3.2 · p. 48

6.4 Neural tangent model

  • Neural-tangent and random-features models have similar generalization when parameter counts are matched, while NT has lower prediction-time complexity and greater expressivity under computational constraints.At equal parameter count p, the stated prediction costs are O(pd) for RF and O(p) for NT.Source: §6.4 · p. 49
  • When d^ℓ+δ ≤ md ≤ d^ℓ+1−δ, the NT model can approximate degree-ℓ polynomials to arbitrarily good relative accuracy and is roughly orthogonal to higher-degree components.This is the n = ∞ approximation-error result, under the theorem’s technical assumptions.Source: §6.4 · pp. 49–50
  • For finite samples and neurons, interpolation requires sufficient feature-matrix rank; when m = O(d), NT ridge regression can be approximated by raw-covariate ridge regression with adjusted regularization.The text gives md ≥ C0n log n as a sufficient rank condition in the stated setting and establishes an interpolator with high probability under Theorem 6.5’s assumptions.Source: §6.4 · pp. 50–51

7 Conclusions and future directions

The review asks how interpolation can remain optimal or nearly optimal with noisy data, and argues that analyses of linear models offer both direct insight into neural tangent regimes and guidance for more complex settings. It highlights unresolved questions about mechanisms, dimensionality, adaptive complexity, and why overparametrization aids computation.

Simple-plus-spiky decomposition

  • In the overfitting regime, a learned function can combine a simple predictive component with a spiky component that enables interpolation without materially harming test error.For linear models the components are projections onto top kernel eigenvectors and their orthogonal complement; in nonlinear models they need not be orthogonal and may be data-dependent. Whether this decomposition connects to neural-network compressibility [HMD15] remains open.Source: §7 · p. 52

Implicit regularization

  • Among linear interpolators, gradient-based training selects the model closest in ℓ2 norm to its initialization, but the selection mechanism and its interaction with nonlinear dynamics remain open.In some kernel, random-feature, and neural-tangent regimes, the simple component also receives self-induced regularization; understanding that mechanism more broadly is an outstanding challenge.Source: §7 · p. 52

Role of dimension

  • In fixed dimension, noisy-data interpolation can be suboptimal [RZ19], while the probability of nearby test points causing error decays rapidly as dimension grows.For deep learning, it remains unclear whether methods evade low-dimensional limits through irregular near-interpolants or sufficiently large effective dimension; defining effective dimension is also an open question.Source: §7 · p. 52

Adaptive model complexity

  • The complexity k of the predictive component grows with sample size and, in random-feature and neural-tangent models, saturates at the number of network parameters.This motivates the broader hypothesis that, when a simple-plus-spiky decomposition exists, the simple component’s complexity increases with both sample size and network size.Source: §7 · p. 53

Computational role of overparametrization

  • Overparametrization is motivated chiefly by computation: empirical evidence and linearized and mean-field theories suggest it can make global optimization tractable, but the amount required remains unknown.The review notes that neural-network empirical risk minimization is computationally hard and gradient methods generally cannot be expected to find a global minimizer.Source: §7 · p. 53

A.1 Bound on the variance of the minimum-norm interpolant

Appendix A.1 states a variance bound for the minimum-norm interpolant under n ≲ d and k < d, with the eigenvalues of Σ ordered from largest to smallest.

A.1 Bound on the variance of the minimum-norm interpolant

  • The lemma applies to any X and positive semidefinite Σ when n ≲ d and k < d, with λ1 ≥ … ≥ λd the eigenvalues of Σ.The extracted passages do not include the bound’s formula.Source: §A.1 · p. 64
  • The proof splits Σ into its first-k and remaining components, using a deterministic argument due to Liang and arguments from [LR20, Remark 5.1] and [BLLT20].It also invokes the Sherman–Morrison formula.Source: §A.1 · p. 64

A.2 Exact characterization in the proportional asymptotics

The section states a high-probability proportional-asymptotic characterization of the squared bias and variance of the minimum-norm interpolant. It also defines the kernel notation and decomposes the target into affine and non-affine components.

A.2 Exact characterization in the proportional asymptotics

  • The kernel matrix is K = (h(⟨xi, xj⟩/d))i,j≤n, and K1 denotes the linearized kernel.Source: §A.2 · p. 64
  • Theorem 4.13 gives a characterization of the minimum-norm interpolant’s squared bias and variance with probability at least 1 − Cn^-1/4 under the stated proportional-asymptotic assumptions.The assumptions include M^-1 ≤ d/n ≤ M, independent standardized coordinates of Σ^-1/2x, a suitably regular kernel h, and an L4+η-bounded target function.Source: §A.2 · p. 65
  • The target function is decomposed into its mean, a linear component indexed by β0 = Σ^-1E[xf*(x)], and a component orthogonal to affine functions.The non-affine component has zero expectation and zero cross-moment with x.Source: §A.2 · p. 65

A.2.1 Preliminaries

The preliminaries establish a high-probability lower bound for the kernel matrix and approximations used in the proof. They also specify the concentration events and local smoothness conditions behind those estimates.

A.2.1 Preliminaries

  • When h is non-linear, K ⪰ c*I_n for c*=βγ>0 with probability at least 1−Cn^-D.This is the stated lower bound under the assumptions of Theorem 4.13.Source: §A.2.1 · p. 65
  • Lemma A.3 gives ∥v−v0∥2 ≤ Cd^-1√log d and ∥M−M0∥F ≤ Cd^-3/2 log d with very high probability.The proof establishes these estimates on the intersection E1∩E2, which holds with very high probability.Source: §A.2.1 · p. 66
  • The proof uses h smooth on [−t0,t0] and concentration events ensuring normalized pairwise inner products lie in that interval; extending h smoothly outside it incurs only O(e^-d/C) error.The tail error is negligible compared with the approximation errors in the lemma.Source: §A.2.1 · p. 67

A.2.2 An estimate on the entries of the resolvent

This section develops moment and probability estimates for off-diagonal resolvent entries under sub-Gaussian row assumptions. It uses orthogonality of the weighting function and moment bounds to control products of entries, culminating in a high-probability estimate.

Lemma A.4

  • Lemma A.4 assumes iid zero-mean C-sub-Gaussian rows with C^-1 ≤ n/d ≤ C, a bounded positive semidefinite S, and a centered, linearly orthogonal g with unit second moment.For any λ > 0, it states a finite-constant estimate for distinct indices; its displayed bound is not included in the supplied passage.Source: §A.2.2 · p. 71
  • For two distinct indices, the off-diagonal entry Y12 is rewritten using a cross term, then bounded using positive semidefiniteness and the corresponding diagonal quadratic forms.The proof applies the Hanson–Wright inequality and uses g's orthogonality to linear functions.Source: §A.2.2 · pp. 71–72

Lemma A.5

  • Under Lemma A.4's assumptions, Lemma A.5 extends the entry-product estimate to four distinct indices, using expansions and moment bounds for the resulting terms.The supplied passage omits the displayed bound's value.Source: §A.2.2 · pp. 72–73

Lemma A.6

  • Under Lemma A.5’s definitions and assumptions, Lemma A.6 further assumes E{|g(z)|^(2+η)} ≤ C for 0 < C, η < ∞ and treats E{YijYjkg(zi)g(zj)^2g(zk)} for any triple of four distinct indices i, j, k.Source: §A.2.2 · p. 74

Theorem A.7

  • For any λ > 0, Theorem A.7 gives its target estimate with probability at least 1 − Cd^-1/4 under the stated sub-Gaussian, bounded-matrix, and function-moment assumptions.The assumptions include E{g(z1)} = E{z1g(z1)} = 0 and E{|g(z1)|4+η} ≤ C.Source: §A.2.2 · p. 74

A.2.3 Proof of Theorem 4.13: Variance term

The variance-term proof combines high-probability lemmas to simplify the variance calculation, then identifies the remaining asymptotics with ridge regression on the simple features X. Its approximation and matrix-control steps are stated under Theorem 4.13’s assumptions.

A.2.3 Proof of Theorem 4.13: Variance term

  • Lemma A.8 supplies a very-high-probability result under Theorem 4.13’s assumptions that enables taking the expectation with respect to x.It defines M0 as in Lemma A.3; the displayed bound itself is not included in the supplied passage.Source: §A.2.3 · pp. 74–75
  • With very high probability, the matrix B defined in Eq. (177) is within C d^-3/2 of B0 in operator norm.Source: §A.2.3 · p. 75
  • The proof uses Sherman–Morrison to control the terms involving 1 and ã against K^-2, relying on βγ being bounded away from zero.The proof also uses Lemma A.11 under Theorem 4.13’s assumptions; its stated bound is not visible in the supplied passage.Source: §A.2.3 · pp. 76–77
  • The remaining variance asymptotics are those of ridge regression on the simple features X, with ridge regularization proportional to γ; the proof invokes [HMRT20].This follows after applying Lemmas A.8, A.10, and A.11 and controlling residual terms.Source: §A.2.3 · p. 77

A.2.4 Proof of Theorem 4.13: Bias term

The proof decomposes the bias according to the orthogonal constant, linear, and nonlinear parts of the target, then controls their contributions under Theorem 4.13’s assumptions. It reduces the bias to tractable terms, including ridge-regression bias for the linear component and high-probability bounds for nonlinear and mixed contributions.

Bias decomposition

  • The target is decomposed into orthogonal constant, linear, and nonlinear components, yielding an expression for squared bias in terms of K, M, v, and the target’s L2 norm.The constant and linear components are defined by orthogonality; the remaining component is f*NL.Source: §A.2.4 · p. 78

Lemma A.12

  • Under a bounded fourth-moment assumption on f*(x), Lemma A.12 controls target norms and the concentration of its empirical squared norm.The stated assumption is E{f*(x)^4} ≤ C0; the proof uses it to bound the L2 norm and apply Chebyshev’s inequality to the empirical norm.Source: §A.2.4 · p. 78

Lemmas A.13–A.14

  • Lemma A.13 reduces the analysis to M0 and v0 with probability at least 1−Cn^-1/4, while Lemma A.14 shows the constant-component contribution is negligible with very high probability.The norm control from Lemma A.12 supports the reduction; the proof then works with the decomposed bias terms.Source: §A.2.4 · pp. 78–79

Lemma A.15

  • The linear component’s contribution is recognized as ridge-regression bias for linear features and is bounded using [HMRT20].The comparison concerns responses given by the same linear function of the features.Source: §A.2.4 · p. 80

Lemma A.16

  • The nonlinear bias contribution is bounded with probability at least 1−Cn^-1/4 under the assumptions of Theorem 4.13.Lemma A.16 controls the nonlinear term RNL using V(Σ).Source: §A.2.4 · p. 81

Lemma A.17 and proof conclusion

  • The mixed bias contribution is bounded with probability at least 1−Cd^-1/4, completing the proof with Lemmas A.15–A.17.Lemma A.17 provides the bound for Rmix; the theorem proof concludes by combining the three lemmas.Source: §A.2.4 · p. 82

A.2.5 Consequences: Proof of Corollary 4.14

The proof establishes a unique solution to Eq. (166), then uses its bounds and Theorem 4.13 to derive high-probability and bias bounds under the stated assumptions.

A.2.5 Consequences: Proof of Corollary 4.14

  • Eq. (166) has a unique solution because its left side is strictly increasing, its right side is strictly decreasing, and their limiting values ensure an intersection.The proof orders the eigenvalues of Σ as λ1 ≥ ··· ≥ λd.Source: §A.2.5 · p. 82
  • When λ* ≥ c*λk+1, the proof derives an explicit lower bound on λ* from the inequality involving Eq. (166).Source: §A.2.5 · p. 82
  • Under the stated right-hand-side bound of 1/2, Theorem 4.13 yields the claimed high-probability bound, and the related assumption implies k ≤ n/2.Source: §A.2.5 · p. 83
  • Expressing β0 in the eigenvector basis and applying Theorem 4.13 gives the desired bound on the bias.Source: §A.2.5 · p. 83

B Optimization in the linear regime · Further define

In the linear regime, gradient flow fits the training data exponentially while staying close to its initialization and to the linearized flow. For two-layer networks, the stated conditions yield exponential convergence and similarity between the nonlinear and linearized models on test data.

B Optimization in the linear regime

  • In the linear regime, empirical risk decreases exponentially to zero at rate λ0=σ_min²/(2n).The result is stated for all t>0.Source: Further define · p. 83
  • The parameters stay close to initialization and are tracked by the linearized flow, whose model is also similar to the gradient-flow model on test data.The proof concludes the test-data similarity bound by combining bounds for its two component terms.Source: Further define · pp. 83, 84, 86

Further define

  • Under Lemma 5.3’s Gaussian-input and sub-Gaussian-response assumptions, the two-layer setup controls the initialization output; for θ(2) 0, its norm is at most C1α√n with the claimed probability.The lemma’s stated conditions include md≥C0n log n and n≤d^ℓ0.Source: Further define · p. 86
  • Under the Hermite-coefficient and sample-size conditions, the empirical NT kernel has minimum eigenvalue at least c0 with the stated probability [EK10].The condition includes n≤d^ℓ0.Source: Further define · p. 87
  • The initialization Jacobian’s largest singular value is bounded by B∥X∥, with the claim following from standard operator-norm estimates for random matrices.The bound is established under the two-layer setup’s stated assumptions.Source: Further define · p. 88
  • For two-layer networks, gradient flow converges exponentially to a global minimizer with rate λ*=C1α²d/n and remains similar to the linearized flow on test data.These guarantees hold with the theorem’s stated initialization and sampling conditions, with probability at least 1−2 exp(−n/C0).Source: Further define · p. 88

Related papers

Loading 2103.09177v1…