Optimal approximation of piecewise smooth functions using deep ReLU neural networks

Philipp Petersen; Felix Voigtlaender

Source-linked AI summary

Optimal approximation of piecewise smooth functions using deep ReLU neural networks

Philipp Petersen, Felix Voigtlaender

arXiv:1709.05289v4Sep 15, 2017math.FAcs.LGstat.ML

TL;DR

The paper asks how much depth and how many weights ReLU networks need to approximate piecewise smooth classifier functions accurately. It constructs such networks and proves optimal weight scaling, depth requirements, and feature-dimension-dependent rates for structured high-dimensional functions.

Problem
The paper studies the optimal trade-off between ReLU network complexity and approximation accuracy for piecewise constant or smooth classifier-like functions.
Source: §1 · p. 2
Method
It constructs ReLU approximants and establishes optimality through weight-count lower bounds under an information-theoretic encoding framework.
Source: §1 · p. 2, §1.3 · p. 4
Results
O(ε^-2(d-1)/β) weights achieve L2 error ε optimally, while optimal approximation requires O(1 + β/d) layers up to a log factor.
Source: §1 · p. 2
Takeaways & Limitations
For functions factored through a k-dimensional smooth feature map, the approximation rate depends on k rather than the ambient input dimension d.
Source: §1 · p. 2
The optimality results assume each network weight can be encoded using O(log2(1/ε)) bits.
Source: §4.1 · p. 11

Abstract

from arXiv · show

We study the necessary and sufficient complexity of ReLU neural networks---in terms of depth and number of weights---which is required for approximating classifier functions in $L^2$. As a model class, we consider the set $\mathcal{E}^β(\mathbb R^d)$ of possibly discontinuous piecewise $C^β$ functions $f : [-1/2, 1/2]^d \to \mathbb R$, where the different smooth regions of $f$ are separated by $C^β$ hypersurfaces. For dimension $d \geq 2$, regularity $β> 0$, and accuracy $\varepsilon > 0$, we construct artificial neural networks with ReLU activation function that approximate functions from $\mathcal{E}^β(\mathbb R^d)$ up to $L^2$ error of $\varepsilon$. The constructed networks have a fixed number of layers, depending only on $d$ and $β$, and they have $O(\varepsilon^{-2(d-1)/β})$ many nonzero weights, which we prove to be optimal. In addition to the optimality in terms of the number of weights, we show that in order to achieve the optimal approximation rate, one needs ReLU networks of a certain depth. Precisely, for piecewise $C^β(\mathbb R^d)$ functions, this minimal depth is given---up to a multiplicative constant---by $β/d$. Up to a log factor, our constructed networks match this bound. This partly explains the benefits of depth for ReLU networks by showing that deep networks are necessary to achieve efficient approximation of (piecewise) smooth functions. Finally, we analyze approximation in high-dimensional spaces where the function $f$ to be approximated can be factorized into a smooth dimension reducing feature map $τ$ and classifier function $g$---defined on a low-dimensional feature space---as $f = g \circ τ$. We show that in this case the approximation rate depends only on the dimension of the feature space and not the input dimension.

1 Introduction

The paper studies optimal ReLU-network complexity for approximating piecewise smooth and classifier functions in L2, establishing sharp weight and depth requirements. It also shows that dimension-reducing structure can make approximation rates depend on feature dimension rather than ambient dimension.

1.4 Our contribution

For functions f = g ◦τ with a smooth dimension-reducing feature map τ : R^d → R^k and a piecewise smooth classifier g, the approximation rate becomes O(ε^-2(k−1)/β), independent of ambient dimension d.This model captures application-specific invariances through the feature map τ.Source: §1 · p. 2, §1.4 · p. 5

1.1 Classification with neural networks

Piecewise constant classifier functions map inputs to finitely many labels, while sharp but smooth probability transitions ultimately yield piecewise constant label maps when the highest-probability label is selected.This motivates studying piecewise constant and, more generally, piecewise smooth functions with regular boundaries.Source: §1.1 · p. 2

1.2 Related work on approximation of piecewise smooth functions

Piecewise smooth functions generalize classifier functions and admit the same ReLU approximation rates, while prior deep-network results often concern L∞ approximation that cannot directly handle jumps.Related representation systems include shearlets, curvelets, bandelets, and surflets; the paper draws especially on partition-of-unity and local-approximation ideas from surflets.Source: §1.2 · p. 3

1.3 Our notion of optimality

Optimality is defined through nonzero-weight complexity and an information-theoretic encoding argument that converts function-class description complexity into network-size lower bounds.Unlike some dimension-based lower bounds, this approach targets finite-p approximation and does not require an upper bound on network depth, but it assumes encodable weights.Source: §1.3 · p. 4

1.4 Our contribution

ReLU networks approximate piecewise C^β functions in L2 with O(ε^-2(d−1)/β) nonzero weights and O(log2(β + 2) · (1 + β/d)) layers, with optimal weight scaling under O(log2(1/ε))-bit encodability.The construction applies on [−1/2, 1/2]^d for d ≥ 2 and ε ∈ (0, 1/2).Source: §1.4 · p. 4
Achieving the optimal approximation rate requires depth at least max{1, β/(4(d −1))} for nonlinear smooth functions, and the constructed depth matches this lower bound up to a logarithmic factor.The required depth is independent of ε and depends on input dimension and function regularity.Source: §1 · p. 2, §1.4 · p. 4
The construction combines fixed-depth approximate multiplication, polynomial approximation, and Lp cutoffs to approximate functions that are locally well approximated by polynomials.For multiplication, the depth is independent of ε and only the approximation rate depends on depth; this extends an observation previously made by Yarotsky [62].Source: §1.4 · p. 5

2 Neural networks

This section formalizes neural networks as weighted layered architectures together with their realized functions, and develops composition and parallelization operations. It also introduces bounded, quantized weights as a storage-conscious model whose approximation impact is controlled for fixed depth.

Network definition

A neural network is a sequence of affine matrix-vector layers, while its realization alternates these layers with a componentwise activation function.The section distinguishes the structured weights from the function they compute and defines depth, neuron count, weights, and output dimension.Source: §2 · p. 6

Network operations

Network concatenation realizes function composition, and ReLU networks additionally support identity-padding, sparse concatenation, and parallelization across networks of equal or unequal depth.Sparse concatenation preserves composition while using at most 2M(Φ1) + 2M(Φ2) weights, with iterated constructions bounded by 4^(n−1) times the largest component size.Source: §2 · pp. 6–7
Parallelization combines two same-depth networks, while ReLU identity networks first equalize depths when the component networks have different numbers of layers.The resulting parallel network retains the common input dimension and layer count, and the unequal-depth construction uses sparse identity concatenation.Source: §2 · p. 7

Quantized weights

(s, ε)-quantized weights restrict every parameter to a bounded dyadic grid, enabling controllable computer storage as approximation accuracy improves.For fixed depth, bounded-weight networks can be replaced by quantized-weight networks with the same depth and weight count while preserving approximation up to a controlled error; the quantization parameter depends on depth.Source: §2 · p. 8

3 Approximation of classifier functions

The section establishes ReLU approximation rates for horizon, piecewise constant, and piecewise smooth classifier functions, with complexity controlled by boundary regularity and fixed depth. The results also motivate the later optimality analysis of the required number of layers.

3.1 Approximation of horizon functions

Horizon functions are {0,1}-valued classifiers whose jump surfaces are graphs of smooth functions, and their approximation directly enables optimal rates for broader piecewise classes.The class is defined through a Heaviside jump across a Cβ graph, while Theorem 3.1 gives the corresponding smooth-function approximation framework.Source: §3.1 · p. 9
Horizon functions admit Lp approximation with O(ε^-p(d−1)/β) nonzero quantized weights and depth depending only on d and β, not ε.The construction uses a refined multiplication operator and avoids the logarithmic-in-1/ε depth required by an earlier L∞ result [62].Source: §3.1 · p. 9

3.2 Approximation of piecewise smooth functions

O(ε^-p(d−1)/β) nonzero quantized weights suffice to approximate indicators of sets with locally Cβ boundaries, using a depth fixed independently of ε.The result applies to the class Kr,β,d,B and includes piecewise constant functions; the required depth depends only on d and β.Source: §3.2 · p. 10
Piecewise smooth functions combine boundary and interior regularity by setting β′ = dβ/[p(d−1)], yielding the same O(ε^-p(d−1)/β) rate.For f = χK · g, the boundary regularity β and region regularity β′ are combined through β0 = max{β, β′}, which determines the depth bound.Source: §3.2 · p. 10
The piecewise smooth approximation depth is later shown to be optimal up to a factor involving 1 + ⌈log2 β0⌉ when achieving the stated rate.This connects the constructive upper bound to the section’s subsequent depth lower-bound analysis.Source: §3.2 · p. 10

4 Optimality

Section 4 proves that the preceding approximation constructions are optimal up to logarithmic factors in both weight count and depth. The lower bounds apply broadly across activations or, for depth, to ReLU networks approximating sufficiently regular nonlinear functions.

4.1 Optimality in terms of the number of weights

At least Ω(ε^-p(d-1)/β) nonzero weights are generally necessary for Lp approximation of horizon functions, for activations satisfying ρ(0)=0.The sharper lower bound includes a logarithmic factor, c·ε^-p(d-1)/β log2(1/ε), under a bounded-complexity weight assumption.Source: §4.1 · pp. 10–11
The lower bounds established for horizon functions also hold for piecewise constant and piecewise smooth function classes; the constructed network sizes are optimal up to a logarithmic factor in 1/ε.Source: §4.1 · pp. 10, 12
The weight lower bounds require limiting weight complexity, because unrestricted, highly complex activations can approximate arbitrary continuous functions with constant-size networks.The paper assumes each weight is encodable with at most ⌈C0·log2(1/ε)⌉ bits; this includes usual fixed-precision floating-point weights.Source: §4.1 · p. 11
The exponent p(d−1)/β is optimal even for one fixed, suitably chosen horizon function, not only in the uniform class-wide sense.For that function, Mε,p(f) is not O(ε^-γ) for any γ < p(d−1)/β.Source: §4.1 · pp. 11–13

4.2 Optimality in terms of the number of layers

For ReLU networks approximating nonlinear C3 functions, any family achieving a given approximation rate in Lp, for arbitrary p ∈ (0, ∞), requires a lower bound on depth.Source: §4.2 · p. 13
For the piecewise-smooth approximation setting, the constructed networks require at least β/(2p(d−1)) layers up to a logarithmic factor in β.Thus the depth of the constructions is optimal up to that multiplicative logarithmic factor; regularity is necessary because functions such as ReLU itself admit fixed-size exact approximation.Source: §4.2 · pp. 13–14

5 Curse of dimension

The section addresses the curse of dimension by modeling classifier invariances through a smooth, dimension-reducing feature map and proves approximation rates governed by feature dimension d rather than ambient dimension D.

Motivation

Piecewise smooth approximation has rate O(M^-β/(p(d-1))) in Lp, which becomes very slow for large input dimension d.This motivates modeling classifier functions beyond classical function spaces.Source: §5 · p. 14

Feature-map model

Classifier invariances are modeled by decomposing f = g ◦ τ, where τ is a smooth dimension-reducing feature map and g is piecewise smooth.The modeled invariances include translation, scaling, small deformations, and changes in color, brightness, or contrast.Source: §5 · p. 14
The required Lp norm condition for τ is satisfied by smooth submersions under a full-rank derivative assumption on a compact set.Lemma 5.2 provides a constant C such that ∥f ◦ τ∥_Lp(K) ≤ C^1/p · ∥f∥_Lp(τ(K)).Source: §5 · pp. 14–15

Approximation theorem

c · ε^-p(d-1)/β nonzero quantized weights and at most L layers suffice to approximate every modeled function with Lp-error ε.The constants and layer bound depend on d, D, p, κ, r, β, B, and a; the layer bound is non-explicit and likely suboptimal.Source: §5 · p. 15
The approximation exponent -p(d-1)/β matches the optimal rate for d-dimensional piecewise smooth functions and is independent of ambient dimension D.The weight-count constant c may still depend on D.Source: §5 · p. 15

A Approximation of piecewise smooth functions

This section proves the paper’s approximation results and develops a bounded-realization construction for ReLU networks. The construction clips outputs while preserving values in a prescribed range and controls quantization, depth, and weight count.

Output-bounding construction

A network with quantized weights can be transformed into one whose outputs are coordinatewise clipped by a 1-Lipschitz map while preserving all outputs bounded by ⌈B⌉.The transformed network has the same input and output dimensions, and its weights are (s0, ε)-quantized with s0 := max{⌈log2(⌈B⌉)⌉, s}.Source: A Approximation of piecewise smooth… · p. 15
The clipping module uses duplicated coordinates, pairwise differences, and biases to implement the scalar truncation map for each of the k output coordinates.Its matrices and biases have explicitly bounded sparsity, with the module using at most 7k nonzero weights and two layers.Source: A Approximation of piecewise smooth… · p. 16
Composing the clipping module with the original network yields the claimed transformed network, with a universal construction constant that can be chosen as c = 14.The clipping module’s weights are (⌈log2(⌈B⌉)⌉, ε)-quantized for ε ∈ (0, 1/2).Source: A Approximation of piecewise smooth… · p. 16

A.1 Approximation of the Heaviside function

The section constructs a fixed-size ReLU network that recreates the sharp jump of the Heaviside function, a first step toward approximating horizon functions.

Motivation

Approximating a sharp Heaviside jump is identified as necessary for constructing horizon-function approximations.Source: §A.1 · p. 16

Construction

A two-layer network with five nonzero weights approximates the Heaviside function, with pointwise error confined to the strip [0, ε] × R^(d−1).The weights take values only in {ε^-1, 1, −1}.Source: §A.1 · p. 16

A.2 Approximation of smooth functions

This section develops fixed-depth ReLU network constructions for approximating smooth functions using multiplication, monomial reproduction, local Taylor polynomials, and cutoff or partition-of-unity networks. The resulting quantized networks have controlled depth and O(ε^-d/β) nonzero weights, with depth independent of accuracy.

Construction overview

The smooth-function approximation pipeline combines approximate multiplication, monomial reproduction, Taylor polynomials at multiple base points, and an approximate partition of unity.The resulting combination is used to approximate C^β functions.Source: §A.2 · p. 16

Approximate multiplication

The multiplication construction approximates xy on [−M,M]^2 with error at most ε and returns zero whenever xy=0, using a square-function approximation and polarization identity.Source: §A.2 · pp. 17–18

Monomial reproduction

For every monomial x^α with |α|≤n, a ReLU network uses at most L≤(1+⌈log2 n⌉)(10+ℓ/d) layers and O(ε^-d/ℓ) nonzero quantized weights.The constants depend on the dimension, monomial degree, and ℓ, but not on ε.Source: §A.2 · pp. 18–19

Taylor-polynomial networks

A single network approximates m Taylor polynomials simultaneously with at most c(ε^-d/β+m) nonzero quantized weights and at most 1+(1+⌈log2 β⌉)(11+β/d) layers.This shared construction avoids the m·W cost of implementing each polynomial separately, achieving O(m+W) scaling, and approximates every polynomial uniformly within ε.Source: §A.2 · pp. 19–20

Cutoff construction

Cutoff networks reproduce a bounded output y on an interior rectangle while suppressing it near the boundary, using at most four layers and a constant number of quantized weights.The boundary region has measure controlled by the cutoff resolution, enabling the construction to preserve Lp accuracy for bounded measurable functions.Source: §A.2 · pp. 21–22

Local Taylor approximation

A degree-n Taylor polynomial at any point x0 approximates f ∈ Fβ,d,B with pointwise error at most C B |x − x0|^β, where β = n + σ.The polynomial is the Taylor polynomial of degree n, and C depends only on β and d.Source: §A.2 · p. 23

Main approximation theorem

ReLU networks approximate every f ∈ Fβ,d,B with at most L(β,d) layers and O(ε^-d/β) nonzero (s, ε)-quantized weights.The constants may depend on d, β, B, and p, while the layer bound is independent of ε.Source: §A.2 · p. 24

Network construction

The construction partitions the domain into small cubes, assigns each cube a Taylor polynomial, and combines their local approximations using neural networks.The proof selects interior base points and derivative coefficients on N^d cubes, then realizes the resulting piecewise polynomial approximation with bounded-depth networks.Source: §A.2 · p. 24

A.3 Approximation of horizon functions

The section constructs ReLU networks for horizon functions by approximating their smooth boundary and composing it with an approximate Heaviside function. The resulting networks use fixed depth and achieve Lp error at most ε with complexity scaling as ε^-p(d−1)/β.

Network construction

The construction represents a horizon function as H∘eγ, approximates the smooth boundary γ, and then composes it with an approximate Heaviside network.The boundary map is eγ(x)=(x1+γ(x2,...,xd),x2,...,xd), after reducing the permutation matrix to the identity.Source: §A.3 · pp. 25–26
For every f in HFβ,d,B and ε in (0, 1/2), a ReLU network achieves Lp error at most ε using at most L layers and c·ε^-p(d−1)/β nonzero quantized weights.Here L depends on d and β, while c and the quantization parameter may also depend on B and p.Source: §A.3 · p. 25
The boundary approximation and Heaviside realization preserve the ε^-p(d−1)/β weight scaling up to constants, while the composed network has depth bounded in terms of d and β.The proof obtains the boundary approximation from Theorem A.9 and combines it with Lemma A.2, with quantized weights available up to multiplicative constants.Source: §A.3 · p. 26

A.4 Approximation of piecewise constant and piecewise smooth functions

The section constructs ReLU networks approximating indicators of piecewise-smooth regions with complexity scaling as ε^-p(d−1)/β, then extends the result to piecewise smooth functions. The construction partitions the domain into cells, locally represents the region by horizon functions, and combines subnetworks while controlling approximation error and quantized complexity.

Piecewise constant functions

The indicator construction partitions the domain into cells whose restrictions of χ_K coincide with horizon functions, approximates each locally, and merges the subnetworks with controlled error.The merged network uses at most 2^rd·c1·ε^-p(d−1)/β weights, and the resulting estimate is bounded by ε.Source: §A.4 · pp. 27–28
Theorem A.11 provides networks for χ_K with at most L=L(β,d) layers and O(ε^-p(d−1)/β) nonzero (s,ε)-quantized weights.The bound applies for arbitrary K in K_r,β,d,B and ε∈(0,1/2).Source: §A.4 · p. 27

Piecewise smooth functions

Corollary A.12 extends the approximation guarantee to f=χ_K·g, where g is smooth on the region, using networks for the indicator, smooth component, and their product.The three constituent networks each have complexity proportional to ε^-p(d−1)/β, and the final network preserves this exponent with depth depending only on d and β.Source: §A.4 · pp. 28–29
The smooth-function construction combines the indicator and smooth approximants through a product network, yielding the claimed error bound for f=χ_K·g.The error estimate uses the identity f=g·χ_K and bounds the indicator-approximation contribution using the uniform bound on g.Source: §A.4 · pp. 28–29

B Lower bounds for the approximation of horizon functions

This section proves lower bounds for approximating horizon functions, both uniformly over the class and for a single suitably chosen function. The proof develops the uniform case first, then transfers the result to one function using the Baire category theorem.

Overview

The section establishes lower bounds for horizon-function approximation uniformly over the class and for a single judiciously chosen horizon function.These results are stated as Theorems 4.2 and 4.3, respectively.Source: B Lower bounds for the approximation… · p. 29

Proof strategy

The proof begins with the simpler uniform setting because it contains most of the crucial ideas, then obtains the single-function bound through the Baire category theorem.The Baire-category argument provides the passage from a uniform lower bound to a lower bound for one suitably chosen function.Source: B Lower bounds for the approximation… · p. 29

B.1 Lower bounds for the uniform setting

This section establishes minimax code-length lower bounds for piecewise-smooth horizon functions and relates them to neural-network complexity through finite-bit encodings. It transfers entropy bounds to horizon classifiers, encodes approximating networks into binary strings, and uses the reconstruction guarantee to derive a contradiction.

Minimax lower bound

Horizon classifiers transfer L1-separated smooth boundary functions into separated classifier functions, yielding the entropy-based lower bound.For boundary functions γ and ψ, the Lp distance between HFγ and HFψ is controlled by the L1 distance between γ and ψ, enabling known entropy estimates for C0,β([−1/2, 1/2]d−1) to apply.Source: §B.1 · pp. 30–31
The minimax code length for HFβ,d,B scales at least as ε^-p(d-1)/β for sufficiently small ε.This lower bound applies to any encoder-decoder pair achieving Lp distortion ε, with constants depending on d, p, β, and B.Source: §B.1 · pp. 30–31

Network encoding

Networks with M units and K-bit encoded nonzero weights admit injective representations using O(M(K + ⌈log2 M⌉)) bits.The encoding stores layer structure, sparse weight locations, and K-bit values in a uniquely decodable bit string.Source: §B.1 · pp. 32, 34

Uniform optimality argument

Combining the code-length lower bound with network encodings reduces the uniform approximation optimality theorem to proving that sufficiently accurate approximants require large M.The argument fixes K0 proportional to log2(1/ε) and seeks a horizon function that cannot be approximated within ε unless M exceeds a threshold.Source: §B.1 · p. 34

Encoding argument

The encoder–decoder construction reconstructs every function in the class within ε in Lp, yielding an upper bound on the minimax code length.The construction uses an injection into binary strings and a left inverse to decode the encoded network.Source: §B.1 · p. 34

Length estimate

Elementary estimates bound the encoding length using M0 and log2 M0 under the condition ε < 1/2.The proof uses log2(1/ε) ≥ 1 to control both M0 and its logarithm.Source: §B.1 · p. 34

Contradiction

Substituting the definitions of M0, ℓ, and C produces the contradiction needed to establish the claimed lower bound.The contradiction follows after applying Equation (B.5).Source: §B.1 · p. 34

B.2 Lower bounds for the setting of instance optimality

This section establishes lower bounds for instance optimality by constructing a single horizon function and accuracy sequence that challenge increasingly precise encoder-decoder schemes. It uses Baire category to extend non-uniform approximation bounds and shows that logarithmic-depth networks require more than network weights at selected accuracies.

Instance-optimality lower bound

A single judiciously chosen function in HFβ,d,B cannot be approximated too well by any sequence of finite-bit encoder-decoder pairs, extending the uniform-class lower bound to instance optimality.The proof first establishes a non-uniform lower bound for smooth functions and then transfers it to horizon functions.Source: §B.2 · pp. 35, 38

Baire-category upgrade

Baire’s category theorem upgrades a uniform encoder-decoder lower bound over Fβ,d,B to a lower bound with non-uniform error control.The argument finds an interior ball on which one fixed decoder-size regime applies, then constructs approximating encoder-decoder maps for that neighborhood.Source: §B.2 · p. 35

Contradiction via packing

Exponential L1-packing of smooth functions combined with the pigeonhole principle forces two well-separated functions to share one binary code, contradicting vanishing reconstruction error.For sufficiently large code length ℓ, the construction yields more than 2^ℓ separated functions, while the approximation error tends to zero along an infinite index set.Source: §B.2 · p. 36

Transfer to horizon functions

The lower bound transfers to HFβ,d,B by encoding horizon functions through their boundary maps, using continuity and the Lp–L1 relation between horizon-function and boundary errors.The transfer constructs modified encoder-decoder pairs for boundary functions and applies the preceding lemma to obtain the contradiction.Source: §B.2 · pp. 36–38

Theorem construction

The theorem proof prepares an infinite sequence of network encoder-decoder pairs whose code lengths incorporate the target accuracy, weight budget, and logarithmic weight-encoding precision.The construction defines Ωε, Kε, and ℓε, then obtains approximation control for every f ∈ HFβ,d,B along the resulting infinite index set.Source: §B.2 · pp. 38–39

Construction

The preceding estimate yields a sequence (ε_k)_{k∈N} such that 0 < ε_k ≤ ε_0 ≤ 1/4.Source: §B.2 · p. 40

Monotonicity and encoding

Consistency of the encoding scheme and monotonicity of Ω_ε and K_ε allow the lower-bound argument to transfer across accuracy levels.For 0 < ε ≤ ε′ ≤ ε_0, the supplied passage states Ω_ε ≥ Ω_ε′ and K_ε ≥ K_ε′, while Range(B_ℓ) ⊂ Range(B_{ℓ+1}).Source: §B.2 · p. 40

Lower-bound conclusion

M_{B,ρ,C0}(ε_k,p)(f) > Ω_{ε_k} for every k, establishing the desired lower bound on network size.The argument assumes an approximation using M weights and derives a contradiction whenever M ≤ Ω_{ε_k}.Source: §B.2 · p. 40

C Depth matters: Fast approximation needs deep networks

This section establishes depth lower bounds for ReLU approximation of nonlinear smooth functions by reducing the problem to one-dimensional affine-approximation barriers. It does so by bounding the complexity of network restrictions along affine lines through their bounded-sawtooth structure and layerwise piece counting.

One-dimensional lower bound

In one dimension, affine functions cannot approximate the square function or C3 functions with uniformly nonvanishing second derivative arbitrarily well in Lp.The proof starts from a fixed positive distance between x^2 and the space of affine functions, then transfers this obstruction through Taylor approximation.Source: C Depth matters: Fast approximation… · pp. 40–41

Relation to prior work

The depth obstruction holds for every p in (0, ∞), whereas related work considered only L2, and the presented proof avoids Legendre-polynomial properties.The authors contrast their Lp-general result with [55] [54], which treat p = 2 and rely crucially on Legendre polynomials in [54].Source: C Depth matters: Fast approximation… · p. 40

Slice-affine approximation

Any P-piecewise slice affine approximation of a nonlinear C3 function on a bounded connected domain has an Lp error lower bound depending inversely on P.The argument finds a direction with nonzero Hessian curvature, applies one-dimensional affine-approximation bounds on slices, and integrates them using Fubini’s theorem.Source: C Depth matters: Fast approximation… · pp. 42–44

Depth lower bound

ReLU networks approximating nonlinear C3 functions in Lp require depth growing according to the network’s approximation rate and number of neurons.The proof combines Telgarsky’s bound that depth-L networks with N neurons are P-piecewise slice affine, with a lower bound for approximating nonlinear functions by such functions.Source: C Depth matters: Fast approximation… · pp. 44–45

Scope

The same depth lower-bound claim can be adapted from C3 to C2+ε functions for any fixed ε > 0.The authors state that the adaptation mainly modifies the proof of the one-dimensional curvature estimate and omit the details.Source: C Depth matters: Fast approximation… · p. 44

Sawtooth-complexity bound

Along any affine line x + t·v, the network realization g_x,v is P-sawtooth, with P ≤ (2/L)^L · (N(Φ) − 1)^L.The proof defines layerwise restrictions and shows the final restriction is sawtooth with the stated complexity bound.Source: C Depth matters: Fast approximation… · p. 45

Inductive proof

The layerwise induction starts from affine-linear input restrictions and propagates sawtooth complexity through affine combinations and the 2-sawtooth activation.Each component begins as 1-sawtooth, while applying the activation and affine layer updates multiplies and aggregates the piece counts.Source: C Depth matters: Fast approximation… · p. 45

Product estimate

Concavity of the natural logarithm bounds the product of layer widths by ((N(Φ) − 1)/L)^L, yielding the final estimate for P.The output-layer condition N_L = 1 is used in this product estimate.Source: C Depth matters: Fast approximation… · p. 45

D Composition with smooth submersions

This section proves that composition with a smooth submersion, f ↦ f ◦ τ, is bounded from Lp to Lp. The argument combines the coarea formula with local constant-rank coordinates and Hausdorff-measure estimates.

D Composition with smooth submersions

The proof establishes Lp-boundedness of f ↦ f ◦ τ for smooth submersions using the coarea formula and constant rank theorem.The authors provide a full proof because they could not find a reference for this fact.Source: D Composition with smooth submersions · p. 46
Full rank of Dτ on a compact neighborhood yields a positive lower bound for the associated Jacobian and a controlled neighborhood where τ is Lipschitz.The construction uses continuity, compactness, and bounds on Dτ and τ.Source: D Composition with smooth submersions · p. 46
After extending τ locally by a Lipschitz map, the coarea formula reduces the composition estimate to controlling Hausdorff measures of fibers τ⁻¹({t}) ∩ K.The extension is obtained through the Kirszbraun-Valentine theorem, while the Jacobian agrees with that of τ on the relevant neighborhood.Source: D Composition with smooth submersions · pp. 46–47
The constant rank theorem locally straightens τ, implying each fiber piece lies in a Lipschitz image of an (m−n)-dimensional rectangle.Compactness supplies finitely many such coordinate neighborhoods covering K, enabling uniform Hausdorff-measure control.Source: D Composition with smooth submersions · p. 47

E Approximation of high-dimensional functions

The section proves an auxiliary composition-approximation lemma and applies it by constructing neural networks for the classifier and dimension-reducing feature map. The resulting composition satisfies the lemma’s assumptions and achieves the target approximation error with controlled depth, weights, and Lipschitz growth.

Auxiliary approximation lemma

The auxiliary lemma bounds the Lp error between f∘τ and its network surrogate by ε when the approximations and Lipschitz conditions satisfy its assumptions.The proof splits the error into two terms I1 and I2 and concludes ∥f∘τ−f̂∘τ̂∥_Lp(V)≤ε.Source: E Approximation of high-dimensional… · p. 48

Network construction

For any ε∈(0,1/2), a classifier network Φg^ε is constructed with a fixed layer bound and at most c·ε^(-p(d−1)/β) nonzero quantized weights.The constants and layer bound are independent of g, while the weight-count constant depends on the stated problem parameters.Source: E Approximation of high-dimensional… · pp. 48–49
Because Φg^ε has bounded weights, bounded depth, and ReLU activations, its realization R_ρ(Φg^ε) is Lipschitz with constant ε^(-T) for a parameter-dependent T.The Lipschitz estimate uses the unit Lipschitz constant of ReLU and the restriction ε∈(0,1/2).Source: E Approximation of high-dimensional… · p. 49

Feature-map approximation

The feature-map coordinates τ_i are approximated by parallelized neural networks of common depth L′ depending on the input and feature dimensions, regularity, and approximation parameters.The construction applies the cited approximation results coordinatewise and combines the subnetworks through parallelization.Source: E Approximation of high-dimensional… · p. 49

F An estimate of intermediate derivatives

This section proves an intermediate-derivative estimate for smooth functions on [0,1]^d by reducing fractional seminorms through coordinatewise interpolation and induction.

F An estimate of intermediate derivatives

Lemma F.1 establishes a uniform estimate for derivatives of every f ∈ C^n([0,1]^d), with constants depending on n, d, and σ.The proof handles derivatives of orders up to n and concludes with a constant chosen uniformly over the relevant multiindices.Source: F An estimate of intermediate… · pp. 49, 51
The central induction proves |f|_k,σ ≤ N · |f|_k + C_σ,d,k,N · ||f||_sup for every f ∈ C^k([0,1]^d).The base cases use the coordinatewise estimate (F.1), while higher orders apply it to partial derivatives and absorb the resulting term by choosing N sufficiently large.Source: F An estimate of intermediate… · p. 50
The proof also bounds fractional seminorms by higher-order derivatives, using |f|_k,σ ≤ d^2 · |f|_{k+1}, and then descends to intermediate derivative orders.The fractional estimate follows from the domain diameter and the Lipschitz bound, while the descent is formalized through induction on the derivative gap.Source: F An estimate of intermediate… · pp. 50–51

G Reducing the number of neurons

This appendix shows that one-dimensional-output networks can be reduced to at most M(Φ)+d+1 neurons without changing their represented function. The reduction preserves key architectural and weight-value properties needed in later encoding arguments.

Reduction statement

Any neural network Φ with d-dimensional input and one-dimensional output can be assumed to satisfy N(Φ) ≤ M(Φ)+d+1.This observation is used in the proofs of Lemma B.4 and Theorem C.6.Source: G Reducing the number of neurons · p. 51

Reduction lemma

If N(Φ)>M(Φ)+d+1, an iterative reduction produces Φ′ with the same input-output dimensions and represented function, while decreasing neurons and not increasing weights or layers.The reduction also preserves containment of all nonzero weight values in the original set I.Source: G Reducing the number of neurons · pp. 51–52

Construction

The construction removes a neuron with an identically zero incoming row and bias, handling hidden-layer, one-neuron-layer, and zero-output cases while preserving the network function.The zero-activation condition (0)=0 ensures equivalence after deleting or restructuring the redundant neuron.Source: G Reducing the number of neurons · pp. 51–52