---
kind: concept
slug: depth-separation
title: Depth separation
summary: >-
  Deep ReLU networks can reach error eps with polylog(1/eps) neurons when their depth grows like log(1/eps), while shallow networks need poly(1/eps) neurons for the same smooth functions. The result is a size-and-depth statement about what networks can represent, proved by construction and lower bound. It says nothing about training, and the constructions use hand-built weights.
tags: [theory, expressivity, function-approximation]
papers: ["1610.04161"]
related: [multi-layer-perceptron]
status: draft
updated_at: 2026-10-18
---

## 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 [arxiv: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)) [arxiv: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 [arxiv: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 [arxiv: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 [arxiv: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 [arxiv:1610.04161 thm. 2]. Card: [Why Deep Neural Networks for Function Approximation?](/papers/1610.04161).

### 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 [arxiv:1610.04161 lem. 3, thm. 4]. The derivative bound is a hypothesis to check for each function; it is not automatic for smooth functions [arxiv:1610.04161 thm. 4].

### Linear combinations, products and compositions

Linear combinations of k such functions keep the same size, independent of k [arxiv: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) [arxiv: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 [arxiv: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) [arxiv: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 [arxiv: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)) [arxiv:1610.04161 thm. 11]. For depth L the bound becomes L (mu/(16 eps))^(1/(2L)) [arxiv:1610.04161 app. F]. Together with the upper bound this makes the log size tight for x^2 [arxiv: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 [arxiv: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.

| Situation | Use | Why |
|---|---|---|
| Ask how small a network can be for a smooth 1-D target at error eps | Smooth univariate result | Depth Theta(log 1/eps), size polylog(1/eps) [arxiv:1610.04161 thm. 4] |
| Target is a low-degree polynomial with bounded coefficients | Polynomial result | Depth O(p + log(p/eps)) [arxiv:1610.04161 thm. 2] |
| Ask whether a shallow net of fixed depth is enough | Lower bound | Size at least log2(mu/(16 eps)) for any depth; the depth-L form applies to fixed L [arxiv:1610.04161 thm. 11, app. F] |
| Target is a sum, product or composition of smooth pieces | Linear, product, composition results | Size independent of k for sums; grows with k for products and compositions [arxiv:1610.04161 cor. 5, cor. 6, cor. 7] |
| Need a trained network or a learning rate | None on this page | The paper trains nothing and states no optimiser or data [arxiv:1610.04161 §3] |

## Caveats

- **Existence, not learnability.** The constructions give weights by design. The paper does not show that gradient descent finds them [arxiv: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 [arxiv: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 [arxiv: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 [arxiv: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 [arxiv: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 [arxiv: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 [arxiv:1610.04161 thm. 1]. Replacing the square by a polynomial evaluator gives the smooth-function construction [arxiv:1610.04161 thm. 4]. The sketch below follows that chain.

```pseudocode
# 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?](/papers/1610.04161): the depth-versus-size bounds above for ReLU and binary step networks, with matching lower bounds for strongly convex functions.