Source-linked AI summary
Error bounds for deep ReLU networks using the Kolmogorov--Arnold superposition theorem
Hadrien Montanelli, Haizhao Yang
TL;DR
Deep-network approximation seeks to understand when network size can avoid the curse of dimensionality. This paper constructs a Kolmogorov–Arnold superposition approximation for a subset of continuous multivariate functions, showing a reduced network-size and depth growth rate while identifying conditions and settings that bound the result’s scope.
Problem
Deep-network approximation seeks to determine when network size can avoid the O(ε^-n) growth associated with the curse of dimensionality.
Source: §1 · p. 2Method
Results
O(ε^-log n) depth and size growth, rather than O(ε^-n), is established for the specified multivariate functions.
Source: §5 · p. 7Takeaways & Limitations
Abstract
from arXiv · showhide
We prove a theorem concerning the approximation of multivariate functions by deep ReLU networks, for which the curse of the dimensionality is lessened. Our theorem is based on a constructive proof of the Kolmogorov--Arnold superposition theorem, and on a subset of multivariate continuous functions whose outer superposition functions can be efficiently approximated by deep ReLU networks.
1. Introduction
The introduction traces the Kolmogorov–Arnold theorem to Hilbert’s 13th problem and frames its relevance to the curse of dimensionality in deep-network approximation. The paper develops a constructive superposition-based approach for a subset of continuous multivariate functions.
1. Introduction
- The Kolmogorov–Arnold superposition theorem represents continuous multivariate functions using one-variable functions, following work prompted by Hilbert’s 13th problem.Kolmogorov and Arnold’s results successively reduced the number of variables, with the final theorem requiring only one-variable functions.Source: §1 · p. 1
- Earlier neural-network interpretations of the theorem were criticized because its inner and outer functions were difficult to approximate and the outer functions depended on the target function.The latter dependence meant the network architecture could not be parametrized.Source: §1 · p. 1
- The theorem’s construction builds on Sprecher’s work and later corrections, while subsequent studies also explored numerical implementations.Braun and Griebel modified Sprecher’s constructive proof, and later work proposed algorithms to implement the theorem.Source: §1 · p. 2
- Deep-network approximation asks when network size can avoid the O(ε^-n) growth associated with the curse of dimensionality.The introduction identifies this as a central theoretical problem.Source: §1 · p. 2
- The paper introduces a subset of continuous multivariate functions whose outer superposition functions are amenable to deep ReLU approximation, lessening the curse of dimensionality.Its proof uses a constructive Kolmogorov–Arnold theorem and approximates both inner and outer functions with very deep ReLU networks.Source: §1 · p. 2
2. Constructive version of the Kolmogorov–Arnold superposition theorem
This section presents a constructive Kolmogorov–Arnold decomposition, building a Hölder-continuous inner function and iteratively constructing outer functions. It then restricts attention to functions for which the outer functions have controlled Lipschitz constants.
2. Constructive version of the Kolmogorov–Arnold superposition theorem
- The constructive theorem represents each continuous f using a common Hölder-continuous inner function and m + 1 continuous outer functions.The proof follows a construction associated with Sprecher, with later modifications completing the proof.Source: §2 · p. 2
- The inner function ψ is defined recursively on uniform grids D_k whose step sizes are γ^-k.Its construction begins at grid points and extends to the function’s domain and range [0, 2).Source: §2 · pp. 2–3
- The constructed inner function is (ν, α)-Hölder continuous, with α = log_γ 2.Its graph exhibits self-similarity as k increases, as illustrated for n = 2 and γ = 10.Source: §2 · p. 3, Figure 1 · p. 3
- Outer functions are constructed iteratively using shifted grids and approximate residuals, with grid resolution chosen according to the residual’s continuity.The construction starts with f_0 = 0 and forms successive approximate functions f_r.Source: §2 · pp. 3–4
- The outer functions’ Lipschitz constants depend on f through the iteration-specific grid indices k_ℓ(f).This dependence motivates the function class defined by bounding those indices uniformly across iterations.Source: §2 · p. 4
- The class K_C comprises continuous functions whose iteration indices k_r(f) are bounded by a constant C, yielding controlled outer-function Lipschitz constants.The definition is given for n ≥ 2, m ≥ n, γ ≥ m + 2, and the specified δ and η.Source: §2 · p. 4
3. Approximation of the inner and outer functions by very deep ReLU networks
This section uses modulus-of-continuity bounds and a scaling argument to extend deep-ReLU approximation results to scaled hypercubes, then applies them to the inner and outer functions in the superposition construction.
3. Approximation of the inner and outer functions by very deep ReLU networks
- For comparison, Yarotsky’s 2018 bound is O(ω(O(W^-2/n))) for very deep networks, while classical multivariate polynomial approximation incurs O(ω(d^-1/n)) errors.The cited account says the neural-network bound matches a lower bound based on VC dimension, and the classical rate matches a lower bound based on nonlinear widths.Source: §3 · p. 5
- The section extends Yarotsky’s very-deep-network result from the unit hypercube to domains [0, M]^n.The scaled-domain corollary gives networks of size W and depth L ≤ c0(n)W for continuous functions with a modulus of continuity.Source: §3 · p. 5
- A rescaling g(x) = f(x/M) transfers the scaled-domain problem to [0, 1]^n, with modulus ωg(δ) = ωf(Mδ).The resulting network is evaluated at Mx to approximate f on the original domain.Source: §3 · p. 5
- The construction assumes m = 2n and γ = 2n + 2 throughout the remainder of the paper.Source: §3 · p. 5
- The inner function ψ also admits a deep ReLU approximation for any 0 < ε < 1, with depth L ≤ c0(1)W.The supplied proposition states the depth bound but does not include the complete size bound.Source: §3 · p. 5
- The outer functions have deep ReLU approximations of depth L ≤ c0(1)W and size W, with W as small as c4(n, r)ε^-1/2 for ε approximation error.The outer functions are defined at iteration r for functions in KC([0, 1]^n; R) with sup norm at most 1.Source: §3 · pp. 5–6
4. Main theorem
The theorem gives deep ReLU approximation guarantees for bounded functions in KC([0, 1]^n; R), using the Kolmogorov–Arnold superposition theorem and ReLU approximations of its inner and outer functions. Its upper bounds lessen the curse of dimensionality asymptotically as the error approaches zero.
4. Main theorem
- For n ≥ 2 and ∥f∥L∞([0,1]^n) ≤ 1, a deep ReLU network achieves ∥f − f̃r∥L∞([0,1]^n) ≤ ε for any 0 < ε < 1.Source: §4 · p. 6
- Choosing r(ε) as specified in the theorem gives ∥f − fr∥L∞([0,1]^n) ≤ ε/2 before the network approximation is applied.Source: §4 · p. 6
- The resulting network has depth L ≤ c0(1)(Wψ + Wφ) and size W ≤ n(2n + 1)Wψ + (2n + 1)Wφ.Source: §4 · p. 7
- The theorem’s upper bounds show that the curse of dimensionality is lessened asymptotically as ε approaches zero.Source: §4 · p. 7
- For functions with m weak and bounded derivatives, Yarotsky’s O(ε^-n/m) bound can be smaller than O(ε^-log n) at fixed n and large m, but larger at fixed m and large n [27, Thm. 1].Source: §4 · p. 7
5. Discussion
The paper proves deep-ReLU approximation bounds with reduced dimensional dependence by implementing the Kolmogorov–Arnold superposition theorem. It identifies Lipschitz inner functions and bounds for other activations as directions for further work.
5. Discussion
- Network depth and size grow like O(ε^-log n), rather than O(ε^-n), by implementing the Kolmogorov–Arnold superposition theorem.These are upper bounds for approximating multivariate functions by deep ReLU networks.Source: §5 · p. 7
- A Lipschitz continuous inner function would yield O(ε^-1) estimates, but Actor and Knepley’s algorithm does not provide a method to compute the outer functions [34].Source: §5 · p. 7
- Error bounds for deep networks with sigmoid or tanh activations remain an open theoretical direction; the paper notes ReLU’s role in avoiding gradient degeneracy during training.The gradient-degeneracy statement is qualified to ReLU combined with other tricks.Source: §5 · p. 7