The phase diagram of approximation rates for deep neural networks

Section 3

• The deep discontinuous approximation phase extends to arbitrary smoothness r > 0.The paper also identifies the region occupied by this phase.Source: §1 · p. 3

Section 4

• Fully connected networks of constant width H = 2d + 10, depending only on dimension d, achieve asymptotically almost optimal rates for arbitrary smoothness.The authors describe this as universal adaptivity to smoothness.Source: §1 · p. 3

Section 5

• Any activation with a point of nonzero curvature supports the deep discontinuous phase, so piecewise-polynomial activations share ReLU’s phase diagram.Source: §1 · p. 3

Section 6

• Periodic-activation networks achieve much faster, exponential approximation rates than ReLU networks’ polynomial rates.The proof uses dichotomy-based lookup in a new bit-extraction procedure, replacing sequential extraction.Source: §1 · p. 3

Section 7

• In deep discontinuous ReLU approximation, information is uniformly distributed across encoding weights, whereas deep Fourier approximation concentrates it in one weight.For ReLU, the total information is ϵ^-d/r across ϵ^-1/p encoding weights, with ϵ^1/p-d/r bits per weight.Source: §1 · p. 3

Smooth functions

• For r > 0, write r = k + α with k ≥ 0 and 0 < α ≤ 1; the function classes Fr,d are unit balls in the corresponding Hölder spaces Ck,α([0, 1]d).These spaces comprise k-times continuously differentiable functions with finite norm.Source: §2 · pp. 3–4

Neural networks

• A feedforward network is specified by a directed acyclic graph whose hidden units apply an activation to weighted incoming signals plus a bias, while its single output unit has no activation.Sections 3 and 4 use ReLU, σ(x) = max(0, x).Source: §2 · p. 4
• The paper otherwise imposes no special connectivity assumptions, but Section 4 studies standard deep fully-connected architectures with constant width and connections only between neighboring layers.Input and output units connect only to the first and last hidden layers, respectively.Source: §2 · p. 4, Figure 2 · p. 4
• Piecewise linear or polynomial activations are required to have finitely many intervals of linearity or polynomial behavior; without finiteness, activations could be drastically more expressive.The passage gives joining a dense countable subset of polynomials as an example.Source: §2 · p. 4

Approximations

• Approximation uses a common architecture ηW for all f ∈ F, with f-dependent weights; weight assignment is continuous when f ↦ wf is continuous in the uniform-norm topology.The framework defines achievement of a rate p through the accuracy–complexity relation, and treats r and d as fixed in asymptotic relations.Source: §2 · p. 4

The shallow continuous phase

• At p = r/d, ReLU networks achieve the shallow continuous rate with L ≤ c_{r,d}log W layers and continuous weight assignments.The result extends to non-integer smoothness; the proof uses local Taylor approximations and removes a logarithmic factor from an earlier bound.Source: §3 · p. 5

Feasibility of rates p > r/d

• Rates p > 2r/d are infeasible for ReLU networks, making 2r/d the boundary of the feasible region.For rates in the deep phase, continuous weight assignments cannot achieve the rate; achieving it requires depth at least c_{p,r,d}W^{pd/r−1}/log W.Source: §3 · pp. 5–6

The deep discontinuous phase

• For every r > 0 and r/d < p ≤ 2r/d, deep ReLU networks achieve rate p with L ≤ c_{r,d}W^{pd/r−1} layers.This extends the deep discontinuous phase beyond the previously established case r ≤ 1.Source: §3 · p. 5
• The deep-phase construction encodes Taylor coefficients across fine patches within coarser patches, then uses a deep subnetwork to decode the coefficients for the input patch.Taylor approximation sets the fine scale, while sequential encoding lets one weight store information for many patches; the decoding depth scales with the number of fine patches per coarse patch.Source: §3 · pp. 5–6

4 Fixed-width networks: universal adaptivity to smoothness

• Width 2d + 10 fully connected ReLU networks achieve nearly optimal approximation rates across smoothness levels, with W ∼ ε^(-d/(2r)) log(1/ε).The architecture width depends on dimension but not on smoothness; the rate differs from the optimal rate by a logarithmic factor.Source: §4 · pp. 6–7
• Widths H ≥ d + 1 are necessary and sufficient for fully connected ReLU networks to approximate every d-variate continuous function, so Theorem 4.1 cannot hold with d-independent widths [23] [24].Source: §4 · p. 6
• Freshly decoding Taylor coefficients at each M-knot keeps width independent of smoothness but increases depth by a logarithmic factor.The construction separately computes an approximate Taylor polynomial for each M-patch, using fixed-width multiplication and a chain of additions and multiplications.Source: §4 · p. 6

5 Activation functions other than ReLU

• An activation with a point of nonzero second derivative supports the deep discontinuous phase, with rates p in (r/d, 2r/d) achievable using L ≤ c_{r,d}W^(pd/r−1) layers.The theorem extends the existence result for the deep discontinuous phase to activations with nonzero curvature.Source: §5 · p. 7
• The proof reduces approximation by curved-activation networks to deep polynomial approximation, replacing bit extraction with a polynomial dynamical system.The authors note that compositional complexity, rather than degree, constrains the polynomials, allowing more accurate approximation of ReLU.Source: §5 · p. 7
• Continuous piecewise-polynomial activations have the ReLU phase diagram: rates p < 2r/d are feasible, while rates p > 2r/d are infeasible.Piecewise-linear activations are essentially equivalent to ReLU, and the infeasible-rate result extends to piecewise-polynomial activations.Source: §5 · p. 7
• For the standard sigmoid, rates p > 4r/d are infeasible, but whether rates up to p = 4r/d are feasible remains unknown.The bound follows by using an O(W^4) VC-dimension bound for sigmoid networks in place of the O(W^2) bound for piecewise-polynomial activations; the cited sigmoid bound is from.Source: §5 · p. 7
• With mild constraints on weight growth, rates p > 2r/d can also be excluded for rather general activation functions.The preceding results ignore weight precision and magnitude; the exclusion uses a covering-number bound.Source: §5 · p. 7

6 “Deep Fourier expansion”

• A dichotomy-based lookup computes output digits using a dynamical system controlled by input digits, unlike sequential bit extraction that requires significant depth and caps feasible rates at p = 2r/d.Figure 4 contrasts standard sequential bit extraction with dichotomy-based extraction.Source: Figure 4 · p. 8, §6 · p. 8
• The model is described as more expressive than standard Fourier expansion and deep ReLU networks because of the periodic activation.The paper contrasts this simple, general activation class with an exotic analytic activation result.Source: §6 · p. 8
• The result applies to mixed ReLU/σ networks when σ is Lipschitz and periodic, has opposite signs on the two half-periods, and has equal-magnitude maximum and minimum.The particular form of the periodic activation is not important.Source: §6 · p. 8
• Only one network weight depends on the approximated function; all other weights are assigned independently of it.Thus, all information about the function can be encoded in a single weight.Source: §6 · p. 8
• The exponential rate corresponds to p = ∞, making the ReLU-infeasible sector p > 2r/d feasible for mixed ReLU/periodic networks.The theorem’s rate has a constant depending on r and d.Source: §6 · p. 8

7 Distribution of information in the network

• ϵ^-d/r is the small-ϵ scaling of the Hölder ball’s ϵ-entropy, so any network achieving accuracy ϵ must encode at least that many bits about f.This information requirement constrains weight magnitude and/or precision when networks are small or their weights have limited possible values.Source: §7 · pp. 8–9
• ϵ^-d/r weights with O(log(1/ϵ))-bit precision suffice for classical linear models and shallow ReLU networks to accommodate the total ϵ-entropy.Source: §7 · p. 9
• ϵ^-1/p encoding weights, each requiring ∼ϵ^(1/p-d/r) bits, characterize deep discontinuous ReLU networks with rate p.The passage states this characterization for p in an interval, but the interval is truncated in the supplied text.Source: §7 · p. 9
• ϵ^-d/r log(1/ϵ) bits are roughly estimated to be contained in the unique encoding weight of the deep Fourier model, in agreement with the Hölder-ball ϵ-entropy.Source: §7 · p. 9

• Network-size reductions trade off against activation or arithmetic complexity, require increased operation precision and discontinuous weight assignments, and may be hard to train with usual gradient-based methods.The authors suggest other fitting algorithms may be needed, but do not study learning in this paper.Source: §8 · p. 9
• For piecewise polynomial activations, feasible rates span p ≤ 2r/d, but whether this holds for standard nonpolynomial activations such as sigmoid is unknown.The authors connect this open question to the long-standing problem of optimality for Khovanskii’s fewnomial bounds [33].Source: §8 · p. 9
• The hypothetical deep Fourier model achieves exponential approximation rates while storing all information in a single weight, but appears impractical with current technologies.The authors highlight its theoretical demonstration of network-size reduction relative to shallow Fourier expansion and its novel bit-extraction mechanism.Source: §8 · p. 9

A Theorem 3.3: proof details

• For arbitrary r > 0, a network with W weights and L = O(W^(pd/r-1)) layers approximates every f in F_{r,d} with error O(W^-p).This generalizes the result of [10], which proved Theorem 3.3 for r ≤ 1.Source: A Theorem 3.3: proof details · p. 12
• The proof’s main novel element is the network computation of Taylor approximations.The proof proceeds through the space partition, network structure, and then the Taylor-approximation computation.Source: A Theorem 3.3: proof details · p. 12

A.1 Space partitions

• The space partition uses a continuous piecewise-linear spike function that is linear on each simplex and can be computed by a ReLU network with O(d^2) weights [10, Section 4.2].Rescaling the spike function gives a function that equals one at a selected N-knot and vanishes at the other N-knots.Source: §A.1 · p. 12
• Assigning values to K knots yields a piecewise-linear interpolant computable exactly with O(K) weights and O(1) layers.For disjoint N-patches, the construction can assign values across each patch and retain the same network-size bounds.Source: §A.1 · p. 12

A.2 The filtering subgrids

• Splitting the N-grid into 3^d subgrids with three-times grid spacing gives disjoint N-patches within each subgrid, with O(N^d) knots per subgrid.The disjointness ensures that any point lies in at most one patch for a given subgrid, allowing Proposition A.2 to be applied.Source: §A.2 · p. 13
• The final approximation combines local approximants with filters that vanish outside their subgrid domains; because the filters sum to one, the combined error remains O(W^-p).Each local approximant has error O(W^-p) within its domain, and the blend is a weighted sum with weights summing to one.Source: §A.2 · p. 13
• The filters are linear on each triangulation simplex, sum to one everywhere, and each can be implemented with O(W) weights and O(1) layers.The partition-of-unity property follows because each N-knot belongs to exactly one subgrid.Source: §A.2 · p. 13

A.3 The approximation for a subgrid

• Restricting the Taylor sum to the M-knots in the N-cube for x reduces it to (M/N)^d terms and yields error O(W^-p) on each subgrid domain.The full-grid sum has M^d terms and O(M^d log M) weights; the restricted construction has total weight count O(W) below the boundary and O(W log W) at p = 2r/d, with O(W^{pd/r-1}) layers.Source: §A.3 · pp. 14–15

A.4 Encoding and decoding Taylor coefficients

• When the stated sufficient coefficient condition holds, the construction uses at most 2(d + 1)⌈r⌉−1 encoding weights and bounds approximation error by c_{r,d}M^-r, with c_{r,d} independent of M.Source: §A.4 · pp. 16, 18

A.5 Getting rid of logarithmic factor

• At p = 2r/d, the logarithmic factor arises because O(W) terms each require O(log W) weights to implement an approximated Taylor sum.The supplied passage begins to note that most terms vanish for a particular x, but provides no further result about removing the factor.Source: §A.5 · p. 19
• Computing each Taylor partial sum only once reduces the network’s weight count from O(W log W) to O(W).The construction computes a total of 3^d partial sums.Source: §A.5 · p. 19
• Disjoint M-patches and patch-indicator functions identify the Taylor coefficients needed for the partial sum associated with each patch.The indicators equal 1 on their associated patch and vanish on the other patches in the domain.Source: §A.5 · p. 19
• For p = r, the construction instead splits the N-grid into 3^d disjoint sets, with a continuous weight-assignment map that is linear in f.This case does not use an M-grid.Source: §A.5 · p. 19

B Theorem 4.1: proof details

• The construction sets M = ϵ^-1/r and N = ϵ^-1/(2r), recomputing Taylor coefficients at new M-patches rather than updating them.Source: B Theorem 4.1: proof details · p. 19
• The network uses d channels to pass input components, one to accumulate the approximation, and serially computes the finite decomposition over q-subgrids.Source: B Theorem 4.1: proof details · pp. 19–20
• A width-(2d + 10) ReLU network achieves accuracy ϵ at depth O(ϵ^-d/(2r) log(1/ϵ)), yielding ϵ = O(L^-2r/d log^(2r/d) L).Source: B Theorem 4.1: proof details · p. 20
• N-knot positions are computed using a width-2 subnetwork, while an encoding weight carries Taylor coefficients that can be reconstructed from O(ϵ^-d/(2r)) log(1/ϵ) bits.Source: B Theorem 4.1: proof details · p. 20
• At each M-knot, the network computes a Taylor polynomial serially, using width-4 multiplication subnetworks and O(log(1/ϵ)) layers per polynomial.Across the knots, this computation uses O(ϵ^-d/(2r) log(1/ϵ)) layers; the resulting subnetwork for each q-term uses d + 8 channels.Source: B Theorem 4.1: proof details · p. 20

Step 1: Reduction to polynomial approximation

• If σ has a point where its second derivative exists and is nonzero, σ-networks can approximate any multivariate polynomial on bounded sets, and fixed-size subnetworks can approximate multiplication.The polynomial approximation can achieve any accuracy by suitably assigning weights.Source: C Theorem 5.1: proof · p. 21

Step 2: Fast polynomial approximation of thresholds and ReLU

• A size-O(n) σ-network approximates |x| and x+ on [−1, 1] with accuracy 2^-n/2.The construction uses iterated polynomials to approximate ReLU.Source: C Theorem 5.1: proof · p. 21

Step 3: Reduction to efq

• For N = W^(1−δ)/d and n proportional to log W, filtering functions achieve error O(W^-r/d) with network size O(W^(1−δ) log W).The spike approximations combine to produce filtering functions with the stated accuracy and size.Source: C Theorem 5.1: proof · p. 22

Step 4: Bit extraction

• A length-n binary sequence can be decoded by a size-O(n) σ-network from an encoding weight specified to precision 6^-n, with uncertainty reducible or tolerable.The polynomial dynamical system decodes interval membership; small subnetworks can reduce uncertainty, and some coefficient uncertainty is tolerable.Source: C Theorem 5.1: proof · p. 22

Step 5: Computation of the encoding weight corresponding to given input x

• Although σ-networks cannot determine encoding weights exactly, the constructed map approximates them within O(N^d7^-D) using size O(N^d log W), which fits budget W.Choosing N ∼ W^(1−δ)/d makes the error satisfy the required 6^-D precision.Source: C Theorem 5.1: proof · p. 23

D Expressiveness of networks with Lipschitz activation functions and slowly growing weights

• Bounded Lipschitz activation networks under mild weight-growth assumptions can achieve only rates p ≤ 2r/d, while faster rates require the weight bound V to grow very rapidly with network size.The comparison uses the network covering-number bound and the approximation-rate condition; the section notes that this rapid growth agrees with the lower bound for periodic-activation networks, whose construction uses log a_K ∼ 2K with K ∼ W^1/2.Source: D Expressiveness of networks with… · pp. 23–24
• The restriction is established for networks with bounded Lipschitz neuron activations, per-neuron weight-vector l1-norm at most V, adjacent-layer connections, and non-decreasing first-layer activations.The network has at least two layers and W weights.Source: D Expressiveness of networks with… · p. 23
• A Hölder-ball packing argument converts the number of separated functions on a grid into a lower bound on the network class’s covering number.The packing uses signed, rescaled spikes on a grid with spacing proportional to ϵ^1/r, yielding at least 2c_{r,d}ϵ^-d/r mutually separated functions.Source: D Expressiveness of networks with… · pp. 23–24

E Theorem 6.1: sketch of proof

• Choosing N=1 lets M grow roughly exponentially with W, while approximate parity functions encode each M-patch in a binary sequence using a network of size ∼d log_2 M.The parity approximation fails only near integer points; coordinate-wise rescaled versions create the patch dictionary.Source: E Theorem 6.1: sketch of proof · p. 24
• ε ∼ 2^{-c'W^(1/2)} (c'∼r/d) follows from patch classifiers with total weight count W=O(KR), where K∼d log_2 M and R∼r log_2 M.Approximating f by patchwise constants gives accuracy ε∼M^{-r}; encoding their binary values and summing the classifiers reconstructs the approximation.Source: E Theorem 6.1: sketch of proof · p. 24
• Any assignment A:{0,1}^K→{0,1} can be implemented by a size-O(K) network using a single encoding weight wA.The construction branches between identity and rescaled sinusoidal operations according to each encoded bit, enabling a dichotomy-based lookup in K∼log_2 S steps for a sequence of size S=2^K.Source: E Theorem 6.1: sketch of proof · p. 25
• The R patch-classifier encoding weights can be generated from one f-dependent weight using an f-independent network of complexity O(R).The sketch first uses R f-dependent weights, then approximates their values by serial applications of the rescaled activation.Source: E Theorem 6.1: sketch of proof · pp. 24–26
• The encoding weight is roughly estimated to contain ε^{-d/r} log(1/ε) information.The estimate uses R∼log_2(1/ε) patch classifiers and roughly −log_2 lK information in each classifier's encoding weight.Source: E Theorem 6.1: sketch of proof · p. 26

F Theorem 6.1: proof details

• Partition-of-unity filters reduce the boundary problem to disjoint patches, where patch encoders take the required ±1 values and the classifier construction yields the asymptotic relation (4).The parity approximation is invalid near integer boundaries; filtering functions make the supports disjoint so the patchwise construction applies.Source: F Theorem 6.1: proof details · p. 27
• Combining the filtered approximations requires approximate products with O(log(1/ε)) ReLU connections, asymptotically negligible beside the O(log^2(1/ε)) patch-classifier complexity.The construction sums the products of the approximations and their filters over q∈{0,1}^d [6, Proposition 3].Source: F Theorem 6.1: proof details · p. 27