Source-linked AI summary
Sharp Bounds on the Approximation Rates, Metric Entropy, and $n$-widths of Shallow Neural Networks
Jonathan W. Siegel, Jinchao Xu
TL;DR
The paper asks how efficiently shallow neural-network variation spaces can be approximated and how their metric entropy and n-widths behave. It introduces smoothness-based upper bounds and ridge-function lower bounds, obtaining sharp rates for important ReLU^k and bounded-variation sigmoidal activations. These results improve prior bounds and establish optimality within the corresponding variation spaces.
Problem
The paper studies efficient approximation of variation spaces by nonlinear dictionary expansions and the asymptotics of their metric entropy and n-widths.
Method
The paper combines smoothly parameterized dictionary bounds with a generalized Makovoz construction producing nearly orthogonal ridge functions for lower bounds.
Results
The resulting bounds give sharp approximation, entropy, and n-width rates for ReLU^k networks and extend lower bounds to sigmoidal activations with bounded variation.
Takeaways & Limitations
ReLU^k networks are optimal on their corresponding variation spaces, and stable or continuous nonlinear methods cannot improve on them there.
Takeaways & Limitations
The entropy upper bound is expected to be sharp only for p = 2, while its implied constants may be quite large and depend on the manifold and parameterization.
Abstract
from arXiv · showhide
In this article, we study approximation properties of the variation spaces corresponding to shallow neural networks with a variety of activation functions. We introduce two main tools for estimating the metric entropy, approximation rates, and $n$-widths of these spaces. First, we introduce the notion of a smoothly parameterized dictionary and give upper bounds on the non-linear approximation rates, metric entropy and $n$-widths of their absolute convex hull. The upper bounds depend upon the order of smoothness of the parameterization. This result is applied to dictionaries of ridge functions corresponding to shallow neural networks, and they improve upon existing results in many cases. Next, we provide a method for lower bounding the metric entropy and $n$-widths of variation spaces which contain certain classes of ridge functions. This result gives sharp lower bounds on the $L^2$-approximation rates, metric entropy, and $n$-widths for variation spaces corresponding to neural networks with a range of important activation functions, including ReLU$^k$ activation functions and sigmoidal activation functions with bounded variation.
1 Introduction
The paper develops smoothness-based upper bounds and ridge-function lower bounds for approximation, metric entropy, and n-widths of shallow neural-network variation spaces. Applied to ReLU^k and bounded-variation sigmoidal activations, these tools yield improved and often sharp rates.
- Main Results: Smoothly parameterized dictionaries produce upper bounds for approximation rates, metric entropy, and n-widths that exploit parameterization smoothness.The framework applies when a dictionary is parameterized to order s by a compact d-dimensional manifold.
- Main Results: For ReLU^k dictionaries, the paper shows approximation exponents satisfy α(k,d) ≥ 2k+1/(2d) for all k ≥ 0.The result improves previously described approximation rates when k ≥ 2.
- Main Results: The entropy upper bound is expected to be sharp only for p = 2 in the stated range because stronger L∞ approximation rates are available when k = 1.This is the authors’ stated limitation for that upper-bound result.
- Main Results: A generalized Makovoz construction yields nearly orthogonal functions and lower bounds for entropy and n-widths when dictionaries contain suitable ridge functions.The lower-bound method applies broadly to variation spaces containing the relevant ridge-function classes.
- Main Results: The lower bounds make the ReLU^k approximation exponent unimprovable even when the weight constraint is relaxed from ℓ1 to ℓ∞.They also combine with upper bounds to give a sharp metric-entropy decay rate in L2 for the corresponding variation space.
- Main Results: The same lower-bound approach extends to sigmoidal activations with bounded variation, under weaker assumptions than earlier results.The paper also reports a sharp entropy rate for the relevant variation spaces when the lower and upper bounds coincide.
- Main Results: Linear methods are substantially worse than shallow neural networks on the ReLU^k variation class, while stable or continuous nonlinear methods cannot improve on them there.The comparison is based on lower bounds for metric entropy and several n-widths.
2 Type-2 Spaces and Maurey’s Sampling Argument
The section establishes type-2 Banach spaces as the setting for Maurey’s sampling argument and derives nonlinear approximation of convex-hull functions through empirical sampling.
- Type-2 Banach spaces control randomized sums through a constant C2,X, with Hilbert spaces having C2,X = 1.The type-2 constant is defined by the relevant inequality; Hilbert-space orthogonality gives the value 1.
- Lp(dµ) is a type-2 Banach space for 2 ≤ p < ∞ by Khintchine’s inequality.The argument applies Khintchine’s inequality after interchanging expectation and integration.
- For f in the convex hull B1(D), Maurey’s theorem gives an n-term approximation rate under the type-2 assumption and dictionary bound KD.The theorem assumes X is type-2 and D is uniformly bounded, with KD := supd∈D ∥d∥X < ∞.
- The proof approximates f by a finite convex combination, samples dictionary-valued random variables, and uses their empirical average as an n-term expansion.The sampled average lies in Σn,1(D), while the type-2 estimate controls its distance from the finite approximation.
- Symmetrization with independent copies and Rademacher signs reduces the sampling estimate to the type-2 inequality.The proof uses exchangeability of independent copies, Jensen’s inequality, and the type-2 property.
3 Smoothly parameterized dictionaries
This section develops approximation, entropy, and width bounds for dictionaries smoothly parameterized by compact manifolds, with applications to shallow-network ridge-function dictionaries. The resulting rates depend on parameterization smoothness and are shown to be sharp in key cases.
- 3 Smoothly parameterized dictionaries: Smooth parameterization of order s yields upper bounds for sparse approximation, metric entropy, and n-widths of the convex hull B1(D).The bounds apply when the parameter domain is a compact d-dimensional smooth manifold and the ambient space has type 2.
- 3.1 Smoothness of ridge-function parameterizations: For ridge-function dictionaries, the parameter domain is represented using the compact manifold S^(d−1) × [c1,c2], enabling the general smooth-parameterization results to apply.The section establishes smoothness properties for the corresponding parameterization and treats the resulting shallow-network dictionaries.
- 3.3 Metric entropy bounds for smoothly parameterized dictionaries: The metric-entropy result removes a logarithmic factor from the preceding bound and yields a corresponding rate for variation spaces of shallow ReLU^k networks.The ReLU^k rate is stated to be sharp up to a constant factor in Section 4.
- 3.5 Gelfand numbers of smoothly parameterized dictionaries: Gelfand widths cannot generally be bounded through the stated width relation when the evaluation operator is non-injective.A finite dictionary example gives c1(T_D) < d1(B1(D)), leaving direct bounds for d_n(B1(D)) open in that setting.
4 Lower Bounds for Dictionaries of Ridge Functions
The section develops lower bounds for convex subsets containing suitable ridge-function classes by constructing nearly orthogonal elements and analyzing their convex hulls. Applied to neural-network variation spaces, this yields improved or sharp lower bounds for entropy, approximation rates, and n-widths.
- General lower-bound method: The resulting framework applies to ridge-function dictionaries and variation spaces for shallow neural networks.The section explicitly targets entropy and n-width lower bounds for these spaces.
- General lower-bound method: Nearly orthogonal vectors in a symmetric convex set generate lower bounds for metric entropy and Kolmogorov and Bernstein n-widths through their convex hull.The approach improves earlier entropy bounds by constructing larger collections of nearly orthogonal vectors.
- Applications to neural networks: The analysis settles a conjectured improvement for ReLU^k variation spaces for all k ≥ 0 and d ≥ 2, removing a logarithm from an earlier lower bound.It also derives improved Kolmogorov n-width and Bernstein-width bounds.
- Width bounds: For the Kolmogorov width, the optimal n-dimensional subspace is spanned by eigenfunctions associated with the n largest eigenvalues, with equality when λ_n > λ_{n+1}.Under this eigenvalue gap, invariance makes the relevant average and maximum coincide.
- Applications to neural networks: The approximation-rate exponent cannot improve beyond −1/(2d) for shallow ReLU^k networks, even when outer coefficients are bounded in ℓ∞.The same optimality conclusion extends to general bounded-variation sigmoidal activations under the stated setting.
- Applications to neural networks: Bounded-variation sigmoidal activations satisfy the lower-bound framework, extending earlier results without requiring Lipschitz continuity or polynomial convergence to the Heaviside function.The result also applies to more general activations such as B-splines, although details are omitted.
5 Conclusion
The paper develops upper and lower bounds for approximation rates, metric entropy, and n-widths of shallow-neural-network variation spaces, yielding sharp ReLU^k rates and optimality results on corresponding variation spaces. It also identifies unresolved entropy and n-width questions outside L2, dimension-dependent constants, and extensions to deeper networks.
- Contributions: The proposed dictionary framework yields approximation, metric-entropy, and n-width bounds for shallow neural-network variation spaces, including sharp ReLU^k approximation rates.The results improve several existing rates and establish optimality on the corresponding variation spaces.
- Open questions: The paper leaves entropy and n-width bounds for B1(D), particularly B1(Pd_k), in Lp for p ≠ 2 unresolved.The authors state that complete solutions may require significant new ideas.
- Scope limitations: The analysis primarily targets fixed dimension and does not precisely determine the implied constants, limiting its immediate interest to fixed moderate dimensions.Tighter constants are identified as important for quantifying the curse of dimensionality.
- Open questions: The authors propose extending the theory from shallow to deeper neural networks.