PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Mikhail Belkin

arXiv:2105.14368v1stat.MLcs.LGmath.ST

TL;DR

The paper addresses why classical learning theory has not convincingly explained deep learning’s practical success. It uses interpolation and over-parameterization as organizing concepts, synthesizing mathematical and empirical evidence that interpolating predictors can generalize strongly, while acknowledging that the resulting picture remains incomplete.

  • Problem

    Classical machine-learning theory has struggled to explain the strong practical performance of modern deep networks and interpolating predictors.

  • Method

    The paper informally synthesizes emerging theory and empirical phenomena through the connected themes of interpolation, over-parameterization, optimization, and generalization.

  • Results

    Interpolating predictors often provide strong generalization, including nearly optimal performance for kernel machines trained on data with substantial label noise.

  • Takeaways & Limitations

    Interpolation serves as a prism for disentangling generalization and optimization properties in modern machine learning.

  • Takeaways & Limitations

    The account is informal, subjective, partly conjectural, and explicitly not a definitive description of the field.

Abstract

from arXiv · show

In the past decade the mathematical theory of machine learning has lagged far behind the triumphs of deep neural networks on practical challenges. However, the gap between theory and practice is gradually starting to close. In this paper I will attempt to assemble some pieces of the remarkable and still incomplete mathematical mosaic emerging from the efforts to understand the foundations of deep learning. The two key themes will be interpolation, and its sibling, over-parameterization. Interpolation corresponds to fitting data, even noisy data, exactly. Over-parameterization enables interpolation and provides flexibility to select a right interpolating model. As we will see, just as a physical prism separates colors mixed within a ray of light, the figurative prism of interpolation helps to disentangle generalization and optimization properties within the complex picture of modern Machine Learning. This article is written with belief and hope that clearer understanding of these issues brings us a step closer toward a general theory of deep learning and machine learning.

1 Preface

The paper situates deep learning’s practical successes alongside an incomplete mathematical understanding and presents its discussion as an informal, evolving perspective.

  • Deep learning’s practical successes have increased the importance of understanding the mathematical principles underlying them.
  • The paper assembles pieces of an emerging mathematical mosaic around deep learning.
  • The discussion is informal, subjective, and partly conjectural rather than a definitive account of the field.

2 Introduction

The introduction contrasts classical learning theory with modern over-parameterized regimes, where interpolation can coexist with strong generalization and requires understanding solution selection.

  • Classical learning theory struggled to explain deep learning’s successes on practical problems.
  • Over-parameterized model classes can contain many interpolating predictors, so the key statistical question becomes which solutions are preferred by inductive bias.
  • Interpolation fits training data exactly, while over-parameterization supplies enough parameters to satisfy those fitting constraints.
  • Interpolation is not necessary for good generalization because regularization or early stopping can be preferable to exact fitting.
  • Interpolating predictors can generalize strongly, and modern practice often operates closer to interpolation than to classical matching of training and testing losses.

3 The problem of generalization

This section introduces supervised learning and classical empirical-risk theory, where generalization depends on approximation and controlling hypothesis-class capacity.

  • Supervised learning seeks predictors that accurately classify or regress on unseen data from the same underlying distribution.
  • Empirical Risk Minimization uses training data as a proxy for the unknown data distribution when approximating the optimal predictor.
  • Uniform Laws of Large Numbers make empirical loss predictive of expected loss across a hypothesis class.
  • Classical generalization requires both capacity control and a hypothesis class capable of approximating the optimal predictor.
  • When cap(H) ≪ n, empirical risk minimization can have nearly optimal true risk, but excessive capacity can make the bound tautological.
  • Structural Risk Minimization enlarges the hypothesis class toward a point balancing empirical risk against the capacity term.

3.3 Margins theory and data-dependent explanations.

Margins theory narrows complexity analysis to plausible, data-dependent predictors, while noisy-data experiments show that interpolation can generalize nearly optimally and challenge WYSIWYG bounds.

  • Margins theory and data-dependent explanations.: Classical capacity bounds apply to every function in H, although most such functions may be implausible predictors.
  • Margins theory and data-dependent explanations.: Margins theory focuses on subsets with small empirical loss, whose data-dependent capacity can be much smaller than cap(H).
  • Margins theory and data-dependent explanations.: The resulting data-dependent margin bounds were developed partly to explain the lack of over-fitting observed in boosting.
  • What you see is not what you get: Interpolating Laplace and Gaussian kernel machines trained on q-corrupted labels generalize nearly optimally on similarly corrupted test data.
  • What you see is not what you get: The Laplace kernel tracks Bayes error closely even when 80% of the data are corrupted.
  • What you see is not what you get: General uniform bounds cannot provide the needed explanation in the relevant settings because their capacity terms cannot adapt tightly to the noise level.
  • What you see is not what you get: These results show that strong generalization from noisy-data interpolation is incompatible with WYSIWYG bounds, independently of the capacity term.

3.5 Giving up on WYSIWYG, keeping theoretical guarantees

Interpolating predictors can retain theoretical guarantees despite fitting noisy data exactly. Progression from 1-NN through simplicial interpolation to singular-kernel weighted nearest neighbors improves statistical behavior, especially in high dimensions.

  • 1-NN interpolates training data exactly while its asymptotic classification risk is bounded above by twice the Bayes-optimal risk.Its empirical risk is zero, despite the absence of an ERM-style analysis.
  • Simplicial interpolation preserves interpolation and becomes nearly optimal for classification and regression as dimension increases.Its excess risk decreases with dimension, with analogous regression results and stronger classification bounds under additional conditions.
  • In a simplex with one noisy vertex, simplicial interpolation differs from the optimal predictor only in a localized neighborhood of that vertex.High-dimensional geometry makes such neighborhoods occupy a smaller fraction of the total space, allowing noise effects to remain localized.
  • Simplicial interpolation is not consistent, even though it approaches the optimal predictor in high dimension.This motivates consistent interpolation schemes based on weighted nearest neighbors and singular kernels.
  • Singular-kernel weighted nearest-neighbor predictors can be consistent for regression and classification and optimal in a statistical sense.For noisy linear regression, the interpolating predictor is close to optimal on most points, with that fraction tending to one as n →∞.

3.6 Inductive biases and the Occam’s razor

In over-parameterized settings, interpolation exposes the inductive-bias problem: among many exact-fitting predictors, generalization depends on which solution an algorithm selects. A maximum-smoothness principle favors the smoothest interpolating function, while increasing model size can improve approximation and produce double descent.

  • Inductive bias: Over-parameterization creates many interpolating predictors, so training data alone cannot explain why some solutions generalize and others do not.An interpolating algorithm selects one predictor from the set of exact-fitting solutions, making its inductive bias central.
  • Occam’s razor: Maximum smoothness selects the smoothest function among those that fit the data perfectly.This principle treats fitting as consistency with evidence and smoothness as simplicity.
  • Double descent: Beyond the interpolation threshold, increasing capacity can improve generalization even though risk is typically high at the threshold.Below the threshold, predictors follow the classical U-curve; beyond it, the generalization curve descends again.
  • Double descent: Double descent has been observed across datasets and algorithms, including deep neural networks, linear models, boosting, and random forests.The modern regime describes cases where large parameter counts do not lead to over-fitting.
  • Smoothness and richer classes: Larger hypothesis spaces contain larger sets of interpolators, allowing minimum-smoothness-norm solutions to approximate the ultimate smoothness minimizer more closely.For Random Fourier Features, increasing the number of parameters expands the interpolating space and improves approximation to the kernel solution.
  • Random Fourier Features: In Random Fourier Features on MNIST, generalization follows double descent while the weight norm rises to the interpolation peak and then decreases toward the kernel solution’s functional norm.The weight norm asymptotes to the true functional norm as the number of features grows.

3.8 When do minimum norm predictors generalize?

Minimum-norm interpolation provides a tractable way to study generalization in noisy, over-parameterized linear models. Gradient descent initialized at the origin aligns with this interpolating solution, connecting optimization to the selected predictor.

  • Minimum-norm interpolation: In noisy over-parameterized linear regression, least squares yields a minimum-norm interpolator rather than the classical non-interpolating regularized solution.The model assumes y_i = ⟨β*, x_i⟩ + ϵ_i with d > n, and the interpolator is expressed using the data matrix pseudoinverse.
  • Generalization: Benign over-fitting studies identify settings where interpolating predictors achieve optimal or near-optimal predictions despite noisy data.Recent work has developed spectral characterizations and analyzed interpolation across linear and kernel models.
  • Generalization: Minimum-norm solutions have special properties that can support generalization in over-parameterized linear and kernel models.These models contain manifolds of interpolating solutions, but minimum-norm selection distinguishes a particular predictor.
  • Optimization and selection: Gradient descent or stochastic gradient descent initialized at the origin converges to the minimum-norm interpolator in over-parameterized linear and kernel models.The optimization path remains in the span of the training examples, whose intersection with the interpolating set is the minimum-norm solution.

3.10 Is deep learning kernel learning? Transition to linearity in wide neural networks.

The paper examines whether wide neural networks become kernel machines by transitioning to linearity in their parameters. For certain architectures this transition yields a constant neural tangent kernel, but output nonlinearities and bottlenecks can prevent it, and the phenomenon is not required for optimization.

  • Scope: Neural-network generalization is described as robust across architectures, optimization methods, and datasets, while many training details matter for state-of-the-art performance.The broader interpretation remains qualified: kernel equivalence may hold only in some interesting and practical regimes.
  • Transition to linearity: Wide neural networks with linear output layers can transition to parameter-space linearity, making their behavior equivalent to kernel-machine training in certain regimes.The transition occurs for a range of infinitely wide architectures around a random initialization.
  • Neural tangent kernel: The neural tangent kernel is K(x,z)(w) = ⟨∇_w f(w; x), ∇_w f(w; z)⟩, a positive semidefinite kernel induced by the parameter-gradient embedding.It is the linear kernel in the embedding space of parameter gradients.
  • Mechanism: The transition to linearity follows structural scaling in which the Hessian’s spectral norm is smaller than the gradient’s scale in high dimensions.For general deep networks, the argument relies on structural differences related to the scaling of 2-norms and infinity-norms.
  • Failure modes: A smooth nonlinear output layer with nonzero second derivative prevents the tangent kernel from becoming constant as width tends to infinity.A single narrow bottleneck layer can have the same effect when nonlinear activations occur in deeper layers.
  • Optimization: Transition to linearity is not necessary for optimization, so successful gradient-based training need not depend on this infinite-width phenomenon.The paper explicitly considers neural networks that could remain optimizable even without the transition.

4 The wonders of optimization

Over-parameterization changes optimization landscapes from locally convex, isolated-minimum settings to non-convex landscapes with global-minimum manifolds, where PL* supports interpolation and gradient-method convergence. Interpolation also explains exponential SGD convergence and computational advantages below a critical batch size.

  • From convexity to the PL* condition: Over-parameterized landscapes generically have positive-dimensional manifolds of global minimizers and are not even locally convex.This contrasts with classical landscapes containing isolated local minima and local convexity around each minimum.
  • From convexity to the PL* condition: The PL condition is a first-order inequality that can guarantee gradient-descent convergence within a sufficiently large ball.Unlike convexity, it is compatible with curved manifolds of minimizers but requires knowledge of the global minimum value.
  • From convexity to the PL* condition: Removing L(w*) yields PL*, whose validity on a sufficiently large ball implies an interpolating solution and exponential convergence of GD and SGD.In sufficiently wide neural networks, kernel-eigenvalue control can establish PL* on fixed-radius balls; Hessian and transformation control extend convergence results to nonlinear last layers.
  • Efficient optimization by SGD: Interpolation causes automatic variance reduction because per-example losses approach zero, enabling fixed-step-size SGD to converge exponentially for convex losses.Under under-parameterization, conflicting constraints leave nonzero mini-batch variance and require additional algorithmic ingredients.
  • Efficient optimization by SGD: For mini-batches m ≤ m*, one SGD iteration is equivalent to m batch-one iterations, whereas m > m* saturates at the effectiveness of m* or full-batch GD.The critical batch size separates linear scaling from saturation.
  • Efficient optimization by SGD: m* is typically below 100 for kernel methods and essentially independent of n, yielding an O(n) computational advantage for small-batch SGD over GD.For n = 10^6 and m* = 10, the stated advantage is a factor of 10^5.
  • Efficient optimization by SGD: The convergence analysis for SGD’s advantage is established in the convex interpolated setting, while available PL* bounds are not tight enough to show an unambiguous advantage over GD.The paper notes that empirical evidence suggests analogous results for neural networks.

5 Odds and ends

Cross-entropy makes exact interpolation occur only at infinite margins, complicating optimization analysis and making practical interpolation unlikely. Yet square-loss classification can perform at least as well as, or slightly better than, cross-entropy, while interpolation also offers a picture of adversarial examples as sparse error basins.

  • Square loss for training in classification?: Cross-entropy reaches zero loss only when y_i f(x_i) = ∞, so interpolation occurs at infinity and optimization escapes every fixed-radius ball.Its infinite solution norm also prevents a transition-to-linearity analysis covering the whole optimization path.
  • Square loss for training in classification?: Convergence is much slower under cross-entropy than under square loss, making interpolation unlikely in practice.
  • Square loss for training in classification?: Theoretical and empirical evidence challenges the view that cross-entropy is superior: square loss is at least as good or slightly better across many classification tasks.Empirical evaluations covered Natural Language Processing, Speech Recognition, and Computer Vision.
  • Interpolation and adversarial examples: Interpolation frames adversarial examples as incorrect-classification basins surrounding noisy or misclassified data points.The basins can be everywhere dense while occupying negligible volume as sample size grows.
  • Interpolation and adversarial examples: Random perturbations usually avoid adversarial basins, whereas targeted optimization methods such as PCG can find them.The paper notes that other explanations may also contribute to adversarial examples.

6 Summary and thoughts

The paper summarizes modern over-parameterized learning and identifies unresolved questions about inverse methods, optimization-induced generalization, kernel equivalence, early stopping, and depth. It presents interpolation as a useful organizing perspective while emphasizing that major theoretical gaps remain.

  • Summary and thoughts: Modern over-parameterized regimes differ sharply from classical regimes in generalization curves, optimization geometry, and the structure of minimizers.The summary table contrasts U-shaped versus descending curves, locally unique minimizers versus manifolds, and local versus global optimization behavior.
  • Inverse and direct methods: Why inverse methods outperform direct methods such as nearest neighbors remains a central unresolved question.Kernel machines appear to outperform Nadaraya-Watson classifiers using the same kernel family despite sharing the same functional form.
  • Why does optimization align with statistics?: Optimization selects parameters from a distribution over interpolating solutions, but why these selected parameters generalize remains poorly understood for deep learning.Interpolation helps isolate this question by removing the trade-off between inductive bias and empirical loss.
  • Early stopping vs. interpolation: Early stopping is often computationally necessary, while its statistical trade-offs in non-convex over-parameterized regimes remain murky.For standard Laplacian and Gaussian kernel machines, early stopping provides at best a modest generalization improvement.
  • Are deep neural networks kernel machines?: Very wide neural networks can be equivalent to kernel machines in certain regimes, but the relationship between practical networks and kernels remains unsettled.Possible accounts include non-kernel-replicable performance, data-dependent kernels, and effective Neural Tangent Kernel approximations.
  • The role of depth: The importance of depth is still poorly understood, and increasing depth can have effects unlike increasing width, with very deep networks sometimes inferior.The paper notes that width generally improves observed performance more consistently than depth.
Loading 2105.14368v1…