Source-linked AI summary
New error bounds for deep networks using sparse grids
Hadrien Montanelli, Qiang Du
TL;DR
Standard multivariate approximation bounds suffer from the curse of dimensionality, and results avoiding it often focus on specially structured functions. This paper uses sparse-grid approximations for functions in Korobov spaces. Its estimates significantly lessen, but do not eliminate, dimensional dependence.
Problem
Standard approximation results suffer from the curse of dimensionality, with network size growing geometrically in dimension; prior results avoiding it often rely on special function structure.
Source: §1 · pp. 1–2Method
The paper establishes deep-network approximation estimates for Korobov-space functions by approximating sparse grids.
Source: §1 · p. 4, §2.3 · p. 7Results
The curse is not eliminated but is significantly lessened, since dimension d affects logarithmic factors |log2 ε|.
Source: §1 · p. 4Takeaways & Limitations
The estimates address a more generic high-dimensional multivariate function space rather than relying on special function structures such as compositionality.
Source: §1 · p. 1Sparse grids, particularly the norm used, are highly anisotropic and require functions to be aligned with the axes to be efficient.
Source: §4 · p. 11
Abstract
from arXiv · showhide
We prove a theorem concerning the approximation of multivariate functions by deep ReLU networks. We present new error estimates for which the curse of the dimensionality is lessened by establishing a connection with sparse grids.
1. Introduction.
Standard approximation bounds for multivariate functions suffer from geometric growth with dimension, while prior results avoiding that curse often rely on special function structure. This paper gives deep-network error estimates for Korobov spaces using sparse grids, lessening—but not eliminating—the dimensional dependence.
1. Introduction.
- The paper takes a different route by considering a more generic function space for high-dimensional multivariate approximation and connecting its error estimates to sparse grids.The introduction frames understanding when deep networks lessen or break the curse as an important theoretical problem.Source: §1 · p. 1
- Standard approximation results suffer from the curse of dimensionality because network size grows geometrically with dimension d.For small d, the size increases at a reasonable rate as accuracy ε improves.Source: §1 · p. 2
- Earlier results that avoid the curse often target special structures, including compositional functions represented by binary trees with d − 1 local functions.For d = 8, the illustrated tree has three levels and seven local functions, each approximated by a subnetwork.Source: §1 · p. 3, Figure 1.1 · p. 4
- For functions in Korobov spaces X2,p(Ω) with mixed derivatives of order two, accuracy ε is achieved with deep networks of depth O(|log2 ε| log2 d).The introduction also states a network-size bound, but its expression is not fully available in the supplied passage.Source: §1 · p. 4
- Sparse-grid approximation significantly lessens the curse, but does not eliminate it; dimension d affects logarithmic factors |log2 ε|.Korobov spaces X2,p(Ω) are described as subsets of Sobolev spaces W2,p(Ω).Source: §1 · p. 4
2. Korobov spaces and sparse grids.
The section develops hierarchical bases, extends them to multivariate Korobov spaces, and uses a truncated expansion to construct sparse grids. Sparse grids use many fewer points than full grids, with only slightly deteriorated accuracy.
2.1. One-dimensional hierarchical basis.
- For one variable, level-l grids have spacing 2^-l, and their piecewise-linear hat functions form hierarchical or nodal bases spanning the same space.At n = 3, the hierarchical basis uses three grids with mutually disjoint supports within each grid; these bases also generalize to higher-order polynomials and wavelets.Source: §2 · p. 4, Figure 2.1 · p. 5, §2.1 · p. 5
2.2. Multi-dimensional hierarchical basis and Korobov spaces.
- The multi-dimensional hierarchical basis consists of the bases corresponding to increment spaces W_l, and functions in X2,p(Ω) have a unique infinite expansion in it.Source: §2.2 · pp. 6–7
- Korobov spaces measure smoothness through mixed derivatives of order two and are subsets of Sobolev spaces W 2,p(Ω).Source: §2.2 · pp. 6–7
2.3. Discretization.
- Sparse grids discretize X2,p(Ω) by truncating its hierarchical expansion.Source: §2.3 · p. 7
- Sparse grids use many fewer points than full grids, with only slightly deteriorated accuracy.They omit cross-terms with small support in multiple dimensions.Source: §2.3 · pp. 7–8
3. Error bounds using sparse grids.
The section replaces polynomial approximation with sparse-grid approximation to establish deep ReLU network error bounds. It builds the network by implementing multidimensional hat-function products and then representing sparse-grid approximations with those subnetworks.
3. Error bounds using sparse grids.
- The proof replaces the usual polynomial-approximation route with sparse-grid approximations represented by deep networks.The construction uses M subnetworks to implement approximate multiplications for the sparse-grid terms.Source: §3 · p. 8, §3.1 · p. 9, §3.2 · p. 9
3.1. Approximating multi-dimensional hat functions by deep networks.
- Deep ReLU networks approximate multidimensional hat-function products with accuracy ǫ and depth and size O(| log2 ǫ| log2 d).The products are arranged in a binary tree; the multiplication building block is attributed to Yarotsky [21, Prop. 3].Source: §3.1 · pp. 8–9
3.2. Approximating sparse grids by deep networks.
- For any dimension d, Theorem 1 gives accuracy ε for functions in X2,p([0, 1]d) with |f|2,∞≤1 and depth O(| log2 ǫ| log2 d).The theorem also gives a network-size bound, but its full expression is not present in the supplied passage.Source: §3.2 · p. 9
- The sparse-grid construction uses M subnetworks, each implementing an approximate multiplication, to represent the sparse-grid approximation of f.The component hat functions are computed to accuracy δ using Proposition 2.Source: §3.2 · pp. 9–10, §3.1 · p. 9
4. Discussion.
The paper establishes upper bounds for approximating Korobov-space functions with deep ReLU networks, lessening the curse of dimensionality by approximating sparse grids through a binary-tree structure.
4. Discussion.
- Sparse-grid approximation through a binary-tree structure yields rigorous deep ReLU upper bounds for Korobov spaces that lessen the curse of dimensionality.The authors note that this structure resembles the compositional structure used in.Source: §4 · p. 11
- The discussion identifies extensions to smoother functions, piecewise-smooth functions, Jacobi-weighted Korobov spaces, and energy-based sparse grids.It also proposes a shallow-network lower bound to assess whether deep networks have an advantage.Source: §4 · p. 11
- The theorem bounds complexity for one network architecture shared across a Korobov space, with only its weights depending on the function.The authors expect function-adaptive architectures to decrease complexity.Source: §4 · p. 11
- Sparse-grid efficiency requires axis-aligned functions, because the sparse-grid norm is highly anisotropic.The discussion notes this alignment also occurs in some multivariate approximation algorithms, including low-rank compressions and quasi-Monte Carlo methods.Source: §4 · p. 11
Appendix A. Proof of Proposition 2.
The proof constructs multiplication networks by induction on the input dimension, combining approximate products hierarchically to obtain depth and size O(|log2 ǫ| log2 d).
Appendix A. Proof of Proposition 2.
- The induction assumes d is a power of 2 and builds the d-input product from two d/2-input products in a hierarchical binary combination.The inductive subnetwork combines d/2 − 1 approximate products.Source: Appendix A · pp. 13–14
- For d = 2, the product network has depth and size O(|log2 ǫ|) and inherits the 0-in-0-out property.The base construction combines networks representing each input function with the approximate-multiplication network.Source: Appendix A · p. 13
- The proof allocates error to the top multiplication so the combined bound stays within ǫ.The second term is bounded by ǫ/2 + ǫ2/16, and the top multiplication is targeted at ǫ/2 − ǫ2/16.Source: Appendix A · p. 15
- O(|log2 ǫ| log2 d) bounds both depth and size of the full multiplication network.The proof combines the top multiplication with the previously constructed subnetwork and gives this overall bound.Source: Appendix A · p. 15