Source-linked AI summary
Deep ReLU network approximation of functions on a manifold
Johannes Schmidt-Hieber
TL;DR
Approximating functions from data on a low-dimensional manifold is less well understood than recovering the manifold itself. This paper uses sparse deep ReLU networks with bounded parameters for manifold-based function approximation. The construction achieves a parameter count governed by intrinsic dimension, with a corresponding statistical-rate result for empirical risk minimization.
Problem
Approximation rates for functions defined on manifolds are less known, although inputs may lie on a low-dimensional manifold embedded in a higher-dimensional space.
Source: §1 · pp. 1–2Method
The paper approximates manifold-defined functions with sparsely connected deep ReLU networks whose parameters are bounded in absolute value by one.
Source: §1 · p. 4, §3 · p. 11Results
O(ε^-d*/β log(1/ε)) non-zero parameters suffice for ε approximation of a β-smooth function on a d*-dimensional manifold.
Source: §1 · p. 2Takeaways & Limitations
The approximation parameter count can depend on the manifold’s intrinsic dimension rather than the ambient dimension.
Source: §1 · p. 2The stated extension to M×U assumes the target function is independent of the coordinates in U.
Source: §3 · p. 11
Abstract
from arXiv · showhide
Whereas recovery of the manifold from data is a well-studied topic, approximation rates for functions defined on manifolds are less known. In this work, we study a regression problem with inputs on a $d^*$-dimensional manifold that is embedded into a space with potentially much larger ambient dimension. It is shown that sparsely connected deep ReLU networks can approximate a H\"older function with smoothness index $\beta$ up to error $\epsilon$ using of the order of $\epsilon^{-d^*/\beta}\log(1/\epsilon)$ many non-zero network parameters. As an application, we derive statistical convergence rates for the estimator minimizing the empirical risk over all possible choices of bounded network parameters.
1 Introduction
The paper studies function approximation when inputs lie on a low-dimensional manifold, rather than recovering the manifold itself. It gives a sparse deep ReLU approximation rate governed by intrinsic dimension and shows that good rates are possible with parameters bounded by one.
1 Introduction
- The learning task is to recover the input-output function from training data, not to reconstruct the manifold.The inputs are modeled as lying on an unknown d*-dimensional manifold embedded in R^d.Source: §1 · pp. 1–2
- O(ε^-d*/β log(1/ε)) non-zero parameters suffice for ε approximation of a β-smooth function on a d*-dimensional manifold.Approximating over the ambient domain instead can require ε^-d/β/(L log(1/ε)) parameters.Source: §1 · p. 2
- On a manifold, the local coordinate map reduces the target to a function on R^d* with the same smoothness, making it easier to approximate.The proposed composition lets a deep network learn the coordinate map and the transformed function in its first and last layers.Source: §1 · p. 3
- All network parameters can be bounded in absolute value by one while still achieving good approximation rates.The paper motivates this constraint by noting that networks are initialized with small random values and trained weights are typically close to initialization.Source: §1 · p. 4
- The introduction situates the approach among work on composition-structured functions and manifold approximation, while noting that the theory still imposes unrealistic assumptions.It contrasts its composition-based strategy and unit-bounded weights with Nakada and Imaizumi [21].Source: §1 · pp. 2–4
2 Deep feedforward neural networks
This section defines the feedforward ReLU network classes used in the paper and describes how their function spaces can be combined. The constructions support building larger networks from smaller ones by composition, layer synchronization, and parallel computation.
2 Deep feedforward neural networks
- A feedforward network passes information in one direction and uses ReLU activations, with an output activation chosen for the statistical task.For regression the output activation is the identity; for classification it is softmax.Source: §2 · p. 5
- A network architecture fixes the depth and layer widths, while its function is formed from weight matrices, shifts, ReLU activations, and an output activation.For a fixed architecture, approximation adjusts the matrix entries and shift vectors to reduce error.Source: §2 · p. 5
- Increasing layer widths or the allowed number of non-zero entries enlarges the sparse network function class.The section also defines sparse networks whose parameters are bounded in absolute value by one.Source: §2 · p. 6
- Networks can be composed when the first network’s output dimension matches the second network’s input dimension.Identity-weight layers can be inserted to synchronize hidden-layer counts.Source: §2 · p. 6
- Networks of equal depth can be combined in parallel to compute two network functions.The section also notes a width convention for sparse networks and a shorthand for repeated hidden-layer widths.Source: §2 · pp. 6–7
3 ReLU network approximation of a function on a manifold
The section develops the smooth-coordinate and Hölder-function framework for approximation on compact manifolds, then combines local networks to construct manifold approximations. It also describes an extension for functions invariant to additional coordinates.
Hölder functions and smoothness on a manifold
- A β-Hölder function is locally approximable by a polynomial of order ⌊β⌋ with error O(|x−a|∞^β).The section extends this smoothness framework from open Euclidean domains to subsets of metric spaces.Source: §3 · pp. 7–8
Manifolds with smooth local coordinates
- The framework assumes a compact manifold with smooth local coordinates, since smoothness of the manifold alone does not ensure smooth coordinate maps or inverses.The section also establishes smooth partition-of-unity functions with support inside chart regions.Source: §3 · p. 9
Main idea for construction of network approximation
- The manifold construction combines networks for the coordinate maps, localized functions, and partition weights to mimic a sum that reconstructs the target.The construction follows the partition-of-unity strategy summarized in Figure 1.Source: §3 · pp. 9–10, Figure 1 · p. 10
Approximations of Hölder functions by deep ReLU networks
- Theorem 1 gives a deep ReLU approximation result for Hölder functions on bounded subsets of Euclidean space, using local Taylor approximations on a grid.The proof reconstructs values by weighted sums of Taylor approximations at nearby grid points.Source: §3 · pp. 10–11
- With m ≍ log(N), the stated tradeoff yields approximation error O(N^-β/d) using O(N log N) non-zero parameters.The passage identifies the first error term growing when m is small and the second matching the expected rate up to a factor m.Source: §3 · p. 11
Remark 1
- For functions independent of added coordinates, the section states an O(Lη^-d*/β) parameter bound on M × U, depending on intrinsic dimension d* and smoothness β.The passage contrasts this with O(Lη^-d/β) for an unmodified approach when d is much larger than d*.Source: §3 · pp. 11–12
4 Statistical risk bounds
The section turns approximation bounds into prediction-risk guarantees for empirical risk minimization under Gaussian-noise regression, with inputs on an unknown compact manifold.
4 Statistical risk bounds
- The model assumes i.i.d. standard normal errors independent of the design, which lies on an unknown compact d*-dimensional manifold with smooth local coordinates.The regression function is assumed to have Hölder smoothness β.Source: §4 · pp. 12–13
- The empirical risk minimizer is studied over bounded network functions in F(L, p, s).The class is intersected with functions mapping [0, 1]^d to [-1, 1].Source: §4 · p. 13
- The prediction-risk guarantee is an oracle inequality: it compares the estimator with the best class member and adds a model-complexity penalty.The section derives this bound using empirical-process results before applying Theorem 2.Source: §4 · p. 13
- In particular, for L chosen of order log(n), the risk is bounded by constant × n^(-2β/(2β+d*)) log^3(n).Source: §4 · p. 13
5 Proofs
The proofs construct approximations first on Euclidean domains using grid-based Taylor constructions, then on the manifold by combining chartwise approximations, coordinate maps, local functions, and localized weights into one network. They also establish membership in the stated sparse-network class when depth, width, and sparsity meet specified lower bounds.
Proof of Theorem 1
- Theorem 1 adapts Theorem 5 in [26] by approximating grid-point Taylor polynomials, assigning nearby points outside U to a closest grid point in U, and bounding network parameters by one.The construction does not require enlarging the network architecture; extending from the central cube uses an affine transformation, adding one layer and 2d non-zero parameters.Source: §5 · pp. 16–17
- The transformed-domain network has depth 9 + (m + 5)(1 + ⌈log2(d ∨ β)⌉), at most 142(d + β + 1)^(3+d)N(m + 6) parameters, and the stated error bound.The error is bounded by (2R^βK + 1)(1 + d^2 + β^2)6dN2^-m + R^βK3 2^βN^-β.Source: §5 · p. 17
Proof of Theorem 2
- The construction uses r parallel networks with nonnegative outputs, then adds a layer computing a weighted sum; its multiplier approximates xy within 2^-m for x, y in [0, 1].Source: §5 · p. 21
- For chart-coordinate approximators, depth L1 ≥ K1 log(1/η), pmax1 ≥ K′1η^-d*/β, and s1 ≥ K′′1L1η^-d*/β suffice, with constants independent of η.The chart-map approximation applies Theorem 1 on each chart domain.Source: §5 · p. 19
5 Proofs
- For positive constants c, C, and C′, the network ef belongs to F(L, (d ∼p ∼1), s) when L ≥ c log(1/eta), p ≥ C eta^(-d*/beta), and s ≥ C′L eta^(-d*/beta).Source: §5 · p. 21