---
kind: concept
slug: universal-approximation
title: Universal approximation
summary: >-
  A large enough feedforward network can approximate a target to any accuracy. This page tracks what that costs in neurons and layers. Depth-based ReLU constructions give polylogarithmic size for smooth one-dimensional targets. RUMnet networks are dense in random utility choice models. These are existence results; only the RUMnet card gives a training bound.
tags: [theory, expressivity, function-approximation]
papers: ["1610.04161", "2207.12877"]
related: [depth-separation, multi-layer-perceptron, discrete-choice-modeling]
status: draft
updated_at: 2026-10-19
---

## Overview

Universal approximation says that a network of sufficient size can reach any
target accuracy [arxiv:1610.04161 §1]. It answers whether a network exists, not
how large it must be. The question this page tracks is the size and depth that
a given error eps requires, which the paper frames as a choice of depth L(eps)
and size N(eps) for a fixed function class [arxiv:1610.04161 §2.2, eq. 1].

The depth results use the uniform (sup-norm) error over the input cube
[arxiv:1610.04161 §3]. The networks are feedforward with ReLU units, binary step
units, or both [arxiv:1610.04161 §2.1]. Every upper bound is a construction
with explicit weights, not a trained network [arxiv:1610.04161 §3.1]. The depth
card is theory only and states no optimiser, learning rate or dataset
[arxiv:1610.04161 §1, §3].

The RUMnet result measures closeness of choice models rather than of a scalar
function [arxiv:2207.12877 §3]. Its card includes experiments, but the authors'
numbers do not test the approximation claim itself [arxiv:2207.12877 §6.3].

## Variants

The variants differ by target class, and by whether they give an upper bound
(a construction) or a lower bound (a necessary size).

### Classical width-based existence

The paper cites the earlier universal approximation results of Cybenko (1989)
and Hornik (1991) as the starting point [arxiv:1610.04161 §1]. No card on this
page covers them, so this page gives no sizes or constants for them.

### Depth-based constructions for smooth one-dimensional functions

A network reads the binary digits of its input, one digit per layer, and
combines them with ReLU units to evaluate a polynomial. For a continuous f on
[0, 1] whose derivatives are bounded as the paper requires, a degree-N
interpolant at Chebyshev nodes with N = ceil(log2(2/eps)) is evaluated this
way. The result has depth O(log 1/eps), O(log 1/eps) binary units 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, not something smoothness gives
automatically [arxiv:1610.04161 thm. 4]. Card: [Why Deep Neural Networks for Function Approximation?](/papers/1610.04161).

### Polynomials and squares

For f(x) = x^2 on [0, 1], depth O(log 1/eps) and O(log 1/eps) units of each
kind reach error eps [arxiv:1610.04161 thm. 1]. Degree-p polynomials with
absolute sum of the non-constant coefficients at most 1 need depth
O(p + log(p/eps)) and O(p log(p/eps)) ReLUs [arxiv:1610.04161 thm. 2].

### Sums, products and compositions

Linear combinations of k such functions keep the same size, independent of k
[arxiv:1610.04161 cor. 5]. Products 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 has a size bound of p^2 binom(p+d-1, d-1)
log(pd/eps) [arxiv:1610.04161 thm. 9]. The paper sets this against three-layer
bounds from earlier work, d^p/eps^2 and d^(2p)/eps^2 [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 that is within eps of f everywhere on the cube has size
at least log2(mu/(16 eps)) [arxiv:1610.04161 thm. 11]. With depth L the bound
weakens to L (mu/(16 eps))^(1/(2L)) [arxiv:1610.04161 app. F]. For x^2 this
matches the upper bound, so the logarithmic size is needed there
[arxiv:1610.04161 §4].

### Deep versus shallow

If a univariate f satisfies both the upper and the lower bound, a shallow
network of depth o(log 1/eps) needs poly(1/eps) neurons for error eps, while a
network of depth Theta(log 1/eps) reaches the same error with polylogarithmic
size [arxiv:1610.04161 §1, cor. 12]. See [depth-separation](/concepts/depth-separation)
for the full comparison.

### Random utility choice models

The target here is a choice probability over an assortment, not a scalar
function. RUMnet averages K^2 softmax outputs. Each output uses one sampled
product function and one sampled customer function, both feedforward networks,
and a utility network [arxiv:2207.12877 §2.2, §2.3]. Its theory uses ReLU
networks [arxiv:2207.12877 §4.1]. The set of RUMnet choice models is dense in
the set of RUM models, so the error can be made small with enough samples and a
large enough network [arxiv:2207.12877 §3, Proposition 1].

The sample count is the size knob. The card reports that K can be chosen of
order 1/eps^2, times a polynomial in log(1/eps), depth, the assortment size and
e^M [arxiv:2207.12877 §4.2, Proposition 3]. The theory assumes independent
unobserved attributes, attributes normalised to [-1, 1], and ties of
probability zero [arxiv:2207.12877 §2.1, §4.1]. Card:
[Representing Random Utility Choice Models with Neural Networks](/papers/2207.12877).

## When to use which

The choice depends on what you need to know. The 1610 card gives no measured
performance, so its rows name the question and the bound that answers it. The
RUMnet rows name the result and its assumptions; its accuracy numbers are
author-reported and are not evidence for the approximation claim.

| Situation | Use | Why |
|---|---|---|
| You only need to know that some network reaches error eps | Classical existence results | Cited in the paper, not covered by a card here [arxiv:1610.04161 §1] |
| Target is a random utility choice model over an assortment | RUMnet density result | Dense in the RUM class; K of order 1/eps^2 [arxiv:2207.12877 §3, Prop. 3] |
| Choice model, and you need the estimation cost as well | RUMnet generalisation bound | Gap does not grow with K but grows exponentially with depth [arxiv:2207.12877 §4.2, Prop. 2] |
| Smooth one-dimensional target, size budget for error eps | Smooth univariate construction | Depth O(log 1/eps), ReLUs O((log 1/eps)^2) [arxiv:1610.04161 thm. 4] |
| Low-degree polynomial target with bounded coefficients | Polynomial result | Depth O(p + log(p/eps)) [arxiv:1610.04161 thm. 2] |
| Target is a sum, product or composition of smooth pieces | Sum, product or composition bounds | Sums keep their size; products and compositions grow with k [arxiv:1610.04161 cor. 5, cor. 6, cor. 7] |
| Fixed shallow depth, and you want to know if it can reach eps | Lower bound | Size at least log2(mu/(16 eps)) for strongly convex f [arxiv:1610.04161 thm. 11, app. F] |
| You need a learning-rate recipe for a smooth function | None on this page | The depth paper trains nothing [arxiv:1610.04161 §3] |

The bounds are existence statements with unstated O() constants. Use them to
compare growth rates, not as a parameter count for a real model
[arxiv:1610.04161 thm. 4].

## Implementation sketch

The sketch below only computes the growth the upper bound allows for a smooth
one-dimensional target. It builds no network. The O() constants are not stated
in the paper, so the outputs are relative sizes.

```pseudocode
# Relative size of a depth-based construction for a smooth f on [0, 1]
# Growth only: constants are not stated  [thm. 4]

def construction_size(eps):
    # 1. Degree and number of binary digits N  [app. thm. 4 proof]
    N = ceil(log2(2 / eps))
    # 2. Depth grows like log(1/eps), i.e. like N  [thm. 4]
    depth = N
    # 3. ReLU count grows like (log 1/eps)^2, i.e. like N^2  [thm. 4]
    relus = N ** 2
    return depth, relus
```

## Contradictions

No direct contradiction. The two cards measure different things, so their
results do not compete.

- Size for a given error: the depth card says depth lets a network reach error
  eps with polylogarithmic size [arxiv:1610.04161 thm. 4, cor. 12]. The RUMnet
  card says the generalisation gap does not depend on K but grows exponentially
  with depth [arxiv:2207.12877 §4.2, Proposition 2]. This is a trade-off between
  expressivity and estimation, not a disagreement. The page does not resolve it.
- Card-internal problems remain on the depth card: the binary-unit count in
  thm. 8 and the composition bound in cor. 7 are listed there and are not
  resolved here [arxiv:1610.04161 thm. 8, cor. 7].

## Papers

- [Why Deep Neural Networks for Function Approximation?](/papers/1610.04161): shows that depth-based ReLU and step networks reach error eps with polylogarithmic size for smooth one-dimensional targets, with a matching lower bound for strongly convex functions.
- [Representing Random Utility Choice Models with Neural Networks](/papers/2207.12877): shows that a sample-averaged feedforward architecture is dense in the class of random utility choice models and gives a sample-size bound, with author-reported choice results.