PaperlayerView exact revision on arXiv

Source-linked AI summary

Neural Network Approximation

Ronald DeVore, Boris Hanin, Guergana Petrova

arXiv:2012.14501v1math.NA

TL;DR

Neural networks lack a solid mathematical explanation for their empirical success, particularly regarding approximation. This survey compares their approximation properties and rates, finding an optimal rate of n^-2s/d for p=∞ and 0<s≤1 while highlighting stability challenges.

  • Problem

    The empirical success of neural networks lacks solid mathematical explanation, including rigorous understanding of their distinctive approximation properties.

  • Method

    The survey analyzes neural-network approximation using rate-distortion tools, focusing on nonlinear manifolds and deep ReLU networks.

  • Results

    For p=∞ and 0<s≤1, the optimal approximation rate is n^-2s/d for n≥1.

  • Takeaways & Limitations

    Depth produces richer ReLU-network outputs and can yield greater approximation efficiency, but space-filling properties are accompanied by numerical instability.

  • Takeaways & Limitations

    The exceptional approximation performance requires a parameter-selection map that cannot be continuous, making numerical parameter search difficult.

Abstract

from arXiv · show

Neural Networks (NNs) are the method of choice for building learning algorithms. Their popularity stems from their empirical success on several challenging learning problems. However, most scholars agree that a convincing theoretical explanation for this success is still lacking. This article surveys the known approximation properties of the outputs of NNs with the aim of uncovering the properties that are not present in the more traditional methods of approximation used in numerical analysis. Comparisons are made with traditional approximation methods from the viewpoint of rate distortion. Another major component in the analysis of numerical approximation is the computational time needed to construct the approximation and this in turn is intimately connected with the stability of the approximation algorithm. So the stability of numerical approximation using NNs is a large part of the analysis put forward. The survey, for the most part, is concerned with NNs using the popular ReLU activation function. In this case, the outputs of the NNs are piecewise linear functions on rather complicated partitions of the domain of $f$ into cells that are convex polytopes. When the architecture of the NN is fixed and the parameters are allowed to vary, the set of output functions of the NN is a parameterized nonlinear manifold. It is shown that this manifold has certain space filling properties leading to an increased ability to approximate (better rate distortion) but at the expense of numerical stability. The space filling creates a challenge to the numerical method in finding best or good parameter choices when trying to approximate.

1. Introduction

The article surveys neural-network approximation properties and compares them with classical approximation methods. It emphasizes that ReLU networks’ space-filling flexibility may improve approximation with few parameters while worsening parameter-selection stability and performance guarantees.

  • Article scope: The article aims to characterize NN approximation properties and compare their performance with other approximation methods using rates, n–widths, metric entropy, and approximation classes.The comparative framework begins in §5 and treats NN approximation as nonlinear manifold approximation.
  • ReLU structure: ReLU networks produce continuous piecewise linear functions whose allowable partitions and correlations among linear pieces become richer as depth increases.The output domains are partitioned into increasingly complex structures, with deeper networks providing richer output sets than shallow networks.
  • Space-filling properties: For fixed n, ReLU networks form a rich parametric family of continuous piecewise linear functions with space-filling properties in the error-measuring Banach space.These space-filling properties are described as both a benefit and a bottleneck.
  • Trade-offs: Space filling may approximate larger function classes with relatively few parameters, but it can reduce parameter-selection stability and weaken a priori performance guarantees and uncertainty quantification.The paper presents this as a trade-off requiring comprehensive study.
  • Open questions: Important open questions include matching ReLU approximation-rate bounds, identifying beneficiary function classes, and determining how stability constraints affect parameter selection and network performance.The exposition explicitly states that a satisfactory approximation theory remains unavailable, even for ReLU networks.

2. What is a Neural Network?

This section defines feed-forward neural networks through directed acyclic graphs whose nodes compute weighted, biased activations, then specializes to fully connected layered networks. With fixed architecture and activation, varying weights and biases generates a parameterized family of output functions used for approximation.

  • General feed-forward networks: A feed-forward neural network is associated with a directed acyclic graph containing input, output, and hidden nodes, with activations, biases, and edge weights.Hidden nodes store intermediate values, while input nodes receive independent variables and output nodes produce the network output.
  • General feed-forward networks: For fixed architecture, the trainable weights and biases determine a family of output functions mapping inputs in Ω⊂R^d to outputs in R^d′.The network inputs form x=(x_1,...,x_d), and the output function is denoted S_N.
  • Fully connected networks: The paper specializes to fully connected networks whose vertices are organized into layers, with every vertex connected to all vertices in the next layer.A common activation is used at hidden vertices, while output activations are the identity.
  • Fully connected networks: Fully connected networks are represented by weight matrices and bias vectors through the layerwise recursion X^(ℓ)=σ(W^(ℓ)X^(ℓ−1)+b^(ℓ)).The activation acts coordinatewise on each layer vector, with X^(0)=x and hidden layers indexed by ℓ=1,...,L.
  • Parameterized output classes: For fixed width, depth, input/output dimensions, and activation, the output class ΥW,L is a parameterized manifold obtained by mapping a parameter vector θ of weights and biases to output functions.The paper uses “manifold” loosely and notes that distinct parameter choices can describe the same output.
  • Parameterized output classes: Designing a neural-network approximation method amounts to choosing parameters θ=a(f) from the target function or information about it.The architecture and activation fix the map from network parameters to output functions.

3. ReLU Networks

ReLU networks produce continuous piecewise linear functions organized over convex-polytope partitions. For a network with m hidden neurons, the output uses at most 3m cells, improving to at most 2m cells for almost every parameter choice in a fixed architecture.

  • General structure: ReLU network outputs are continuous piecewise linear functions subordinate to partitions of the input domain into convex polytopes.Each cell is a convex polytope, and the output is affine on each cell while remaining globally continuous.
  • General structure: 3m cells: A ReLU network with d inputs, one output, and m hidden neurons has an output partition with at most 3m cells.The partition arises from neuron activation patterns, whose regions are convex polytopes.
  • Generic parameter choices: At most 2m cells: For a fixed architecture with m neurons, almost every parameter choice yields an output subordinate to a partition with no more than 2m cells.The exception is a measure-zero subset of parameter space where activation-pattern cells can include zero-valued neuron components.
  • Section scope: The section studies the geometry of ReLU-generated polytope partitions and the complexity of their continuous piecewise linear outputs, beginning with one-dimensional inputs and outputs.Higher-dimensional input cases are deferred to a later subsection.

3.1. Univariate ReLU Networks

For univariate ReLU networks, outputs are continuous piecewise-linear functions, matching linear free-knot splines in approximation power for comparable parameter counts. Increasing depth can produce exponentially many breakpoints, but the resulting functions form only a constrained subset of all such splines.

  • Univariate outputs: Univariate ReLU outputs are continuous piecewise-linear functions on R, equivalent to continuous linear free-knot splines over interval partitions.Here both input and output dimensions equal one.
  • Approximation power: ReLU networks and linear free-knot splines have essentially the same approximation power with comparable parameter counts: 3W + 1 versus 2W parameters.The network class does not contain all splines with W + 1 intervals, but it contains all splines in ΣW,1.
  • Depth effects: For one hidden layer, outputs have at most W breakpoints, and every function in ΣW,1 is representable.The bound W is sharp, although the network class does not contain all of ΣW+1,1.
  • Depth effects: m(L) ≤ (W + 1)^L bounds the number of breakpoints for width W and depth L.This exponential-in-depth upper bound follows from a recursion beginning with m(1) = W.
  • Depth effects: 2^L − 1 teeth are attained by composing the hat function H(0,1/2,1) with itself L − 1 times, yielding a sawtooth in Υ2,L(ReLU; 1, 1).Despite exponential breakpoint growth, these outputs are far from representing all continuous piecewise-linear functions with the same number of breakpoints because of linear dependencies among pieces.

3.2. Multivariate ReLU Networks

Multivariate ReLU networks produce continuous piecewise-linear functions on convex-polytope partitions, but their outputs form a restricted subset of all such functions. In deeper networks, composition can generate many more cells, with partition complexity potentially far exceeding parameter count.

  • One hidden layer: The number of cells in a one-hidden-layer partition can grow as fast as W^d when W ≥ d, with the upper bound attained for hyperplanes in general position.This follows from the cited special case of Zaslavsky’s theorem.
  • One hidden layer: One-hidden-layer multivariate ReLU outputs are CPwL functions subordinate to convex-polytope partitions generated by arrangements of W hyperplanes.The cells are closures of connected components formed after removing the hyperplanes.
  • One hidden layer: Not every CPwL function subordinate to a hyperplane arrangement is representable by a one-hidden-layer multivariate ReLU network.The network class contains no nonzero compactly supported functions on R^d for d > 1, and representable functions satisfy constrained gradient-jump conditions across hyperplanes.
  • Deep networks: 3WL cells provide a general deep-network bound, improved to 2WL in the generic case for the associated convex-polytope partition.For deeper networks, the relevant zero sets are bent hyperplanes rather than affine hyperplanes, so the arrangement need not be minimal.
  • Deep networks: Deep ReLU networks can generate exponentially many cells as depth L increases, because composition repeatedly increases the number of linear pieces.The resulting number of cells can be very large compared with the number of network parameters n(W, L).

3.3. Properties of deep ReLU networks

Deep ReLU networks support structured constructions for addition, minimization, maximization, tent functions, and broader continuous piecewise-linear approximation. These constructions can represent infinitely many partition-based finite-element spaces and may improve approximation efficiency, although stable numerical implementation remains uncertain.

  • Operations on network outputs: Addition of m network outputs can be implemented by increasing depth to L = L1 + · · · + Lm while using width W + d + 1.The construction concatenates augmented networks with source and collation channels.
  • Piecewise-linear approximation: Deep ReLU networks represent tent functions on d-dimensional simplices with width W = 3·2⌈log2(d+1)⌉−1 and sufficiently large depth.They also represent any CPwL function on a rectangle with width d + 2 and suitably large depth.
  • Approximation efficiency and stability: The network output class contains infinitely many partition-based finite-element spaces, including adaptive partitions, and may offer higher approximation efficiency for elliptic problems.The supplied passage notes that maintaining this advantage in stable numerical implementation is less clear.

3.4. Width versus depth

With a fixed parameter budget, depth can produce richer ReLU network function classes than width in settings involving composition, motivating the question of whether shallow networks embed into fixed-width deep networks with comparable parameter counts.

  • Width versus depth: Addition can be implemented by increasing either width or depth, whereas composition and forming minimums require increasing depth.Width implements addition through parallelization, while depth implements it through concatenation.
  • Width versus depth: With width W0 fixed sufficiently large, depth supports compositions while using n(W0,L) ≍ n parameters, comparable to Υn,1, making depth richer than width in this case.The comparison views functions on [0,1] or any finite interval, with L ≍ n/W0^2 and n(W0,L) ≍ W0^2L ≍ n.
  • Width versus depth: Problem 2 asks whether every shallow network can be represented by a fixed-width deep network when the two architectures have comparable parameter counts.The proposed inclusion is ΥW,L(ReLU; d, 1) ⊂ ΥW0,L0(ReLU; d, 1) whenever n(W0,L0) ≍ n(W,L), with constants depending at most on d.
  • Width versus depth: Without parameter-count control, Problem 2 has a positive answer because every ReLU network output is CPwL and belongs to Υd+2,L for sufficiently large L.Thus, controlling the number of parameters is identified as the key issue.

3.5. Interpolation by neural network outputs

The section characterizes when ReLU neural networks can interpolate finite data, showing sharp limitations for shallow one-dimensional networks and constructive guarantees for deep or higher-dimensional networks. It also relates NN approximation bounds to finite-element interpolation estimates.

  • One-dimensional shallow networks: For one-dimensional ReLU networks with width W and one hidden layer, every dataset of W + 1 ordered points can be interpolated, with infinitely many interpolants.The construction varies the W breakpoints between consecutive data sites.
  • One-dimensional shallow networks: For n ≥ 3 alternating-sign values at n ordered points, no width n − 2 one-hidden-layer ReLU network can interpolate the data.This establishes that interpolation at W + 2 points is generally impossible for width W.
  • Deep fixed-width networks: A ReLU network with width 3 and depth D − 1 can interpolate any D data points in [0, 1].The construction implements the piecewise-linear interpolant through source, middle, and collation channels.
  • Higher-dimensional networks: For arbitrary input dimension d ≥ 1, the maximal universally interpolable dataset size satisfies D*(W, L; ReLU, d) ≥ D*(W, L; ReLU, 1).A projection onto a direction with distinct site coordinates reduces the problem to univariate interpolation via a ridge function.
  • Connection to finite-element approximation: NN approximation errors can be bounded using finite-element interpolation estimates, with dist(f, ΥW,L(ReLU; d, 1))C(Ω) ≤ 2 dist(f, X(K))C(Ω).The bound follows from a projection operator and applies estimates known for FEM to NN approximation.

3.6. VC dimension of ReLU outputs

The VC dimension of ReLU-network outputs is characterized in relation to architecture size, with one-hidden-layer networks exhibiting dimension-dependent bounds and deep networks achieving quadratic growth in depth-related complexity through bit extraction. The bit-extraction construction shows how networks with O(n) parameters can control n^2 data points.

  • The VC dimension of ΥW,1(ReLU; d, 1): For one-hidden-layer ReLU networks, VC(ΥW,1(ReLU; 1, 1)) = W + 1, while for d ≥ 2 it is at most C0W log2 W.C0 depends only on d.
  • The VC dimension of ΥW,1(ReLU; d, 1): For d ≥ 4, the one-hidden-layer VC dimension is at least c0W log2 W, whereas for d = 2, 3 it is at least W + 1.c0 depends only on d, and the exact value for d = 2, 3 remains undetermined because upper and lower bounds do not coincide.
  • The VC dimension of ΥW0,L(ReLU; d, 1): With fixed sufficiently large width W0 and variable depth L, the network parameter count satisfies n(W0, L) ≍ W0^2L.Theorem 3.9 gives VC-dimension bounds with constants depending only on d, though the supplied passage does not display their explicit formula.
  • Bit extraction: Bit extraction constructs networks with fixed width and O(n) parameters that shatter N = n^2 equally spaced points and realize specified bit data.The construction is presented explicitly for d = 1; full implementations for d ≥ 2 are cited elsewhere in the passage.

4. Classical model classes: smoothness spaces

Classical model classes for multivariate approximation are compact unit balls of smoothness spaces, including Lipschitz, Hölder, Sobolev, and Besov spaces. Besov spaces provide flexible smoothness scales with embedding properties and atomic spline decompositions that support approximation analysis.

  • Classical model classes: Classical model classes are compact subsets of Banach spaces, commonly represented by unit balls of Lipschitz, Hölder, Sobolev, and Besov spaces.The spaces are considered on Ω = [0, 1]^d, with definitions extending to Lipschitz domains in R^d.
  • Classical model classes: Sobolev spaces weaken the classical derivative requirements of C^r spaces by using weak derivatives belonging to Lp(Ω).For integer order r, W^r(Lp(Ω)) requires D^αf ∈ Lp(Ω) for all |α| = r.
  • Besov spaces: Besov spaces extend smoothness measurement to arbitrary order s > 0 and refine modulus-of-smoothness decay through the parameter q.Their smoothness is measured in Lp, with q providing a finer gradation.
  • Besov spaces: Besov embeddings order spaces by smoothness and integrability, while compact embedding into Lp(Ω) occurs for points strictly above s = d(1/τ − 1/p).The graphical representation identifies each space with (1/p, s); spaces on or above the line embed into Lp, and those strictly above it embed compactly.
  • Atomic decompositions: Tensor-product cardinal B-splines provide atomic decompositions for Lp, Sobolev, and Besov spaces, and equivalent coefficient norms characterize Besov membership.This equivalence is used as a starting point for proving approximation theorems for Besov functions.

5. Evaluation of nonlinear methods of approximation

The section evaluates neural-network manifold approximation against linear and other nonlinear methods using approximation rates and stability constraints. For classical smoothness classes, continuity or Lipschitz stability limits manifold methods to established rates, while deep networks leave room for faster rates.

  • Approximation framework: Manifold approximation represents functions through parameterized mappings, enabling comparison with linear spaces, adaptive finite elements, and n-term wavelet methods.The comparison concerns performance limits and whether a method is optimal for a model class under a fixed parameter budget.
  • Approximation limits: For classical smoothness classes, manifold approximation is no better than n-term wavelets or adaptive finite elements under modest assumptions on the parameterization and reconstruction maps.The result applies to unit balls of Besov, Sobolev, Lipschitz, and related smoothness spaces.
  • Stability: Stable manifold widths have tight upper and lower bounds in Hilbert spaces, and under Lipschitz stability their performance cannot decay faster than the entropy numbers of the model class.These bounds are especially relevant because Hilbert-space approximation is common in neural-network applications.
  • Approximation limits: Continuity of the maps a and M limits manifold approximation for classical smoothness classes to the rate O(n^-s/d), also achieved by adaptive finite elements and n-term wavelet approximation.The restriction includes neural-network approximation when its parameter and reconstruction maps are continuous.
  • Deep networks: For deep-network parameter spaces, the lower bound C(s, d)n^-2s/d leaves open substantially improved rates over classical methods, and later analysis shows these rates are attained.Here n denotes the number of parameters describing the space ΥW0,L.

6. Approximation using ReLU networks: overview

This section frames ReLU-network approximation through model families indexed by parameter count, emphasizing fixed-width deep networks as especially efficient while noting major gaps in stability and inverse-theorem understanding.

  • Network families: The survey primarily compares shallow networks ΥW,1 as W →∞ with fixed-width networks ΥW0,L as L →∞.The fixed-width, increasing-depth setting is highlighted for its dramatic gain in approximation efficiency.
  • Approximation framework: Approximation performance is organized by the decay of error as the parameter count n →∞, using Σn to represent network classes with n proportional to their parameters.Examples include Σn = Υn,1 and Σn = ΥW0,n.
  • Approximation framework: The analysis studies ReLU outputs on [0, 1]^d using Lp(Ω) approximation error, emphasizing p = ∞, 2, and 1.For p = ∞, approximation is uniform when f is continuous; the parameter count is n(W, L).
  • Scope and limitations: The Lp error framework does not match classification performance measures based on misclassification probability or expectation, a distinction the survey leaves unresolved.The authors note that this distinction may underlie neural networks’ success in learning environments.
  • Model classes: The analysis compares neural networks with classical approximation on standard smoothness classes and seeks new classes where neural networks outperform traditional methods.Such new classes are intended to clarify when neural-network approximation is beneficial in applications.
  • Approximation classes: Precise characterizations of neural-network approximation classes remain largely unavailable, unlike for many classical linear and nonlinear approximation methods.Known inverse theorems are limited to certain activation functions, including ReLU, in the one-dimensional shallow-network case.

7. Approximation using single layer ReLU networks

Single-layer ReLU networks are equivalent to free-knot linear splines in one dimension, where approximation is best understood, while higher-dimensional approximation remains only partially characterized. Their hyperplane-induced, potentially anisotropic partitions motivate new model classes but also make sharp performance results difficult.

  • d > 1: In higher dimensions, hyperplane arrangements generate complex, potentially anisotropic convex-polytope partitions, and not every subordinate CPwL function belongs to Σn.The resulting partitions have no simple characterization and can contain many cells.
  • d > 1: Matching lower bounds and complete approximation characterizations remain unknown in general dimensions, including for several Besov and Sobolev model classes.Known results also do not reflect the expected gain from the nonlinear approximation method.
  • New model classes: Barron classes provide one advance toward new model classes, with ReLU networks inheriting Barron’s approximation result through a difference of shifted ReLUs.The result concerns approximation in the L2(Ω) norm for the single-layer family.
  • d = 1: For d = 1, approximation by single-layer ReLU networks is essentially free-knot linear spline approximation, so known spline results provide the theoretical foundation.The one-dimensional case is presented as the best-understood setting and as guidance for higher dimensions.
  • d = 1: O((n + 1)−s) approximation rates apply to several one-dimensional smoothness classes, including cases where smoothness is measured in Lτ(Ω) with τ ≠ p.When τ ≥ p, equally spaced breakpoints suffice; when τ < p, the nonlinear structure of Σn is needed.
  • d > 1: For the Lip 1 ball measured in C(Ω), the approximation rate is n−1/d modulo logarithmic factors, which remain of interest to remove.Bounds for Kα := U(Lip α), 0 < α < 1, can be derived from the Lip 1 result by interpolation theory.

8. Approximation using deep ReLU networks

Deep ReLU networks match or improve on classical nonlinear approximation rates for many smoothness classes, with especially strong rates arising from deep compositions and self-similar constructions. These gains are accompanied by logarithmic limitations, incomplete lower-bound theory, and unresolved questions about stable numerical implementation and new high-dimensional model classes.

  • Classical smoothness classes: Deep ReLU networks approximate classical Lipschitz, Hölder, Sobolev, and Besov classes at least as well as known nonlinear approximation methods.The comparison is made for errors measured in an Lp norm with 1 ≤ p ≤ ∞.
  • Classical smoothness classes: Deep ReLU networks achieve error rates dramatically better than standard nonlinear methods for classical model classes.For Besov classes, the classical rate is O(n^-s/d), while the network construction achieves corresponding rates modulo logarithmic factors.
  • Constructive approximation: Deep ReLU networks approximate multiplication and monomials with exponential accuracy, enabling accurate approximation of tensor-product constructions.For multiplication derivatives, the bound is ∥∂iΠ − ∂iΠn∥L∞([0,1]^2) ≤ 2 · 2^-n; tensor-product approximation additionally satisfies ∥g − S∥C(Ω) ≤ dε + ed · 4^-n.
  • Lipschitz approximation: For Lipschitz spaces, the approximation rate is O(n^-2), twice the standard n-parameter rate, with matching upper and lower bounds.The result is interpreted as evidence that the network manifold has space-filling properties.
  • Limitations and open questions: Approximation theory remains incomplete because optimal rates and matching lower bounds are unavailable for many Besov cases, while stable numerical methods and high-dimensional model classes remain insufficiently understood.For p < ∞, available super rates lack close lower bounds; for p = ∞, a complete description is known only when 0 < s ≤ 1, with optimal rate n^-2s/d.
  • Self-similar model classes: Self-similarity from compositions of continuous piecewise-linear functions explains how deep ReLU outputs can approximate functions such as the Weierstrass nowhere differentiable function.As the input traverses [0, 1], the composition traces scaled copies or parts of one component function.

9. Stable approximation

The section examines how stability and continuity constraints affect neural-network approximation rates and numerical construction. It establishes local Lipschitz continuity of the network-output map while leaving optimal stable rates for key model classes unresolved.

  • Stability constraints: Stability restrictions limit achievable neural-network approximation rates to no better than the model class’s entropy numbers.These entropy numbers provide a benchmark for optimal performance but do not guarantee that neural networks attain it.
  • Stability constraints: For Besov balls embedded in Lp, entropy yields the lower-bound rate O(n^-s/d), but stable or continuous neural-network mappings achieving it are not provided.The same unresolved situation applies when only continuity is required.
  • Output-map stability: The natural network-output mapping Mn is Lipschitz on every finite parameter ball, with a constant depending only on the ball, width, depth, and dimension.This establishes local Lipschitz continuity of the architecture’s parameter-to-function map.
  • Output-map stability: The Lipschitz constant can be controlled on sufficiently small balls around the origin, whose required size decreases as network width increases.The control is obtained by keeping the layer matrix norms small.
  • Continuity and attainable rates: Under continuous parameter selection, approximation rates better than O(n^-s/d) are impossible for compactly embedded Besov balls, while the rate is known attainable when τ ≥ p.In those cases, finite-element spaces contained in the neural-network sets achieve the rate through linear operators.

10. Approximation from data

Learning-based neural-network approximation recovers a function from finite observations rather than full access to the target, so quantitative guarantees require model-class information and incur performance loss. Optimal recovery uses the Chebyshev center of the data-consistent model-class slice, while surrogate classes and least-squares procedures provide more practical numerical methods.

  • Motivation: Data observations alone do not provide a rigorous quantitative guarantee for recovering the target function, unlike approximation with full access to f.Learning observes f only through data, so performance guarantees must account for the loss caused by incomplete information.
  • Problem formulation: Quantitative recovery requires both bounded linearly independent observations and model-class information stating that f belongs to a compact set K.The observations are functionals applied to f, while K supplies additional information needed to quantify recovery accuracy.
  • Optimal recovery: Given the data and model class, the Chebyshev center of the data-consistent set Kw is the optimal approximation, with error equal to its Chebyshev radius Rw.Every function in Kw remains a possibility for f, so the center minimizes the worst-case error over those possibilities.
  • Numerical recovery: The optimal Chebyshev-ball construction guides numerical procedures but is difficult to compute, and the appropriate model class K may be uncertain in practice.Least-squares recovery with a model-class constraint and surrogate classes are presented as standard practical approaches.
  • Surrogate models: For a surrogate based on a nonlinear manifold, the approximation S* satisfies ∥f − S*∥H ≤ 2µnεn + εn for f ∈ Kw.The surrogate approximation error εn combines with the recovery bound involving µn, yielding the stated guarantee.

11. Using Neural Networks for data fitting

Deep learning fits high-dimensional, noisy data with overparameterized neural networks, but its strong empirical generalization lacks satisfactory a priori theoretical guarantees. Gradient descent selects among many interpolants in a way influenced by initialization and, in suitable regimes, resembles optimization in an RKHS.

  • Motivation: Deep learning successfully handles very high-dimensional problems, yet its performance is established mainly empirically and generally lacks a priori guarantees.Performance is evaluated on new data draws, while model-class assumptions are typically not formulated.
  • Overparameterized learning: Neural networks are often overparameterized, yielding infinitely many parameter choices whose outputs interpolate the training data.The central analytical problem is identifying which interpolant the numerical method selects and whether that selection defines a hidden model-class assumption.
  • Gradient descent: With appropriate step sizes, gradient descent can produce parameter iterates whose resulting network approximations generalize well.The kth iterate is denoted θ(k), and the procedure is described as converging to a limiting parameter selection.
  • Gradient descent: Random initialization affects the component of the parameters not seen by the data, while greedy gradient descent leaves that component unchanged.Its norm equals the distance between the selected parameter θ* and ˆθ, making initialization consequential.
  • Analytic interpretation: For small step sizes and large widths, fixed-depth neural-network gradient descent is similar to gradient descent for least-squares regression in the RKHS determined by Kσ,L.This provides an analytic perspective on the optimization dynamics, but why overparameterized learning generalizes well remains poorly understood.
  • Open questions: Understanding whether the gradient-descent-generated surrogate is good for a universal collection of model classes remains an open analytical question.The section also asks about the regularity of the algorithmic map and the compact sets on which it behaves well.

Manuscripta Math.

This section lists related work on neural-network approximation, including universal approximation, deep-network expressivity, and ReLU linear-region complexity.

  • Related work: Several cited studies analyze approximation by deep neural networks, including approximation spaces, smooth functions, and piecewise smooth functions.
  • Related work: Prior work establishes multilayer feedforward networks as universal approximators.
  • Related work: Other references study the number of linear regions and activation patterns in deep ReLU networks.
Loading 2012.14501v1…