Why Does Deep and Cheap Learning Work So Well?

By Henry W. Lin, Max Tegmark. 2016

645 citations recorded by the source corpus.

We show how the success of deep learning could depend not only on mathematics but also on physics: although well-known mathematical theorems guarantee that neural networks can approximate arbitrary functions well, the class of functions of practical interest can frequently be approximated through “cheap learning” with exponentially fewer parameters than generic ones. We explore how properties frequently encountered in physics such as symmetry, locality, compositionality, and polynomial log-probability translate into exceptionally simple neural networks. We further argue that when the statistical process generating the data is of a certain hierarchical form prevalent in physics and machine learning, a deep neural network can be more efficient than a shallow one. We formalize these claims using information theory and discuss the relation to the renormalization group. We prove various “no-flattening theorems” showing when efficient linear deep networks cannot be accurately approximated by shallow ones without efficiency loss; for example, we show that n variables cannot be multiplied using fewer than 2n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^n$$\end{document} neurons in a single hidden layer.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics, Scaling & Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

In Scaling & Learning Theory

Citations in the corpus

A Closer Look at Memorization in Deep Networks (2017, background): “Lin & Tegmark (2016) further suggest that the priors of deep learning are well suited to the physical world.”
Bayesian Deep Convolutional Networks with Many Channels are Gaussian Processes (2018, background): “For instance, properties of NNs which are believed to make them well suited to modeling the world include: hierarchy and compositionality (Lin et al., 2017; Poggio et al., 2017), Markovian dynamics (Tiňo et al.”
The Challenge of Machine Learning in Space Weather: Nowcasting and Forecasting (2019, background): “The reader interested in the theme of why machine learning works so well in physics and why deep learning often works better than shallow learning should consult, for example, Lin et al. (2017) and Poggio et al. (2017).”
A free energy principle for a particular physics (2019, background): “A working definition of renormalization involves three elements (Lin et al., 2017): vectors of random variables, a course-graining operation and a requirement that the operation does not change the functional form of the Lagrangian (or equivalent description of the dynamics).”
Deep Convolutional Neural Network for Inverse Problems in Imaging (2016, background): “Researchers have begun to investigate the link between conventional approaches and deep learning networks [28]–[31].”
Tensor Networks for Dimensionality Reduction and Large-scale Optimization: Part 2 Applications and Future Perspectives (2017, background): “…within the theory of TNs, which often employ physical constraints of locality, symmetry, compositional hierarchical functions, entropy, and polynomial log-probability, that are imposed on the measurements or input training data [Chen et al., 2017, Lin and Tegmark, 2016, Poggio et al., 2016].”
Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations (2019, background): “The effectiveness of this simple idea may be related to the remarks put forth by Lin, Tegmark and Rolnick [30] and raises many interesting questions to be quantitatively addressed in future research.”
Doing the Impossible: Why Neural Networks Can Be Trained at All (2018, background): “For example, some have addressed how, given that the space of possible functions is so large, can any ﬁnite computational stage do a good job approximating physical systems [14].”
Artificial intelligence and machine learning approaches to energy demand-side response: A systematic review (2020, background): “14 not fully understood why they work so well in certain types of problems [219], and it should be noted that arbitrarily increasing the depth of an ANN might not always yield the best results [220].”
Recent advances and applications of deep learning methods in materials science (2021, background): “However, it is important to note that the theorem doesn ’ t guarantee that the functions can be learnt easily 52 .”
Random forest as a generic framework for predictive modeling of spatial and spatio-temporal variables (2018, background): “…can be used to represent inherently634 complex ecological systems, and because computing costs are exponentially decreasing, it can be said that635 most of the generic Machine Learning techniques are in fact ‘cheap’ and have quickly become mainstream636 data science methods (Lin et al., 2017).”
Universal Function Approximation by Deep Neural Nets with Bounded Width and ReLU Activations (2017, background): “Much of the work to date has focused on the problem of explaining and quantifying the expressivity − the ability to approximate a rich class of functions − of deep neural nets [1, 7, 8, 10, 11, 12, 14, 15, 16, 17].”