PaperlayerView exact revision on arXiv

Source-linked AI summary

Every Layer Counts: An Exponential $L_2$ Depth Hierarchy for ReLU Networks

Itay Safran

arXiv:2608.23877v1cs.LG

TL;DR

The paper addresses the gap in exponential ReLU depth separations between fixed depths beyond depth 3 versus depth 2. It develops a recursive hardness mechanism and proves a complete adjacent-depth hierarchy, alongside an exact depth-4-versus-depth-3 separation. The approximation construction remains outside circuit-complexity reductions because its support radius is exponential.

  • Problem

    Prior exponential ReLU separations did not establish a hierarchy across all adjacent fixed depths, while related threshold-circuit lower bounds remain open.

  • Method

    A recursive mechanism reduces hardness at one depth to a hard instance at the preceding depth, producing separations layer by layer.

  • Results

    For every fixed ℓ≥3, polynomial-width depth-ℓ networks represent targets whose constant-error approximation at depth ℓ−1 requires exponential width with unrestricted weights; exact depth-4 representations can likewise require exponential first-layer width at depth 3.

  • Takeaways & Limitations

    The paper establishes a complete exponential hierarchy across adjacent ReLU depths and extends depth-separation evidence to exact computation under polynomially bounded normalization.

  • Takeaways & Limitations

    The approximation hierarchy uses a distribution supported at exponential radius, placing it outside the polynomial-radius regime underlying the Vardi–Shamir circuit-complexity reduction.

Abstract

from arXiv · show

We prove a depth hierarchy for ReLU neural networks in which every additional ReLU layer can save exponentially many neurons. For every $\ell\geq 3$, a globally $[0,1]$-valued, $1$-Lipschitz function is realized by a depth-$\ell$ network of width $\mathcal{O}(d^4)$, whereas every depth-$(\ell-1)$ network with unrestricted weights and width at most $2^d/[2d(\ell-2)]$ has squared $L_2$ error at least $1/24$ under an absolutely continuous distribution. To the best of our knowledge, this is the first exponential separation for ReLU networks between two fixed depths whose shallower depth is at least $3$, and the first exponential hierarchy across all adjacent fixed depths. The lower bound also immediately yields the corresponding hierarchy for exact computation. Moreover, the case $\ell=3$ gives a compactly supported depth-$3$-versus-depth-$2$ separation with unrestricted shallow-network weights, answering a question raised by Safran, Eldan, and Shamir (2019, Sec. 2.3). The corresponding distribution nevertheless has all its mass at exponential radius, so the construction falls outside the regularity regime in which such a separation would imply major threshold-circuit lower bounds. We also prove an exact separation for a more benign function. It is computed by a polynomial-width depth-$4$ network, whereas every depth-$3$ network agreeing with it on the unit hypercube requires exponentially many neurons in its first hidden layer, again without any restriction on the weights. The function is globally $[0,1]$-valued and $\mathcal{O}(\sqrt d)$-Lipschitz, and maps the unit hypercube onto $[0,1]$.

1 Introduction

The paper closes longstanding gaps in ReLU depth hierarchies by establishing exponential separations between every pair of adjacent fixed depths. It also relates these results to normalization limits, circuit-complexity barriers, and exact computation.

  • Motivation and contribution: Exponential separations between adjacent fixed depths were previously unavailable beyond depth 3 versus depth 2; the paper establishes a complete hierarchy across all such depths.A recursive mechanism transfers hardness from one depth to the preceding depth, allowing the reduction to be applied once per layer.
  • Motivation and contribution: For every fixed ℓ≥3, polynomial-width depth-ℓ ReLU networks represent functions whose constant-error approximation at depth ℓ−1 requires exponential width, even with unrestricted weights.The target functions are globally bounded and Lipschitz, and the result closes the fixed-depth gap for ReLU networks.
  • Normalization and comparison: The normalization scale remains unchanged under output scaling and input dilation, measuring whether hardness is carried by domain size, target variation, or approximation accuracy.This scale enables comparisons across L2 separation results without depending on input or output units.
  • Normalization and comparison: The approximation hierarchy lies outside the Vardi–Shamir circuit-reduction regime because its distribution has exponential support radius, despite constant Lipschitz and accuracy scales.The paper leaves open whether the support radius can be reduced to polynomial or constant while retaining unrestricted-weight lower bounds.
  • Normalization and comparison: The ℓ=3 specialization gives an exponential depth-3-versus-depth-2 separation under an absolutely continuous, compactly supported distribution with unrestricted weights.This simultaneously addresses compact support and unrestricted shallow-network weights, but the support radius is exponential.
  • Exact computation: Exact computation offers a complementary separation: polynomial-width depth-4 networks compute a family exactly, while depth-3 networks require exponential first-layer width on the unit hypercube.This result keeps the domain radius and Lipschitz constant polynomially bounded and the image interval non-degenerate.

2 Preliminaries and Notation

The paper fixes notation for norms, Lipschitz constants, continuous piecewise-linear maps, ReLU networks, and their width, size, approximation, and exact-computation conventions.

  • Notation: The notation Lip(f) denotes the Euclidean-to-Euclidean Lipschitz constant, while ⟨x,z⟩ and ∥x∥_p denote the Euclidean inner product and ℓp norm.
  • Notation: CPWL maps are continuous functions affine on each cell of a finite polyhedral partition.
  • Neural Networks: A depth-ℓ ReLU network is a fully connected feedforward composition of affine maps and coordinatewise ReLUs, with depth counting affine maps.A depth-2 network has one hidden ReLU layer.
  • Neural Networks: Network width is the maximum hidden-layer width, while network size is the sum of hidden-layer widths; weights and biases are arbitrary real numbers unless stated otherwise.
  • Approximation and exact computation: Squared L2 error is defined with respect to a probability distribution, and the paper uses “L2 error” to mean this squared quantity.
  • Approximation and exact computation: Exact computation on a set requires equality at every point, while global computation requires equality on all of R^d; U(A) denotes the uniform distribution on a measurable set A.

3 Adjacent-Depth L2 Separation

The paper constructs a complete exponential hierarchy across adjacent fixed ReLU depths: adding one layer reduces constant-error width requirements from exponential to polynomial in dimension, while the construction uses exponentially distant support.

  • Main result: At every fixed depth ℓ≥3, adding one ReLU layer reduces the width required for constant-error approximation from exponential to polynomial in dimension.
  • Main result: A globally defined CPWL target is computed by a depth-ℓ ReLU network with width at most Cd^4.
  • Main result: The target is globally 1-Lipschitz, and the distribution is uniform on 2^{d(ℓ−2)} disjoint cubes whose support lies at exponential radius.The cubes have side length 2·4^{-(ℓ−2)} and lie between radii 2^{c(ℓ−2)d^3} and 2^{C(ℓ−2)d^3}.
  • Scope and limitation: The hierarchy avoids the Vardi–Shamir threshold-circuit reduction because, for sufficiently large d, no polynomial-radius box contains any mass of the distribution.The target remains [0,1]-valued, but the support violates the reduction’s almost-bounded-support assumption.
  • Proof technique: The construction recursively creates 2^d translated-and-rescaled copies, arranged so each affine hyperplane intersects at most d copies.A narrow first layer therefore has a fixed activation pattern on many copies, allowing it to merge with the next layer and expose the preceding hard instance.
  • Proof technique: The perturbation is computed by a one-hidden-layer ReLU network of width O(d^4), while quantitative affine general position prevents any affine hyperplane from intersecting more than d protected cubes.
  • Proof technique: The base ridge h0(x)=[1−|x1|]+ has squared error at least 1/12 for every affine approximant, and iteration yields a lower bound of at least 1/24 at the theorem’s width threshold.

4 An Exact Depth-4-versus-Depth-3 Separation

The section constructs a globally bounded CPWL function computed by a polynomial-width depth-4 ReLU network, while exact depth-3 computation requires exponentially wide first layers. The proof uses transported depth-2 hard points in affine general position and preserves polynomial normalization on the unit hypercube.

  • Theorem 4.1: Theorem 4.1 gives a globally defined CPWL function computed by a depth-4 ReLU network with hidden-layer widths at most Cd^4, 2d, and 1.
  • Normalization: The construction operates on the unit hypercube, maps it onto [0,1], and has Lipschitz constant O(sqrt(d)), yielding a normalization scale linear in d.
  • Construction and proof technique: A depth-2 hard point is one whose every neighborhood cannot be computed by a depth-2 network; a depth-3 representation therefore needs a first-layer activation hyperplane through it.
  • Construction and proof technique: The target has 2^d−1 transported hard points in affine general position, so each hyperplane covers at most d points and exponentially many first-layer neurons are necessary.
  • Construction and proof technique: A CPWL map U perturbs hard points into affine general position while acting as a translation near each point, preserving the base function’s local behavior; the target is g_d := t_d ◦ U.

5 Conclusions and Future Work

The paper establishes an exponential hierarchy across every pair of adjacent ReLU depths and a complementary exact depth-4-versus-depth-3 separation under polynomial normalization. The approximation hierarchy’s main unresolved boundary is whether its exponential support radius can be reduced to the regularity regime relevant to threshold-circuit barriers.

  • Conclusions: For every ℓ≥3, globally bounded Lipschitz targets have polynomial-width depth-ℓ representations, while constant-error approximation at depth ℓ−1 requires exponential width with unrestricted weights.
  • Conclusions: The exact depth-4-versus-depth-3 separation keeps the target globally bounded and its Lipschitz constant polynomially controlled on the unit hypercube.
  • Future work: The approximation construction has compactly supported regular distributions, but its support lies at exponential radius, outside the polynomial-radius regime underlying the Vardi–Shamir barrier.
  • Future work: Whether a comparable adjacent-depth hierarchy can be established with polynomially bounded or constant-radius approximation domains remains a major open problem.

A Perturbing hypercube vertices into general position

The construction perturbs Boolean-cube vertices into affine general position while preserving locally constant sign features. A polynomial-width ReLU map realizes these features and yields small, Lipschitz-controlled displacements with an inverse-exponential determinant margin.

  • Random sign features: M = O(d^3) randomly selected subset-sign features can be chosen so every d + 1 feature vectors are linearly independent.A probabilistic-method argument uses independent random subset products, concentration, and a union bound over sign vectors.
  • Plateau feature map: The plateau function g alternates between (−1)^j near integers j and is representable using exactly 2d scalar ReLUs.Its plateaus make the resulting feature map locally constant around Boolean-cube vertices.
  • Local constancy: The feature map e_z is locally constant near each sign vertex, taking value z_s whenever ||x − s||_∞ < 1/(4d).Each coordinate is bounded and the full vector-valued depth-2 realization uses O(d^4) hidden neurons.
  • Simultaneous independence: A rational matrix B is chosen so every determinant D_I(B) is nonzero simultaneously, making all d + 1 perturbed vertices affinely independent.The product polynomial Π is nonzero, and a rational grid point controls both displacement size and denominator.
  • Quantitative bounds: The resulting perturbation has polynomial network width and determinant magnitude at least 2^−O(d^3), providing quantitative affine general position.The rational denominator bounds prevent nonzero determinants from becoming arbitrarily small.

B Proof of Theorem 4.1

Theorem 4.1 builds a globally bounded target with exponentially many locally depth-2-hard points in affine general position. A polynomial-width depth-4 network realizes it, while depth-3 networks must place first-layer hyperplanes through all marked points and therefore require exponential width.

  • General-position reduction: Perturbation preserves each marked point’s local function while moving the points into affine general position inside the open unit hypercube.The displacement map is locally constant around the points, so the local form is reproduced after translation.
  • First-layer forcing: Every depth-3 network agreeing with the target must have a genuine first-layer activation hyperplane through each marked point.Otherwise the first layer is affine on a neighborhood and can be absorbed into the next affine map, contradicting local depth-2 hardness.
  • Width lower bound: At most d marked points lie on any first-layer hyperplane, forcing first-layer width at least (2^d − 1)/d.Affine general position limits each hyperplane’s coverage, yielding the exponential shallow-network lower bound.
  • Deep realization: The target is computed by a depth-4 ReLU network with hidden widths at most Cd^4, 2d, and 1.The first layer computes the perturbation, the next recovers coordinates, and the final layers compute the bounded target.
  • Regularity: The constructed function is globally [0,1]-valued, continuous, and maps the unit hypercube onto [0,1].Continuity and endpoint attainment establish surjectivity on the connected cube.

C Proof of Theorem 3.1

Theorem 3.1 recursively copies a hard target into 2^d protected regions at each step, allowing hardness at one depth to transfer to the next. This yields exponential L2 and exact-computation depth separations through a copier implemented by one additional hidden layer.

  • Base hardness: The affine base function has squared L2 error at least 1/12 under the uniform distribution for every affine approximant.The optimal affine approximant is constant, reducing the calculation to one dimension.
  • Inductive reduction: Each protected cube is intersected by at most d affine hyperplanes, so a narrow first layer misses many copies and can be absorbed into the next layer.This exposes the preceding hard instance and drives the induction across adjacent depths.
  • Recursive copier: A depth-2 copier creates 2^d exact translated-and-rescaled copies of any target on pairwise disjoint protected cubes.The identity (h ◦ S)(q_s + r u) = h(u) preserves the target exactly on each cube.
  • Network implementation: The copier is implemented by one shared hidden layer of width O(d^4), combining perturbation features, clipping features, and identity carriers.Its affine output merges with the next network layer, so precomposition adds exactly one hidden layer.
  • Scope boundary: The distributional construction keeps support geometrically explicit but spreads it to exponential radius, placing the result outside the boundedness regime relevant to the Vardi–Shamir barrier.The additional distributional properties are not used in the lower-bound induction.
Loading 2608.23877v1…