Source-linked AI summary
Why Deep Neural Networks for Function Approximation?
Shiyu Liang, R. Srikant
TL;DR
The paper asks why deep networks may require fewer neurons than shallow networks for accurate function approximation. It analyzes ReLU and binary-step networks and reports exponential size differences for broad smooth function classes, with logarithmic-depth networks achieving polylogarithmic size.
Problem
The paper studies whether shallow networks require exponentially more neurons than deep networks to achieve a given approximation error for broad function classes.
Method
The paper analyzes feedforward networks combining ReLUs and binary step units, using uniform L∞ approximation and depth- and size-bound questions.
Results
Θ(log(1/ε))-layer networks need O(polylog(1/ε)) neurons, while o(log(1/ε))-layer networks require Ω(poly(1/ε)) neurons for sufficiently piecewise-smooth functions.
Takeaways & Limitations
For the studied smooth univariate and multivariate functions, deep networks use exponentially fewer neurons than shallow networks at comparable approximation accuracy.
Takeaways & Limitations
The multivariate upper bound can be loose because it assumes a general multivariate polynomial of degree p.
Abstract
from arXiv · showhide
Recently there has been much interest in understanding why deep neural networks are preferred to shallow networks. We show that, for a large class of piecewise smooth functions, the number of neurons needed by a shallow network to approximate a function is exponentially larger than the corresponding number of neurons needed by a deep network for a given degree of function approximation. First, we consider univariate functions on a bounded interval and require a neural network to achieve an approximation error of $\varepsilon$ uniformly over the interval. We show that shallow networks (i.e., networks whose depth does not depend on $\varepsilon$) require $Ω(\text{poly}(1/\varepsilon))$ neurons while deep networks (i.e., networks whose depth grows with $1/\varepsilon$) require $\mathcal{O}(\text{polylog}(1/\varepsilon))$ neurons. We then extend these results to certain classes of important multivariate functions. Our results are derived for neural networks which use a combination of rectifier linear units (ReLUs) and binary step units, two of the most popular type of activation functions. Our analysis builds on a simple observation: the multiplication of two bits can be represented by a ReLU.
1 INTRODUCTION
The paper investigates whether depth reduces the neuron count needed for accurate function approximation. It develops results showing exponential size differences between shallow and deep networks for broad function classes.
- Motivation: Recent work suggests depth can exponentially reduce the neurons needed to approximate specific functions or neural-network classes.Prior results include exponential increases in linear regions with depth and exponential shallow-network size requirements for selected functions.
- Motivation: The paper asks whether shallow networks require exponentially more neurons than deep networks at a fixed approximation error for a large class of functions.
- Setup: The networks may combine rectifier linear units and binary step units.
- Main results: Θ(log(1/ε))-layer networks use O(polylog(1/ε)) neurons, whereas o(log(1/ε))-layer networks require Ω(poly(1/ε)) neurons for sufficiently piecewise-smooth functions.The paper also states a matching Ω(log(1/ε)) neuron lower bound for differentiable strongly convex functions.
- Organization: The paper’s results are organized around definitions, upper bounds, lower bounds, and conclusions, while noting related work by Yarotsky.
2 PRELIMINARIES AND PROBLEM STATEMENT
This section defines the feedforward-network setting and formulates approximation questions in terms of depth, size, and error. It also specifies the activation functions and the sufficient-versus-necessary bounds the paper studies.
- Feedforward neural networks: A feedforward neural network consists of computational layers and defines a function from R^d to R.The network is parameterized by layer outputs, weights, biases, depth, and total size.
- Feedforward neural networks: The analysis considers ReLUs, binary step units, and combinations of these activations.The ReLU is max{0,x}, while the binary step unit is I{x ≥ 0}.
- Feedforward neural networks: Figure 1 illustrates an n-layer structure for finding the binary expansion of a number in [0, 1].
- Problem statement: The approximation problem asks whether depth L and size N can achieve ε-approximation, and how minimum size changes when depth is fixed.Together, these questions characterize sufficient and necessary network-size and depth bounds.
- Problem statement: The paper compares deeper and shallower networks approximating the same function with the same error through the size ratio N_d/N_s.
3 UPPER BOUNDS ON FUNCTION APPROXIMATIONS
The paper develops upper bounds showing that deep ReLU/BSU networks can approximate broad classes of univariate and multivariate functions with polylogarithmic-size networks, while exploiting depth to represent polynomial structure efficiently.
- L∞ approximation measures the maximum pointwise disagreement between two functions on the cube [0, 1]^d.
- Univariate functions: A deep network for binary-expansion-based approximation uses O(n) layers, O(n) binary step units, and O(n) rectifier linear units.The construction extracts binary digits and then evaluates the resulting representation.
- Univariate functions: Deep networks approximate sufficiently smooth univariate functions with polylogarithmic neuron counts at ε error.The result covers general functions with enough smoothness and extends beyond individual polynomial examples.
- Univariate functions: For sufficiently smooth component functions, deep networks also approximate linear combinations, multiplications, and compositions with ε error.The size bound for linear combinations is independent of the number of component functions, whereas multiplication and composition bounds grow with that number.
- Multivariate functions: For multivariate functions, the paper gives upper bounds for products of linear functions, general polynomials, and compositions involving multivariate polynomials and smooth univariate functions.The multivariate polynomial result follows by viewing a polynomial as a linear combination of products.
- Multivariate functions: Deep networks can reduce polynomial-approximation size from O(exp(p)) to O(poly(p)) as polynomial degree p becomes large.This comparison is stated for fixed input dimension and the same ε error.
- Multivariate functions: The upper bounds provide approximation error at most ε, and the paper states that combining them with lower bounds yields tight network-size bounds.
4 LOWER BOUNDS ON FUNCTION APPROXIMATIONS
The paper establishes lower bounds showing that accurate approximation of strongly convex functions requires network size growing logarithmically with 1/ε, and contrasts shallow and deeper networks under shared function conditions.
- N ≥ log2(µ/ε) − 4 for ε-approximating differentiable, µ-strongly convex functions with ReLU and binary step networks.
- For univariate functions satisfying both theorem conditions, a shallow network of depth o(log(1/ε)) can be replaced by a deeper network of depth Θ(log(1/ε)).
- The deeper network requires polynomially logarithmic size relative to the shallow network for approximating the same function.
- The strong-convexity result also applies to strongly concave functions and functions composed of strongly convex or strongly concave pieces.
5 CONCLUSIONS
The conclusions state that shallow feedforward networks can require exponentially more neurons than deep networks for approximating broad classes of smooth univariate and multivariate functions using ReLUs and binary step units.
- Exponentially more neurons are needed by shallow networks than deep networks for function approximation across a large class of smooth univariate and multivariate functions.
- The results concern feedforward neural networks using rectifier linear units and binary step units.
- The constructive approximation uses binary expansions and networks whose implementation can require O(N) layers, O(N) binary step units, and O(N^2) ReLU units.
APPENDIX C PROOF OF COROLLARY 7
The proof constructs approximations to compositions by cascading approximating subnetworks and tracks error and resource growth across the composition depth.
- Fm is defined inductively as h1 ◦ ... ◦ hm, allowing the approximation to be built by cascading approximations for Fm−1 and hm.
- The base case establishes an approximating network for F1, after which the induction assumes an approximation for Fm−1 and constructs one for Fm.
- The proof bounds derivative-related quantities and propagates layer, binary-step-unit, and ReLU-unit counts through the cascade.
- The resulting resource bounds include logarithmic factors in k and 1/ε, with separate accounting for binary step units and rectifier linear units.
APPENDIX D PROOF OF THEOREM 8
The proof approximates multivariate functions by converting each input coordinate to a finite binary expansion, evaluating the resulting polynomial approximation, and accounting for the resulting network resources.
- The construction first finds binary expansions of the input coordinates and then uses a multilayer network to approximate the polynomial.
- For d coordinates and n-bit expansions, the binary-conversion stage uses n layers and dn binary step units.
- The implementation uses dn ReLU units in each of p layers, totaling dnp ReLU units for the polynomial stage.
- The full network uses p + n layers, dn binary step units, and dnp rectifier linear units.
- The proof separately analyzes the approximation error after binary conversion and polynomial evaluation.
APPENDIX E PROOF OF THEOREM 9
The proof constructs a deep network for multinomial functions by combining approximations of individual monomials and bounding their total number. It then characterizes the resulting size when either input dimension or degree is fixed.
- The proof applies Theorem 4 to construct a deep neural network for each multinomial function gα(x) = xα.The resulting network is denoted ˜gα.
- The total network size is bounded by summing the contributions from all multinomial functions.
- With fixed input dimension d, the size bound in (8) has the order stated for that regime.
- With fixed degree p, the size bound in (8) has the order stated for that regime.
APPENDIX F PROOF OF THEOREM 11
The proof derives lower bounds by relating the break points required for uniform approximation to network depth and size. It extends the univariate argument to multivariate functions and compares the resulting shallow and optimally deep regimes.
- Univariate lower bound: The univariate proof first lower-bounds the break points needed for ε-approximation, then relates that number to network depth L and size N.A break point is a discontinuity of the function or its derivative.
- Univariate lower bound: Strong convexity forces break points in separated intervals when a ReLU-and-step network attempts to approximate the target with no interior break point.Assuming linearity across the larger interval leads to a contradiction with the approximation inequalities.
- Univariate lower bound: The approximation therefore requires at least the stated number of break points in [0, 1].
- Depth-size relation: A depth-L, size-N network has at most (N/L)^L break points, imposing a constraint on L and N.Writing m = N/L and using m ≥ 2 supports the subsequent bound.
- Multivariate extension: For d > 1, fixing all but one coordinate reduces the argument to a strongly convex univariate restriction with the same ε-approximation guarantee.
- Conclusion: The proof concludes the theorem after combining the break-point argument with the depth-size constraint.
- Depth-size relation: If depth L is fixed, the lower bound gives the stated shallow-network growth; optimizing L yields Ω(log 1/ε), close to the O(log2 1/ε) upper bound.
APPENDIX H PROOF OF COROLLARY 13
The Gaussian-function corollary constructs a deep network for a multivariate Gaussian on [0, 1]^d by combining coordinatewise subnetworks with networks that combine their outputs.
- For the Gaussian function f(x) = e−∑i=1^d(x(i))^2/2 on [0, 1]^d, the corollary asserts existence of a deep neural network with the stated resource bounds.
- The construction first builds d coordinatewise multilayer networks using binary step units and rectifier linear units.
- A separate deep network combines the coordinatewise approximations to form the multivariate approximation.
- The resulting approximation error is bounded above by the expression obtained from inequalities (13) and (14).
- The constructed deep network has the stated size bound.
APPENDIX I PROOF OF COROLLARY 14
The ridge-function corollary reduces approximation of f(x) = g(aT x) to the univariate variable t = aT x. The resulting deep network inherits the univariate approximation construction and error guarantee.
- For f(x) = g(aT x) with ∥a∥1 = 1, a ⪰ 0, and x ∈ [0, 1]^d, the corollary asserts a multilayer network with the stated resource bounds.
- Defining t = aT x gives 0 ≤ t ≤ 1, so the univariate network construction for g applies.
- The multivariate network is defined from the univariate approximator by substituting the ridge coordinate aT x.
- The resulting approximation error is obtained from the univariate network's error bound.
- The proof concludes the ridge-function corollary.