PaperlayerView exact revision on arXiv

Source-linked AI summary

Nonlinear Approximation and (Deep) ReLU Networks

I. Daubechies, R. DeVore, S. Foucart, B. Hanin, G. Petrova

arXiv:1905.02199v1cs.LG

TL;DR

The paper asks whether deep neural networks offer greater approximation efficiency than classical nonlinear methods, beyond their universal approximation property. It compares fixed-width ReLU networks with free-knot splines and constructs function classes where depth and composition yield substantially better approximation, while restricting the analysis mainly to univariate ReLU networks.

  • Problem

    The central gap is a rigorous understanding of why deep networks can approximate functions more efficiently per parameter than shallow networks and classical nonlinear methods.

  • Method

    The paper studies univariate fixed-width ReLU approximation families ΥW,L against free-knot linear splines Σn with comparable parameter counts, using depth, composition, and constructed function classes.

  • Results

    Deep ReLU networks can approximate self-similar classes with exponentially decaying error, while free-knot splines achieve only polynomial decay, and can generate CPwL functions with breakpoint counts exceeding any power of n.

  • Takeaways & Limitations

    Depth adds approximation capabilities beyond free-knot splines while retaining their approximation power at comparable parameter complexity.

  • Takeaways & Limitations

    The analysis focuses on univariate ReLU networks, and a theory completely quantifying neural-network approximation power remains lacking even in this setting.

Abstract

from arXiv · show

This article is concerned with the approximation and expressive powers of deep neural networks. This is an active research area currently producing many interesting papers. The results most commonly found in the literature prove that neural networks approximate functions with classical smoothness to the same accuracy as classical linear methods of approximation, e.g. approximation by polynomials or by piecewise polynomials on prescribed partitions. However, approximation by neural networks depending on n parameters is a form of nonlinear approximation and as such should be compared with other nonlinear methods such as variable knot splines or n-term approximation from dictionaries. The performance of neural networks in targeted applications such as machine learning indicate that they actually possess even greater approximation power than these traditional methods of nonlinear approximation. The main results of this article prove that this is indeed the case. This is done by exhibiting large classes of functions which can be efficiently captured by neural networks where classical nonlinear methods fall short of the task. The present article purposefully limits itself to studying the approximation of univariate functions by ReLU networks. Many generalizations to functions of several variables and other activation functions can be envisioned. However, even in this simplest of settings considered here, a theory that completely quantifies the approximation power of neural networks is still lacking.

1 Introduction

The article studies whether deep ReLU networks approximate functions more efficiently than classical nonlinear methods, focusing on univariate functions and fixed-width depth. It identifies composition and depth as sources of approximation power beyond free-knot splines.

  • Motivation: Neural-network approximation remains theoretically incomplete despite strong empirical performance across vision, language, and reinforcement learning.The paper emphasizes the need for a rigorous account of how and why neural networks work.
  • Approximation framework: The paper compares fixed-width ReLU families ΥW,L with free-knot linear splines Σn having comparable parameter complexity.Since ReLU networks produce continuous piecewise linear functions, Σn is their closest classical nonlinear comparator.
  • Expressive power of depth: Deep ReLU networks with n parameters can create CPwL functions whose breakpoint counts exceed any power of n, although these functions have special structure.Composing CPwL functions multiplies breakpoints, producing roughly W^L breakpoints for selected weights and biases.
  • Expressive power of depth: For every fixed width W ≥ 2, fixed-width deep ReLU networks retain the approximation power of free-knot linear splines with comparable parameter counts.Theorem 3.1 establishes this up to a constant multiplicative factor.
  • Approximation consequences: The paper seeks compact function classes where neural networks outperform classical methods, while noting that classical smoothness classes generally cannot provide such separation.A limited improvement for certain Lipschitz, Sobolev, and Besov classes is possible when parameter selection is unstable.
  • Approximation consequences: Deep ReLU networks exploit composition to approximate self-similar function classes with exponentially decaying error, whereas Σn achieves only polynomial decay.The contrast follows from the availability of composition in the network class and its failure for free-knot splines.

2 Preliminaries and notation

The preliminaries define fully connected univariate ReLU networks and relate shallow networks to continuous piecewise linear functions. They introduce the parameterized family ΥW,L and its computation through layerwise activations.

  • Definitions: ReLU applies coordinatewise as max{0, xj} to vectors in R^d.This is the activation function used throughout the network definitions.
  • Definitions: A width-W, depth-L fully connected ReLU network consists of weight matrices and bias vectors whose dimensions match one-dimensional input, W-dimensional hidden layers, and scalar output.Hidden-layer matrices are W × W, while the first and final matrices connect the scalar input and output.
  • Definitions: The family ΥW,L contains all univariate functions generated by these networks over all choices of weights and biases.Every such function is continuous piecewise linear on the real line.
  • Computation: Each network computes intermediate activation vectors layer by layer before applying a final affine map to produce the scalar output.The computation graph displays these activations, weights, biases, and interlayer connections.
  • Shallow networks: The hat function H is an example of a function in Υ2,1, illustrated through its computation graph and usual graph.The figure connects the network representation with the graph of H.
  • Shallow networks: A one-hidden-layer network produces a CPwL function with at most W breakpoints, and conversely represents any CPwL function with W − 1 interior breakpoints on [0,1].Thus ΥW,1 and the corresponding free-knot spline family have essentially the same approximation power.

3 ReLU networks are at least as expressive as free knot linear splines

The section constructs special ReLU networks that represent free-knot linear splines with comparable parameter counts, using depth to process increasingly many breakpoints. It also establishes closure properties and the resulting complexity bound.

  • 3.2 Proof of Theorem 3.1: Theorem 3.1 embeds every free-knot spline space Σn into width-W, depth-L ReLU networks with at most Cn parameters.The construction treats fixed width W ≥ 4 and uses depth to accommodate the spline representation.
  • 3.1 Special ReLU neural networks: Special networks reserve source and collation channels to carry the input forward and collect intermediate results.The remaining channels perform computations, requiring width W ≥ 4.
  • 3.1 Special ReLU neural networks: Although special networks use ReLU-free source and collation channels, their produced function sets are included in those of standard ReLU networks.The networks themselves are not literal subsets because of the ReLU-free nodes.
  • 3.2 Proof of Theorem 3.1: The construction begins with two-layer networks representing spline collections with N = q(W − 2) breakpoints, where q = ⌊(W − 2)/6⌋ for W ≥ 8.The remaining widths 4 ≤ W < 8 are handled separately in the appendix.
  • 3.2 Proof of Theorem 3.1: By partitioning basis functions according to coefficient signs and separated principal breakpoints, the proof organizes spline components into computational channels.The partition uses at most 6q sets, bounded by W − 2.

4 More about standard and special networks

This section develops composition and summation rules for standard and special networks. These rules extend the spline representation results to compositions and sums of compositions while tracking width, depth, and parameter complexity.

  • 4 More about standard and special networks: Theorem 4.1 applies these network properties to compositions and sums of compositions of free-knot linear splines, with explicit parameter bounds.The theorem states separate cases for compositions and sums of compositions under width- and breakpoint-related conditions.
  • 4 More about standard and special networks: Composing functions from ΥW,Lj yields a function in ΥW,L with L = L1 + · · · + Lk.The construction concatenates the component networks and connects the output of each network to the next network’s input.
  • 4 More about standard and special networks: Summing k network functions yields a special network with width W + 2 and depth L = k + L1 + · · · + Lk.The added source and collation channels organize the component outputs and their accumulation.
  • 4 More about standard and special networks: Proposition 4.3 represents S = Σ_i a_i T^∘i using a special network of width W + 2 and depth Lm.The construction places each weighted iterate a_iT^∘i in the collation channel.
  • 4 More about standard and special networks: Proposition 4.4 represents sums of compositions Sg using a special network of width W + 2 and depth ℓ(m + 1).Copies of the network for g process the iterates T^∘i, whose weighted outputs are collected in the collation channel.

5 ReLU networks efficiently produce functions with self similarity

ReLU networks efficiently represent self-similar continuous piecewise linear functions by replicating one pattern across many intervals. Their parameter count scales with the pattern complexity and number of intervals, rather than the total number of breakpoints.

  • Network representation: The construction uses sums, compositions, and differences of CPwL functions to reproduce the pattern across intervals.The proof handles general patterns by decomposing them into nonnegative parts and separating odd and even interval contributions.
  • Self-similar functions: A self-similar function places dilated copies of a pattern S on m intervals with disjoint interiors.The pattern has k breakpoints, and each interval carries a rescaled version of S.
  • Self-similar functions: Although the resulting function has roughly km breakpoints, it is described by only 2(k + m) parameters.Treating the function as a free-knot spline with km breakpoints would overstate its effective description complexity.
  • Network representation: Theorem 5.1 places every such function in a ReLU network class with n(W, L) ≤ C1(k + m) + C2W^2.This holds for W ≥ 8 and absolute constants C1, C2 > 0.
  • Network representation: The resulting parameter estimate is n(W, L) ≍ W^2L = 4W^2 + 8W^2(L′ + L′′) ≤ C1(k + m) + C2W^2.The proof concludes through a parameter count after constructing the required network depth.
  • Scope: The argument also applies when the pattern itself is represented by a suitable ReLU network with bounded parameter count.The stated variant assumes S(0) = S(1) and n(W − 4, L) ≤ Ck.

6 ReLU networks are at least as expressive as Fourier-like sums

ReLU networks efficiently generate linear combinations of a Riesz basis of continuous piecewise linear functions that emulates trigonometric expansions. The construction controls depth according to the largest selected index and supports nonlinear dictionary approximation.

  • Network realization: ReLU networks can produce 2k-term linear combinations of selected basis elements with controlled depth.The selected indices need not be consecutive, which is the defining feature of an n-term dictionary approximation.
  • Fourier-like basis: The functions Ck and Sk are defined as piecewise linear basis elements, with representative graphs shown for C, S, C3, and S3.Figure 14 depicts examples from this family.
  • Fourier-like basis: The family F := (Ck, Sk)k≥1 is a Riesz basis for the zero-mean space L2[0, 1].The basis consists of continuous piecewise linear functions and is intended to emulate the trigonometric basis.
  • Network realization: Each basis function with index j can be realized with depth proportional to ⌈log2 j⌉, so a selected family is controlled by λ := max{j : j ∈ Λ}.The construction uses compositions of a hat function to generate sawtooth functions and then obtains Cj and Sj.
  • Network realization: A width-W network realizes sums of selected basis functions with parameter count of order Wk log2(λ).Stacking networks yields the stated depth and parameter scaling.
  • Complexity caveat: The construction is comparable to the 2k parameters describing the basis combination only when width W is treated as an absolute constant.The logarithmic factor is ignored in this comparison.

7 Approximation by (deep) neural networks

Deep ReLU networks can match classical approximation rates for smooth functions while efficiently representing broad, irregular function classes that challenge classical nonlinear methods. Their approximation power derives from depth, parameter-efficient constructions, and the ability to combine several function families.

  • Expressiveness: ReLU networks are at least as expressive as free-knot splines, self-similar functions, and Fourier-like CPwL expansions, and therefore as expressive as their union.These families use essentially the same number of parameters when represented by suitable deep networks.
  • Approximation framework: The approximation framework compares decay rates for individual functions and compact classes under deep networks with those achieved by continuous piecewise-linear methods.Approximation error on a class is measured by the worst error over that class.
  • Nonsmooth functions: Nonlinear approximation classes are substantially larger than linear ones, and ReLU networks capture additional functions, including continuous bounded-variation functions and nonsmooth Takagi-type constructions.Some Takagi-class functions can achieve exponential approximation accuracy despite lacking Lipschitz regularity of any order.
  • Classical approximation: Free-knot spline approximation transfers to fixed-width ReLU networks with a comparable parameter count, so spline error bounds also apply to deep networks after a constant-factor adjustment.The construction gives σ2(f, Υ)C[0,1] ≤ σm(f, Σ)C[0,1], and corresponding results hold with σγm for Υ.
  • Nonsmooth functions: ReLU networks approximate certain nowhere-differentiable self-similar functions exponentially accurately while standard approximation methods perform poorly on them.The paper attributes this example to a function with self-similarity and little classical smoothness.
  • Classical smoothness: For classical smoothness spaces, ReLU networks retain the approximation accuracy of algebraic polynomials while also approximating functions with little classical smoothness.The paper derives exponential approximation for x2 and power functions, then extends the conclusion to analytic and Sobolev functions through summation.

8 Neural network approximation as manifold approximation

The section frames neural-network approximation as manifold approximation and asks how to construct stable parameter-selection schemes that achieve near-best approximations. It shows that even continuous parameter selections face classical lower bounds, excluding certain logarithmic improvements.

  • Approximation schemes: Neural-network approximation is modeled by a map M_m from parameter vectors in R^m to generated functions, viewed as an m-dimensional manifold.An approximation method adds a parameter-selection map a_m from target functions to network parameters.
  • Stability requirements: A reasonable approximation scheme must impose conditions on both the network map M_m and the parameter-selection map a_m.The section presents numerical stability as a central issue for theory and practice.
  • Stability requirements: Lipschitz stability requires both mappings to have a fixed constant Γ independent of m under a norm on R^m.The stated condition is a Lipschitz requirement with exponent 1.
  • Manifold widths: Continuous parameter selection is weaker than Lipschitz stability but still restricts approximation of compact sets characterized by classical smoothness.The manifold-width framework takes its infimum over continuous maps.
  • Manifold widths: δ_m(K) ≥ C m^-α for the unit ball of Lip α, so continuous parameter selection cannot attain the logarithmic improvement discussed in §7.2.The section connects this lack of continuity in some schemes with instability concerns for optimization-based network approximation from data.

9 Appendix

The appendix develops constructions and proof components for representing spline compositions and related systems with ReLU networks. It also establishes quantitative parameter bounds and operator properties used in later approximation results.

  • Spline representations: Free-knot linear splines with n breakpoints are embedded into functions generated by width-W and depth-L ReLU networks.The construction handles small n by adding artificial breakpoints and concatenates networks across layers.
  • Spline representations: For one construction, the network parameter count is bounded by W−2 n + W^2 + 4W + 1 < 25n.The appendix separately records n(4,2) = 33 = W^2 + 4W + 1 for W = 4.
  • Spline compositions: Representative spline compositions can be chosen so intermediate maps send [0,1] into [0,1] while preserving the original composition.This normalization supports realization of the composition by ReLU networks with controlled width and depth.
  • Spline compositions: Each component spline in a representative composition can be produced by a ReLU network, yielding the composed function in Υ_{W,P_k}.The appendix derives this from Proposition 4.2 and Theorem 3.1.
Loading 1905.02199v1…