Source-linked AI summary
Depth Separation for Neural Networks under Gaussian Measure
Cynthia Bortolotto, Francisco Ganacim, Roberto I. Oliveira
TL;DR
The paper studies depth separation for radial-function approximation under the standard Gaussian measure, a setting distinct from prior examples using other measures. It proves that high-degree Hermite mass obstructs approximation by shallow networks, then applies the result to show an exponential-versus-polynomial size separation between depth-2 and depth-3 ReLU networks at fixed sufficiently small error.
Problem
The paper examines depth separation for radial-function approximation under the standard Gaussian measure, a setting distinct from earlier separation results using other measures.
Source: §1 · p. 2Method
It proves that substantial high-degree Hermite mass in a radial function prevents good approximation by depth-2 networks with small width and bounded component norms.
Source: §1 · pp. 3–4Results
At fixed sufficiently small approximation error, depth-2 networks with the stated parameter bound require exponential size, while depth-3 networks achieve the same error with polynomial size.
Source: §1 · p. 5Takeaways & Limitations
The paper establishes an exponential depth separation for radial functions on R^d under the standard Gaussian measure.
Source: §1 · pp. 2, 5The lower-bound setup assumes each ridge component g_j has L2(γ) norm at most M.
Source: §1 · p. 4
Abstract
from arXiv · showhide
We revisit the problem of depth separation for neural networks, as studied by Eldan and Shamir, Daniely, and others. Specifically, we consider the natural setting of $L^2$ approximation of radial functions under the standard Gaussian measure in $d$ dimensions. We show that there is a radial function in $L^2$ under the standard Gaussian measure that can be approximated to a fixed sufficiently small $L^2$ error by a depth-3 ReLU neural network of polynomial size in $d$ but can only be approximated by depth-2 networks with subexponentially bounded weights if their size is at least exponential in $d$. For that, we prove a general result showing that if a radial function has substantial mass in the high frequencies of its Hermite expansion, then it cannot be well approximated by a depth-2 neural network with small width and bounded weights. All theorems, lemmas, propositions, and corollaries are verified in Lean~4.
1. Introduction
The paper establishes depth separation for radial-function approximation in L2 under the standard Gaussian measure, using high-degree Hermite mass to derive lower bounds for shallow networks. It applies this result to exhibit a radial target that depth-3 ReLU networks approximate with polynomial size, while depth-2 networks require exponential size at fixed sufficiently small error.
1. Introduction
- The introduction situates this result among earlier depth separations, including results for tailored measures and other input domains.Eldan and Shamir [4] used a measure tailored to a Fourier-analytic proof, while Daniely [3] studied a uniform product distribution on spheres.Source: §1 · p. 2
- A radial target with substantial Hermite mass in high degrees cannot be well approximated by a small number of ridge functions.This is the paper's general lower-bound result for depth-2 networks.Source: §1 · p. 3
- For targets F(x) = ϕ(∥x∥2 /d), failure of low-degree polynomial approximation implies substantial high-degree Hermite mass and yields a width lower bound.The polynomial approximation is considered in L2(ρd(t) dt).Source: §1 · pp. 3–4
- The proof radializes ridge functions by averaging over rotations, then uses the decay of spherical moments to bound their Hermite-degree correlations.The target's radial symmetry means only the radial part of a ridge function contributes to correlation.Source: §1 · p. 4
- At fixed sufficiently small approximation error, depth-2 networks with the stated parameter bound require exponential size, whereas depth-3 networks achieve the same error with polynomial size.The separation is established for a radial function under the standard Gaussian measure.Source: §1 · pp. 2, 5
- The paper reports that all theorems, lemmas, propositions, and corollaries are formally verified in Lean 4.The code is available in a companion GitHub repository.Source: §1 · p. 6
2. Hermite Expansions and Rotational Symmetry
The section develops the Hermite decomposition under Gaussian measure and establishes that orthogonal transformations preserve each degree of Gaussian chaos. This rotational symmetry supports the paper’s later analysis of radial targets.
2. Hermite Expansions and Rotational Symmetry
- Orthogonal transformations preserve each Hermite degree, so the corresponding chaos projections commute with rotations.Source: §2 · pp. 7–8
- The proof uses ridge Hermites to span each chaos and shows that rotation maps these functions within the same degree.Source: §2 · pp. 7–8
3. Radialization of Ridge Functions
The section expresses radialized ridge functions through Hermite coefficients and moments of a uniform spherical vector. Its moment bounds show that high-degree radial components shrink rapidly with dimension.
3. Radialization of Ridge Functions
- A ridge function’s radialization is obtained by averaging it over rotations, with its Hermite expansion expressed through spherical moments.Source: §3 · pp. 8–9
- Radialization is the orthogonal projection onto radial functions and commutes with Gaussian chaos projections.Source: §3 · p. 8
- For odd Hermite degrees, spherical moments vanish whenever a multi-index has an odd component.Source: §3 · p. 10
- The even-degree radial component is governed by K_n, whose product formula makes it exponentially small when degree is proportional to dimension.Source: §3 · pp. 10–11
- K_n is nonincreasing along even degrees, supporting uniform control of the higher-degree terms.Source: §3 · p. 11
4. Correlation Estimates and the Ridge Lower Bound
The section bounds correlations between radial Hermite projections and ridge functions, then uses a tail estimate to derive a width lower bound. The argument links substantial high-degree mass to the need for many ridge functions.
4. Correlation Estimates and the Ridge Lower Bound
- The correlation bound controls how well a ridge function can capture a radial function’s degree-n projection.Source: §4 · pp. 11–12
- Odd-degree projections of radialized ridge functions vanish, while even-degree bounds depend on spherical moments and the ridge function’s Hermite coefficient.Source: §4 · p. 12
- The tail estimate applies to even n0 and bounds approximation using r ridge terms whose component functions lie in L2(γ).Source: §4 · p. 13
- The tail estimate yields the main lower bound: radial functions with substantial high-degree Hermite mass require many ridge functions for approximation under the stated norm and error conditions.Source: §4 · pp. 12–13
5. Depth Separation
The section constructs a rapidly oscillating radial sine function with substantial high-chaos mass, then uses it to establish depth separation under Gaussian measure. A depth-3 ReLU network approximates the function with polynomial width, while bounded-weight ridge approximations require exponentially many terms.
5. Depth Separation
- The target is chosen as a rapidly oscillating function of ∥x∥^2 that retains substantial high-chaos energy while remaining approximable by a depth-3 ReLU network.Source: §5 · p. 14
- The proof reduces radial functions in low Gaussian chaoses to polynomials in ∥x∥^2/d, turning approximation into a one-dimensional weighted polynomial problem.The weight is the density of ∥X∥^2/d for X distributed according to the standard Gaussian measure.Source: §5 · p. 14
- The oscillation argument compares alternating sine signs with the signs of a low-degree polynomial across half-period intervals, discarding intervals containing polynomial zeros.The remaining intervals form same-sign blocks for the polynomial, leaving opposite-sign intervals for comparison.Source: §5 · pp. 16–17
- The constructed radial sine target has high-chaos mass at least c, and its ridge-width lower bound grows exponentially with d for bounded output functions.The lower bound is r ≥ c·2^(d/4)/(4M).Source: §5 · p. 18
- The depth-3 network N_{R,ε}, formed by composing Nsin and Nsq, has width O(d^(5/2)(R^2+1)/ε); R^2=O(d+log(1/ε)) gives the claimed bounds.Source: §5 · p. 20
6. Lean formalization
The paper formalizes and verifies its theorems, lemmas, propositions, and corollaries in Lean 4. The authors report auditing the statements and provide the source code in a companion repository.
6. Lean formalization
- All theorems, lemmas, propositions, and corollaries are formalized and verified in Lean 4 using Mathlib.The authors also audited the Lean statements.Source: §6 · p. 20
- The formalization was developed with assistance from Claude Fable and GPT Sol, and its complete source code is available in a companion GitHub repository.Source: §6 · p. 20
- The mathematical library uses no admitted proofs or project-defined axioms; its audit accepts only propext, Classical.choice, and Quot.sound.Source: §6 · pp. 20–21