Source-linked AI summary
Optimal approximation of continuous functions by very deep ReLU networks
Dmitry Yarotsky
TL;DR
The paper studies the optimal approximation of general continuous functions on finite-dimensional cubes by deep ReLU networks as a function of the modulus of continuity and weight count. It adapts bit extraction and approximation-theoretic techniques to characterize feasible rates, showing that the fastest rate requires depth growing nearly linearly with W and discontinuous weights. Constant-width fully connected networks achieve this fastest rate, while feasibility and discontinuity impose corresponding boundaries.
Problem
The paper asks for the optimal uniform approximation rate of general continuous functions on [0,1]^ν using ReLU networks with W weights.
Method
The paper adapts bit extraction and two-scales expansion techniques to approximation theory, using VC-dimension connections to construct deep ReLU architectures.
Results
O(ω_f(O(W^-2/ν))) is the fastest feasible rate up to logarithmic factors, achieved by constant-width networks with depth proportional to W and requiring discontinuous weight assignments.
Takeaways & Limitations
Approximation rates form two phases: a slower continuous-weight phase and a faster phase requiring depth growth and discontinuous weight assignments.
Takeaways & Limitations
Rates with exponent p>2/ν are infeasible, and rates with p>1/ν cannot be achieved with continuous weight assignments.
Abstract
from arXiv · showhide
We consider approximations of general continuous functions on finite-dimensional cubes by general deep ReLU neural networks and study the approximation rates with respect to the modulus of continuity of the function and the total number of weights $W$ in the network. We establish the complete phase diagram of feasible approximation rates and show that it includes two distinct phases. One phase corresponds to slower approximations that can be achieved with constant-depth networks and continuous weight assignments. The other phase provides faster approximations at the cost of depths necessarily growing as a power law $L\sim W^α, 0<α\le 1,$ and with necessarily discontinuous weight assignments. In particular, we prove that constant-width fully-connected networks of depth $L\sim W$ provide the fastest possible approximation rate $\|f-\widetilde f\|_\infty = O(ω_f(O(W^{-2/ν})))$ that cannot be achieved with less deep networks.
1 Introduction
The paper asks how efficiently general continuous functions on finite-dimensional cubes can be approximated by deep ReLU networks as the weight budget grows. It adapts bit extraction and approximation-theoretic tools to establish a phase diagram separating slower continuous-weight approximations from faster deep, discontinuous ones.
- Motivation: The central question is the optimal uniform approximation rate for continuous f:[0,1]^ν→R using architectures with W weights.The rate is measured through the modulus of continuity ω_f as W increases.
- Motivation: Existing work left a gap between lower and upper approximation exponents for ReLU networks when depth was unconstrained.Prior results included rates for Sobolev classes and stronger lower bounds, but did not close the gap in the general deep setting.
- Approach: The paper bridges this gap for continuous functions by connecting approximation theory with VC-dimension bounds and adapting bit extraction.The bit extraction technique compresses substantial expressiveness into a single network weight.
- Main result: O(ω_f(O(W^-2/ν))) is the optimal rate up to a logarithmic factor, whereas shallow networks attain O(ω_f(O(W^-1/ν))).The faster rate requires very deep networks, while the slower rate can be achieved with continuous weight assignments.
- Main result: The paper presents a complete phase diagram for approximation rates parameterized by the modulus of continuity and total weight count.The results and proofs are developed in Sections 2–5.
- Main result: Intermediate rates O(ω_f(O(W^-p))) for p∈(1/ν,2/ν] require depths proportional to W^(pν−1) and discontinuous weight assignments.These rates can be obtained by combining deep constant-width and shallow parallel architectures.
2 The results
The paper identifies two feasible approximation phases for continuous functions: a constant-depth, continuous-weight phase at p = 1/ν and a faster phase requiring growing depth and discontinuous weight assignments, up to the optimal feasible exponent p = 2/ν.
- Phase diagram: p ≤ 2/ν is the generally feasible region, with qualitatively distinct behavior at p = 1/ν and for larger p.The phase diagram separates a slower regime from a deeper, discontinuous regime.
- Deep discontinuous phase: p ∈ (1/ν, 2/ν] requires depths scaling as L ∼ W^(pν−1) and weight assignments discontinuous in f.The lower bound gives L ≥ dW^(pν−1)/ln W, while the upper constructions attain matching scaling up to logarithmic factors.
- Constant-depth phase: p = 1/ν is achievable with fixed-depth architectures whose weights depend linearly and continuously on f.Proposition 1 uses O(W) parallel blocks with depth depending on ν but not W.
- Fastest rate: p = 2/ν is the fastest feasible rate, achieved by constant-width fully connected networks with depth proportional to W.These narrow architectures attain the optimal approximation rate when the width is sufficiently large and fixed.
- Constructive rates: O(ω_f(O(W^−p))) is obtained for p ∈ (1/ν, 2/ν] using architectures with depth L = O(W^(pν−1)).Stacked architectures interpolate between parallel shallow networks and serial narrow networks, and are optimal up to logarithmic correction under the stated depth constraint.
- Construction: The faster phase combines a coarse piecewise-linear interpolation with a discrete approximation of its residual on a finer scale.The residual approximation uses finitely many possible shapes, which produces discontinuous weight assignment.
3 Discussion
The paper frames discontinuous weight dependence as a common feature of optimal approximation and quantifies its accuracy benefit for deep ReLU networks.
- Discontinuous dependence of optimal neural-network weights on the approximated function is consistent with prior approximation theory.
- The paper quantifies the accuracy gain from abandoning continuous weight assignments in deep ReLU approximation.
- Deep architectures in this work are presented in the broader context of nonlinear approximation schemes that often use discontinuity.
- The paper does not use quantized weights in the problem statement, but uses them in the solution to store small-scale descriptions of the approximated function.
4 Preliminaries and proof of Proposition 1
The section develops ReLU and interpolation preliminaries for approximating continuous functions on a cube, culminating in a weight-controlled piecewise-linear approximation.
- The modulus of continuity ω_f is introduced to characterize how function values vary with spatial scale.
- ReLU implements binary maximum, minimum, and absolute value operations through explicit algebraic identities.
- Linear units and identity pass-forward operations can be simulated within ReLU networks by shifting preactivations and compensating downstream biases.
- The piecewise-linear approximation ef1 interpolates f on the grid (Z/N)^ν using a standard triangulation of R^ν.
- The spike function is a continuous piecewise-linear basis function constructed from affine maps and ReLU-compatible minimum operations.
- The interpolation preserves a modulus bound, including ω_ef1(r) ≤ 2√νω_f(r) for r ∈ [0, 2/N], and the discrepancy f2 has a controlled modulus.
- With N = cW^(1/ν), the parallel network implementing the interpolation uses at most W weights and achieves the desired rate with p = 1.
5 Proof of Theorem 2
The proof of Theorem 2 is organized around constructing, storing, evaluating, and implementing a two-scales approximation under the network-size constraint.
- The proof has three parts: construct and estimate the two-scales approximation, store and evaluate it using bit extraction, and verify its neural-network implementation and size.
5.1 The two-scales approximation and its accuracy
The two-scales construction first approximates f coarsely, then refines the residual on localized patches, while allocating weights and scales to meet the target rate.
- The initial interpolating approximation ef1 is allocated at most W/2 weights, reserving the remainder for the second approximation.
- The residual f2 = f − ef1 is approximated using functions supported on disjoint patches at a smaller length scale.
- The full approximation ef is assembled from refined approximations ef2,q to the residual components f2,q.
- The refined scale is controlled by M, with M/N assumed integer so the coarse grid is a subgrid of the refined grid.
- The refined piecewise-linear approximants are compared with exact interpolants to bound their approximation errors on each patch.
- Summing component errors yields the full approximation bound, and implementing ef within W weights gives the desired approximation rate.
5.2 Storing and decoding the refined approximation
The refined approximation is encoded patchwise in ternary weights, decoded by iterative deep ReLU shifts, and combined with patch-dependent basis functions to compute ef2,q.
- Patch encoding and decoding: Ternary weights bq,n encode all patch values Bq,n(m), which are recovered as digits through iterative updates zt+1 = 3zt − floor(3zt).The decoded digit satisfies Bq,n(mt) = floor(3zt−1) − 1.
- Patch encoding and decoding: O((M/N)^ν) layers and weights suffice to reconstruct all Bq,n(m) when χϵ(3zt) equals floor(3zt).This requires ϵ < 3^−(2M/N−1)^ν.
- Patch-dependent computation: Within a patch, ef2,q is computed by multiplying recovered Bq,n(m) with basis values eΦm,q(m1, x) and summing over indices.The basis values are computed iteratively in parallel with the decoded Bq,n values.
- Patch-dependent computation: The network maps each input x to its patch center Ψq(x), selects the corresponding encoding bq,n, and suppresses contributions outside valid patches.The auxiliary function θq(x) vanishes outside the patches and dominates the relevant basis factors inside them.
- Patch-dependent computation: O((M/N)^ν) linear and ReLU operations compute all eΦm,q(m1, x), completing the patchwise computation of ef2,q.The construction uses cumulative sums over m1 and parallel alignment with the decoded coefficients.
5.3 Network implementations
The refined approximation is implemented by combining shallow patch-processing components with deep decoding and accumulation subnetworks, using either narrow fully connected or stacked architectures.
- Weight budget: W/2 weights are allocated to ef2 because ef1 already uses W/2 weights in the overall approximation.The construction therefore proves the total network-size bound by separately budgeting the two approximations.
- Weight budget: O(N^ν) elementary operations implement stage 1 at constant depth, while stages 2–4 use O((M/N)^ν) layers and weights.The constants are chosen so stage 1 fits within W/4 and the deep stages fit the remaining budget.
- Narrow fully connected implementation: 2ν + 10 channels suffice for the narrow fully connected computation of ef2,q and ef.Stages 2 and 3 run in parallel, while stage 4 adds a channel for multiplication-formula ReLU operations.
- Stacked implementation: The stacked architecture processes all q ∈ S in parallel and therefore uses a deep-subnetwork width of 3ν(2ν + 10).The shallow parallel subnetwork handles ef1 and stage 1, while the deep narrow subnetwork handles stages 2–4.