Universal approximation

Overview

Universal approximation says that a network of sufficient size can reach any target accuracy 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 1610.04161 §2.2, eq. 1.

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

The RUMnet result measures closeness of choice models rather than of a scalar function 2207.12877 §3. Its card includes experiments, but the authors' numbers do not test the approximation claim itself 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 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 1610.04161 lem. 3, thm. 4. The derivative bound is a hypothesis to check for each function, not something smoothness gives automatically 1610.04161 thm. 4. Card: Why Deep Neural Networks for Function Approximation?.

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 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 1610.04161 thm. 2.

Sums, products and compositions

Linear combinations of k such functions keep the same size, independent of k 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 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) 1610.04161 thm. 9. The paper sets this against three-layer bounds from earlier work, d^p/eps^2 and d^(2p)/eps^2 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)) 1610.04161 thm. 11. With depth L the bound weakens to L (mu/(16 eps))^(1/(2L)) 1610.04161 app. F. For x^2 this matches the upper bound, so the logarithmic size is needed there 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 1610.04161 §1, cor. 12. See 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 2207.12877 §2.2, §2.3. Its theory uses ReLU networks 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 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 2207.12877 §4.2, Proposition 3. The theory assumes independent unobserved attributes, attributes normalised to [-1, 1], and ties of probability zero 2207.12877 §2.1, §4.1. Card: Representing Random Utility Choice Models with Neural Networks.

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.

The bounds are existence statements with unstated O() constants. Use them to compare growth rates, not as a parameter count for a real model 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.

# 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 1610.04161 thm. 4, cor. 12. The RUMnet card says the generalisation gap does not depend on K but grows exponentially with depth 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 1610.04161 thm. 8, cor. 7.

Papers

• Why Deep Neural Networks for Function Approximation?: 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: 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.