Depth separation

Overview

Universal approximation says a network of any size can reach any accuracy. Depth separation asks how the required size changes with the target error eps, and how much depth helps 1610.04161 §1. For a family of smooth univariate functions on [0, 1], the answer is that a deep feedforward network of depth Theta(log 1/eps) and size polylog(1/eps) reaches error eps, while a shallow network of depth o(log 1/eps) needs size Omega(poly(1/eps)) 1610.04161 thm. 4, §1.

The invariant every variant shares: the network reads the binary digits of its input, one digit per layer, and combines them with ReLU units to build a polynomial. Each extra layer buys one more binary digit of precision, so accuracy is paid for in depth and not in width 1610.04161 §3.1, fig. 1.

The cards on this page prove the construction and a matching lower bound, all for ReLU and binary step units. The paper runs no experiments 1610.04161 §1.

Variants

The variants differ by function class and by which side of the bound they cover. Only one paper is on this page so far.

Squares and polynomials

For f(x) = x^2 on [0, 1] with error eps, a network with O(log 1/eps) layers, binary step units and ReLUs, each of that order, suffices 1610.04161 thm. 1. Degree-p polynomials whose non-constant coefficients have absolute sum at most 1 need depth O(p + log(p/eps)) and O(p log(p/eps)) ReLUs 1610.04161 thm. 2. Card: Why Deep Neural Networks for Function Approximation?.

Smooth univariate functions

A continuous f on [0, 1] whose derivatives up to order ceil(log2(2/eps)) + 1 are bounded by n! is approximated by a degree-N interpolant at Chebyshev nodes, with N = ceil(log2(2/eps)). The paper evaluates that polynomial with the bit-reading network, giving depth O(log 1/eps) and O((log 1/eps)^2) ReLUs 1610.04161 lem. 3, thm. 4. The derivative bound is a hypothesis to check for each function; it is not automatic for smooth functions 1610.04161 thm. 4.

Linear combinations, products and compositions

Linear combinations of k such functions keep the same size, independent of k 1610.04161 cor. 5. Products of k of them need O((k log k)^2 + (log 1/eps)^2) ReLUs, and compositions need O(k^2 (log 1/eps)^2 + (log 1/eps)^4) 1610.04161 cor. 6, cor. 7. Products of p linear forms in d dimensions need depth O(p + log(pd/eps)) and O(pd log(pd/eps)) ReLUs 1610.04161 thm. 8.

General multivariate polynomials

A degree-p polynomial in d variables needs size p^2 binom(p+d-1, d-1) log(pd/eps) 1610.04161 thm. 9. The paper compares this with three-layer bounds it cites from earlier work, which are polynomial in d^p and 1/eps 1610.04161 §3.2.

Lower bound for any depth

For a differentiable, strongly convex f on [0, 1]^d with constant mu, any ReLU or step network within eps of f has size at least log2(mu/(16 eps)) 1610.04161 thm. 11. For depth L the bound becomes L (mu/(16 eps))^(1/(2L)) 1610.04161 app. F. Together with the upper bound this makes the log size tight for x^2 1610.04161 §4.

Deep versus shallow

If f satisfies both the upper and the lower bound, and a shallow network of depth o(log 1/eps) and size N_s reaches error eps, then a network of depth Theta(log 1/eps) and size O(L_s^2 log^2 N_s) reaches the same error 1610.04161 cor. 12. The corollary is stated with the shallow depth L_s and the size N_s; see the caveat below.

When to use which

The paper gives existence and size bounds only. The choice below depends on what you want to know, not on a deployed system.

Caveats

• Existence, not learnability. The constructions give weights by design. The paper does not show that gradient descent finds them 1610.04161 §1.
• Binary step units. The bit reader uses binary step units, which are discontinuous. The paper gives the reader only as a figure and a sentence, with no explicit weights 1610.04161 §3.1, fig. 1. Implementers must build that decoder themselves.
• Derivative hypothesis. The smooth-function bound needs derivative bounds up to order about log2(1/eps). Check this per function before quoting the bound 1610.04161 thm. 4.
• Tightness only in one case. The lower bound matches the upper bound for x^2. For general strongly convex functions the paper's own remark leaves a log factor open 1610.04161 §4.
• Corollary 12 hides a depth term. Its last step drops L_s, which the hypothesis does not bound, so the stated size bound needs care 1610.04161 cor. 12.
• Constants and bases. The O() constants are not stated, and some bounds leave the log base open. Size comparisons are about growth rates only 1610.04161 thm. 2, thm. 8.

Implementation sketch

The shared core is the bit reader. A deep ReLU network with one layer per digit gives the value of x truncated to n binary digits, and a sum of ReLUs over those digits gives a square of x 1610.04161 thm. 1. Replacing the square by a polynomial evaluator gives the smooth-function construction 1610.04161 thm. 4. The sketch below follows that chain.

# Approximate smooth f on [0, 1] to error eps with a deep ReLU net  [thm. 4]
# Requires |f^(n)| <= n! for n up to N + 1, with N = ceil(log2(2 / eps))

def depth_separated_net(f, eps):
    N = ceil(log2(2 / eps))
    # 1. Degree-N interpolant of f at Chebyshev nodes  [lem. 3]
    poly = chebyshev_interpolant(f, degree=N)
    # 2. One layer per binary digit x_0 .. x_N of the input  [fig. 1]
    bits = binary_digits_layers(N)
    # 3. Evaluate poly at the truncated value using ReLU chains  [eq. 2]
    return poly_chain_eval(poly, bits)

Contradictions

None known: only one card is on this page.

Papers

• Why Deep Neural Networks for Function Approximation?: the depth-versus-size bounds above for ReLU and binary step networks, with matching lower bounds for strongly convex functions.