The phase diagram of approximation rates for deep neural networks
Using bit extraction, ReLU networks achieve r/d<p≤2r/d; fixed width is nearly optimal, while periodic activations yield near-exponential rates.
Key Findings
Methodology
The paper studies uniform approximation of the Hölder unit ball F_{r,d} on [0,1]^d with W trainable parameters and error O(W^{-p}). Constructions combine local Taylor polynomials, encoded weights, approximate multiplication, and sequential bit extraction for ReLU networks. Periodic activations use dichotomy-based lookup. Feasibility follows constructive upper bounds; impossibility follows continuous nonlinear approximation and VC-dimension bounds.
Key Results
- For every r>0, ReLU networks have a shallow continuous phase p=r/d, a deep discontinuous phase r/d<p≤2r/d, and an infeasible region p>2r/d. Super-classical rates require discontinuous weight assignment; attaining p requires depth at least cW^{pd/r−1}/log W.
- Standard fully connected ReLU networks of fixed width H=2d+10 achieve error ≤c_{r,d}W^{-2r/d}log^{2r/d}W, nearly matching the optimal exponent without width depending on smoothness.
- Any activation with a point of nonzero curvature supports r/d<p<2r/d; continuous piecewise-polynomial activations therefore share ReLU’s phase diagram. For sigmoid, the known VC bound only proves p>4r/d infeasible. No dataset experiments are reported.
Significance
This work unifies parameter count, depth, activation regularity, weight continuity, and target smoothness in one approximation-rate diagram. It explains why depth can surpass classical continuous approximation: weights become high-precision information containers and depth becomes a decoder. The results cover every positive smoothness r and show that a simple fixed-width architecture is almost rate-optimal. For practice, however, the gains expose a trade-off between representational efficiency and precision, depth, and trainability.
Technical Contribution
The central construction encodes Taylor coefficients from many fine cells into one coarse-cell weight. With M≈ε^{-1/r} and N≈ε^{-1/(pd)}, there are about ε^{-1/p} encoding weights, each carrying ε^{-(d/r−1/p)} bits. ReLU floor approximation, multiplication subnetworks, and sequential bit extraction reconstruct the target polynomial. The decoder depth explains the 2r/d boundary. Periodic activations replace sequential scanning with dichotomy-based lookup, concentrating information in one encoding weight and enabling near-exponential rates.
Novelty
Earlier coding-based ReLU results primarily covered r≤1. This paper extends the discontinuous phase to all r>0, identifies its exact boundary, proves smoothness adaptation with width 2d+10, and establishes activation-class invariance for piecewise polynomials. It also gives a principled explanation for the much faster regime of periodic deep networks.
Limitations
- The results are existential approximation theorems, not optimization or learning guarantees. They provide no evidence that gradient descent discovers the discontinuous encodings, and they do not address statistical noise or generalization.
- The constructions rely on high-precision real weights, discontinuous function-to-weight assignments, and potentially very large depth. Quantization, bounded weights, hardware arithmetic, or perturbations may destroy the stated rates.
- The near-exponential periodic-activation result is architectural and theoretical; finite-precision, noisy-input, and real-dataset behavior remain untested.
Future Work
Important directions include phase diagrams under finite-bit and bounded-magnitude weights, trainable coding mechanisms, sharp sigmoid and periodic-activation bounds, and robustness to perturbations. Empirical studies should test whether explicit or learned lookup modules realize the theory across dimensions, domains, and Besov-type classes.
AI Executive Summary
How efficiently can a neural network approximate a smooth function? Yarotsky and Zhevnerchuk study functions on [0,1]^d from a Hölder class F_{r,d}, measuring uniform error against the number W of parameters. Classical continuous approximation suggests the power law W^{-r/d}. The paper shows that deep networks can do better, but only by using weights as high-precision code and depth as a decoder.
For ReLU, the authors combine local Taylor approximation, encoded weights, approximate multiplication, and sequential bit extraction. A fine grid with M≈ε^{-1/r} controls Taylor error; coefficients from many fine cells are packed into fewer coarse-cell weights. The resulting phase diagram is exact: p=r/d is the continuous shallow regime; r/d<p≤2r/d is feasible only with discontinuous weight assignment and sufficient depth; p>2r/d is impossible for piecewise-polynomial activations. A standard fully connected network of width H=2d+10 reaches cW^{-2r/d}log^{2r/d}W, nearly optimal while adapting to unknown smoothness.
The activation function changes the decoder’s capabilities. Continuous piecewise-polynomial activations share ReLU’s diagram, whereas periodic activations enable dichotomy-based lookup instead of sequential bit reading, yielding theoretically near-exponential “deep Fourier expansion.” The paper reports no MNIST, CIFAR-10, or other dataset experiments: its evidence is mathematical. Its broader message is that approximation power is governed not only by parameter count, but by information placement, numerical precision, architecture, and depth.
Deep Analysis
Background
Linear width theory gives W^{-r/d} for d-variate smoothness-r functions. Continuous nonlinear approximation retains the p≤r/d barrier. Earlier work by Yarotsky and others showed ReLU coding can exceed it, reaching up to 2r/d for r≤1 through deep bit extraction. Open issues concerned higher smoothness, architecture dependence, and activation sensitivity.
Core Problem
The paper asks whether the discontinuous phase persists for arbitrary r>0, where feasibility ends, and whether a simple fixed-width architecture can adapt to smoothness. It also asks whether replacing ReLU changes the diagram and whether periodic activations can overcome the polynomial-rate ceiling. These questions couple representation, VC complexity, depth, and numerical precision.
Innovation
- �� Extends the deep discontinuous phase to every r>0. • Uses VC dimension O(W^2) to establish p≤2r/d for piecewise-polynomial networks. • Proves width H=2d+10 gives near-optimal, smoothness-adaptive rates. • Shows any activation with nonzero curvature supports the interior phase. • Introduces periodic deep Fourier expansion with dichotomy-based lookup rather than sequential decoding.
Methodology
- �� Define F_{r,d} as the Hölder unit ball, with r=k+α, and measure ||f−f~||∞. • Choose fine scale M≈ε^{-1/r}; degree ⌈r⌉−1 Taylor polynomials give O(M^{-r}) local error. • Group fine cells into coarse cells of scale N≈ε^{-1/(pd)}. • Encode roughly (M/N)^d coefficient information in each weight. • Decode with ReLU approximations to floor, multiplication, and sequential bit extraction. • Count weights and depth to derive the 2r/d boundary. • For fixed width, decode coefficients afresh, causing logarithmic overhead. • For periodic activations, use dichotomy lookup.
Experiments
This is a theoretical NeurIPS 2020 paper, not a benchmark study. It reports no MNIST, CIFAR-10, UCI, or synthetic numerical experiments, and no optimizer or hyperparameter comparison. Evaluation consists of constructive approximation bounds, impossibility results, layer lower bounds, and VC-dimension arguments. Metrics are the exponent p, uniform error ε, parameter count W, and depth L.
Results
The ReLU diagram is p=r/d for continuous shallow approximation, r/d<p≤2r/d for deep discontinuous coding, and impossible for p>2r/d. The construction has L≤cW^{pd/r−1}; continuous assignments cannot realize the super-classical interval. Width 2d+10 yields cW^{-2r/d}log^{2r/d}W. Piecewise-polynomial activations match ReLU, while sigmoid’s known bound only excludes p>4r/d.
Applications
The theory suggests using width 2d+10 when target smoothness is unknown, especially in low-dimensional scientific approximation. High-precision encoded weights could compress local surrogate models; periodic activations may benefit periodic signals, spectral representations, and indexed lookup tasks. Deployment requires additional work on quantization, optimization, stability, and resource budgets.
Limitations & Outlook
The strongest rates may depend on discontinuous encoders, ideal real-valued weights, and depth growing with accuracy. The paper does not show that gradient-based training can learn these encodings. Sigmoid’s p=4r/d barrier is only inherited from a loose VC estimate, not proven sharp. Periodic networks lack finite-precision and noisy-data analysis. Future work should connect existential representation theory to trainable, robust implementations.
Plain Language Accessible to non-experts
Imagine a warehouse storing instructions for drawing a very detailed map. The ordinary strategy gives every tiny square its own box. If the map becomes smoother, the squares can be larger; if it becomes more detailed, the number of boxes grows rapidly. This is the classical W^{-r/d} behavior.
A deep ReLU system uses a clever alternative. It packs the instructions for many tiny squares into one long, precise number. When a request arrives, the warehouse worker identifies the relevant square and reads the number step by step until the needed instructions emerge. The saving is real, but reading takes time: beyond roughly the 2r/d boundary, the worker’s steps cost more than the boxes saved.
The paper also finds that a warehouse with only 2d+10 parallel aisles can handle maps of many smoothness levels, nearly reaching the best possible efficiency. Periodic labels allow a faster strategy: repeatedly split the candidate list in half, like a guessing game. That can approach exponential speed. These are mathematical guarantees, not proof that ordinary workers—or training algorithms—can easily discover the packing scheme.
ELI14 Explained like you're 14
Picture a game map made from lots of tiny tiles. To describe the whole map, you could write one note for every tile. That works, but the number of notes gets huge when the tiles become tiny. A neural network is another way to store those notes.
The paper’s deep ReLU network hides many tile instructions inside long decimal numbers. When it sees a location, it reads the hidden number bit by bit and finds the right instruction. More layers mean more reading steps. This trick beats the usual storage speed, but not forever: the authors prove that, for ReLU, the magic zone ends at a rate called 2r/d.
Here r means how smoothly the map changes, and d means how many directions the map has. Bigger r makes the job easier; bigger d makes it harder. Surprisingly, a regular network only 2d+10 units wide can nearly get the best speed even when it does not know r beforehand. Pretty neat!
Periodic activations are even more playful. Instead of checking choices one after another, they can repeatedly cut the possibilities in half—like a super-fast search in a game menu. The theory predicts almost exponential improvement. But remember: this paper proves what networks can represent with very precise numbers. It does not show that normal training will find the secret code, or that noisy computers will preserve it.
Glossary
Hölder ball
A bounded family of functions whose derivatives vary with controlled smoothness. Technically, F_{r,d} is the unit ball of C^{k,α} with r=k+α.
It is the target class for uniform approximation.
Approximation rate
The exponent p in an error law O(W^{-p}), where W is the parameter count. Larger p means faster accuracy improvement per parameter.
The phase diagram classifies feasible p.
Deep discontinuous phase
A regime where weights encode information discontinuously and deep computation decodes it. For ReLU it is r/d<p≤2r/d.
It explains non-classical ReLU rates.
Bit extraction
Sequentially recovering digits or bits from a high-precision encoded number. ReLU networks approximate floor-like operations to implement it.
It is the main decoder in the coding construction.
VC dimension
A combinatorial measure of how many labeling patterns a model can realize. For piecewise-polynomial networks it is O(W^2).
This yields the impossibility of p>2r/d.
Deep Fourier expansion
Approximation by deep networks with periodic activations, generalizing shallow sine-based Fourier series. Its key decoder is dichotomy-based lookup.
It produces near-exponential theoretical rates.
Open Questions Unanswered questions from this research
- 1 It remains unknown whether the 2r/d boundary survives realistic finite-bit, bounded-weight, and trainability constraints. Resolving this needs quantitative coding and optimization theories.
- 2 The precise near-exponential rate, robustness, and learnability of periodic lookup networks are open. Experiments on controlled functions and real signals are needed to test whether the theoretical mechanism is practically accessible.
Applications
Immediate Applications
Smoothness-adaptive scientific surrogates
Researchers approximating low-dimensional physical response functions can try fixed-width H=2d+10 ReLU networks when smoothness is unknown. The theorem predicts near-optimal parameter scaling, but sufficient precision and a reliable training or initialization strategy are prerequisites.
Periodic signal representation
Audio, oscillatory simulations, and spectral lookup tasks may benefit from periodic activations and binary-search-like decoding. Users should first control frequency range, phase errors, quantization, and optimization instability, none of which are resolved by the theorem.
Long-term Vision
Trainable neural information stores
A future system could explicitly learn coefficient encoders, decoders, and lookup operations, turning the paper’s existential constructions into compact scientific simulators or differentiable function libraries. The main obstacles are robustness, finite precision, and scalable training.
Abstract
We explore the phase diagram of approximation rates for deep neural networks and prove several new theoretical results. In particular, we generalize the existing result on the existence of deep discontinuous phase in ReLU networks to functional classes of arbitrary positive smoothness, and identify the boundary between the feasible and infeasible rates. Moreover, we show that all networks with a piecewise polynomial activation function have the same phase diagram. Next, we demonstrate that standard fully-connected architectures with a fixed width independent of smoothness can adapt to smoothness and achieve almost optimal rates. Finally, we consider deep networks with periodic activations ("deep Fourier expansion") and prove that they have very fast, nearly exponential approximation rates, thanks to the emerging capability of the network to implement efficient lookup operations.