Source-linked AI summary
Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks
Itay Safran, Ohad Shamir
TL;DR
The paper asks when neural-network depth matters for approximating simple natural functions, beyond the fact that shallow networks are universal approximators. It proves depth-separation results for ball indicators, L1-radial functions, and smooth nonlinear functions, and experimentally tests a unit-ball indicator. The results show that deeper networks can approximate or learn these functions substantially better than much wider shallower networks, while the L1 lower bound is weaker than the ball result.
Problem
Despite strong empirical performance, the theoretical conditions under which depth improves neural-network approximation remain limited, especially for natural interpretable functions.
Method
The paper analyzes approximation error for standard feed-forward networks and proves width lower bounds for shallow networks alongside constructive deeper-network approximations, with a unit-ball learning experiment.
Results
Deeper networks separate from shallower ones for ball and ellipsoid indicators, L1-radial nonlinear functions, and smooth nonlinear functions; experiments find 3-layer learning significantly better than larger 2-layer networks.
Takeaways & Limitations
Depth can be crucial for expressing and learning simple natural functions, so parameter count alone may not predict approximation or learning performance.
Takeaways & Limitations
For L1-radial functions, the paper’s lower bound is polynomial rather than exponential in the relevant parameters, and the authors conjecture it can be improved.
Abstract
from arXiv · showhide
We provide several new depth-based separation results for feed-forward neural networks, proving that various types of simple and natural functions can be better approximated using deeper networks than shallower ones, even if the shallower networks are much larger. This includes indicators of balls and ellipses; non-linear functions which are radial with respect to the $L_1$ norm; and smooth non-linear functions. We also show that these gaps can be observed experimentally: Increasing the depth indeed allows better learning than increasing width, when training neural networks to learn an indicator of a unit ball.
1 Introduction
The paper studies how neural-network depth affects approximation of natural functions, addressing limited theoretical understanding despite deep learning’s empirical success. It develops depth-separation results for balls, L1-radial functions, and smooth nonlinear functions, alongside an experiment on learning a unit-ball indicator.
- Motivation: 2-layer networks can approximate any continuous target on [0, 1]^d with sufficient width, but the paper investigates when depth still provides a substantial advantage.The work focuses on expressiveness measured directly through approximation error.
- Motivation: The paper targets natural, interpretable functions that deeper networks can approximate well but much larger shallower networks cannot.Such results are intended to clarify what neural-network architectures can express in practice.
- Contributions: The Euclidean unit-ball and ellipsoid indicators are approximable by 3-layer networks but require exponential width for comparable 2-layer approximation.For the unit ball, a 3-layer network uses O(d/ϵ) neurons while 2-layer error cannot exceed O(1/d^4) unless width is exponential in d.
- Contributions: Experiments show that a 3-layer network learns a unit-ball indicator significantly better than larger 2-layer networks using standard backpropagation.The result supports observing the theoretical depth/width gap during learning, not only approximation analysis.
- Contributions: L1-radial piecewise-linear functions require depth-2 ReLU width ˜Ω(min{1/ϵ, exp(Ω(d))}) for accuracy ϵ, while depth 3 represents them exactly.This establishes another depth/width trade-off for a natural function class.
- Contributions: A broad family of nonlinear twice-differentiable functions admits polylogarithmic-depth-and-width approximation but requires Ω(poly(1/ϵ)) width at constant depth.The stated family includes x 7→x^2 on [0,1].
2 Preliminaries
The preliminaries define the feed-forward ReLU network model, its depth and width, and the approximation-error measures used throughout the paper.
- Neural Networks: A neuron computes σ(w⊤x+b), with ReLU defined as σ(z)=max{0,z}.Layers apply the activation coordinatewise to affine transformations.
- Neural Networks: Network depth is the number of layers, while network width is the maximum neuron count across layers.The final layer is linear, and the paper uses “2-layer” and “3-layer” for those depths.
- Approximation error: The paper measures approximation quality with expected squared error E_x∼µ[(f(x)−f̃(x))^2].This is the paper’s L2-norm approximation criterion.
- Approximation error: L∞ approximation is defined as sup_x∈X|f(x)−f̃(x)| and upper-bounds the square root of the L2 error.Thus, L2 lower bounds are stronger than corresponding L∞ lower bounds under the stated relationship.
3 Indicators of L2 Balls and Ellipsoids
For Euclidean balls and ellipsoids, the paper proves a strong depth separation and then tests whether the predicted advantage of depth appears when networks learn a unit-ball indicator.
- Theoretical separation: 2-layer networks of width at most c3 exp(c4d) cannot approximate f(x)=1{∥Ax+b∥≤r} beyond the theorem’s stated L2-error threshold.The result holds for sufficiently large d, nonsingular A, vectors b, positive r, and a suitable continuous distribution.
- Theoretical separation: The lower bound is obtained by reducing the ellipsoid-indicator problem to Eldan and Shamir’s hard radial-function result.The reduction represents the hard radial function through a sum of Θ(d^2) indicator differences.
- Theoretical separation: 3-layer networks approximate ellipsoid indicators arbitrarily well under any continuous distribution, with size polynomial in dimension and required accuracy.The construction approximates squared coordinates, combines them into ∥Ax+b∥, and then approximates the threshold.
- Experiment: The experiment trains one 3-layer ReLU network against 2-layer networks with widths 100, 200, 400, and 800 on a unit-ball indicator in R^100.Training uses backpropagation, squared loss, batches of 100, momentum 0.95, and a decaying learning rate.
- Experiment: The 3-layer network achieves significantly better training and validation performance despite the width-800 2-layer network having approximately 80K parameters versus approximately 10K.Increasing 2-layer width also shows diminishing returns.
4 L1 Radial Functions; ReLU Networks
For nonlinear functions depending on the L1 norm, the paper proves that shallow ReLU networks need substantial width, whereas 3-layer networks can represent the relevant piecewise-linear class exactly.
- Example: For f(z)=[z−1]+, approximating [∥x∥1−1]+ with two layers requires width ˜Ω(min{1/ϵ, exp(Ω(d))}) under some distribution.The construction uses the piecewise-linear representation of the L1 norm.
- Upper bound: Every piecewise-linear L1-radial function f(∥x∥1) is exactly representable by a 3-layer ReLU network.The example [∥x∥1−1]+ uses a width-2d construction.
- Proof intuition: The proof links the lower bound to geometry: each shallow ReLU nonlinearity lies on a hyperplane, while one hyperplane’s neighborhood covers only a small portion of an L1 sphere.Covering most points near the sphere therefore requires many hyperplanes.
- Scope and limitation: The paper notes that this theorem’s lower bound is polynomial rather than exponential in the relevant error parameter and conjectures substantial improvement.For [∥x∥1−1]+, the authors do not know an approximation using fewer than Ω(2^d) neurons at better than constant accuracy.
5 C2 Nonlinear Functions; ReLU Networks
For C2 functions with curvature on a substantial domain region, shallow ReLU networks face width-dependent approximation limits, while deeper networks can achieve exponentially better accuracy for functions built from bounded additions and multiplications.
- Nonlinear function class: C2 functions with nonzero curvature along a fixed direction over a substantial domain region define the nonlinear class studied for depth separation.The paper measures this region through σλ(f), the largest connected set where curvature is at least λ along that direction.
- Lower bound: Theorem 4 shows that approximating such C2 functions with depth l and width m has an error lower bound that improves only polynomially with width while worsening exponentially with depth.The result applies to any C2 target satisfying the stated curvature condition and any ReLU network of the specified depth and maximal width.
- Illustration: Figure 2 illustrates the mechanism by approximating x 7→x2 through five extracted bits, whose linear-segment count grows exponentially with the bit count and network size.The construction uses bit extraction to build a piecewise-linear approximation of multiplication and hence squaring.
- Depth-based construction: Depth enables highly oscillatory ReLU constructions that extract high-order binary bits, supporting arithmetic computations such as multiplication.The construction extracts bits of x and combines them with y using a procedure resembling long multiplication.
- Approximability upper bound: ReLU networks can approximate functions computed by boundedly many weighted additions and multiplications with moderate width and depth, with stronger L∞ guarantees.Theorem 6 formalizes this for functions whose intermediate values remain bounded and whose target approximation uses at most t such operations.
- Depth-width tradeoff: Under the corollary’s assumptions, accuracy ϵ requires fixed-depth networks to have width at least poly(1/ϵ), whereas networks with depth and width p(log(1/ϵ)) suffice.The deeper construction achieves accuracy ϵ in the infinity norm, while the fixed-depth lower bound concerns L2 approximation.
6 Proofs
The proofs establish depth–width separations for ball indicators, L1-radial functions, and smooth nonlinear functions by combining approximation constructions with lower bounds for shallower or piecewise-linear models.
- L1-radial functions: The L1-radial lower bound reduces approximation to controlling how often affine pieces intersect a narrow radial interval, yielding width ˜Ω(min{1/ϵ, exp(Ω(d))}).The proof constructs a distribution on the unit L1 sphere and bounds the relevant slab probability.
- Smooth nonlinear functions: For C2 functions, piecewise-linear approximations cannot have error decay faster than quartically in the number of segments along any one-dimensional projection.This projection-based bound is stronger than one stated only using the total number of regions in Rd.
- Smooth nonlinear functions: The smooth-function argument combines lower bounds for piecewise-linear projections with network-induced bounds on the number of linear segments.Approximating an intermediate target and the target function each to accuracy ϵ gives total error 2ϵ.
- Smooth nonlinear functions: Quadratic and strongly convex or concave functions supply concrete one-dimensional lower bounds for piecewise-linear approximation.For quadratic functions, the optimal error depends only on the interval length.