Source-linked AI summary
Provable approximation properties for deep neural networks
Uri Shaham, Alexander Cloninger, Ronald R. Coifman
TL;DR
The paper studies how to approximate functions on low-dimensional manifolds while addressing theoretical questions about neural-network topology and approximation guarantees. It constructs a sparsely connected depth-4 network using ReLU-computed wavelets and manifold charts, with size controlled by function complexity and geometry and only weakly by ambient dimension. The construction provides approximation capabilities for sparse-wavelet and smooth function classes, while relying on handmade architectures and a manifold-concentration conjecture for broader applicability.
Problem
Deep neural networks have strong practical performance, but theoretical results on topology and approximation properties remain incomplete.
Method
The paper combines an atlas of the manifold with chartwise wavelet approximations computed from ReLU units to construct a sparsely connected depth-4 network.
Results
The network size depends on wavelet complexity, manifold curvature and dimension, and only weakly on ambient dimension, with error rates given for sparse-wavelet and C2 functions.
Takeaways & Limitations
The construction gives a formal approximation-capability description of depth-4 neural networks for functions defined on smooth manifolds.
Takeaways & Limitations
The architecture and weights are handmade and unlikely to result from standard training; broader application also depends on a conjecture about low-dimensional manifold structure in hidden representations.
Abstract
from arXiv · showhide
We discuss approximation of functions using deep neural nets. Given a function $f$ on a $d$-dimensional manifold $Γ\subset \mathbb{R}^m$, we construct a sparsely-connected depth-4 neural network and bound its error in approximating $f$. The size of the network depends on dimension and curvature of the manifold $Γ$, the complexity of $f$, in terms of its wavelet description, and only weakly on the ambient dimension $m$. Essentially, our network computes wavelet functions, which are computed from Rectified Linear Units (ReLU)
1 Introduction
The paper addresses theoretical gaps in neural-network approximation by constructing depth-4 sparse networks for functions on smooth manifolds. Network size and error guarantees depend on manifold geometry and function complexity, with only weak dependence on ambient dimension.
- Deep neural networks have achieved strong practical results, but their theoretical framework remains incomplete.
- The paper focuses on specifying network topology to obtain approximation properties for target functions.
- A smooth d-dimensional manifold Γ ⊂ R^m admits a depth-4 sparsely-connected network approximating f ∈ L2(Γ) at level δ.
- Network size depends on wavelet complexity, manifold curvature and dimension, and only weakly on ambient dimension m.
- For functions with l1 wavelet coefficients and for C2 functions with bounded Hessian, the paper provides depth-4 network approximation error rates.
- The manuscript specifies network topology and notation for wavelet terms, manifolds, atlases, tangent hyperplanes, and scaling functions.
2 Related work
Related work establishes universal approximation and approximation-rate results, while highlighting unresolved architecture and dimension issues. The paper targets these issues using manifold dimension and a wavelet-based construction.
- Classical universal approximation allows shallow sigmoidal networks to approximate compactly supported continuous functions but does not relate units to accuracy.
- Barron-type results provide approximation rates for single-hidden-layer networks, but their assumptions and constants can become restrictive with ambient dimension m.
- The manuscript achieves a known optimal point-wise rate with respect to manifold dimension d rather than ambient dimension m.
- Earlier wavelet-network studies used wavelet-computing hidden units without specifying architectures for desired approximation properties.
- Deep-network theory shows that depth can improve representational efficiency and the number of linear regions relative to equally sized shallow networks.
- A related manifold network maps data to local coordinates and approximates chartwise using B-splines, whereas this paper uses wavelets.
3 Preliminaries
The preliminaries develop manifold and wavelet tools for the construction, including atlases, partitions of unity, wavelet frames, sparse representations, and greedy approximation.
- Manifolds and atlases: A compact smooth manifold Γ ⊆ R^m is covered by local charts, whose collection forms an atlas.
- Manifolds and atlases: Charts provide Euclidean coordinates on manifold neighborhoods, while partitions of unity supply smooth compactly supported functions subordinate to the cover.
- Wavelet frames: The paper constructs a wavelet frame on R^d using averaging kernels, mother wavelets, and dual elements.
- Sparse approximation: A dictionary represents f through unit-norm elements with absolutely summable coefficients, whose absolute sum defines ∥f∥L1.
- Sparse approximation: L1 functions can be approximated with N dictionary terms with squared error proportional to 1/√N.
- Sparse approximation: The orthogonal greedy algorithm iteratively selects the dictionary element most correlated with the residual and updates the approximation by projection.
- Sparse approximation: Sparse wavelet coefficients can be identified without explicitly computing them by convolving f with wavelet terms across scales.
4 Approximating functions on manifolds using deep neural nets
The construction approximates functions on smooth manifolds by combining ReLU-generated wavelet frames with manifold charts, partitions of unity, and curvature-dependent extensions. The resulting network architecture reflects the manifold’s dimension and curvature, the function’s wavelet complexity, and the ambient dimension.
- 4.4 Extending wavelets to the ambient space: Wavelet terms are extended from tangent hyperplanes to R^m using trapezoidal profiles in orthogonal directions, with support chosen according to manifold curvature.The extension remains constant near the tangent hyperplane and decays linearly before vanishing, preventing support from reaching the manifold again within the chart construction.
- 4.1 Constructing a wavelet frame from rectifier units: ReLU units generate a wavelet frame of L2(R^d), providing the basic functions used in the approximation.The frame elements are constructed from rectifiers, and {ψ_k,b} is shown to be a frame.
- 4.1 Constructing a wavelet frame from rectifier units: Each wavelet term ψ_k,b can be computed by a sparse multilayer network, while sums of terms share the same basic architecture.A single wavelet term uses 8d rectifiers in the first layer, 2 in the second layer, and one linear unit in the third layer.
- 4.2 Creating an atlas: The manifold is covered by open balls whose number depends on its surface area, covering thickness, and curvature-related scale.The construction seeks a smaller atlas for lower-curvature manifolds; the covering thickness grows relatively slowly with d.
- 4.3 Representing functions using local coordinates: A partition of unity decomposes a function on Γ into chartwise functions on R^d, each of which receives a wavelet expansion.The chart images lie in d-dimensional tangent hyperplanes, which are identified with R^d.
- 4.4 Extending wavelets to the ambient space: The construction supports all charts through linear coordinate mappings, while the additional m−d trapezoids can be shared across scaling terms using 4(m−d) rectifiers.For points outside a chart but whose projected coordinates remain in the chart image, the corresponding wavelet terms lie outside their support.
5 Specifying the required size of the network
The paper specifies a depth-4 network whose unit counts depend on chart-local wavelet complexity, manifold geometry, and intrinsic dimension, with only limited ambient-dimension dependence. It also gives approximation rates for sparse-wavelet and twice-differentiable functions.
- Network construction: A depth-4 network approximates f by mapping inputs to local chart coordinates, approximating chart functions with wavelet terms, and summing the chart approximations.The first layer computes local coordinates, while compactly supported chart functions allow the network outputs to be combined across charts.
- Network size: The network uses mCΓ linear units initially, 8dΣ_iN_i + 4CΓ(m − d) rectifiers in the second hidden layer, 2Σ_iN_i rectifiers in the third layer, and one linear output unit.N_i is the number of wavelet terms used to approximate f on chart i.
- Approximation conditions: For sufficiently small chart radius δ, regularity or sparsity properties of the chart functions ˆf_i transfer to the target function f.The considered chart-function classes include L2 functions, functions with sparse coefficients, and twice-differentiable functions.
- Dimension dependence: The ambient dimension m affects the first two layers through the atlas size CΓ and extension units, while the third and fourth layer sizes are independent of m.The dependence of CΓ on manifold curvature makes curvature part of the network-size bound.
- Sparse-wavelet case: If ˆf_i has l1 wavelet coefficients, the required unit count is c1 + c2N, with N = max_iN_i and M = max_i∥ˆf_i∥L1 used in the approximation bound.The supplied passages state the resulting linear-in-N form and define c1 and c2, but omit the preceding error expression.
- Smooth-function case: For twice-differentiable chart functions, truncating wavelet levels through K yields a point-wise error rate of N^-2 when N = 2^(K+1).The corresponding network-size expression is again c1 + c2N.
- Tighter counting: The unit-count bounds are overly pessimistic when wavelet terms overlap across charts, because shared wavelets can reduce the effective term count and constant c2.For the all-scales-through-K construction, the shared-term adjustment gives c2 = 8d + 2.
6 Conclusions
The conclusion presents the construction as an analytical wavelet-frame component combined with a topological manifold-chart component. It emphasizes intrinsic-dimension scaling and states approximation rates, while noting that the architecture and weights are handmade rather than typically learned by standard training.
- Construction: The construction combines a ReLU-generated wavelet frame on L2(R^d) with an atlas-based representation of functions on a d-dimensional manifold.Wavelet approximations are extended from chart coordinates in R^d to the ambient space R^m.
- Scaling: Network size depends on wavelet complexity and manifold curvature, with stronger dependence on intrinsic dimension d than ambient dimension m when d ≪ m.Curvature is represented through atlas size, while wavelet-term counts represent function complexity.
- Approximation rates: The work obtains squared-error rates for functions with sparse wavelet expansions and point-wise error rates for twice-differentiable functions.These are the two function classes highlighted in the conclusion.
- Scope: The architecture and weights are handmade, so the stated approximation properties describe theoretical neural-network capability rather than networks expected to arise from standard training.The conclusion frames this as the intended significance of the results.
- Extensions: The paper proposes non-isotropic, non-axis-aligned wavelets such as curvelets as a possible way to obtain more efficient chart representations.The proposal is motivated for functions that are relatively constant in certain directions.
- Extensions: The authors conjecture that convolutional and pooling representations concentrate near low-dimensional manifolds, which would allow this construction to be applied to hidden representations.This conjecture is presented as a possible extension, not an established result.
- Activation functions: ReLU units are convenient but not essential, because similar wavelet frames can be built from localized bump-producing functions such as suitable sigmoids.The paper states that such frames are equivalent.
A Equivalence of representations in different wavelet frames
The appendix passage notes that wavelet representations can be compared through the interactions of wavelet terms across scales and shifts.
- Wavelet-frame equivalence: Wavelet-term interactions are strongest near matching scales, while widely separated scales produce small inner products.At comparable scales, only a small number of offsets have large-magnitude inner products.
- Wavelet-frame equivalence: The small interaction at separated scales follows from pairing a peaked, zero-integral function with a relatively flat function.The passage identifies this as the idea formalized in related work.
B Proof of Lemma 4.1
The appendix proves that the averaging kernels satisfy the required conditions by exploiting translation symmetry, compact support, boundedness, and derivative estimates.
- Kernel conditions: The proof uses ρ(x,b) = c∥x − b∥^d to express the volume of the smallest Euclidean ball containing x and b.The goal is to establish constants satisfying the averaging-kernel conditions for every scale and points in R^d.
- Proof setup: The proof may assume b = 0 without loss of generality and then establishes the estimates for arbitrary x and x′.An arbitrary positive ε is introduced in the argument.
- Symmetry reduction: Because S_k depends only on x − b and is symmetric about the origin, several kernel conditions reduce to proving one representative inequality.This reduction is stated for conditions 3.15–3.16 and 3.17.
- Estimate strategy: Condition 3.19 is handled under simultaneous proximity assumptions on x,x′ and b,b′ relative to the scale-dependent quantity 2^-k + ρ(x,b).The passage states the two distance constraints used in this part of the proof.
- Estimate strategy: The proof applies the mean value theorem to control variation in the kernel arguments and uses bounded, compactly supported functions to obtain uniform estimates.The argument introduces constants from these estimates and combines them by taking their maximum.
C Proof of Lemma 4.5
The proof establishes structural properties of the wavelet system and uses them to bound approximation by truncating the wavelet expansion. It combines vanishing moments, coefficient decay, pointwise bounds, and local support sparsity.
- Wavelet properties: Each primal and dual wavelet has two vanishing moments.The proof derives the primal moments from symmetry and change of variables, then transfers the property to the dual wavelets through convolution operators.
- Wavelet properties: The wavelet functions decay faster than any polynomial.This decay is used to establish finiteness of an integral appearing in the coefficient estimates.
- Wavelet properties: Every point belongs to the support of at most 12^d wavelet terms at each scale.This local support bound limits the number of nonzero terms contributing to the pointwise expansion.
- Approximation bound: For compactly supported, twice-differentiable f in L2(R^d) with d ≤ 3, truncating the expansion to scales k ≤ K yields a pointwise approximation bound.The proof combines the truncation f_K with support sparsity, wavelet magnitude bounds, and coefficient estimates before substituting them into Equation (115).
- Approximation bound: The proof relies on bounded wavelet amplitudes and coefficient decay to control the retained wavelet terms and the truncation error.The cited estimates include |ψ_k,b| ≤ 2^k/2 − 2 and a scale-dependent bound on the dual-wavelet coefficients.