PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal approximation of piecewise smooth functions using deep ReLU neural networks

Philipp Petersen, Felix Voigtlaender

arXiv:1709.05289v4math.FAcs.LGstat.ML

TL;DR

The paper asks how ReLU network complexity—measured by nonzero weights and depth—controls approximation of piecewise smooth classifier functions. It constructs approximating networks, proves optimal weight scaling and depth requirements, and shows that dimension-reducing feature maps can avoid dependence on the input dimension.

  • Problem

    The paper studies the optimal trade-off between ReLU network complexity, measured by nonzero weights, and approximation fidelity for piecewise constant or piecewise smooth classifier functions.

  • Method

    The paper combines constructive ReLU approximation results with information-theoretic lower bounds under assumptions on weight encodability, and analyzes factorizations through smooth low-dimensional feature maps.

  • Results

    O(ε^-2(d−1)/β) nonzero weights suffice and are optimal for L2 accuracy ε; optimal approximation requires depth O(1 + β/d), while factored functions require O(ε^-2(k−1)/β) weights.

  • Takeaways & Limitations

    Efficient approximation of piecewise smooth functions may require deep ReLU networks, while feature representations can make the approximation rate depend on feature dimension k rather than input dimension d.

  • Takeaways & Limitations

    The optimality results assume that each approximating-network weight can be encoded using at most O(log2(1/ε)) bits.

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 characterizes how ReLU network depth and nonzero-weight count govern L2 approximation of piecewise smooth and piecewise constant functions, including high-dimensional functions with low-dimensional structure.

  • Approximation results: ReLU networks approximate piecewise constant functions with O(ε^-2(d−1)/β) nonzero weights and O((1 + β/d) · log2(2 + β)) layers.The approximation achieves L2 error at most ε.
  • Optimality: The O(ε^-2(d−1)/β) weight scaling is optimal under natural assumptions and O(log2(1/ε))-bit encodability of each weight.Networks with fewer weights cannot achieve the same approximation accuracy under the stated assumptions.
  • Depth: Achieving the optimal complexity–approximation trade-off requires depth O(1 + β/d), and the constructed networks match this lower bound up to a log factor.For the explicit lower-bound formulation, networks with at most c · ε^-2(d−1)/β weights require at least max{1, β/(4(d−1))} layers for sufficiently small ε.
  • High-dimensional structure: For functions f = g ◦τ with a smooth dimension-reducing feature map and low-dimensional classifier g, the weight rate depends on feature dimension k rather than input dimension d.The stated complexity is O(ε^-2(k−1)/β) weights, avoiding the usual dimension dependence for this structured class.
  • Optimality framework: The paper measures optimality through information-theoretic encoding: network descriptions induce lossy compression rates for the approximated function class.Network size is primarily measured by the number of nonzero weights.
  • Construction: The approximation construction uses ReLU networks for approximate multiplication with depth independent of ε, while depth controls the weight-based approximation rate.This supports approximation of functions that are locally well approximated by polynomials.

2 Neural networks

The paper defines neural networks as structured weights whose realization alternates affine transformations and componentwise nonlinearities. It develops concatenation, parallelization, ReLU identity networks, and quantized-weight representations for controlling network composition and storage.

  • Network definition: A neural network is a sequence of matrix-vector tuples, while its realization is the function obtained by applying fixed componentwise activations between affine maps.The paper explicitly distinguishes the structured network from its associated function.
  • Complexity measures: The number of weights is the total number of nonzero matrix and bias entries, while output dimension and neuron count are defined separately.These quantities provide the paper’s basic complexity measures.
  • Network composition: Concatenating networks produces a composed realization, with the ordinary construction using L1 + L2 − 1 layers.The realization of the concatenation equals the composition of the two realizations.
  • ReLU constructions: ReLU networks can realize the identity map, enabling sparse concatenation and depth equalization before composing networks.The identity follows from x = ReLU(x) − ReLU(−x), and sparse concatenation controls composition overhead.
  • Network composition: Parallelization combines two networks with the same input and layer dimensions into a network with shared input and equal depth.Networks of unequal depth are first extended using a ReLU identity network.
  • Weight representation: Bounded, quantized weights make network storage requirements controllable and support approximation by networks with the same depth and weight count.Quantization preserves the network size while controlling realization error under the stated bounded-weight conditions.

3 Approximation of classifier functions

This section establishes ReLU approximation results for smooth, horizon, piecewise constant, and piecewise smooth functions. The rates depend on smoothness and boundary regularity, with fixed-depth constructions and matching lower-complexity claims.

  • Setup: The approximation results use ReLU networks and state bounds in Lp for smooth and classifier-function classes.The section presents the main approximation theorems while referring proofs to the appendix.
  • Smooth functions: Smooth functions admit networks with at most (2 + ⌈log2 β⌉) · (11 + β/d) layers and O(ε^-d/β) nonzero quantized weights.The number of layers depends on dimension and regularity rather than approximation accuracy.
  • Horizon functions: Horizon functions are {0, 1}-valued functions whose jump lies along a hypersurface represented as the graph of a smooth function.Their approximation is used as a building block for piecewise constant and piecewise smooth functions.
  • Horizon functions: Horizon functions admit networks with at most (2 + ⌈log2 β⌉) · (14 + 2β/d) layers and O(ε^-p(d−1)/β) nonzero quantized weights.The construction achieves Lp error at most ε for the stated horizon-function class.
  • Piecewise constant functions: Piecewise constant functions with Cβ jump boundaries admit O(ε^-p(d−1)/β) weights and fixed depth depending on d and β, with fewer weights unable to attain the same rate under natural assumptions.The boundary regularity determines the classifier approximation exponent.
  • Piecewise smooth functions: Piecewise smooth functions balance boundary and regional regularity through β′ := dβ/(p(d−1)) and β0 := max{β, β′}.The resulting networks use at most c · ε^-p(d−1)/β nonzero quantized weights and a depth bound involving β0.

4 Optimality

The paper establishes near-optimal lower bounds for network size and depth when approximating piecewise smooth functions, with qualifications on weight encoding and regularity. Its results show that the constructed ReLU networks achieve optimal complexity up to logarithmic factors.

  • Optimality in terms of the number of weights: Ω(ε^-p(d−1)/β) nonzero weights are generally necessary for Lp approximation of horizon functions, for arbitrary fixed activations satisfying ̺(0)=0.The precise lower bound includes a logarithmic factor in 1/ε under the stated encoding assumptions.
  • Optimality in terms of the number of weights: The lower bounds for horizon functions extend to piecewise constant and piecewise smooth function classes.This transfers the weight-complexity optimality conclusions to the classifier-function model studied in the paper.
  • Optimality in terms of the number of weights: The weight lower bounds assume that network weights have bounded encoding complexity, such as at most ⌈C0·log2(1/ε)⌉ bits per weight.Without restrictions on activation functions or weight complexity, highly complex activations can approximate broad function classes with constant network size.
  • Optimality in terms of the number of weights: A single suitably chosen horizon function requires approximation complexity that cannot scale as O(ε^-γ) for any γ < p(d−1)/β.Thus the exponent is optimal not only uniformly over the class, but also for one fixed function.
  • Optimality in terms of the number of layers: ReLU networks need a sufficiently large depth to attain specified approximation rates for nonlinear smooth functions.The depth lower-bound result applies in Lp for arbitrary p∈(0,∞), and the constructed networks are optimal up to logarithmic factors.
  • Optimality in terms of the number of layers: For piecewise smooth functions, the constructed networks have a layer lower bound proportional to β/(2p(d−1)) and are optimal up to a factor logarithmic in β.This connects the required depth to regularity, dimension, and the target norm.

5 Curse of dimension

The paper studies structured high-dimensional functions that factor through a smooth, dimension-reducing feature map and shows approximation rates governed by feature-space dimension rather than ambient dimension. The framework formalizes this class and establishes approximation guarantees, while noting dependencies in constants and network size.

  • Motivation: Piecewise smooth functions in R^d achieve the optimal Lp approximation rate O(M^-β/(p(d-1))) with M nonzero weights, but this rate suffers from the curse of dimension.For large input dimension d, the exponent yields only a slow guaranteed approximation rate.
  • Function class: Classifier functions can be modeled as f = g ◦ τ, where τ is a smooth dimension-reducing feature map and g is a piecewise smooth classifier.The feature map incorporates invariances, while g performs the classification.
  • Function class: The norm-control assumption is satisfied by smooth submersions whose derivatives have full rank on the relevant compact set.The paper invokes a lemma establishing the bound for continuously differentiable full-rank maps.
  • Approximation result: The constructed ReLU networks use at most L layers and at most c · ε^-p(d-1)/β nonzero quantized weights for the structured class.The constants may depend on the model parameters and feature-map class.
  • Approximation result: The approximation rate matches the optimal rate for the low-dimensional class and is independent of ambient dimension D, although the neuron-count constant depends on D.Thus the exponent avoids ambient-dimensional dependence, but the prefactor does not.

A Approximation of piecewise smooth functions

The approximation proof begins with a network transformation that bounds realizations while preserving the original network on a prescribed output range. This produces controlled ReLU networks with quantized weights and fixed depth overhead.

  • Bounded realizations: The transformed network has the same input and output dimensions as the original network.Its weights remain quantized, with the quantization parameter enlarged when necessary to encode the clipping bound.
  • Bounded realizations: A bounded-output transformation clips each output coordinate while preserving values within the range [-⌈B⌉,⌈B⌉].The clipping map is 1-Lipschitz and is composed with the original realization.
  • Bounded realizations: The clipping module uses duplicated coordinates, linear recombination, and biases to implement coordinatewise truncation.The matrices and biases encode pairwise differences that realize the clipped output map.
  • Bounded realizations: The clipping module has two layers and at most 7k nonzero weights for k output coordinates.Its weights are quantized independently of ε, with the size parameter determined by B.

A.1 Approximation of the Heaviside function

The Heaviside function, which supplies a sharp classification jump, can be approximated by a fixed-size two-layer ReLU network with an error confined to a thin transition strip.

  • Construction: Two layers and five nonzero weights suffice to approximate the Heaviside function for every ε > 0.The weights take values only in {ε^-1, 1, -1}.
  • Error localization: The pointwise approximation error is bounded by the indicator of the strip [0,ε] × R^(d-1).Outside this strip, the approximation agrees with the Heaviside function.

A.2 Approximation of smooth functions

The smooth-function approximation strategy builds fixed-depth ReLU networks from approximate multiplication, monomials, Taylor polynomials, and polynomial combinations. The resulting networks control both depth and nonzero-weight growth as accuracy increases.

  • Approximate multiplication: Approximate multiplication is built from an approximate square function and the polarization identity xy = 1/2((x+y)^2-x^2-y^2).The multiplication network approximates products on bounded domains and preserves zero products exactly.
  • Approximate multiplication: For any θ > 0, approximate multiplication can use a fixed number of layers while its weight count grows no faster than cL,M,θ · ε^-θ.The depth condition is L > (2θ)^-1.
  • Square-function approximation: Repeated composition of a tent map yields continuous piecewise affine functions with 2^t pieces using two-layer networks.These functions support the square-function approximation used later in the construction.
  • Square-function approximation: The square approximation uses a fixed-depth network with nonzero-weight count bounded by c2 · m · 2^N.The construction has 2L + 4 layers and quantized weights.
  • Monomials: Monomials of degree at most n are approximated by networks with at most L layers and O(ε^-d/ℓ) nonzero quantized weights.The depth bound satisfies L ≤ (1 + ⌈log2 n⌉) · (10 + ℓ/d).
  • Polynomial approximation: Multiple Taylor-polynomial approximations require O(ε^-d/β + m) nonzero weights rather than m times the cost of one polynomial.The resulting network has m-dimensional output and satisfies the stated approximation bound at the expansion points.
  • Smooth functions: Smooth functions in F^β,d,B admit fixed-depth ReLU approximations with at most c · ε^-d/β nonzero weights.The depth L depends on β and d but not on ε.

A.3 Approximation of horizon functions

Horizon functions are approximated by transforming a smooth boundary with a ReLU network and then realizing a Heaviside threshold. The construction achieves controlled Lp error with depth and weight complexity depending on dimension, regularity, and accuracy.

  • Construction: The smooth boundary map γ is approximated by a ReLU network before the Heaviside operation is implemented.The proof combines a network for γ with an approximate realization of the Heaviside function.
  • Complexity: At most L layers and c·ε^-p(d-1)/β nonzero quantized weights suffice for every horizon function in the considered class.The constants depend on d, β, B, and p, while the depth depends on d and β.
  • Construction: A horizon function is represented as a Heaviside function applied to a smooth coordinate transformation.The transformation is eγ(x)=(x1+γ(x2,...,xd),x2,...,xd).
  • Error control: The construction controls the Heaviside approximation between zero and one while combining boundary and threshold errors to obtain the target Lp accuracy.The proof estimates the disagreement region through the difference between the true and approximated boundary functions.

A.4 Approximation of piecewise constant and piecewise smooth functions

The construction extends horizon-function approximation to piecewise constant and piecewise smooth functions by combining local region indicators with approximations of the regional functions. The resulting networks retain the same accuracy-dependent weight exponent and have bounded depth.

  • Piecewise constant functions: Piecewise constant regions are partitioned into cubes whose indicators are locally represented by horizon functions.This permits separate ReLU approximations for the region indicators.
  • Piecewise constant functions: A network for each region is combined into one network with at most L layers and c·ε^-p(d-1)/β nonzero quantized weights.The construction aggregates 2^(rd) local components, with the multiplicative factor absorbed into the constant.
  • Error control: The combined network achieves the target Lp error by controlling the maximum local approximation error across all regions.The aggregation estimate bounds the global error using the local errors and the number of regions.
  • Piecewise smooth functions: The same construction extends to piecewise smooth functions by multiplying smooth regional approximations with approximated region indicators.The paper describes this as a simple extension of the piecewise constant result.
  • Piecewise smooth functions: For the piecewise smooth class, networks use at most L layers and c·ε^-p(d-1)/β nonzero quantized weights.The depth bound depends on d and β, while the constant also depends on r, p, and B.

B Lower bounds for the approximation of horizon functions

The paper develops lower bounds for approximating horizon functions in both uniform-over-class and single-function settings. The uniform lower bound supplies the central ideas, while the single-function result uses the Baire category theorem.

  • Lower-bound strategy: The uniform lower bound applies across the entire class of horizon functions.The paper identifies this setting as simpler and as containing most of the crucial ideas.
  • Lower-bound strategy: A lower bound for one suitably chosen horizon function is obtained from the uniform result through the Baire category theorem.This extends the lower-bound conclusion beyond uniform approximation over the full class.

B.1 Lower bounds for the uniform setting

The uniform lower-bound argument reduces approximation to description complexity: separated smooth boundary functions induce separated horizon functions, forcing long encoder-decoder codes. This yields an ε^-p(d-1)/β lower bound on the minimax code length.

  • Transfer to networks: The coding lower bound transfers to neural networks because encodable network weights define an encoder-decoder pair.Thus approximation by networks with too few describable weights would contradict the minimax code-length lower bound.
  • Separation argument: Horizon functions convert boundary-function separation into function separation in Lp.For bounded boundary maps, the disagreement between horizon functions is controlled by the L1 difference of their boundaries.
  • Lower bound: ε^-p(d-1)/β bits are necessary for Lp distortion ε over the horizon-function class.The lower bound is established through the minimax code length and a pigeonhole argument.
  • Coding formulation: An encoder-decoder pair achieves Lp distortion ε over a class when every function is reconstructed within ε.The minimax code length is the shortest binary code length permitting such uniform reconstruction.
  • Entropy growth: The smooth boundary class contains exponentially many pairwise L1-separated functions at scale ε.This follows from metric-entropy estimates for Hölder-type function classes.

B.2 Lower bounds for the setting of instance optimality

The section establishes lower bounds for approximating individual functions in the horizon-function class, rather than only obtaining uniform lower bounds over the entire class. The proof uses encoder–decoder reductions, Baire category arguments, and a transfer from boundary functions to horizon functions.

  • Rate: The section’s broader lower-bound framework concerns approximation rates scaling as ε^−p(d−1)/β for horizon functions.This rate appears in the preceding lower-bound statement and its associated lemma assumptions.
  • Instance-optimality target: The target is a lower bound for approximating a single suitably chosen horizon function, not merely uniform approximation over the whole class.This extends the preceding class-wide lower-bound setting to instance optimality.
  • Transfer to horizon functions: A continuous transfer from boundary functions to horizon functions carries the encoder–decoder lower bound into the horizon-function class.The proof explicitly uses the map γ 7→HFγ and continuity of this map.
  • Proof strategy: The proof first obtains lower bounds for encoder–decoder pairs with uniform error control, then upgrades them to non-uniform control using Baire’s category theorem.The relevant function space is treated as a complete metric space so that one encoder–decoder pair has nonempty interior in the argument.
  • Encoding argument: For each sufficiently large code length ℓ, the construction produces at least e^ℓ well-separated functions while only 2^ℓ binary codes are available.The resulting pigeonhole collision forces two distinct functions to share a code, yielding the contradiction used in the lower-bound proof.

C Depth matters: Fast approximation needs deep networks

This section shows that fast approximation of nonlinear smooth functions requires sufficient network depth. It reduces the problem to one-dimensional approximation by affine pieces, lifts the bound to higher dimensions, and combines it with the piecewise-affine structure of ReLU networks.

  • One-dimensional lower bound: The proof begins in one dimension by lower-bounding affine approximation of the square function and nonlinear C3 functions in Lp.Taylor expansion transfers the square-function estimate to functions with nonvanishing second derivative.
  • Higher-dimensional reduction: In dimensions d>1, a Fubini-type argument lifts the one-dimensional estimate to nonlinear functions approximated by P-piecewise slice affine functions.A slice is the restriction t 7→g(x0 + tv0), which is piecewise affine-linear with at most P pieces.
  • ReLU structure: ReLU realizations are P-piecewise slice affine with P ≍ [N(Φ)]^L(Φ), linking the number of affine pieces to network width and depth.This structural result is supplied through known results of Telgarsky.
  • Scope: The argument applies to approximation in Lp for arbitrary p∈(0,∞), whereas related results cited in the section considered L∞ or only p=2.The paper also characterizes its proof as more elementary than the cited Legendre-polynomial approach.

D Composition with smooth submersions

The section develops the analytic machinery for composing functions with smooth submersions. It establishes local coordinate representations, Lipschitz control, and estimates for fibers needed to analyze approximation after dimension reduction.

  • Composition map: The map f 7→f◦τ is shown to be bounded from Lp to Lp when τ is a smooth submersion.The proof uses the coarea formula and the constant rank theorem.
  • Submersion control: Full-rank derivatives imply γ(x)>0 on the compact set K, yielding a uniform positive lower bound by continuity and compactness.Here γ is the quantity derived from Dτ that certifies full rank on the relevant neighborhood.
  • Lipschitz control: After shrinking the neighborhood, τ is Lipschitz on U′, with the estimate obtained from bounded derivatives locally and bounded image diameter away from the local regime.The proof separates the cases |x−y|<r and |x−y|≥r.
  • Local coordinates: The constant rank theorem supplies local diffeomorphisms and affine maps satisfying Tx◦τ◦ϕx=π|Vx.Thus, locally, the submersion is transformed into projection onto the first n coordinates.
  • Fiber geometry: Each local fiber Wxi∩τ−1({t}) lies inside the image of an (m−n)-dimensional coordinate slice under ϕxi.This representation supports the Hausdorff-measure estimates used in the composition bound.

E Approximation of high-dimensional functions

The section applies the composition framework to high-dimensional functions whose structure factors through a smooth feature map. The resulting approximation error can be controlled by separately approximating the feature map and the low-dimensional classifier.

  • Composition estimate: The proof reduces approximation of f◦τ to controlling approximation errors for f and τ through a composition estimate.Lemma E.1 combines the two error contributions using the Lipschitz continuity of the approximated outer function.
  • Error guarantee: If the outer approximation is Lipschitz with constant ε^−T and the component errors satisfy the lemma’s assumptions, the composed approximation has Lp error at most ε.The conclusion is stated as ∥f◦τ−f̂◦τ̂∥Lp(V)≤ε.
  • Assembly: The final theorem follows by constructing networks whose activations satisfy the composition lemma’s assumptions.The section explicitly identifies this construction as the remaining step after establishing Lemma E.1.
  • Classifier approximation: The auxiliary classifier network uses at most c·ε^−p(d−1)/β nonzero weights and a bounded number of layers, with constants independent of the particular classifier g.Its weights are also controlled through quantization assumptions.
  • Feature-map approximation: The feature-map network is constructed by approximating each component τi and parallelizing the resulting networks at a common depth.The component maps are approximated using the paper’s earlier network approximation theorem.

F An estimate of intermediate derivatives

The appendix establishes estimates controlling intermediate derivatives and Hölder seminorms by higher-order regularity and the supremum norm. These bounds are proved through coordinatewise estimates and induction.

  • Inductive estimate: The appendix proves an estimate bounding lower-order derivative seminorms by a higher-order Hölder seminorm and the supremum norm.The result is established inductively for functions in C^k([0,1]^d).
  • Coordinatewise argument: The first-order estimate partitions one coordinate into K = ⌈N^(1/σ)⌉ intervals and applies the mean value theorem.This yields control of ∂1f through local Hölder variation and a derivative value at an intermediate point.
  • Base estimate: |f|k,σ ≤ d^2 · |f|k+1 connects the σ-Hölder seminorm of order k to the next derivative order.The proof uses the diameter of [0,1]^d and Lipschitz continuity.
  • Induction step: The induction applies the first-order case to partial derivatives of order k and uses bounds on the number of multi-indices.The parameter N is chosen sufficiently large to absorb the resulting d^2 term.
  • Completion: A second induction extends the estimate to intermediate derivative orders and then proves the final claim for arbitrary multi-indices γ with |γ| ≤ n.The resulting constant is chosen as the maximum over the intermediate-order constants.

G Reducing the number of neurons

This section shows that one-output neural networks can be reduced to a simpler representation without changing the represented function. The construction removes redundant neurons while preserving key architectural and weight properties.

  • Main reduction: N(Φ) ≤ M(Φ) + d + 1 can be assumed essentially without loss of generality for one-output networks.This supports encoding represented network functions using a fixed number of bits and is used in later results.
  • Preserved properties: The reduction preserves the input and output dimensions and the represented function while not increasing the number of nonzero weights or layers.It also preserves the set containing the values of all nonzero weights.
  • Redundant-neuron detection: If a network has more than M(Φ) + d + 1 neurons, a zero row in some layer can be identified because the total number of rows exceeds the number of nonzero matrix entries.The maximal such layer determines the subsequent reduction case.
  • Boundary cases: Special cases handle zero-width or degenerate layers while ensuring N(Φ′) < N(Φ), M(Φ′) ≤ M(Φ), and L(Φ′) ≤ L(Φ).In the final-layer case, the replacement network has d + 1 neurons and one layer.
Loading 1709.05289v4…