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

Published in

Acta Numerica(2021)

External Links:

Generate Graph DownloadPDF

TL;DR

Just as a physical prism separates colours 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.

Abstract

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-parametrization. Interpolation corresponds to fitting data, even noisy data, exactly. Over-parametrization enables interpolation and provides flexibility to select a suitable interpolating model. As we will see, just as a physical prism separates colours 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 in the belief and hope that clearer understanding of these issues will bring us a step closer towards a general theory of deep learning and machine learning.

Authors

M. Belkin

2 papers

References110 items

Deep learning: a statistical viewpoint

Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity

Theoretical Insights Into Multiclass Classification: A High-dimensional Asymptotic View

Do Deeper Convolutional Networks Perform Better?

Failures of model-dependent generalization bounds for least-norm interpolation

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

Published in

Acta Numerica(2021)

External Links:

Generate Graph DownloadPDF

TL;DR

Abstract

Authors

M. Belkin

2 papers

References110 items

Deep learning: a statistical viewpoint

Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity

Theoretical Insights Into Multiclass Classification: A High-dimensional Asymptotic View

Do Deeper Convolutional Networks Perform Better?

Failures of model-dependent generalization bounds for least-norm interpolation

On the linearity of large non-linear models: when and why the tangent kernel is constant

Finite Versus Infinite Neural Networks: an Empirical Study

When do neural networks outperform kernel methods?

Kernel methods through the roof: handling billions of points efficiently

Evaluation of Neural Architectures Trained with Square Loss vs Cross-Entropy in Classification Tasks

On Uniform Convergence and Low-Norm Interpolation Learning

Classification vs regression in overparameterized regimes: Does the loss function matter?

A brief prehistory of double descent

Neural Kernels Without Tangents

Loss landscapes and optimization in over-parameterized non-linear systems and neural networks

Toward a theory of optimization for over-parameterized systems of non-linear equations: the lessons of deep learning

Backward Feature Correction: How Deep Learning Performs Deep Learning

Improved protein structure prediction using potentials from deep learning

In Defense of Uniform Convergence: Generalization via derandomization with an application to interpolating predictors

Deep double descent: where bigger models and more data hurt

Harnessing the Power of Infinitely Wide Deep Nets on Small-data Tasks

Overparameterized neural networks implement associative memory

Deep Equilibrium Models

The Generalization Error of Random Features Regression: Precise Asymptotics and the Double Descent Curve

Benign overfitting in linear regression

The implicit bias of gradient descent on nonseparable data

Kernel and Rich Regimes in Overparametrized Models

Understanding overfitting peaks in generalization error: Analytical risk curves for l2 and l1 penalized interpolation

On the number of variables to use in principal component regression

High Dimensional Classification via Empirical Risk Minimization: Improvements and Optimality

High Dimensional Classification via Regularized and Unregularized Empirical Risk Minimization: Precise Error and Optimal Loss.

Adversarial Examples Are Not Bugs, They Are Features

Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks

Harmless interpolation of noisy data in regression

Surprises in High-Dimensional Ridgeless Least Squares Interpolation

Two models of double descent for weak features

Wide neural networks of any depth evolve as linear models under gradient descent

On the Expressive Power of Kernel Methods and the Efficiency of Kernel Learning by Association Schemes

Uniform convergence may be unable to explain generalization in deep learning

Reconciling modern machine-learning practice and the classical bias–variance trade-off

Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?

Gradient Descent Finds Global Minima of Deep Neural Networks

On exponential convergence of SGD in non-convex over-parametrized learning

Accelerating SGD with momentum for over-parameterized learning

A jamming transition from under- to over-parametrization affects generalization in deep learning

Gradient Descent Provably Optimizes Over-parameterized Neural Networks

Numerical Optimization

Just Interpolate: Kernel "Ridgeless" Regression Can Generalize

Does data interpolation contradict statistical optimality?

Neural Tangent Kernel: Convergence and Generalization in Neural Networks

Kernel Machines That Adapt To Gpus For Effective Large Batch Training

Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate

Reflections After Refereeing Papers for NIPS

To understand deep learning we need to understand kernel learning

The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning

One Pixel Attack for Fooling Deep Neural Networks

Towards Deep Learning Models Resistant to Adversarial Attacks

Understanding deep learning requires rethinking generalization

Robustness of classifiers: from adversarial to random noise

Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition

An Analysis of Deep Neural Network Models for Practical Applications

Explaining the Success of AdaBoost and Random Forests as Interpolating Classifiers

Adam: A Method for Stochastic Optimization

In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning

SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives

Convex Optimization: Algorithms and Complexity

Intriguing properties of neural networks

Accelerating Stochastic Gradient Descent using Predictive Variance Reduction

Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm

A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets

Non-Asymptotic Analysis of Stochastic Approximation Algorithms for Machine Learning

Random Features for Large-Scale Kernel Machines

Comment: Boosting Algorithms: Regularization, Prediction and Model Fitting

On Early Stopping in Gradient Descent Learning

A Randomized Kaczmarz Algorithm with Exponential Convergence

Beyond the point cloud: from transductive to semi-supervised learning

Introduction to Statistical Learning Theory

The Elements of Statistical Learning: Data Mining, Inference, and Prediction

Rademacher and Gaussian Complexities: Risk Bounds and Structural Results

A Distribution-Free Theory of Nonparametric Regression (Springer Series in Statistics)

The Hilbert Kernel Regression Estimate

A decision-theoretic generalization of on-line learning and an application to boosting

Boosting the margin: A new explanation for the effectiveness of voting methods

Neural Networks and the Bias/Variance Dilemma

Gauss and the Invention of Least Squares

A Correspondence Between Bayesian Estimation on Stochastic Processes and Smoothing by Splines

A two-dimensional interpolation function for irregularly-spaced data

https://www.cambridge.org/core. IP address: 54.70.40.11,

A jamming transition from under- to over-parametrization affects loss landscape and generalization

Tutorial on deep learning. Available at https://simons.berkeley.edu/talks/ruslan-salakhutdinov-01-26-2017-1

Reflections on random kitchen

Scattered Data Approximation

International Conference on Learning Representations (ICLR)

Everything old is new again: a fresh look at historical approaches in machine learning

A Distribution-Free Theory of Nonparametric Regression

PERT – Perfect Random Tree Ensembles

100

The Nature of Statistical Learning Theory

101

The Nature of Statistical Learning

102

Simplicial multivariable linear interpolation

103

Nearest neighbor pattern classification

104

Smooth regression analysis

105

On Estimating Regression

106

Gradient methods for minimizing functionals

107

A topological property of real analytic subsets

108

Angenäherte Auﬂösung von Systemen linearer Gleichungen

109

CAMBRIDGE MONOGRAPHS ON APPLIED AND COMPUTATIONAL MATHEMATICS

110

We note that inductive biases are present in any inverse problem

Field of Study

Computer ScienceMathematics

Journal Information

Name

Acta Numerica

Page

203 - 248

Volume

Venue Information

Name

Acta Numerica

Type

journal

URL

https://www.cambridge.org/core/journals/acta-numerica/all-issues

Alternate Names

Acta Numer