Why does deep and cheap learning work so well?

Henry W. Lin; Max Tegmark; David Rolnick

Source-linked AI summary

Why does deep and cheap learning work so well?

Henry W. Lin, Max Tegmark, David Rolnick

arXiv:1608.08225v4Aug 29, 2016cond-mat.dis-nncs.LGcs.NEstat.ML

TL;DR

The paper asks why neural networks can solve practical tasks with exponentially fewer parameters than generic function representations. It uses a physics-based analysis of symmetry, locality, polynomial log-probability, and hierarchical generation, showing that these structures support cheap learning and can make deep networks more efficient than shallow ones.

Problem
The central question is how feasible neural networks approximate practical functions when the space of possible functions is exponentially larger than the space of available networks.
Method
The paper analyzes probability distributions through Hamiltonians and information-theoretic, compositional, and renormalization-group perspectives.
Results
A 4-neuron multiplication approximator yields fixed-size polynomial approximations independent of target accuracy, while hierarchical compositional functions can favor efficient deep networks over flattened ones.
Takeaways & Limitations
Physics-inspired structure and hierarchical generation identify subclasses of distributions for which neural networks can achieve cheap learning and depth-related efficiency.

Abstract

from arXiv · show

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 2^n neurons in a single hidden layer.

I. INTRODUCTION

The paper asks why neural networks with feasible parameter counts can solve problems whose generic function spaces are exponentially larger. It argues that physics-inspired structure and hierarchical data generation make many practical distributions especially simple and favorable to deep learning.

Motivation: Deep learning remains analytically underexplained despite strong empirical performance across applications.The paper seeks analytic insight into both its successes and shortcomings.
Motivation: Neural networks are evaluated here primarily by expressibility and efficiency, rather than learnability.The paper frames its central question around approximating functions with far fewer resources than generic representations require.
The swindle: 256^1000000 possible grayscale images would define an arbitrary classification function using vastly more values than feasible neural networks contain.Yet networks with thousands or millions of parameters can classify such images effectively, motivating the concept of cheap learning.
The swindle: The paper’s physics perspective targets locality, symmetry, polynomial log-probability, and related structure as sources of compact approximations.These properties favor exceptionally simple probability distributions and neural networks.
Depth: Hierarchical generative processes can make deep networks more efficient because inference reverses a compositional hierarchy.The paper connects this depth advantage to information theory and renormalization-style reasoning.

A. Probabilities and Hamiltonians

The paper rewrites conditional probabilities in Hamiltonian form, making their structure easier to analyze. Classification probabilities can then be obtained by computing Hamiltonians with a neural network and applying a final softmax layer.

Probabilities and Hamiltonians: Statistical physics interprets −ln p as surprisal and H_y(x) as the Hamiltonian, or energy of x given y.This dictionary converts probability modeling into a Boltzmann-form representation.
Probabilities and Hamiltonians: The Hamiltonian representation is useful because Hamiltonians often have simple evaluable structure and connect naturally to renormalization.The paper uses this recasting to relate deep learning to statistical physics.
Neural-network representation: A standard feedforward network maps vectors through successive affine transformations and nonlinear operators.The listed operators include elementwise nonlinearities, max-pooling, and softmax.
Neural-network representation: Computing the Hamiltonian vector with an n-layer network followed by softmax yields the desired classification probability vector.The μ-vector becomes the bias term in the final layer.

C. What Hamiltonians can be approximated by feasible neural networks?

Universal approximation does not ensure feasible network size, so the paper focuses on structured Hamiltonians such as low-order polynomials. It shows that smooth nonlinear networks can approximate polynomial computations with size independent of target accuracy.

Why structure matters: Universal approximation theorems guarantee arbitrary accuracy but not a feasible network size for generic functions.There are 2^(2^n) Boolean functions of n variables, making generic representation exponentially expensive.
Why structure matters: Physics and machine learning favor Hamiltonians that are sparse, symmetric, and low-order polynomials.This structured subclass is much smaller than the space of arbitrary functions.
Continuous input variables: A 2–4–1 network can approximate multiplication arbitrarily well using any smooth non-linear activation with a suitable nonzero second derivative.Scaling the input and compensating the output improves accuracy, though practical training cannot use arbitrarily large weights.
Continuous input variables: Any multivariate polynomial can be approximated to accuracy better than ϵ by a fixed-size network independent of ϵ.The size scales with the number of multiplications, typically by a factor slightly larger than 4.
Continuous input variables: This fixed-size accuracy bound is stronger than classic universal-approximation results, which permit network size to diverge as ϵ approaches zero.An earlier ϵ-independent result required a pathological activation function.

2. Discrete input variables

Binary inputs simplify polynomial representations because powers collapse to first powers, allowing arbitrary functions on n bits to be represented by finite products. A three-layer network can then evaluate these products and combine them.

Discrete input variables: For bit inputs, x_i^2 = x_i, so only products containing distinct variables are needed.The resulting finite expansion contains 2^n terms.
Discrete input variables: The 2^n coefficients suffice to exactly parameterize an arbitrary function H_y(x) on n-bit strings.There are exactly 2^n possible bit strings.
Discrete input variables: A three-layer network computes bit products in its middle layer, then forms their linear combination and applies softmax.This works because a product of bits can be determined from their sum.
Discrete input variables: For ten-decimal-place accuracy, the sigmoid construction requires only β > D ln 10 ≈ 23.The exponential saturation of the sigmoid makes moderately large β sufficient in practice.
Discrete input variables: Polynomial representations are not universally compact: generic degree-d polynomials in n continuous variables contain (n+d)!/(n!d!) coefficients.Thus polynomial structure alone can still become unmanageable.

1. Low polynomial order

Physics and machine-learning functions often have simplifying structure: low-order polynomial form, locality, and symmetry can sharply reduce the parameters or computation needed for neural-network approximation. These assumptions are useful but application-dependent and may fail after variables are hidden or transformed.

Hamiltonians in physics are typically low-order polynomials, often with degree 2 to 4.
O(n^4) polynomial coefficients can describe many examples, rather than infinitely many or exponentially many parameters.
Gaussian and maximum-entropy models imply that H = −ln p is a polynomial whose degree reflects the constrained moments.
Translation, rotation, convolution, and Fourier-transform operations provide low-degree or linear structures relevant to image classification.
These structural arguments require case-by-case validation because hidden variables, generic transformations, limited data, and optimization failures can undermine the expected simplicity.
Locality forces most interaction coefficients to vanish, making the number of nonzero coefficients grow linearly with n.
Symmetry reduces parameter counts and can reduce computation: translationally symmetric linear maps are convolutions computable with n log2 n rather than n2 multiplications.

A. Hierarchical processess

Many physical and machine-learning data sets arise through hierarchical generative processes in which simpler causal steps are composed. Deep networks can efficiently reverse and implement these steps, while the observed output may contain far more information than the compact process that generated it.

Hierarchical processes: Physical systems exhibit hierarchical structure, with complex objects and causal processes formed through sequences of simpler steps.
Hierarchical processes: The generative hierarchy is modeled as a Markov chain in which each level depends probabilistically on its causal predecessor.
Hierarchical processes: Examples include cosmological parameters generating sky observations and a contrived image pipeline generating a cat-or-dog image through successive transformations.
Hierarchical processes: Learning reverses the hierarchy by estimating p(y0|yn), such as the posterior over cosmological parameters or the probability that an image is a cat.
Resolving the swindle: Decomposing generation into simpler steps avoids describing an arbitrary high-dimensional distribution directly, because each step can be specified with fewer parameters.
Resolving the swindle: A random output can contain much more information than the compact instruction or generative process that produced it.
Resolving the swindle: Stacking networks for the individual steps can implement the complete generative process efficiently, although most arbitrary functions remain indistinguishable from random ones.

C. Sufficient statistics and hierarchies

Hierarchical generative processes can be optimally reversed one step at a time through functions acting on minimal sufficient statistics. The resulting inference function is compositional and may require depth for efficient approximation.

Sufficient statistics: Minimal sufficient statistics at successive hierarchy levels can be related by functions that optimally reverse each generative step.Theorem 2 states that T_i = f_i ◦ T_{i+1}, preserving all information about the upper level that survives the Markov process.
Hierarchical inference: The inference function can be constructed as a composition of the stepwise functions, with the endpoint functions defined from the sufficient statistics.Corollary 2 defines f_0(T_0) = P(y_0|T_0) and f_n = T_{n−1}.
Hierarchical inference: Efficient approximation of the compositional inference function may require ≳n hidden layers.The paper connects the required depth to the structure of the generative process rather than to expressibility alone.
Information flow: Information flows down the hierarchy with losses from random processes, while optimal reverse inference loses no additional information.The distilled vectors represent successive levels of the hierarchy, with x as the observed endpoint.

D. Approximate information distillation

Approximate information distillation can trade a limited loss of mutual information for a large reduction in computational complexity. Renormalization provides a physics-based example in which coarse-graining suppresses irrelevant parameters while retaining features useful for classification.

Approximate information distillation: Nearly sufficient statistics can be useful when they retain most relevant information while substantially reducing computational complexity.The paper notes that H_y(f(x)) may be easier to implement than H_y(x), despite some mutual-information loss.
Renormalization: Renormalization is defined through coarse-graining that preserves the Hamiltonian’s form while changing its parameters.The framework involves random variables, a coarse-graining operation R, and invariance of the Hamiltonian functional form.
Renormalization: Standard renormalization acts as a supervised feature extractor for long-wavelength or macroscopic properties, not as unsupervised pattern-finding.The relevant features must be specified for an effective field theory approximation to be meaningful.
Renormalization: Repeated coarse-graining makes parameters y_i with i ≥2 decay exponentially, allowing the first few parameters to represent the retained signal.This yields a finite, bounded neural-network computation when classification depends only on coarse-grained variables.
Renormalization: The renormalization-group flow can be viewed as classifying the long-range behavior of statistical systems through their fixed-point structure.The paper connects fixed points and phase classification to pattern recognition of macroscopic behavior.

F. No-flattening theorems

Although deep linear networks can be flattened without changing the represented function, flattening can increase synapse requirements and harm efficiency. No-flattening results quantify this cost for sparse factorizations, Fourier transforms, low-rank multiplication, and related constructions.

Definitions: Flattening cost measures how much optimal flattening increases neuron count and synapse count, establishing when shallow representations lose efficiency.The paper defines neuron- and synapse-efficient flattenings and calls results with cost greater than one no-flattening theorems.
Linear networks: Deep linear networks remain expressively equivalent to single-layer networks, but flattening can still alter learnability and resource efficiency.Successive matrix products represent one matrix, yet sparse factorizations may use substantially fewer synapses.
Fourier transforms: FFT flattening increases synapses from O(n log n) to O(n^2), producing flattening cost C_s = O(n / log n) ∼ O(n).The same depth advantage applies to Fast Wavelet and Fast Walsh-Hadamard transforms.
Matrix multiplication: A rank-k matrix uses n^2 synapses when flattened but 2nk in a one-hidden-layer factorization, giving C_s = n/2k when k < n/2.The factorization A = BC uses B of size k × n and C of size n × k.
Sparse matrices: For sufficiently large n, flattening multiplication by sparse random matrices is highly inefficient because the product becomes much less sparse.The bound C_s ≤ 1/2p is asymptotically saturated when n ≫ 1/p^2.

H. A polynomial no-flattening theorem

The paper proves that multiplying n variables requires exponentially many neurons when flattened into one hidden layer, while a deep binary-tree network uses only linear-size resources. This establishes a concrete no-flattening gap for polynomial computations.

H. A polynomial no-flattening theorem: 2^n neurons are necessary for a single-hidden-layer network to multiply n variables, whereas a deep network can use approximately 4n neurons.For n=32, the shallow network requires 4,294,967,296 neurons, compared with 160 for the deep network.
H. A polynomial no-flattening theorem: A binary-tree architecture evaluates the monomial x_1x_2...x_n with n multiplication gates arranged across log_2 n layers.Each multiplication gate uses about four neurons, yielding linear total size when n is a power of two.
H. A polynomial no-flattening theorem: The result extends universal-approximation claims by showing that efficient approximation depends on network organization, not merely on representability.The paper contrasts arbitrary-function approximation with fixed-size, efficiently structured approximations for relevant polynomials.
H. A polynomial no-flattening theorem: The authors identify sharper no-flattening bounds as a direction for improving the analytic understanding, capability, and robustness of deep learning.They propose placing upper and lower bounds on flattening costs for broader function classes.

Appendix A: The polynomial no-flattening theorem

Appendix A states the polynomial no-flattening theorem: under a generic smooth activation, multiplying n inputs can be approximated with 2^n hidden neurons, and no smaller single-hidden-layer network suffices.

Appendix A: The polynomial no-flattening theorem: 2^n neurons are sufficient to approximate the n-variable product to any desired accuracy with one hidden layer.The theorem assumes a generic smooth activation whose Taylor coefficients through degree n are nonzero.
Appendix A: The polynomial no-flattening theorem: 2^n neurons are also necessary, making the single-hidden-layer construction size-optimal.The appendix presents this as the smallest possible hidden-layer width for the stated activation class.
Appendix A: The polynomial no-flattening theorem: The theorem is framed as a comparison between neural-network depth and Boolean circuit complexity, where layers correspond to depth and neurons correspond to gates.Both models permit computational elements with an unlimited number of inputs.

1. Proof that 2n neurons are sufficient

The sufficiency proof constructs a 2^n-neuron hidden layer by summing activation responses over all sign configurations, causing unwanted monomials to cancel while retaining the full product term.

1. Proof that 2^n neurons are sufficient: Arbitrary accuracy follows when the network’s Taylor expansion matches the product through degree n, with higher-degree terms excluded by scaling.The factors are scaled down before approximate multiplication and the result is scaled back up.
1. Proof that 2^n neurons are sufficient: 2^n hidden neurons are constructed by enumerating every subset of the n inputs and assigning corresponding weights of ±1.The sign pattern for each neuron flips the weights of inputs belonging to its subset.
1. Proof that 2^n neurons are sufficient: Every monomial of degree at most n other than x_1...x_n cancels because it omits at least one variable whose sign can be flipped.Pairing sign configurations with opposite values for the absent variable reverses the associated contribution.
1. Proof that 2^n neurons are sufficient: The proof concludes that the sign-summed network implements the desired product gate.The coefficient analysis verifies the required cancellation and surviving product coefficient.
1. Proof that 2^n neurons are sufficient: The construction is interpreted through the sign-flip group Z_2^n, whose operators eliminate all lower-degree monomials except the full product.The resulting function approximates the product up to a normalizing constant.

2. Proof that 2n neurons are necessary

The necessity proof converts the approximation conditions into a rank argument: distinct subset-associated rows must be linearly independent, forcing at least 2^n hidden neurons.

2. Proof that 2^n neurons are necessary: The proof represents the network constraints using a 2^n × m matrix whose rows encode subset conditions.The argument seeks to show that this matrix has full row rank.
2. Proof that 2^n neurons are necessary: Assuming a nontrivial dependence among distinct subset rows leads to a contradiction after selecting a subset of maximal cardinality.The proof constructs an auxiliary vector and uses the resulting dot product to isolate the contradiction.
2. Proof that 2^n neurons are necessary: The relevant coefficient identities eliminate one term and reduce the argument to linear dependence among distinct monomials.Distinct monomials are linearly independent, contradicting the assumed row dependence.
2. Proof that 2^n neurons are necessary: Therefore, the matrix has full row rank and the hidden-layer width must satisfy m ≥ 2^n.This establishes the lower bound and completes the no-flattening theorem.