Source-linked AI summary
The power of deeper networks for expressing natural functions
David Rolnick, Max Tegmark
TL;DR
The paper asks why deeper networks can represent natural functions more efficiently despite universal approximation by shallow networks. It analyzes standard feedforward networks on polynomial approximation and proves linear-versus-exponential neuron scaling, with intermediate depth suggesting an n^{1/k} exponent and logarithmic layer requirements.
Problem
Universal approximation by single-hidden-layer networks does not explain why deeper networks can be substantially more efficient, motivating concrete resource requirements for natural polynomial classes.
Method
The paper analyzes standard feedforward networks, polynomial approximation, compositional constructions, and neuron requirements as depth varies.
Results
For n-variable sparse polynomials, shallow networks require size exponential in n, deep networks require at most linearly many neurons, and k hidden layers appear to interpolate as exp(n^{1/k}).
Takeaways & Limitations
The results suggest that practical expressibility of simple functions may require only logarithmically many layers in the number of input variables.
Takeaways & Limitations
The paper studies resources required to compute functions at fixed depth, not the training resources required to learn the corresponding weights.
Abstract
from arXiv · showhide
It is well-known that neural networks are universal approximators, but that deeper networks tend in practice to be more powerful than shallower ones. We shed light on this by proving that the total number of neurons $m$ required to approximate natural classes of multivariate polynomials of $n$ variables grows only linearly with $n$ for deep neural networks, but grows exponentially when merely a single hidden layer is allowed. We also provide evidence that when the number of hidden layers is increased from $1$ to $k$, the neuron requirement grows exponentially not with $n$ but with $n^{1/k}$, suggesting that the minimum number of layers required for practical expressibility grows only logarithmically with $n$.
1 INTRODUCTION
The paper studies why deep feedforward networks can be more powerful than shallow ones, extending prior results into concrete neuron requirements for approximating natural polynomial classes.
- Single-hidden-layer networks are universal approximators, but the required size can be extremely large.
- The paper derives resource requirements for standard feedforward networks using uniform approximation of general sparse multivariate polynomials.This extends prior work beyond Taylor approximation of products.
- Arbitrarily close approximations of simple multivariate and univariate polynomials are possible with a bounded number of neurons.
- Such polynomials are exponentially easier to approximate with deep networks than with shallow networks.
- The required number of layers for natural polynomials is at most logarithmic in the number of input variables, with the logarithm’s base determined by layer width.
2 RELATED WORK
Related work characterizes depth advantages through representational complexity, function families requiring exponential shallow width, and alternative network or circuit architectures.
- Deeper networks have greater representational power for piecewise linear decision boundaries and topological invariants.
- Input trajectories can attain exponentially greater length and curvature as network depth increases.
- Several results establish functions that require exponential width in shallow networks, while compositional functions admit much smaller deep-network approximations.
- Other work studies depth-related expressivity in sum-product networks, restricted Boltzmann machines, arithmetic circuits, and convolutional networks.
3 THE POWER OF APPROXIMATION
The paper formalizes feedforward networks and approximation notions, proves bounded-neuron approximation for polynomials, and distinguishes uniform from Taylor approximation while identifying activation-function conditions.
- Network model: The standard feedforward network is represented as a composition of affine maps and element-wise nonlinearities, with k denoting depth.
- Approximation notions: Uniform approximation requires the network’s supremum error on (−R, R)^n to be below ϵ.
- Approximation notions: Taylor approximation means that the target degree-d polynomial is the network’s dth-order Taylor polynomial about the origin.
- Approximation notions: For homogeneous polynomials, Taylor approximation implies ϵ-approximation without changing the number of neurons in any layer.
- Polynomial approximation: A fixed neuron count can achieve arbitrarily good approximations of multivariate polynomials by altering network weights.
- Activation assumptions: Nonzero Taylor coefficients through the polynomial degree are required; ReLUs do not satisfy this condition, so nonlinear polynomial approximation needs increasingly many piecewise-linear pieces.
4 THE INEFFICIENCY OF SHALLOW NETWORKS
The section compares shallow and deep networks for approximating multivariate and univariate polynomials, showing that depth can reduce neuron requirements exponentially.
- Multivariate polynomials: Uniform approximation of monomials requires exponentially more neurons in shallow networks than in deep networks.The result concerns networks with one hidden layer versus deeper networks.
- Multivariate polynomials: Polynomials with unrestricted degree and variable count can require exponentially many neurons, motivating a focus on polynomials with sparsity c.A sparsity-c polynomial is represented as the sum of c monomials and includes many natural functions.
- Multivariate polynomials: For general polynomials with subexponential sparsity, shallow uniform neuron requirements are exponentially large, while deep requirements are subexponential.The corresponding statements also hold for Taylor approximation.
- Assumptions: The results require activation functions to have suitable nonzero Taylor coefficients, though weaker assumptions can still yield exponential lower bounds.Theorem 4.1 assumes a nonzero dth Taylor coefficient, while other results assume nonzero coefficients through degree d or 2d.
- Univariate polynomials: Univariate degree-d polynomials need at most d + 1 neurons in a shallow network, whereas xd can be approximated with at most 7⌈log2(d)⌉ neurons in a deep network.Thus, depth reduces the size gap from linear versus logarithmic for univariate polynomials, compared with exponential versus linear for multivariate polynomials.
- Univariate polynomials: The deep construction repeatedly squares intermediate outputs and selectively multiplies them according to the binary representation of d.Square gates use three neurons, while product or identity gates use four or one neurons, respectively.
5 HOW EFFICIENCY IMPROVES WITH DEPTH
The paper constructs compositional deep networks whose neuron requirements interpolate between exponential width for shallow networks and linear width for logarithmic depth. For product polynomials, optimal layer group sizes approach n^(1/k), and experiments support the predicted transition.
- Theoretical construction: Repeated shallow constructions yield a tree-like network that recursively multiplies groups of inputs across k hidden layers.The group sizes b_1,...,b_k satisfy b_1b_2···b_k=n, producing one neuron representing the product.
- Theoretical construction: For k hidden layers, setting each group size to n^(1/k) gives the stated upper bound on neuron requirements.This choice balances the layerwise multiplication costs under the product constraint.
- Optimal widths: The optimal group sizes are not exactly equal but increase slowly with layer index, approaching n^(1/k) for large n.Figure 1 reports this asymptotic behavior for k=1, 2, and 3.
- Scope: The conjectured optimality concerns the product polynomial and assumes the activation has all nonzero Taylor coefficients.The authors state that the bound in Theorem 5.1 is approximately optimal under this assumption.
- Empirical evidence: Experiments on products of 20 variables show rapid interpolation from exponential to linear width as the number of layers increases.Networks used dense successive-layer connections, varied layer count and width, and were trained with tanh or ReLU nonlinearities.
6 CONCLUSION
The paper concludes that depth can quantify and substantially improve neural-network efficiency for simple polynomials through compositional constructions. It also identifies learning resources and broader polynomial expressivity as important open challenges.
- Main conclusion: For n-variable sparse polynomials, shallow networks require exponentially many neurons, whereas deep networks require at most linearly many.Networks with a constant number k>1 of hidden layers appear to interpolate between these extremes as exp(n^(1/k)).
- Main conclusion: Keeping layers below 2^10 neurons requires roughly log_10 n layers, while the presented O(n) constructions use about log_2 n layers.The latter is approximately a factor of log_2 10 ≈ 3 more layers.
- Architectural interpretation: Compositionality gives the constructions locality, with some natural functions computable using linearly many neurons and at most two incoming connections per neuron.The same framework is related to sharing and pooling properties.
- Open challenges: The analysis measures neurons and synapses needed to compute a function at fixed depth, not the training resources needed to learn its weights.The paper notes that optimization-friendly architectures such as ResNets may improve practical learnability without increasing representational power at equal size.
APPENDIX
The appendix establishes neuron-count bounds for polynomial approximation by proving lower bounds through linear independence and constructing deep-network upper bounds. It also extends the analysis from monomials to sparse general polynomials.
- Shallow-network lower bound: A depth-1 network requires at least Qn_i=1(ri + 1) neurons to approximate the same monomial.The proof makes the approximation error coefficients arbitrarily small, forcing the associated terms to remain linearly independent.
- Monomial approximation: Qn_i=1(ri + 1) neurons are necessary and sufficient for uniformly approximating the monomial with exponents ri.Sufficiency follows by representing the monomial through sign-patterned ridge functions; necessity follows from a full-row-rank argument.
- Deep-network construction: 7⌈log2(ri)⌉ neurons approximate each power x_i^ri in a deep network, while 4n additional neurons multiply the n terms.The resulting construction uses P_i(7⌈log2(ri)⌉+4) neurons.
- Sparse general polynomials: For a polynomial p with c monomials, the rank of its partial-derivative space is at least |D|/c, yielding a lower bound for uniform approximation.The argument selects a linearly independent subset of derivatives by tracking distinct monomials contributed by derivatives of a chosen monomial q.