Source-linked AI summary
The Power of Depth for Feedforward Neural Networks
Ronen Eldan, Ohad Shamir
TL;DR
The paper studies the expressive power of bounded-size feedforward neural networks, focusing on whether shallow networks can efficiently approximate functions computed by networks only one layer deeper. It constructs a function representable by a polynomial-width 3-layer network that requires exponential width for 2-layer approximation at constant error.
Problem
The paper asks how the expressive power of bounded-size neural networks differs between 2-layer and 3-layer architectures, since unrestricted 2-layer networks can approximate continuous functions but may require exponential size in the dimension.
Method
The paper constructs and analyzes a simple approximately radial function on R^d using assumptions requiring the activation function to be universal, with a proof based on high-frequency Fourier mass and random signs.
Results
A function computed by a 3-layer network of width Ccσd^19/4 has squared approximation error at least c for every 2-layer network of width at most c e^{cd}.
Takeaways & Limitations
The result formally shows that increasing depth from 2 to 3 layers can provide an exponential width advantage for standard feedforward neural networks.
Takeaways & Limitations
The separation requires assumptions on the activation function, including universality and an additional stated assumption, and the proof faces uncertainty about preserving high-frequency L2 mass after convolution with a Euclidean ball.
Abstract
from arXiv · showhide
We show that there is a simple (approximately radial) function on $\reals^d$, expressible by a small 3-layer feedforward neural networks, which cannot be approximated by any 2-layer network, to more than a certain constant accuracy, unless its width is exponential in the dimension. The result holds for virtually all known activation functions, including rectified linear units, sigmoids and thresholds, and formally demonstrates that depth -- even if increased by 1 -- can be exponentially more valuable than width for standard feedforward neural networks. Moreover, compared to related results in the context of Boolean functions, our result requires fewer assumptions, and the proof techniques and construction are very different.
1 Introduction and Main Result
The paper asks whether bounded-width feedforward networks gain expressive power from depth and proves a sharp separation between 3-layer and 2-layer networks. Under broad activation assumptions, a polynomial-width 3-layer network computes a function that requires exponentially large width for constant-accuracy approximation by any 2-layer network.
- Research question: Bounded network size is central because universal approximation by depth-2 networks may require exponential size in the dimension.The paper therefore examines approximation by networks whose width is bounded.
- Research question: The paper studies whether depth can provide expressive power that shallow, wider networks cannot efficiently match.It focuses on fully connected feedforward networks with nonlinear hidden neurons and a linear output neuron.
- Assumptions and scope: The separation applies to activation functions satisfying universality and mild growth conditions, including ReLU, sigmoid, threshold, and more general sigmoidal activations.The theorem allows arbitrary real-valued parameters and even permits different adaptive first-layer activations under the stated growth condition.
- Main result: The main theorem gives a function computable by a 3-layer network of width polynomial in d that every 2-layer network of width at most c e^(cd) approximates only to constant error.The constructed function is bounded and supported within a radius proportional to √d.
- Main result: The hard function is approximately radial, and the proof exploits that 3 layers can first approximate the squared norm and then a univariate function of that norm.The corresponding 2-layer approximation requires exponentially many neurons for better-than-constant accuracy.
- Relation to prior work: The result contrasts with related threshold-circuit bounds because it concerns real-valued continuous-network approximation and requires no parameter-size constraints.The paper uses a different construction based on radial functions rather than Boolean inner-product-mod-2 functions.
2 Proof Sketch
The proof constructs an approximately radial function that is easy for a 3-layer network to express but difficult for 2-layer networks because their Fourier support is confined near unions of tubes. High-dimensional sparsity and a randomized shell construction yield the separation.
- 3-layer construction: 3-layer networks approximate radial functions by first computing the squared norm and then applying a univariate function.This produces an approximately radial function from coordinatewise approximations of x ↦ ∥x∥^2.
- 2-layer limitation: 2-layer network functions have Fourier transforms supported on a union of bounded-radius tubes through the origin.The support property holds regardless of the exact first-layer functions, including adaptive or neuron-specific activations.
- High-dimensional separation: Unless the number of tubes is exponential in d, their union is sparse far from the origin, creating a geometric obstruction to approximating suitable radial functions.A radial function with substantial mass at large distances spreads that mass across directions rather than concentrating inside the tubes.
- Hard-function construction: A random superposition of thin spherical shells is used to construct a discontinuous target with substantial high-frequency Fourier mass.Each shell contributes a Bessel-function Fourier transform, and random signs preserve a sufficiently large high-frequency component in at least one construction.
- 3-layer construction: The discontinuous shell function is replaced by a Lipschitz approximation that a 3-layer network can realize arbitrarily well under the chosen probability distribution.The distribution has bounded density, so smoothing shell indicators changes the function on arbitrarily small probability mass.
3 Preliminaries
The preliminaries establish notation for norms, inner products, Fourier transforms, radial functions, and Euclidean geometry, then introduce Bessel functions used in the proof’s Fourier analysis.
- Notation: L2 and L1 denote squared-integrability and absolute-integrability spaces, while ∥·∥ and ∥·∥L2 denote Euclidean and L2 norms.The preliminaries also define function products, sums, set addition, and complements.
- Fourier analysis: The paper specifies Fourier-transform conventions for scalar and d-dimensional functions, enabling later analysis of network representations.Fourier isometry is used when comparing approximation error in the original and transformed domains.
- Radial geometry: A radial function has equal values at points with the same Euclidean norm, so it can be represented interchangeably using vector inputs or scalar radii.The geometric preliminaries define unit spheres, unit balls, and the radius of a volume-one ball.
- Bessel functions: Bessel functions of the first kind are introduced as oscillatory functions whose behavior at large arguments supports the proof’s Fourier estimates.Figure 2 illustrates J20, the order-20 Bessel function.
4 Proof of Thm. 1
The proof constructs an approximately radial function that a small 3-layer network can approximate but every 2-layer network approximates poorly. Fourier analysis supplies the separation, while Lipschitz approximation realizes the function with three layers.
- Constructions: The construction defines a probability measure µ with density ϕ², where ϕ is the Fourier transform of a unit-volume Euclidean ball’s indicator.Fourier-transform isometry establishes that µ is a probability measure.
- Constructions: N = γd² intervals are divided into good and bad intervals, and each good interval defines a localized function g_i.On good intervals, ϕ has constant sign and is sufficiently close to constant.
- Inapproximability: The constructed function is easy to approximate with a 3-layer network but hard to approximate with a 2-layer network.The separation follows from Fourier-support restrictions for ridge-function sums and the high-frequency mass of ˜g.
- Inapproximability: A sign combination ˜g(x) = Σ_i ε_i g_i(∥x∥) is chosen so that its weighted Fourier mass remains substantially outside the low-frequency region relevant to 2-layer networks.The proof uses an orthogonal projection removing low-frequency components and combines the resulting bounds.
- Approximability: A 3-layer network approximates the Lipschitz surrogate with width at most 2cσd²R²L√r/δ + 1, while every 2-layer function remains at least δ1/2 away in L2(µ).The three-layer approximation is obtained by replacing discontinuous indicators with Lipschitz functions and applying the approximation lemma.
B.1 Proof of Lemma 2
The lemma’s proof evaluates the Fourier transform of a radial function by reducing the multidimensional integral to a one-dimensional Bessel-function expression. Radial symmetry then yields the stated formula.
- B.1 Proof of Lemma 2: Radial symmetry permits assuming x = re_1, reducing the Fourier-transform integral to coordinates aligned with the first standard basis vector.The remaining coordinates contribute the volume of a lower-dimensional ball.
- B.1 Proof of Lemma 2: The substitution z = arccos(w_1/R_d) transforms the integral into a trigonometric form involving cos(x cos(z)) and sin^d(z).The bounds change from w_1 ∈ [−R_d,R_d] to z ∈ [π,0].
- B.1 Proof of Lemma 2: Because the Fourier transform is real-valued and even, the proof discards the imaginary components of the transformed expression.A standard Bessel-function identity then gives the desired representation.
B.2 Proof of Lemma 3
The proof shows that on every good interval, the radial Fourier transform has stable sign and limited variation. These properties follow from bounds on Bessel functions and the interval-size conditions.
- B.2 Proof of Lemma 3: On a good interval, ϕ does not change sign when d, α, and N satisfy the lemma’s lower-bound conditions.The relevant condition is N ≥ cα^3/2d² for a sufficiently large universal constant.
- B.2 Proof of Lemma 3: The Lipschitz bound for J_d/2 controls variation across a good interval, yielding an upper bound below 1 + d^-1/2 when N ≥ cα^3/2d².The proof treats the positive case without loss of generality and combines the Bessel bound with the interval definition.
B.3 Proof of Lemma 4
The proof bounds the Fourier mass of each localized interval function and shows that sufficiently small interval width makes the relevant error less than one half. This establishes the lemma’s constant bound.
- B.3 Proof of Lemma 4: Bad intervals are trivial because their associated function g_i is identically zero.The proof therefore focuses on good intervals.
- B.3 Proof of Lemma 4: For a good interval Δ_i = [ℓ, ℓ + δ], the interval width satisfies δ ≤ 1/(50dℓ).The proof uses this condition after dropping the interval index.
- B.3 Proof of Lemma 4: The radial Fourier transform is expressed through a Bessel function after switching to polar coordinates.The bound |J_d/2−1(x)| ≤ 1 controls the resulting expression.
- B.3 Proof of Lemma 4: The final bound is at most 1/2 because 50 exp(1/50) < 1/2 under the lemma’s stated parameter conditions.This completes the required estimate for the good-interval case.
B.4 Proof of Lemma 5
The proof reduces the argument to good intervals, where the relevant function has controlled sign and magnitude. It then combines a suitable constant choice with norm inequalities to derive the lemma’s bound.
- The proof excludes bad intervals because both sides of the lemma’s inequality vanish there.
- On a good interval, ϕ is sign-consistent, allowing the proof to assume it is positive without loss of generality.
- Choosing C sufficiently large permits application of Lemma 4 to continue the lower-bound argument.
- A norm inequality involving u, v, and v − u supplies an additional bound used in the proof.
B.5 Proof of Lemma 6
The proof evaluates the lemma’s integral by exploiting disjoint supports, radial coordinates, interval-wise Lipschitz control, and a variable change. These steps establish that points satisfying the target condition lie in good intervals.
- Disjoint supports of the functions gi reduce the lemma’s integral to separate contributions from individual intervals.
- Switching to polar coordinates and using the definition of ϕ rewrites the integral in radial form.
- The interval width and Lipschitz control of Jd/2(2πRdr) transfer a lower bound at r to nearby r′ in the same interval.
- A variable change x = 2πRdr and subsequent bounds show that r belongs to a good interval.
- The proof concludes after applying the relevant lemmas under the stated parameter condition on d and α.
B.6 Proof of Lemma 7
The proof constructs an N-Lipschitz approximation of each gi and aggregates the resulting errors using their disjoint supports. Polar-coordinate integration and bounds on the Bessel terms yield the desired estimate.
- The proof combines the interval-wise contributions according to whether i is good or bad.
- For bad intervals, the approximation equals gi, while for good intervals it provides an N-Lipschitz approximation.
- Because the supports of the approximating functions are disjoint, their sum f is also N-Lipschitz.
- Disjoint supports let the proof decompose the error integral before applying bounds to J2 and the remaining terms.
- The difference between ˇgi and gi is nonzero only on two sub-intervals of width 1.
C Technical Results On Bessel functions
This section develops bounds and approximations for Bessel functions used in the paper’s technical lemmas. It combines derivative identities, explicit approximations, integral estimates, and parameter conditions to obtain the final bounds.
- For ν ≥ 0, |Jν(x)| ≤ 1; for ν ≥ 1 and x ≥ 3ν, Jν(x) is 1-Lipschitz in x.
- The derivative identity for Jν combines Jν+1(x) and Jν(x), whose magnitudes are bounded using standard Bessel estimates.
- An explicit approximation for Jd/2(x) is obtained from a result of Krasikov together with elementary approximations.
- Lemma 15 applies when β ≥ 1, d ≥ 2, and βd ≥ 127.
- The approximation error is propagated through a difference-of-squares bound involving a = Jd/2(x) and its approximation b.
- A change of variables, integration by parts, and bounds on trigonometric terms produce successive lower bounds for the target integral.
- Concatenating the derived lower bounds completes the technical argument and yields the stated lemma conclusions.