Source-linked AI summary
Error bounds for approximations with deep ReLU networks
Dmitry Yarotsky
TL;DR
The paper asks how shallow and deep piece-wise-linear networks differ in approximating Sobolev-space functions. It establishes ReLU approximation upper and lower bounds, showing greater efficiency for deep networks and an adaptive depth-6 construction for 1D Lipschitz functions.
Problem
The paper studies the expressive-power gap between shallow and deep networks for approximation in Sobolev spaces.
Method
The paper derives ReLU-network approximation upper and lower bounds, including constructions for smooth functions and lower bounds under fixed, adaptive, and individual-approximation settings.
Results
Deep ReLU networks approximate smooth functions more efficiently than fixed-depth networks, while a function-dependent depth-6 network approximates any 1D Lipschitz function with O(1/ϵ ln(1/ϵ)) connections and activation units.
Takeaways & Limitations
Unbounded depth improves approximation efficiency for sufficiently smooth functions, and adaptive finite-depth architectures can reduce complexity for 1D Lipschitz approximation.
Takeaways & Limitations
The Sobolev-space setting may not reflect typical applications whose symmetries and hierarchical or structural properties narrow the relevant function classes.
Abstract
from arXiv · showhide
We study expressive power of shallow and deep neural networks with piece-wise linear activation functions. We establish new rigorous upper and lower bounds for the network complexity in the setting of approximations in Sobolev spaces. In particular, we prove that deep ReLU networks more efficiently approximate smooth functions than shallow networks. In the case of approximations of 1D Lipschitz functions we describe adaptive depth-6 network architectures more efficient than the standard shallow architecture.
1 Introduction
The paper studies shallow-versus-deep expressiveness for Sobolev-space approximation and develops upper and lower complexity bounds for ReLU networks. Its results show advantages for unbounded depth and function-dependent depth-6 architectures, alongside lower bounds under several approximation settings.
- Motivation: The paper examines shallow-versus-deep expressiveness for approximating Sobolev-type function spaces with ReLU networks.The setting uses L∞ approximation over Wn,∞([0,1]^d), including fixed and adaptive architectures.
- Upper bounds: O(ln(1/ϵ)) depth and complexity suffice for ϵ-approximating f(x)=x2, also yielding comparable bounds for approximate multiplication.The multiplication construction follows from the square approximation result.
- Upper bounds: O(ln(1/ϵ)) depth and O(ϵ−d/n ln(1/ϵ)) complexity suffice to approximate every function in Fd,n.This is the paper’s general upper bound for a ReLU architecture approximating functions in the Sobolev ball.
- Adaptive architectures: O(1/ϵ ln(1/ϵ)) connections and activation units suffice for a given 1D Lipschitz function using an adaptive depth-6 ReLU network.The architecture may depend on the function being approximated, and the bound is below the stated continuous-model-selection lower bound.
- Lower bounds: The paper also derives lower bounds for continuous model selection, common architectures, and individual functions, using nonlinear-width and VC-dimension arguments.For continuous model selection, at least ∼ϵ−d/n weights are required; other settings yield distinct lower-bound rates.
- Lower bounds: Fixed-depth approximation of nonlinear C2 functions requires at least ∼ϵ−1/(2(L−2)) computation units, making fixed depth less efficient than unbounded depth for sufficiently smooth functions.The comparison is made against the general upper bound for unbounded-depth networks.
2 The ReLU network model
The paper defines feedforward ReLU networks by layered affine computation units and measures complexity through depth, units, and weights. It shows that continuous piece-wise linear activations with finitely many breakpoints can replace ReLU with only constant-factor complexity changes.
- Network model: Each hidden computation unit applies a weighted affine input followed by the ReLU activation σ(x)=max(0,x), while the output unit is linear.Inputs to a unit may come from units in any preceding layer.
- Complexity measures: Network depth is the number of layers, and complexity is measured by depth, computation units, and total weights.The total number of weights equals connections plus computation units; shallow single-hidden-layer networks are depth-3 under this convention.
- Activation equivalence: Replacing an activation with M breakpoints increases the number of units by at most M+1 and weights by at most (M+1)^2.These are constant-factor overheads when M is fixed.
- Activation equivalence: Conversely, on a bounded input domain, a ReLU network can be represented with the alternative activation using at most 4W weights and 2U units.The construction chooses a local representation of ReLU near zero at each unit.
- Activation equivalence: A continuous piece-wise linear activation with M breakpoints can be represented using ReLU units without changing depth.Each original activation unit is replaced by a linear combination of a constant function and M+1 ReLU units.
3 Upper bounds
The paper develops upper bounds showing that deep ReLU networks approximate squaring, multiplication, and Sobolev functions efficiently, with further savings from function-dependent architectures for one-dimensional Lipschitz functions.
- 3.1 Fast deep approximation of squaring and multiplication: O(ln(1/ϵ)) depth, weights, and computation units suffice to approximate x^2 on [0,1] with error ϵ.The construction uses iterated sawtooth functions implemented by ReLU networks.
- 3.1 Fast deep approximation of squaring and multiplication: O(ln(1/ϵ)) depth, weights, and computation units also suffice for approximate multiplication on inputs bounded by M.The approximation error is at most ϵ, with constants depending on M where stated.
- 3.2 Fast deep approximation of general smooth functions: O(ϵ^−d/n ln(1/ϵ)) weights and computation units, with depth O(ln(1/ϵ)), suffice to approximate every function in Fd,n.The architecture is fixed across the function class, while the weights vary with the approximated function.
- 3.3 Faster approximations using adaptive network architectures: An adaptive depth-6 ReLU architecture approximates any one-dimensional Lipschitz function with O(1/ϵ ln(1/ϵ)) weights, connections, and computation units.The architecture depends on the function being approximated.
- 3.3 Faster approximations using adaptive network architectures: Choosing m = ⌈1/2 log3(1/ϵ)⌉ and T = ⌈2m/ϵ⌉ yields error at most ϵ and complexity O(1/ϵ ln(1/ϵ)).This parameter choice is used in the adaptive one-dimensional construction.
4 Lower bounds
The paper derives lower bounds for ReLU approximation complexity under continuous weight selection, fixed architectures with arbitrary weight dependence, and adaptive architectures. These bounds show both general hardness for Sobolev-space approximation and a separation between fixed and function-dependent architectures.
- 4.1 Continuous nonlinear widths: W ≥ cϵ−d/n under continuous parameter selection when one fixed ReLU architecture approximates every function in Fd,n.This follows from the nonlinear-width theorem applied to the network’s weight space.
- 4.1 Continuous nonlinear widths: Optimal weights minimizing approximation error can be discontinuous in general, so the continuous-selection hypothesis is essential to this lower bound.The paper notes that this discontinuity occurs even for shallow networks.
- 4.3 Adaptive network architectures: For d = n = 1, adaptive architectures achieve an upper bound proportional to ϵ−1 ln(1/ϵ), asymptotically below the continuous-selection lower bound proportional to ϵ−1.The paper interprets this gap as reflecting the extra expressiveness of variable network architectures.
- 4.2 Bounds based on VC-dimension: W ≥ cϵ−d/(2n) for any fixed architecture approximating every function in Fd,n, without assuming continuous dependence of weights on the target function.The proof converts approximation of smooth functions into shattering Boolean labelings on a finite point set and applies VC-dimension bounds.
- 4.2 Bounds based on VC-dimension: W ≥ c2ϵ−d/n ln−2p−1(1/ϵ) when the fixed architecture has depth L ≤ c1 lnp(1/ϵ).For p = 1, this matches the upper bound in Theorem 1 and the continuous-selection lower bound up to a power of ln(1/ϵ).
- 4.3 Adaptive network architectures: There exists f ∈ Wn,∞([0,1]d) whose individual approximation complexity is not o(ϵ−d/(9n)) as ϵ → 0.An enveloping-network argument strengthens a family-wide lower bound into a hard-function result for adaptive architectures.
5 Discussion
The discussion compares deep and shallow ReLU approximation efficiency across smooth-function and architecture-selection settings. Deep networks achieve stronger complexity bounds in several regimes, but adaptive architectures retain a substantial upper–lower-bound gap and the framework may not reflect structured real-world data.
- Deep vs. shallow ReLU approximations of smooth functions: Deep ReLU networks approximate smooth Sobolev functions more efficiently than fixed-depth networks, with depth O(ln(1/ϵ)) and complexity O(ϵ^-d/n ln(1/ϵ)).For nonlinear C2 functions, fixed-depth L networks require at least cϵ^-1/(2(L−2)) units, while very smooth polynomials can use O(ln(1/ϵ)) units.
- Continuous model selection vs. function-dependent network architectures: Function-dependent architecture adjustment yields a depth-6 ReLU upper bound O(ϵ^-1 ln(1/ϵ)) for approximating functions in F1,1.The construction uses reused subnetworks, an idea associated with Boolean-circuit theory.
- Upper vs. lower complexity bounds: For fixed architectures with continuous weight selection, the upper bound O(ϵ^-d/n ln(1/ϵ)) and lower bound cϵ^-d/n are tight up to O(ln(1/ϵ)).This compares Theorem 1's upper bound with the lower bound from Proposition 3.
- Upper vs. lower complexity bounds: For fixed architectures with unconstrained weight selection, the lower bound is cϵ^-d/n ln^-2p−1(1/ϵ) under depth O(ln^p(1/ϵ)), but only cϵ^-d/(2n) without that constraint.Under the depth constraint, the lower and upper bounds differ by O(ln^2p+2(1/ϵ)).
- Upper vs. lower complexity bounds: Adaptive architectures have a large gap between the depth-6 upper bound O(ϵ^-1 ln(1/ϵ)) in one dimension and the general lower bound not o(ϵ^-d/(9n)).The lower bound guarantees a hard function exists but does not match the one-dimensional adaptive upper bound.
- Scope and implications: The Sobolev approximation setting may not reflect real-world applications, which often involve symmetries, hierarchy, and other structural properties narrowing the relevant function classes.The paper identifies structure-aware expressiveness analysis as an important direction for future research.