Why Deep Neural Networks for Function Approximation?

In plain words

A neural network can approximate a curve to any accuracy if it is wide enough. This paper asks a sharper question: how many neurons are needed when the network is allowed to be deep (many layers) versus shallow (few layers)? For a large family of smooth functions, the answer is stark. A deep network reaches accuracy eps with a number of neurons that grows only like a power of log(1/eps). A shallow network needs a number that grows like a power of 1/eps, so the gap widens quickly as you ask for more accuracy.

The key trick is small. Each ReLU unit can multiply two on/off values, so a stack of layers can read the binary digits of an input number one by one and then combine them. Each extra layer buys one more binary digit of precision, which is why depth, not width, is what helps.

The results are mathematical proofs of what networks can represent. They say nothing about whether gradient descent would learn such a network, and the paper runs no experiments.

TL;DR

• For a fixed function class, a network whose depth grows as log(1/eps) reaches error eps with polylog(1/eps) neurons [thm. 4].
• Shallow networks (depth below log(1/eps)) need Omega(poly(1/eps)) neurons for the same error §1.
• For strongly convex functions the lower bound log2(mu/(16 eps)) is shown for any depth [thm. 11], so the log size is needed, not just sufficient §4.
• The constructions use binary step units to read bits. They are existence proofs with hand-built weights, not trained networks.

Problem

Universal approximation says a network of any size can reach any accuracy §1. The paper asks how the required size and depth change with the target error eps, with error measured uniformly (L-infinity) on the input cube §3. It asks two questions: which depth L(eps) and size N(eps) suffice, and, for a fixed depth L, what minimum size N is needed §2.2, eq. 1. The network class is feedforward, with ReLU units (max(0, x)), binary step units (I{x >= 0}), or both §2.1.

Method

The paper has three parts. The upper bounds (§3) are constructions. The lower bounds (§4) are a break-point count. The appendices contain the proofs of the corollaries.

1. Reading the bits of x in [0, 1] with depth fig. 1 §3.1, proof of thm. 1. A chain of n layers of binary step units outputs the first n+1 binary digits x_0, ..., x_n of x, where x = sum_i x_i / 2^i. The paper describes this network only through the figure and the sentence "straightforward to see"; no explicit weights are given in the text.

2. Squaring from the bits [thm. 1]. For f(x) = x^2, write x_tilde = sum_{i<=n} x_i / 2^i. Because x_i is 0 or 1 and 0 <= s <= 2 in the relevant range, x_i * s = max(0, 2(x_i - 1) + s). A single hidden layer of n ReLUs then computes

\tilde f(x) = \sum_{i=0}^{n} \max\Big(0,\ 2(x_i - 1) + \tfrac{1}{2^i}\sum_{j=0}^{n}\tfrac{x_j}{2^j}\Big) [thm. 1 proof]

The error is at most 2 |sum_{i>n} x_i / 2^i| <= 1/2^(n-1), so n = ceil(log2(1/eps)) + 1 gives error eps [thm. 1 proof]. Size: O(log 1/eps) layers, binary units and ReLUs each [thm. 1]. fig. 2 shows the layered network used for polynomials.

# Square x in [0, 1] to error eps with n = ceil(log2(1/eps)) + 1  [thm. 1]
# Output: approximation of x**2 on [0, 1]

def square_approximation(x, n):
    # 1. Read the first n+1 binary digits of x, one layer per digit  [fig. 1]
    bits = binary_digits(x, n)                   # each bit is 0 or 1
    # 2. Truncated value x_tilde = sum_i bits[i] / 2**i  [thm. 1 proof]
    x_tilde = sum(bits[i] / 2 ** i for i in range(n + 1))
    # 3. Bit times s equals max(0, 2 * (bit - 1) + s) for 0 <= s <= 2,
    #    so each term is one ReLU  [thm. 1 proof]
    total = 0
    for i in range(n + 1):
        s = x_tilde / 2 ** i
        total = total + relu(2 * (bits[i] - 1) + s)
    return total

3. Powers of x by depth eq. 2 [thm. 2 proof]. For a polynomial of degree p, the paper builds g_m(x) = x^m by a chain of layers. Each layer applies the same bit-times-value identity to the previous output:

g_{m+1}(\tilde x) = \sum_{j=0}^{n} \max\Big(2(x_j-1)+\tfrac{g_m(\tilde x)}{2^j},\ 0\Big) eq. 2

# Build g_1 .. g_p, with g_m(x) = x**m, using one ReLU layer per step  [eq. 2]
# bits: the n+1 binary digits of x  [fig. 1]

def power_chain(bits, p):
    # g_1 is the truncated value x_tilde itself  [thm. 2 proof]
    g = [sum(bits[j] / 2 ** j for j in range(len(bits)))]
    for m in range(1, p):
        # Each new power is a sum of ReLUs over the bits  [eq. 2]
        nxt = 0
        for j in range(len(bits)):
            nxt = nxt + relu(2 * (bits[j] - 1) + g[-1] / 2 ** j)
        g.append(nxt)
    return g                                     # g[m-1] = x_tilde**m

4. Polynomials [thm. 2]. For f(x) = sum_{i=0}^{p} a_i x^i with sum_{i=1}^{p} |a_i| <= 1 on [0, 1], the output is sum_i a_i g_i(x_tilde). Depth O(p + log(p/eps)), binary units O(log(p/eps)), ReLUs O(p log(p/eps)) [thm. 2].

5. General smooth univariate functions [lem. 3] [thm. 4]. Assume f is continuous on [0, 1], has derivatives up to order ceil(log2(2/eps)) + 1 on (0, 1), and |f^(n)| <= n! for those n. Let N = ceil(log2(2/eps)). Replace f by the degree-N polynomial P_N that interpolates f at Chebyshev nodes [lem. 3], with |f - P_N| <= 1/2^N, and build P_N(x_tilde) with the chain of step 3. Depth O(log 1/eps), binary O(log 1/eps), ReLUs O((log 1/eps)^2) [thm. 4].

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

def smooth_approximation(f, eps):
    N = ceil(log2(2 / eps))
    # 1. Degree-N polynomial that interpolates f at Chebyshev nodes  [lem. 3]
    #    (the paper states the lemma on [-1, 1]; mapping to [0, 1] is not stated)
    poly = chebyshev_interpolant(f, degree=N)
    # 2. Read bits x_0 .. x_N of the input  [fig. 1]
    bits = binary_digits(x, N)
    # 3. Evaluate the polynomial at x_tilde  [thm. 4 proof]
    return poly_chain_eval(poly, bits)           # chain from step 3 above

6. Multivariate and composed functions [cor. 5] [cor. 6] [cor. 7] [thm. 8] [thm. 9] [cor. 10].

• Linear combinations of univariate functions satisfying [thm. 4] keep the same size, independent of the number k of terms [cor. 5].
• Products of k such functions need size O((k log k)^2 + (log 1/eps)^2) ReLUs [cor. 6].
• Compositions of k such functions need O(k^2 (log 1/eps)^2 + (log 1/eps)^4) ReLUs [cor. 7].
• A product of p linear forms w_i^T x with ||w_i||_1 = 1 on [0, 1]^d: depth O(p + log(pd/eps)), ReLUs O(pd log(pd/eps)) [thm. 8].
• A general multivariate polynomial of degree p: size p^2 binom(p+d-1, d-1) log(pd/eps) [thm. 9].

7. Lower bound [thm. 11] app. F. Take a function f on the cube [0, 1]^d that has a derivative and is strongly convex with constant mu. If a ReLU/step network is within eps of f everywhere on the cube, its size N is at least log2(mu/(16 eps)). For depth L, N >= L (mu/(16 eps))^(1/(2L)) app. F, eq. in proof. The argument counts break points (points of discontinuity or of derivative discontinuity) on [0, 1] with four spaced points, then uses Telgarsky's count (N/L)^L for ReLU networks §4, app. F.

8. Deep versus shallow [cor. 12] app. G. If a univariate f satisfies both [thm. 4] and [thm. 11], and a shallow network of depth L_s = o(log 1/eps) and size N_s reaches error eps, then a network of depth Theta(log 1/eps) and size N_d = O(L_s^2 log^2 N_s) reaches the same error [cor. 12].

9. Extensions (no proof given). Piecewise smooth functions are said to follow "essentially unchanged" with an extra factor for the number of pieces §3.2. Gaussians app. H and ridge functions app. I are worked examples.

Hyperparameters

The paper trains nothing and has no learning rate or optimizer. The values below are the construction parameters that fix the network size.

Results

Theoretical bounds only. The paper reports no experiments, so nothing is measured. All size and depth numbers below are upper or lower bounds, and the O() constants are not stated. Baselines are the shallow-network bounds the paper cites.

Paper vs code

No official code. The arXiv metadata and the LaTeX source contain no repository link, and the paper names no project page. A GitHub repository search for the title and for "ReLU binary step units" returned no results (one request was refused with HTTP 403, so that search is incomplete).

Pitfalls

• Binary step units make the network discontinuous. The constructions use binary step units to read bits, so the networks cannot be trained by gradient descent from the step units. The paper proves the existence of weights, not a learning procedure. An implementer must hand-build the decoder, or replace it with an approximation the paper does not analyse.
• The bit decoder is not given explicitly. The text says the n-layer network of fig. 1 "can be used to find x_0..x_n" and gives no weights. The figure is the only description. Indexing starts at 0 with weight 2^(-i), so x_0 has weight 1 and only x = 1 has a nonzero x_0; the paper does not comment on this.
• Theorem 2's constraint and error bound do not match cleanly. The condition is sum_{i=1}^{p} |a_i| <= 1, so a_0 is unconstrained, yet the error bound p/2^(n-1) is written without showing how it follows from that sum. The choice n = ceil(log(p/eps)) + 1 is what matters; the bound is not derived in the text.
• Theorem 4's definition has a typo that matters. The network is defined as P_N(sum_i x_i / 2^N), but the analysis uses x_tilde = sum_i x_i / 2^i. Use the 2^i version; the 2^N version does not satisfy the error bound.
• The norm is not a norm. Theorem 4 and [lem. 3] define ||f|| as max f(x), without absolute value. The intended quantity is the sup norm max |f|. Lemma 3 is stated on [-1, 1] and Theorem 4 on [0, 1]; the rescaling is not shown.
• The derivative hypothesis is strong and must be checked per function. Theorem 4 needs |f^(n)| <= n! for n up to ceil(log2(2/eps)) + 1. Functions that look smooth can fail this for large parameters, for example e^(-dx), whose n-th derivative is d^n e^(-dx). See the Gaussian case below.
• Gaussian corollary (app. H) cites the wrong theorem. Its proof uses "Theorem 4" for the squares and for e^(-dx), but the claimed O(d log(d/eps)) ReLU count matches the quadratic construction [thm. 1], not [thm. 4]. Using [thm. 4] would give d log^2(d/eps) ReLUs. The derivative condition for e^(-dx) also fails for large d, as noted above. One display also writes x^(i) where (x^(i))^2 is meant.
• Composition bounds are not derived as stated (cor. 7). The recursion in the proof gives T_1(k) = O(log k log(1/eps)) and T_3(k) = O((log(1/eps))^2), which are smaller than the stated O(k log k log(1/eps)) and O(k^2 (log 1/eps)^2 + (log 1/eps)^4). The stated bound is looser, but the paper does not reconcile the two. The recursion also mixes accuracy parameters (log_3(3^m/eps) at each stage).
• Intermediate values may leave [0, 1] (cor. 7). The composition feeds h_m-tilde / (1 + eps/3) into a network that is only accurate on [0, 1]. The proof never checks that this value stays in [0, 1].
• Theorem 8's binary-unit count is inconsistent. The statement gives O(log(pd/eps)) binary step units; the proof counts n d = O(d log(pd/eps)). Use the proof's count when sizing.
• Corollary 6's proof has typos that affect the bound. It bounds the error with ||f(1)|| where ||f'|| is meant, and the binomial coefficients in its display do not match the bound that follows. N is chosen by an inequality ("suffices"), so compute it by iterating that inequality.
• Theorem 9 typo and remark exponents. The statement writes |f(x) - f(x_tilde)|, which should be |f(x) - f_tilde(x)|. The remarks give O(d^(p+1)) (fixed p) and O(p^d) (fixed d). The appendix gives O(p^2 (ed)^p) and O((ep)^(d+1)), and the binomial coefficient grows like d^p for fixed p and like p^(d-1) for fixed d. Use the appendix forms.
• Lower-bound constant gap (thm. 11). The last step writes N >= (m / (2 log2 m)) log2(mu/(16 eps)) and then claims m / (2 log2 m) >= 1 for m >= 2. That is false for 2 < m < 4: the function dips to about 0.94 at m = e. The bound holds with a constant of about 0.94 in that range.
• Telgarsky's count is for ReLU networks. The break-point bound (N/L)^L is cited for ReLU networks. The lower bound applies it to networks that also contain binary step units, and the text gives no argument for why this holds.
• "Tight" is only tight for x^2. The introduction calls the lower bound tight. For general strongly convex functions the paper's own Remark (2) leaves a log factor between Omega(log 1/eps) and the O(log^2 1/eps) upper bound. Tightness (Theta(log 1/eps)) holds for x^2 §4.
• Deep-versus-shallow corollary hides a depth dependence (cor. 12). The bound is N_d = O(L_s^2 log^2 N_s), but the final step drops L_s to get O(log^2 N_s). That needs L_s bounded, which the hypothesis L_s = o(log 1/eps) does not give.
• Corollary 10 needs l(x) in [0, 1]. The statement gives l: [0, 1]^d -> [0, 1] but does not show how to keep the polynomial in range; the composition needs it.
• Log base is unstated in some bounds. Theorems 2, 8 and 9 write log without a base. The base changes only constants, but a literal implementation of the bit count needs one.
• Piecewise-smooth extension is asserted, not proved §3.2. The factor for the number of pieces is not given.

Lineage

• Builds on: the universal-approximation results the paper cites (Cybenko 1989; Hornik 1991, among others), depth separation for sum-product networks (Delalleau et al. 2011), linear-region counts (Montufar et al. 2014), and the depth-benefit result of Telgarsky (2016) §1. Its break-point count uses Telgarsky (2016) app. F.
• Compared against: Eldan et al. (2015) on depth for specific functions, and Barron (1993) and Andoni et al. (2014) on three-layer polynomial approximation §1, §3.2.
• A similar paper posted to arXiv around the same time is cited in §1. The paper does not name it in the text.