Source-linked AI summary
The phase diagram of approximation rates for deep neural networks
Dmitry Yarotsky, Anton Zhevnerchuk
TL;DR
The paper asks how neural-network complexity choices constrain approximation rates for smooth function classes. It develops a phase-diagram analysis across architectures and activations, proving broad rate results and introducing deep Fourier expansion. The main outcomes are a universal piecewise-polynomial phase diagram, nearly optimal fixed-width architectures, and exponential rates in the idealized periodic-activation model.
Problem
The paper studies the limits of trading network size, architecture, activation, precision, and weight-assignment continuity against approximation rates.
Method
The paper analyzes approximation rates for ReLU, piecewise-polynomial, fixed-width fully-connected, and periodic-activation networks across Hölder smoothness classes.
Results
Piecewise-polynomial activations share the ReLU feasible region p ≤ 2r/d, fixed-width architectures adapt nearly optimally to smoothness, and deep Fourier achieves exponential rates.
Takeaways & Limitations
Deep discontinuous coding and periodic-activation lookup can substantially reduce network-size requirements, but they rely on increased operational or representational complexity.
Takeaways & Limitations
The deep Fourier result is purely theoretical and does not appear implementable with practical technologies; optimality for standard sigmoid activations remains unresolved.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper studies how network size, architecture, activation, precision, and weight-assignment continuity constrain approximation rates. It extends the phase diagram across smoothness, activation classes, fixed-width architectures, and periodic activations.
- Approximation problem: Approximation accuracy is typically related to parameter count W by a power law with rate p.The paper frames approximation as minimizing uniform error over a function class using W model parameters.
- Existing rate limits: Continuous weight assignment limits rates to p ≤ r/d, while discontinuous coding can reach up to p ≤ 2r/d for piecewise-polynomial activations.The latter bound follows from VC-dimension estimates, while the continuous bound follows from nonlinear width results.
- Approximation phases: Deep discontinuous approximation uses patchwise coding and bit extraction, distinguishing it from the shallow continuous phase.The construction encodes finitely many values in weights and requires network depth for decoding.
- Main contributions: The paper proves that the deep discontinuous phase extends to arbitrary smoothness r > 0 and identifies the feasible region of the phase diagram.This addresses whether the previously known phenomenon for low smoothness persists for smoother function classes.
- Main contributions: Standard fully-connected ReLU architectures of width 2d + 10 achieve asymptotically almost optimal rates for arbitrary smoothness, enabling universal adaptivity to smoothness.The width depends on dimension but not on the smoothness parameter.
- Main contributions: All piecewise-polynomial activations share the ReLU phase diagram, while deep Fourier expansion achieves exponential rates through dichotomy-based lookup.The paper also contrasts information distribution: deep discontinuous ReLU spreads information across encoding weights, whereas deep Fourier concentrates it in one weight.
2 Preliminaries
The preliminaries define the smoothness classes, network models, architectures, activation assumptions, and weight-assignment framework used to analyze approximation rates.
- Function classes: A smoothness r > 0 is represented as r = k + α, with functions drawn from unit balls in Hölder spaces C^k,α([0, 1]^d).Here k is a nonnegative integer and 0 < α ≤ 1.
- Network model: The networks are feedforward directed acyclic graphs whose hidden units apply an activation to an affine combination of incoming signals.Sections 3 and 4 use ReLU, defined as σ(x) = max(0, x).
- Architecture: A standard deep fully-connected architecture uses sequential constant-width layers with connections only between neighboring layers.Inputs connect only to the first hidden layer, and the output connects only to the last hidden layer.
- Activation assumptions: Piecewise-linear and piecewise-polynomial activations are required to use finitely many intervals on which the activation is respectively linear or polynomial.Without finiteness, substantially more expressive activations would be allowed.
- Approximation framework: Approximations assign function-dependent weights to a common architecture, inducing a weight-assignment map whose continuity is assessed in the uniform norm.The analysis treats smoothness r and dimension d as fixed in asymptotic accuracy-complexity relations.
3 The phase diagram of ReLU networks
The ReLU phase diagram separates shallow continuous approximation from a deep discontinuous phase and identifies p = 2r/d as the feasibility boundary. For every r > 0, rates between r/d and 2r/d are achievable with deep networks, while faster rates are infeasible.
- Shallow continuous phase: The shallow continuous phase achieves rate p = r/d with at most O(log W) layers and continuous weight assignment.The extension covers arbitrary positive smoothness r; an earlier result had an extra logarithmic error factor that can be removed.
- Feasibility boundary: Rates p > 2r/d are infeasible for networks with piecewise-polynomial activations, including ReLU networks.The stated infeasibility follows from upper bounds on VC dimensions.
- Deep discontinuous phase: For every r > 0, every rate p in (r/d, 2r/d] is achievable with deep ReLU networks using at most O(W^(pd/r−1)) layers.This generalizes the previously established deep discontinuous phase from r ≤ 1 to arbitrary positive smoothness.
- Construction: The construction partitions the domain into coarse and fine patches, approximates each fine patch by a Taylor polynomial, and encodes many coefficient sets into shared weights.Bit extraction sequentially decodes the coefficients for the input patch, while ReLU subnetworks implement approximate multiplications.
- Feasibility boundary: When p > 2r/d, decoding depth dominates encoding complexity, yielding a less efficient rate and establishing p = 2r/d as the feasible-region boundary.The decoding subnetwork has depth at least proportional to ε^(-d/(2r)) in this regime.
4 Fixed-width networks: universal adaptivity to smoothness
Standard fully connected ReLU networks with width 2d + 10 can adapt to arbitrary smoothness without making width depend on r. They achieve nearly optimal approximation rates, losing only a logarithmic factor.
- Architecture: Width 2d + 10 suffices for standard fully connected ReLU networks to approximate functions with arbitrary smoothness while remaining independent of r.The theorem uses W-weight architectures and establishes universal adaptivity to smoothness.
- Approximation rate: The fixed-width architecture achieves the optimal rate p = 2r/d up to the logarithmic factor log^(2r/d) W.The logarithmic loss arises because the network decodes Taylor coefficients afresh at each traversed fine-scale knot.
- Architecture: Earlier results show that fixed-width fully connected ReLU networks approximate every continuous d-variate function if and only if width is at least d + 1.The present theorem adds smoothness adaptation with only slightly larger width, while d-independent widths cannot support the same result.
- Approximation rate: Using r-independent width requires larger depth, approximately ε^(-d/(2r)) log(1/ε), instead of ε^(-d/(2r)).The extra depth converts to the logarithmic factor in the rate as W is inverted.
5 Activation functions other than ReLU
The section extends the deep discontinuous approximation phase beyond ReLU and shows that continuous piecewise-polynomial activations share ReLU’s phase diagram, while sigmoid feasibility remains unresolved near its upper bound.
- Nonzero-curvature activations: Activations with a point of nonzero curvature support the deep discontinuous phase through a reduction to deep polynomial approximations.The construction replaces ReLU’s bit-extraction dynamics with a polynomial dynamical system.
- Piecewise-polynomial activations: The phase diagram of any continuous piecewise-polynomial activation is the same as ReLU’s.This combines the infeasibility result for rates above 2r/d with the constructive theorem for rates between r/d and 2r/d.
- Sigmoid activation: For sigmoid networks, rates p > 4r/d are infeasible under the stated VC-dimension bound.The cited theorem applies to the standard sigmoid activation σ(x) = 1/(1 + e^-x).
- Open boundary and assumptions: Whether sigmoid networks can achieve approximation rates up to p = 4r/d remains unknown because upper and lower VC-dimension bounds have a significant gap.The paper also notes that all discussed results ignore weight precision and magnitude unless additional growth constraints are imposed.
6 “Deep Fourier expansion”
Deep Fourier expansion uses periodic activations in mixed ReLU/periodic networks to implement dichotomy-based lookup, yielding exponential approximation rates and concentrating function information in one weight.
- Motivation: Periodic activations make mixed ReLU/periodic networks drastically more expressive than standard Fourier expansion and deep ReLU networks.The paper attributes this increased expressiveness primarily to activation periodicity rather than the particular periodic function chosen.
- Theorem assumptions: Periodic-activation networks require assumptions including Lipschitz periodicity, sign changes across half-periods, and balanced extrema.Theorem 6.1 is stated for a periodic activation satisfying these conditions and permits an architecture with W weights.
- Approximation rate: The resulting exponential rate corresponds to p = ∞, making the ReLU-infeasible sector p > 2r/d feasible for mixed ReLU/periodic networks.The architecture achieves this while encoding all information about the approximated function in a single network weight.
- Network mechanism: Deep Fourier expansion replaces sequential bit extraction with a more efficient dichotomy-based lookup.The network computes each output digit using a dynamical system controlled by input digits.
7 Distribution of information in the network
The paper compares how approximation information is distributed across network weights: deep discontinuous ReLU networks spread it across many high-precision weights, whereas deep Fourier expansion concentrates it in one weight.
- Information requirement: Achieving accuracy ϵ uniformly on the Hölder ball requires at least ϵ^-d/r bits of information about the target function.This follows from the ϵ-entropy scaling of the Hölder ball.
- Summary table: Table 1 summarizes approximation modes and gives orders of magnitude for network characteristics as functions of approximation accuracy ϵ.The table’s accuracy is the uniform norm error over the Hölder ball.
- Deep discontinuous ReLU: Deep discontinuous ReLU networks use approximately ϵ^-1/p encoding weights, each requiring approximately ϵ^(1/p−d/r) bits of precision.The total encoded information matches the entropy requirement while using fewer weights than classical linear or shallow ReLU models.
- Deep Fourier expansion: Deep Fourier expansion places the encoding information in a unique weight containing roughly ϵ^-d/r log(1/ϵ) information.This is reported as being consistent with the Hölder ball’s ϵ-entropy.
8 Discussion
The discussion identifies tradeoffs behind the phase diagram, including discontinuous weight assignment and activation or arithmetic complexity. It also states boundaries for piecewise-polynomial activations and limits the practical scope of deep Fourier expansion.
- Complexity tradeoffs: Reducing network size requires greater activation, arithmetic, or operation precision complexity, together with discontinuous weight assignment.The paper suggests that discontinuity may make these networks difficult to train with usual gradient-based methods.
- Phase-diagram boundary: For all piecewise-polynomial activations, feasible approximation rates span the sector p ≤ 2r/d.The paper does not establish whether this boundary holds for standard nonpolynomial activations such as sigmoid.
- Deep Fourier model: Deep Fourier expansion achieves exponential approximation rates while storing all information in a single weight under perfect periodic-neuron computation.This model is theoretical and does not appear implementable with practical technologies.
9 Broader impact
The construction uses spatial partitions, localized spike functions, subgrid filtering, and weighted local approximations to build the network approximation. These components combine to preserve the target error while controlling parameter and multiplication costs.
- Localized interpolation: Spike functions and triangulation-based interpolation compute localized functions exactly with networks using constant depth and controlled weight counts.The spike function is piecewise linear, equals one at a selected grid knot, and vanishes at other grid knots.
- Spatial partitioning: The proof partitions the grid into disjoint subgrids whose associated patches are disjoint, enabling localized computations for each subgrid.Each point in the domain belongs to at most one patch associated with a subgrid.
- Combining local approximations: Each subgrid approximation is accurate on its own domain, while the final approximation combines these terms with weights that vanish outside their domains.The weighting functions form a partition of unity, so the weighted sum retains error O(W^-p).
- Arithmetic implementation: The construction implements multiplication approximately with error O(W^-p) using O(log W) additional weights.This multiplication module is combined with the localized approximation and weighting networks.
A.3 The approximation for a subgrid
The subgrid approximation represents local behavior through Taylor polynomials on fine M-grids, while encoding coefficients within coarser N-cubes. The construction yields the target error with parameter and depth bounds across the relevant rate regimes.
- Grid scales: The construction sets M = W^(p/r), so Taylor approximation error O(M^-r) becomes O(W^-p).M is assumed integer and divisible by N, making the M-partition a refinement of the N-partition.
- Taylor approximation: A Taylor expansion at each M-knot approximates f uniformly with error O(M^-r), but directly implementing all M^d terms requires O(M^d log M) weights.This direct implementation is infeasible for p > r/d.
- Local filtering: Restricting computation to the N-cube containing the input leaves only (M/N)^d = W^(pd/r-1) relevant terms.The resulting local approximation remains accurate on the domain of the selected subgrid.
- Coefficient encoding: Encoding Taylor coefficients in a small number of weights preserves error O(W^-p), while the coefficient-computation construction uses O(W) weights after sharing partial sums.The encoding weights depend on boundedly many values determined by d and the smoothness order.
- Network computation: The network computes the relevant N-knot and encoding weights, reconstructs Taylor coefficients, evaluates local polynomials, and combines their outputs.The coefficient and polynomial computations can be parallelized across M-knots, yielding depth O(log W) for the corresponding stages.
- Complexity bounds: The total layer count is O(W^(pd/r-1)), with the p = 2r/d boundary requiring a logarithmic-factor treatment.For p = 2r/d, the weight count is equivalent to O(W log W) before the specialized adjustment.
B Theorem 4.1: proof details
The fixed-width construction serializes subgrid processing while reserving channels for inputs, locations, encoding weights, and accumulation. It computes localized weights, decodes Taylor coefficients, evaluates polynomials, and combines the results within explicit depth bounds.
- Fixed-width organization: The width-(2d+10) network reserves channels for the input coordinates and final approximation, using the remaining channels for intermediate computations.The construction is organized as interconnected channels that pass information forward through the network.
- Serial subgrid processing: The finite decomposition over q-subgrids is processed serially, so the network only needs to implement one weighted local term at a time.The term combines a localized weight function with its corresponding subgrid approximation.
- Weighting and multiplication: The localized weighting function uses two channels and depth O(ϵ^-d/(2r)), while the local approximation uses d+8 channels and depth O(ϵ^-d/(2r) log(1/ϵ)).Their product is computed by a width-4 multiplication subnetwork with depth O(log(1/ϵ)).
- Knot lookup: The network computes the input’s N-knot and passes its encoding weight forward while decoding coefficient information from that weight.The knot computation uses width 2 and depth O(ϵ^-d/(2r)).
- Coefficient decoding: Taylor coefficients up to order ⌈r⌉−1 are decoded from O(log(1/ϵ)) bits per coefficient at the M-knots in the selected N-patch.The coefficients need precision O(ϵ^r) for the target accuracy.
- Polynomial evaluation: The final local approximation evaluates Taylor polynomials serially, using width 4 for multiplications and total subnetwork depth O(ϵ^-d/(2r) log(1/ϵ)).The complete subgrid approximation occupies d+8 channels and achieves accuracy O(ϵ).
C Theorem 5.1: proof
The proof extends the approximation construction from ReLU networks to activations with a nonzero second derivative, replacing ReLU components by polynomially approximated subnetworks while preserving the target rate and parameter budget.
- Polynomial approximation: A nonzero second derivative at one activation point lets σ-networks approximate any multivariate polynomial on bounded sets with a fixed architecture and suitable weights.The construction also permits multiplication to arbitrary accuracy with fixed-size subnetworks.
- Polynomial approximation: ReLU itself can be approximated on [-1,1] with accuracy 2^-n/2 by a σ-network of size O(n).This approximation is used to reproduce filtering and spike functions needed by the original construction.
- Rate construction: Choosing N = W^(1−δ)/d and n = c log_2 W yields accuracy O(W^-r/d) with an intermediate network size O(W^(1−δ) log W), within the available W-parameter budget.The choice requires c > 2(1−δ)(d+1)+r/d.
- Bit extraction: A polynomial dynamical system decodes length-n binary sequences from an encoding weight whose precision is 6^-n, with a size-O(n) σ-network.The decoded values initially have interval uncertainty, which can be reduced by small subnetworks.
- Encoding weights: Unlike ReLU, general σ-networks cannot determine the encoding weight exactly, but polynomial approximation reduces this error to the precision required by the decoder without substantially increasing network size.The construction implements patch-selecting maps of size O(N^d log W), which fits the W budget when N = W^(1−δ)/d.
D Expressiveness of networks with Lipschitz activation functions and slowly growing weights
The section bounds approximation rates for networks with bounded Lipschitz activations and controlled weights, showing that rates beyond the threshold require rapidly growing weight magnitudes.
- Setup: Bounded Lipschitz activations with per-neuron l1 weight norms bounded by V are analyzed through covering-number estimates for depth-L networks with W weights.The setup assumes adjacent-layer connections, L ≥ 2, and fixed activation bounds and Lipschitz constants.
- Covering argument: For Hölder balls, separated-function constructions lower-bound covering numbers and connect approximation accuracy to the network parameters W, L, and V.The packing uses a grid and rescaled spike functions at spacing proportional to ϵ^(1/r).
- Rate boundary: Rates p > 2r/d require V to grow very rapidly with W under the stated bounded-Lipschitz activation setting.The result follows by comparing the network covering bound with the assumed rate ϵ ≤ C_r,d,a,b W^-p.
- Periodic-activation contrast: Periodic activations can achieve arbitrary rates in the paper’s theorem, but their construction uses rapidly growing constants, with log a_K proportional to 2^K and K proportional to W^1/2.This growth agrees with the lower bound required for rates beyond 2r/d in the controlled-weight setting.
E Theorem 6.1: sketch of proof
The deep Fourier construction uses periodic activations to encode patch classifiers and decode them efficiently, enabling a nearly exponential approximation rate with a single function-dependent weight.
- Efficient decoding: Taking N = 1 lets M grow much faster with W because periodic activations provide more efficient decoding than the earlier constructions.The network layout is summarized in Figure 7.
- Patch encoding: A patch-encoder maps each x to a binary sequence identifying its M-patch, using a network of size approximately d log_2 M.The encoder uses coordinate-wise approximations of the parity function.
- Patch encoding: The approximation partitions [0,1]^d into M-patches, represents each patch value with O(log_2 M) bits, and reconstructs the piecewise-constant approximation from binary patch classifiers.For smoothness r ≤ 1, the piecewise-constant approximation has accuracy ϵ ∼ M^-r.
- Approximation rate: The resulting parameter relations yield ϵ ∼ 2^(-c′W^1/2), with c′ proportional to r/d.The construction relies on rapidly growing periodic-activation scales and efficient lookup operations.
- Patch classification: Periodic activations implement any binary assignment on K-bit patch codes with a size-O(K) network and one encoding weight.The construction interprets this as a dichotomy-based lookup requiring K ∼ log_2 S steps for a binary sequence of size S = 2^K.
- Single-weight construction: The R function-dependent encoding weights can be generated from a single weight using an f-independent subnetwork of complexity O(R).This resolves the gap between the intermediate construction with R weights and the theorem’s single-weight statement.