Source-linked AI summary
Error bounds for approximations with deep ReLU neural networks in $W^{s,p}$ norms
Ingo Gühring, Gitta Kutyniok, Philipp Petersen
TL;DR
The paper addresses the lack of a comprehensive mathematical understanding of deep neural-network approximation in Sobolev settings relevant to PDEs. It constructs ReLU networks and proves upper and lower complexity bounds, showing a regularity-complexity trade-off and a persistent curse of dimensionality, while noting practical constraints on weights and architecture choice.
Problem
A comprehensive mathematical explanation of deep neural-network success is unavailable, while Sobolev-norm approximation is important for derivative-sensitive applications such as numerical PDE solution.
Method
The paper uses a calculus of ReLU networks to construct approximants for Sobolev-regular functions and establishes lower bounds for ReLU-network approximation complexity.
Results
The bounds exhibit a regularity-complexity trade-off, with upper weight and neuron complexity O(ε^-d/(n-s)), and Theorem 4.3 rules out circumventing the curse of dimension in the considered setting.
Takeaways & Limitations
The results provide upper and lower complexity bounds for architectures used in Sobolev training and may support theoretical analyses of deep-learning methods for numerical PDEs.
Takeaways & Limitations
The analysis is tied to the considered setting, cannot avoid the curse of dimension, and includes constructions with weights whose arbitrary or unbounded precision is infeasible to store.
Abstract
from arXiv · showhide
We analyze approximation rates of deep ReLU neural networks for Sobolev-regular functions with respect to weaker Sobolev norms. First, we construct, based on a calculus of ReLU networks, artificial neural networks with ReLU activation functions that achieve certain approximation rates. Second, we establish lower bounds for the approximation by ReLU neural networks for classes of Sobolev-regular functions. Our results extend recent advances in the approximation theory of ReLU networks to the regime that is most relevant for applications in the numerical analysis of partial differential equations.
1 Introduction
The paper studies why deep ReLU networks approximate functions effectively, focusing on Sobolev norms relevant to PDE applications. It develops upper and lower approximation bounds for Sobolev-regular functions and describes the network setting motivating this analysis.
- 1 Introduction: Deep neural networks outperform traditional modelling and classical machine learning methods across applications, but their success lacks a comprehensive mathematical explanation.The paper links this theoretical gap to the need for more efficient architectures and safety-critical understanding.
- 1 Introduction: Approximation theory provides universal and refined results relating neural-network size to approximation fidelity, including results for ReLU networks and their depth.Prior work also connects ReLU approximation rates to sparse grids and linear finite elements.
- 1 Introduction: Sobolev-norm approximation is especially relevant to deep-learning methods for solving partial differential equations, because derivatives matter alongside function values.Earlier results had begun addressing approximation in Sobolev-type norms.
- 1 Introduction: The paper comprehensively analyzes approximation rates for Sobolev-regular functions in fractional Sobolev norms using deep neural networks.Its contribution includes ReLU-network constructions and corresponding lower bounds.
- 1 Introduction: The proposed setting studies feedforward networks built from affine transformations and componentwise activation functions, with complexity measured by layers, weights, and neurons.The work focuses primarily on ReLU networks with skip connections and motivates derivative-aware training through Sobolev training.
2 Neural networks
The paper formalizes feedforward ReLU networks, their architectures and complexity measures, then develops concatenation, identity, parallelization, and standardization constructions.
- Standard neural networks restrict connections to neighboring layers, while the broader architecture permits skip connections between non-neighboring layers.
- Neural networks are sequences of matrix-vector tuples with an activation function applied componentwise between affine transformations.
- Architectures specify layer widths, permitted connections, and binary sparsity patterns; complexity is measured using layers, neurons, and nonzero weights.
- ReLU networks support concatenation for composing realizations and an identity construction that enables sparse concatenation with controlled complexity.
- Parallelization combines networks into one network with maximum depth, additive neuron and weight complexity up to the stated input-dimension adjustment, and concatenated outputs.
- Any ReLU network can be represented by a standard network with the same depth and at most C1LN neurons and C2·(LN+M) nonzero weights.
3 Sobolev spaces
This section introduces Sobolev and fractional Sobolev spaces as function spaces for generalized derivatives, integrability, PDE analysis, and boundary traces.
- Sobolev spaces collect functions whose generalized derivatives satisfy specified integrability conditions and are central to functional-analytic formulations of PDEs.
- The spaces W^n,p(Ω) use Lebesgue integrability of derivatives through order n and form Banach spaces under their Sobolev norms.
- For n=0, the Sobolev space reduces to the Lebesgue space: W^0,p(Ω)=L^p(Ω).
- The analysis assumes convex domains, which are treated as Lipschitz domains when open and bounded.
- Fractional Sobolev spaces characterize boundary regularity through trace operators and are defined here using an intrinsic Sobolev-Slobodeckij norm.
4 Approximations with deep ReLU neural networks in Sobolev type norms
The paper derives upper and lower complexity bounds for deep ReLU approximation of Sobolev-regular functions in Sobolev-type norms, including a regularity–complexity trade-off.
- The section generalizes prior ReLU approximation results from L∞ error to approximation measured in Sobolev-type norms.
- Theorem 4.1 establishes upper complexity bounds for approximating functions in W^n,p((0,1)^d) with errors measured across 0≤s≤1.
- The upper bounds exhibit a trade-off between the regularity used in the approximation norm and the regularity assumed in the function class.
- For s=0 and p=∞, the theorem coincides with Yarotsky’s result, while ReLU realizations on (0,1)^d are bounded and Lipschitz continuous.
- The upper-bound theorem also extends directly to continuous piecewise linear activation functions with finitely many breakpoints.
- Theorem 4.3 extends the regularity–complexity trade-off to lower bounds, including standard architectures and piecewise polynomial activations with finitely many breakpoints.
5 Discussion and future work
The discussion connects the bounds to Sobolev training and PDEs while identifying dimensional, depth-related, and weight-representation limitations.
- Practical relevance: The results provide upper and lower architecture-complexity bounds relevant to Sobolev training and may support theoretical foundations for deep-learning PDE solvers.
- Curse of dimension: The upper bounds scale as O(ε^-d/(n-s)) for weights and neurons, with constants that also grow exponentially in input dimension d.
- Curse of dimension: Theorem 4.3 shows that the considered setting cannot be expected to circumvent the curse of dimension, despite a remaining gap between upper and lower weight bounds.
- The power of depth: For s=0, unbounded-depth constructions can be more efficient than fixed-depth networks in weights and neurons under the cited regularity conditions.
- The power of depth: More than 2d regularity is required to outperform a shallow network, and the result does not completely explain deep networks’ empirical success.
- Unbounded complexity of weights: The construction achieving the upper bound uses weights whose absolute values diverge as ε decreases, creating an unbounded weight-complexity issue in implementation.
- Unbounded complexity of weights: Extending the upper theorem to quantized weights and determining sufficient quantization coarseness remain open directions.
A Interpolation spaces
The section introduces real interpolation spaces through the K-method and records their nesting and operator-interpolation properties. These abstract spaces will later be applied to Sobolev spaces to obtain fractional regularity spaces.
- A Interpolation spaces: Real interpolation spaces are Banach spaces constructed from an interpolation couple using the K-method.The construction uses a norm based on the K-functional and parameters θ and p.
- A Interpolation spaces: The interpolation spaces bridge two Banach spaces and form a continuously nested family as the interpolation parameter increases.For 0 < θ1 < θ2 < 1, the corresponding spaces satisfy a continuous embedding.
- A Interpolation spaces: Interpolating a Banach space with itself reproduces that same space: (B, B)θ,p = B.This holds for 0 < θ < 1 and 1 ≤ p ≤ ∞.
- A Interpolation spaces: An operator bounded on both endpoints of two interpolation couples is bounded between the corresponding interpolation spaces.The theorem applies for every 0 < θ < 1 and 1 ≤ p ≤ ∞.
- A Interpolation spaces: A corollary provides an interpolation-space estimate for elements of the stronger endpoint space.The estimate involves a constant depending on θ and p.
B Sobolev spaces
This section defines scalar and vector-valued Sobolev spaces and their seminorms, then records the connection between Lipschitz continuity and W 1,∞ regularity. It also notes the embedding of W n,∞ into W n,p on bounded domains.
- B Sobolev spaces: Vector-valued Sobolev spaces consist of vectors whose components belong to the corresponding scalar Sobolev space.For f = (f1, ..., fm), W n,p(Ω; Rm) requires fi ∈ W n,p(Ω), with the W n,∞ norm defined by the maximum component norm.
- B Sobolev spaces: The Sobolev seminorm |·|W k,p(Ω) is introduced for derivative orders k ≤ n, and at k = 0 it equals the Lp norm.The definition also covers vector-valued functions and p = ∞.
- B Sobolev spaces: On open convex domains, W 1,∞ functions are Lipschitz with Lipschitz constant controlled by the L∞ norm of their gradient.Conversely, bounded Lipschitz functions belong to W 1,∞ and their weak and classical gradients agree almost everywhere.
- B Sobolev spaces: For open bounded domains, W n,∞(Ω) is continuously included in W n,p(Ω) for every finite p.The stated range is 1 ≤ p < ∞ and n ∈ N0.
B.1 Composition estimate
The section establishes composition estimates in W 1,∞ by representing Sobolev functions with Lipschitz representatives and combining Lipschitz composition with a chain-rule estimate.
- B.1 Composition estimate: The composition g ◦ f is defined using Lipschitz-continuous representatives to make composition well-defined for Sobolev equivalence classes.Different representatives of g may agree almost everywhere without agreeing after composition with f.
- B.1 Composition estimate: The composition of an L1-Lipschitz map with an L2-Lipschitz function is (L1 · L2)-Lipschitz.This elementary estimate supplies the Lipschitz control used for the Sobolev composition result.
- B.1 Composition estimate: For open bounded convex domains with ran f ⊂ Ω2, composing f ∈ W 1,∞(Ω1; Rm) and g ∈ W 1,∞(Ω2) yields g ◦ f ∈ W 1,∞(Ω1).The resulting chain-rule estimate has a constant depending on d and m.
- B.1 Composition estimate: The proof controls the Lipschitz constant of f through its component gradient norms and then combines it with the Lipschitz constant of g.The component bounds are assembled into Lf = (L1, ..., Lm) before applying the composition estimate.
B.2 Product estimate
The section gives a product estimate showing that multiplying a W 1,∞ function by a W 1,p function preserves W 1,p regularity, with a dimension- and p-dependent bound.
- B.2 Product estimate: If f ∈ W 1,∞(Ω) and g ∈ W 1,p(Ω), then fg ∈ W 1,p(Ω).The result holds for 1 ≤ p ≤ ∞.
- B.2 Product estimate: The weak derivatives of fg are handled using the product formula for weak derivatives.The proof applies the formula componentwise and obtains a bound with C = C(d, p).
B.3 Averaged Taylor polynomial
The section introduces averaged Taylor polynomials as polynomial approximants for Sobolev functions and establishes their approximation error under geometric domain conditions.
- Construction: The averaged Taylor polynomial is the first approximation step used to construct a neural-network approximation of f.It is defined for Sobolev functions using averaging over an interior ball and a cut-off function.
- Construction: The averaged Taylor polynomial is linear in f and is a polynomial in x of degree less than n.These properties follow from its integral definition and averaging of polynomial expressions.
- Coefficient control: The coefficients c_α satisfy |c_α| ≤ c r^(−d/p)∥f∥W^(n−1),p(Ω) under the stated ball and domain assumptions.The constant depends on n, d, and R.
- Geometric condition: The construction requires that paths between points in the averaging ball and points in Ω remain inside Ω.This motivates the star-shapedness condition used in the approximation lemma.
- Approximation properties: For domains star-shaped with respect to an interior ball, the Bramble-Hilbert estimate gives |f − Q_nf|W^k,p(Ω) ≤ C h^(n−k)|f|W^n,p(Ω) for k = 0, 1, ..., n.The constant depends on n, d, and the chunkiness parameter γ.
B.4 Fractional Sobolev spaces
This section presents fractional-order Sobolev spaces through interpolation and intrinsic norms, then states their equivalence on Lipschitz domains.
- Definitions: Fractional Sobolev spaces W^s,p are characterized using interpolation of integer-order Sobolev spaces and an intrinsic norm.The two constructions are shown to agree under a regularity condition on Ω.
- Interpolation definition: For 0 < s < 1 and 1 ≤ p ≤ ∞, the section defines W^s,p via Banach space interpolation.This is introduced before comparing the interpolation and intrinsic formulations.
- Norm equivalence: On Lipschitz domains, the interpolation-based and intrinsic definitions yield the same spaces with equivalent norms.The result covers 0 < s < 1 and 1 ≤ p ≤ ∞.
- Use in the paper: Subsequent arguments use the W^s,p norm while transferring interpolation-theoretic results through this norm equivalence.The transfer is made without repeated mention in the following section.
C Upper bounds for approximations
The section constructs ReLU networks for Sobolev approximation by combining polynomial localization, approximate multiplication, and approximation of the square function, with logarithmic accuracy dependence.
- Proof strategy: The upper-bound proof approximates a Sobolev function by a polynomial and then realizes that polynomial approximation with a ReLU network.The analysis measures approximation errors in Sobolev norms, including derivative error in W^1,∞ for the basic operations.
- Localized polynomial approximation: The construction extends approximation from localized monomials to localized polynomials in W^k,p through an embedding, for k = 0, 1.This provides the approximation components used in the upper-bound proof.
- Basic network operations: For ε ∈ (0, 1/2), the square function can be approximated in W^1,∞ using networks with weights, layers, and neurons all scaling as log²(1/ε).The construction is a piecewise-linear interpolation of x ↦ x² with 2^m + 1 breakpoints.
- Basic network operations: Approximate multiplication is constructed from approximate squaring via the polarization identity, with depth and parameter counts bounded by c₁ log²(1/ε) + c₂.The network has two-dimensional input and one-dimensional output and preserves zero inputs.
- Localization: A partition of unity built from products of piecewise-linear factors localizes monomial and polynomial approximations.Each partition function is realized by a small ReLU network, and its W^k,∞ norms are bounded by (cN)^k for k = 0, 1.
- Final architecture: The resulting architecture has at most C₂ log²(1/ε) layers and C₃(N + 1)^d log²(1/ε) weights and neurons.The architecture has d-dimensional input and one-dimensional output and approximates functions in W^n,p((0,1)^d) through localized polynomials.
D Lower bounds for approximations
The lower-bound argument transfers approximation requirements into VC-dimension constraints, then upper-bounds that VC dimension through the network’s computational complexity. This yields weight lower bounds for L∞ and W 1,∞ approximation, with the latter obtained by encoding derivative behavior.
- Derivative-based construction: For W 1,∞ approximation, directional derivatives of ReLU networks are evaluated on regions where the realized function is affine-linear.The proof uses local affine structure and continuity of derivatives to transfer approximation of the function into derivative-based label separation.
- Lower-bound strategy: The lower-bound proof constructs a binary hypothesis class H parameterized by network weights and an auxiliary scalar, linking approximation accuracy to network size.The parameterization enables the class to represent labels through directional derivatives of approximating networks.
- Final lower bounds: The resulting lower-complexity theorem combines the VC-dimension construction with the approximation scale ε ≤ cN^−(n−1), while k = 0 recovers the earlier L∞ result.The proof relates N to ε and then applies Proposition D.2 to obtain the stated weight lower bound.
- Lower-bound strategy: A grid of N^d separated points can be shattered by H, giving VCdim(H) ≥ N^d.For every binary labeling, suitable weights and an auxiliary parameter produce the prescribed labels.
- VC-dimension upper bound: The class H is computed with O(M(Aε)) comparison-based operations, so VCdim(H) is bounded above by C·M(Aε)^2.The network evaluation and geometric preprocessing each require a number of operations proportional to the architecture’s weight count.