Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation

In plain words

Classic statistics says that a model which fits its training data perfectly, noise included, will generalize badly. This essay by Mikhail Belkin argues that this rule breaks down for the large models used in deep learning. A model that has enough freedom to hit every training point can still predict new points well, and the reason lies in which of the many possible exact fits it chooses.

The author gathers the evidence and the mathematics around this idea. Some simple predictors that fit noisy data exactly are shown to be nearly optimal when the data is high-dimensional. Test error can first rise and then fall again as a model grows past the point where it can fit the data exactly. Gradient-based training can find good fits even though the training problem is non-convex, and in the over-parameterized setting plain stochastic gradient descent can converge quickly.

The essay is a survey and an interpretation, not a new method. It reports no experiments of its own; the figures are reproduced or credited from earlier work. It is written as a personal view and says openly that many pieces of the picture are still missing.

TL;DR

• The essay argues that exact interpolation of training data is compatible with good generalization in over-parameterized models, and that this challenges classical learning theory §1 §3.4.
• It gives a "double descent" picture: test risk peaks near the interpolation threshold and falls again for larger models §3.7 fig. 5.
• For optimization, it argues that the PL* condition (a Polyak-Łojasiewicz variant without the optimal loss value) explains why gradient methods reach global minima §4.1 §4.2.
• It is a survey with no experiments of its own, and several central claims are heuristic or cite external theorems §3.5.2 §4.2.

Problem

Classical generalization bounds (uniform convergence, VC or Rademacher complexity) say that training risk approximates test risk for any function in the class. Under that view, fitting noisy data exactly is expected to hurt generalization §3.1 §3.2 §3.4. Kernel machines and neural networks trained to zero training error on label-noisy data nevertheless generalize well, which the author argues is incompatible with such bounds in general §3.4 fig. 2. The essay asks why this happens, why over-parameterized optimization succeeds, and how gradient methods pick a solution among the many exact fits §3.6 §4.

Method

This is an expository essay. Its argument proceeds in the following steps, each citing the section where it is made.

1. Define the setting: statistical learning with i.i.d. data, a Bayes-optimal predictor, and empirical risk minimization (ERM). Structural risk minimization needs a uniform law of large numbers plus capacity control §3.1 §3.2.
2. Show that margin-based and data-dependent bounds still do not explain interpolating kernel machines on label-noisy data. The essay derives that the excess risk of an interpolant with label noise is at least q/2 while a useful bound must be below 1/2 §3.3 §3.4 fig. 2.
3. Replace the classical picture with interpolating predictors that are nearly optimal: the 1-NN rule, simplicial interpolation in high dimension, and a weighted k-NN with a singular kernel that is consistent §3.5.1 §3.5.2 §3.5.3 fig. 3 fig. 4.
4. Introduce inductive bias as the key question. Among interpolating solutions, the smoothest one (in a norm such as the RKHS norm) is preferred, which the author ties to Occam's razor §3.6.
5. Explain double descent. As capacity grows past the interpolation threshold, the minimum-norm interpolant gets smoother and test error falls again §3.7 fig. 5 fig. 6 fig. 7. For over-parameterized linear models, the least-squares minimum-norm interpolator is the solution that gradient descent from zero reaches §3.8 §3.9.
6. Argue that very wide neural networks with a linear output layer behave like kernel machines, because the tangent kernel is nearly constant in a ball around initialization ("transition to linearity"). Adding a non-linear output layer breaks this §3.10.
7. Optimization: over-parameterized losses are non-convex yet satisfy the PL* condition on most of the parameter space, which gives global minima and convergence of GD and SGD §4.1 §4.2 §4.3. Interpolation gives SGD with fixed step size exponential convergence and an efficiency gain over full-batch GD up to a critical batch size §4.4.
8. Discuss cross-entropy versus square loss, interpolation and adversarial examples, and open questions §5.1 §5.2 §6.1 §6.2.

Core interpolant forms used in the essay:

f(x) = \sum_{i=1}^{n} \alpha_i K(x_i, x), \qquad \alpha = K^{-1} y \quad [\text{§3.4}]

f_{\mathrm{ker}}(x) = \arg\min_{f:\, f(x_i) = y_i} \|f\|_{\mathcal H_K} \quad [\text{§3.6}]

\|f\|_{\mathcal H_K}^2 = \alpha^{\top} K \alpha \quad [\text{§3.7}]

Weighted nearest-neighbour interpolant with a singular kernel, as defined in the essay:

# Weighted k-NN interpolant with singular kernel  [§3.5.3]
# Input:  training points xs (n, d), labels ys (n,), query x (d,), k, alpha
# Output: scalar prediction at x

def singular_knn_predict(x, xs, ys, k, alpha):
    # Take the k nearest training points to x  [§3.5.3]
    neighbours = k_nearest(x, xs, k)
    # Singular kernel K(x, z) = 1 / ||x - z||^alpha, alpha > 0  [§3.5.3]
    weights = [1.0 / norm(x - xs[i]) ** alpha for i in neighbours]
    # Weighted average with the singular weights  [§3.5.3]
    numerator = sum(w * ys[i] for w, i in zip(weights, neighbours))
    denominator = sum(weights)
    # Defined as a ratio; the singularities cancel  [§3.5.3]
    return numerator / denominator

Minimum-norm interpolator in the over-parameterized linear case, and the GD path from zero:

# Minimum-norm interpolator for linear regression, d > n  [§3.8] [§3.9]
# Input:  X (n, d) with d > n, labels y (n,)
# Output: beta (d,)

def min_norm_interpolator(X, y):
    # Smallest-norm beta with X beta = y, via the pseudo-inverse  [§3.8]
    beta = pinv(X) @ y
    return beta

# Gradient descent started at beta_0 = 0 stays in span(X) and converges
# to the same minimum-norm solution  [§3.9]

Hyperparameters

The essay reports no hyperparameter search of its own. The values below are the ones it states in its examples and figures.

Results

Author-reported. The essay re-presents results from earlier work and its own illustrative calculations. No new experiments are described. Setups are given where the text states them.

Paper vs code

No official code. The paper has no code link in its LaTeX source or abstract, and it reports no experiments of its own that would need code. I searched for the title on GitHub with the repository search API (query: "fit without fear interpolation"), which returned no results, and tried the author's GitHub repositories page, which returned 404. Nothing was found, so no code fields are set.

Pitfalls

• Gaussian kernel is defined twice with different constants. The essay uses exp(−‖x−z‖²/2) in the kernel discussion §3.2 and exp(−‖x−z‖²) in the random-Fourier-feature limit §3.7. An implementer must choose one and keep it consistent with the RKHS norm formula.
• Interpolation is not the same as ERM in the essay's sense. The essay separates algorithmic ERM (an optimizer minimizing empirical loss) from Vapnik's algorithm-independent ERM §3.6. Results about "the" minimum-norm solution do not hold for every optimizer.
• Several bounds are stated only up to constants. The simplicial bound O(1/√d) and the e^d variant for classification need "additional conditions" that are not spelled out §3.5.2. The 1-NN factor of two holds asymptotically in n §3.5.1.
• Singular kernel parameters are unspecified. The exponent α and the neighbour count k are not given; only consistency and optimality are claimed §3.5.3.
• Transition to linearity is a heuristic argument. The Hessian bound O*(1/√m) is stated for width m = min layer width with unspecified constants §3.10. The two-layer example assumes i.i.d. standard normal first-layer weights, a ball of radius O(1), and fixed output weights in {−1, 1}. The step from Hessian to gradient norm uses the heuristic ‖b‖ ~ √m ‖a‖∞ §3.10. The essay itself says these results do not settle whether deep learning is kernel learning §3.10 §6.2.
• The PL constant is not bounded.* μ = λ_min(K) is justified by parameter counting ("we expect") and the radius O(1/μ) carries no explicit constant §4.2. Treat the PL* statement as an interpretation unless a cited theorem is used.
• Critical batch size formula is for quadratic models. m* = max_i ‖x_i‖² / λ_max(H) is derived for a quadratic model §4.4. The "below 100 for kernel methods" value and the 10^5 speed-up example come from cited work and an illustrative calculation, not from this essay's experiments.
• Cross-entropy and interpolation. Zero cross-entropy loss is only reached at infinite margin, so interpolation does not occur at finite parameters §5.1. The essay's preference for square loss in classification is its own argument, supported by external evaluations §5.1; do not treat it as established practice.
• Several figures are credited to other sources. Fig. 2 is marked as from Belkin et al. 2018; figs. 5 and 7 as from Belkin et al. 2019; figs. 8 and 9 as credited to Liu et al.; fig. 10 as credited to Ma et al.; fig. 4 as credited to Partha Mitra; fig. 1 is a curve cited to Vapnik's book. Do not reproduce any of them without checking their own licenses; this card does not use them fig. 1 fig. 2 fig. 4 fig. 5 fig. 7 fig. 8 fig. 9 fig. 10.
• Draft material in the source. The LaTeX source contains uncommented draft fragments after the Acknowledgements, with section titles such as "Life after ERM" and "ERM, revisited: double descent". They read as author notes, do not match the body's structure, and are not used in this card.
• Early stopping is common in practice. The essay notes that neural networks are usually trained with early stopping rather than to exact interpolation, and that its trade-offs are not well understood §6.2. Results on exact interpolation may not transfer directly to practical training runs.

Lineage

• Builds on: Vapnik's structural risk minimization §3.2; margin theory for boosting (Schapire et al.) §3.3; interpolating kernel experiments of Belkin et al. 2018 §3.4; simplicial interpolation and singular-kernel consistency results of Belkin et al. 2018 §3.5.2 §3.5.3; neural tangent kernel of Jacot et al. §3.10. These papers are named and linked on arXiv; their content is not used here.
• Compared against: classical uniform-convergence bounds and the bias-variance trade-off §3.2 §3.4.
• Companion work: the essay points to a parallel Acta Numerica survey on interpolation in linear regression and kernel methods (cited in the source as bartlett2021deep) §3.8.
• Superseded by: not stated in this card's sources.