Why does deep and cheap learning work so well?

Abstract

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.

Replaced to match version published in Journal of Statistical Physics: https://link.springer.com/article/10.1007/s10955-017-1836-5 Improved refs & discussion, typos fixed. 16 pages, 3 figs

References in corpus (2)

• Solving the Quantum Many-Body Problem with Artificial Neural Networks
• A class of quantum many-body states that can be efficiently simulated

Cited by in corpus (113)

• Quantum Convolutional Neural Networks
• Recent Advances and Applications of Deep Learning Methods in Materials Science
• Parameterized quantum circuits as machine learning models
• A high-bias, low-variance introduction to Machine Learning for physicists
• Deep physical neural networks enabled by a backpropagation algorithm for arbitrary physical systems
• Social physics
• The Challenge of Machine Learning in Space Weather Nowcasting and Forecasting
• Continuous-variable quantum neural networks
• Hierarchical quantum classifiers
• Machine Learning Topological States
• Image sensing with multilayer, nonlinear optical neural networks
• Equivalence of restricted Boltzmann machines and tensor network states
• Identifying Quantum Phase Transitions using Artificial Neural Networks on Experimental Data
• Approximating quantum many-body wave-functions using artificial neural networks
• Universal Function Approximation by Deep Neural Nets with Bounded Width and ReLU Activations
• A test case for application of convolutional neural networks to spatio-temporal climate data: Re-identifying clustered weather patterns
• Training convolutional neural networks to estimate turbulent sub-grid scale reaction rates
• Mutual Information, Neural Networks and the Renormalization Group
• Deep learning and the Schrödinger equation
• Quantum Machine Learning for Chemistry and Physics
• Neural Network Renormalization Group
• Machine Learning of Explicit Order Parameters: From the Ising Model to SU(2) Lattice Gauge Theory
• Tree Tensor Networks for Generative Modeling
• Review: Deep Learning in Electron Microscopy
• Discriminative Cooperative Networks for Detecting Phase Transitions
• Information Perspective to Probabilistic Modeling: Boltzmann Machines versus Born Machines
• Deep Learning and AdS/CFT
• Machine Learning for Condensed Matter Physics
• Learning to fail: Predicting fracture evolution in brittle material models using recurrent graph convolutional neural networks
• Neural network wave functions and the sign problem
• Applying Deep Learning to Fast Radio Burst Classification
• Machine Learning Spatial Geometry from Entanglement Features
• Scale-invariant Feature Extraction of Neural Network and Renormalization Group Flow
• How deep is deep enough? -- Quantifying class separability in the hidden layers of deep neural networks
• Supervised Learning with Projected Entangled Pair States
• Machine Learning meets Quantum Foundations: A Brief Survey
• Sleep-wake classification via quantifying heart rate variability by convolutional neural network
• A prediction and behavioural analysis of machine learning methods for modelling travel mode choice
• Efficient Modelling of Trivializing Maps for Lattice ${\varphi }^4$ Theory Using Normalizing Flows: A First Look at Scalability
• Parameters Estimation for the Cosmic Microwave Background with Bayesian Neural Networks
• Improving Galaxy Clustering Measurements with Deep Learning: analysis of the DECaLS DR7 data
• The Presence and Absence of Barren Plateaus in Tensor-network Based Machine Learning
• Matrix Product Operators for Sequence to Sequence Learning
• Machine Learning Holographic Mapping by Neural Network Renormalization Group
• Generative Tensor Network Classification Model for Supervised Machine Learning
• Revisiting Efficient Multi-Step Nonlinearity Compensation with Machine Learning: An Experimental Demonstration
• Thermodynamics and Feature Extraction by Machine Learning
• Drawing Phase Diagrams of Random Quantum Systems by Deep Learning the Wave Functions
• Partial Scanning Transmission Electron Microscopy with Deep Learning
• Precision Machine Learning
• Improving Electron Micrograph Signal-to-Noise with an Atrous Convolutional Encoder-Decoder
• Efficient approximation of high-dimensional functions with neural networks
• Neural network reconstructions for the Hubble parameter, growth rate and distance modulus
• Is Deep Learning a Renormalization Group Flow?
• Deep learning black hole metrics from shear viscosity
• Renormalization Group Flow as Optimal Transport
• Extracting Critical Exponent by Finite-Size Scaling with Convolutional Neural Networks
• Enforcing constraints for interpolation and extrapolation in Generative Adversarial Networks
• Geometry of energy landscapes and the optimizability of deep neural networks
• Observational cosmology with Artificial Neural Networks
• Hierarchical quantum circuit representations for neural architecture search
• Machine-Learning Non-Conservative Dynamics for New-Physics Detection
• Identifying Product Order with Restricted Boltzmann Machines
• Provably scale-covariant continuous hierarchical networks based on scale-normalized differential expressions coupled in cascade
• Explicitly antisymmetrized neural network layers for variational Monte Carlo simulation
• Bayesian Renormalization
• The Loss Surface of XOR Artificial Neural Networks
• Impossibility Results in AI: A Survey
• Language Design as Information Renormalization
• Variational Neural-Network Ansatz for Continuum Quantum Field Theory
• Neural Network flows of low q-state Potts and clock Models
• Do Neural Nets Learn Statistical Laws behind Natural Language?
• Neural Monte Carlo Renormalization Group
• An Active Galactic Nucleus Recognition Model based on Deep Neural Network
• A Hyperparameter Study for Quantum Kernel Methods
• RG-Flow: A hierarchical and explainable flow model based on renormalization group and sparse prior
• Deep neural networks have an inbuilt Occam's razor
• Warwick Electron Microscopy Datasets
• Three Learning Stages and Accuracy-Efficiency Tradeoff of Restricted Boltzmann Machines
• Decomposing neural networks as mappings of correlation functions
• On the descriptive power of Neural-Networks as constrained Tensor Networks with exponentially large bond dimension
• Dark energy reconstruction analysis with artificial neural networks: Application on simulated Supernova Ia data from Rubin Observatory
• Entropy Regularized Reinforcement Learning Using Large Deviation Theory
• Wavelet Conditional Renormalization Group
• Statistical modeling of equilibrium phase transition in confined fluids
• A Flexible Framework for Anomaly Detection via Dimensionality Reduction
• Machine learning algorithms based on generalized Gibbs ensembles
• Short sighted deep learning
• Investigation of Finite-size 2D Ising Model with a Noisy Matrix of Spin-Spin Interactions
• Identification of Invariant Sensorimotor Structures as a Prerequisite for the Discovery of Objects
• Post-synaptic potential regularization has potential
• Quantum System Compression: A Hamiltonian Guided Walk Through Hilbert Space
• Deep Neural Networks for Automatic Speaker Recognition Do Not Learn Supra-Segmental Temporal Features
• Thermodynamics of the Ising model encoded in restricted Boltzmann machines
• Exploring explicit coarse-grained structure in artificial neural networks
• Machine Learning S-Wave Scattering Phase Shifts Bypassing the Radial Schrödinger Equation
• Categorical Representation Learning and RG flow operators for algorithmic classifiers
• Tensor networks and efficient descriptions of classical data
• Quaternion-based machine learning on topological quantum systems
• Machine learning, quantum chaos, and pseudorandom evolution
• When and Why Metaheuristics Researchers Can Ignore "No Free Lunch" Theorems
• Lateral predictive coding revisited: Internal model, symmetry breaking, and response time
• Comparison of generalised additive models and neural networks in applications: A systematic review
• On the approximation of functions by tanh neural networks
• An Enquiry on similarities between Renormalization Group and Auto-Encoders using Transfer Learning
• On functions computed on trees
• Constructive expansion for quartic vector fields theories. I. Low dimensions
• Efficiency of the hidden fermion determinant states Ansatz in the light of different complexity measures
• inclusiveAI: A machine learning representation of the $F_2$ structure function over all charted $Q^2$ and $x$ range
• Dynamic neuron approach to deep neural networks: Decoupling neurons for renormalization group analysis
• Dynamical transition in controllable quantum neural networks with large depth
• Hybrid Quantum-Classical Clustering for Preparing a Prior Distribution of Eigenspectrum
• Response time of lateral predictive coding and benefits of modular structures