Source-linked AI summary
Approximation by Combinations of ReLU and Squared ReLU Ridge Functions with $ \ell^1 $ and $ \ell^0 $ Controls
Jason M. Klusowski, Andrew R. Barron
TL;DR
The paper asks how accurately many-variable functions can be approximated under ℓ^1 and ℓ^0 sparsity controls. It develops ReLU and squared ReLU ridge-function constructions using a Jones-Barron probabilistic method, obtaining L∞ and L2 bounds and companion lower bounds. In particular, squared ReLU achieves L2 error inversely proportional to inner ℓ^0 sparsity while requiring only sublinear outer ℓ^0 sparsity.
Problem
The paper investigates which functions remain approximable and how accurately under sparsity constraints on ridge-model parameters.
Method
The paper uses ReLU and squared ReLU ridge combinations with bounded parameter norms and a Jones-Barron probabilistic construction interpretable as stratified sampling or two-stage cluster sampling.
Results
Squared ReLU yields L2 approximation error inversely proportional to inner-layer ℓ^0 sparsity and requiring only sublinear outer-layer ℓ^0 sparsity.
Takeaways & Limitations
ReLU and squared ReLU ridge combinations retain desirable approximation behavior under ℓ^1 and ℓ^0 controls, including in high-dimensional settings.
Takeaways & Limitations
The positive results use absolutely continuous Fourier measures in the stated theorems, whereas Fourier measures generally need not be absolutely continuous.
Abstract
from arXiv · showhide
We establish $ L^{\infty} $ and $ L^2 $ error bounds for functions of many variables that are approximated by linear combinations of ReLU (rectified linear unit) and squared ReLU ridge functions with $ \ell^1 $ and $ \ell^0 $ controls on their inner and outer parameters. With the squared ReLU ridge function, we show that the $ L^2 $ approximation error is inversely proportional to the inner layer $ \ell^0 $ sparsity and it need only be sublinear in the outer layer $ \ell^0 $ sparsity. Our constructions are obtained using a variant of the Jones-Barron probabilistic method, which can be interpreted as either stratified sampling with proportionate allocation or two-stage cluster sampling. We also provide companion error lower bounds that reveal near optimality of our constructions. Despite the sparsity assumptions, we showcase the richness and flexibility of these ridge combinations by defining a large family of functions, in terms of certain spectral conditions, that are particularly well approximated by them.
1 Introduction
The paper studies how sparsity constraints affect approximation by ridge-function combinations and identifies conditions yielding accurate approximation with ReLU and squared ReLU activations. It develops probabilistic constructions under inner-parameter controls, establishes accompanying lower bounds, and addresses high-dimensional estimation settings.
- Statistical setting: In high-dimensional statistical settings, penalized estimators can achieve L2 prediction rates of order ((log d)/n)^1/3 for Lipschitz activations and ((log d)/n)^2/5 for activations with Lipschitz derivatives.These results apply when inner parameters have bounded ℓ^0 and ℓ^1 norms and contrast with a previously stated (d/n)^1/2 rate.
- Research questions: The paper asks how sparsity assumptions limit model flexibility, which functions remain approximable, and how approximation error depends on those constraints.These questions concern bounded inner-parameter ℓ^0 and ℓ^1 controls and Lipschitz activations or Lipschitz derivatives.
- Prior approximation results: Classical results obtain m-term L∞ error rates of order c v_f,1 m^-1/2 for step or smooth approximating activations, but smoothness can require unbounded inner ℓ^1 norms.For nonnegative even integer p, related Lp rates are c(p)v_f,1 m^-1/2−1/(pd).
- Main contributions: ReLU and squared ReLU ridge combinations achieve desirable L∞ approximation bounds even with ∥a_k∥1 = 1, bounded thresholds, and equal-magnitude outer coefficients.The ReLU result improves a prior L∞ exponent from 1/2 to 1/2 + O(1/d).
- Main contributions: The tighter rates require finite v_f,2 for ReLU or finite v_f,3 for squared ReLU and use a probabilistic construction interpretable as stratified sampling with proportionate allocation.The method originates from the Jones-Barron approach and is also described through survey-sampling variance reduction.
- Main contributions: The paper supplies companion lower bounds to assess how much the approximation rates can be improved.These lower bounds are presented as complements to the positive approximation results.
2 L∞approximation with bounded ℓ1 norm
The section establishes L∞ approximation results for ReLU and squared ReLU ridge combinations under bounded inner ℓ1 norms, using a probabilistic stratified-sampling construction. Squared ReLU permits stronger rates under a higher-order spectral condition, while the results also identify near-optimality and Fourier-based scope boundaries.
- Positive results: ReLU and squared ReLU ridge combinations achieve L∞ approximation bounds with inner parameters normalized by ∥a_k∥1 = 1 and thresholds 0 ≤ t_k ≤ 1.The construction allows equal-magnitude outer coefficients, with general Lipschitz or Lipschitz-derivative activations covered in the theorem framework.
- Squared ReLU construction: The squared ReLU approximant includes fixed constant, linear, and quadratic terms, with b0 = f(0), a0 = ∇f(0), and A0 = ∇∇T f(0).The remaining approximation is represented through squared ReLU ridge functions with bounded outer coefficients and normalized inner parameters.
- Proof strategy: The construction partitions the parameter space into strata and allocates within-stratum samples proportionally, reducing within-stratum variability before applying empirical-process bounds.The proof combines this allocation scheme with Rademacher arguments and Dudley’s entropy integral.
- Approximation rates: For equally weighted approximants, the construction uses M ≍ ε^-d strata and selects ε of order m^-1/(d+2), while non-equally weighted approximants use ε of order m^-1/d.The resulting bounds are realized by m-term combinations, and the theorem-level minimax statements attain the stated rates.
- Optimality and scope: The results are nearly optimal relative to lower bounds for related ridge approximants, while the Fourier assumptions are not uniformly comparable to alternative bounded-parameter conditions.The paper also notes that its absolutely continuous Fourier-measure setup excludes general discrete Fourier measures such as lattice-supported representations.
3 L2 approximation with bounded ℓ0 and ℓ1 norm
The section develops L2 approximation under simultaneous ℓ0 and ℓ1 controls, using a two-stage Jones–Barron probabilistic construction. For squared ReLU ridge functions, the resulting error decreases inversely with inner-layer sparsity and only sublinearly with outer-layer sparsity.
- Construction: The proof applies the Jones–Barron probabilistic method in two stages: first to outer coefficients, then to inner coefficients.This construction is analogous to two-stage cluster sampling.
- Assumptions: Theorem 5 assumes an integral representation of f over parameters with unit ℓ1-norm inner vectors and signs η(t, a) ∈ {−1, +1}.The representation covers s ∈ {2, 3} on D = [−1, 1]^d.
- Scope: The same rates extend to general f after subtracting a linear or quadratic term, provided v = 2v_f,2 < +∞ for s = 2 or v = v_f,3 < +∞ for s = 3.The adjustment is tied to the corresponding finite variation condition.
- Rates: For squared ReLU ridge functions, the L2(D) error is inversely proportional to inner-layer sparsity and only sublinear in outer-layer sparsity.The result is summarized as an error bound of the form 2v m^−1/2 in the outer-layer term.
- Sparsity control: The sampled inner parameter construction has ℓ0 norm at most m0 while retaining unit ℓ1 norm.This follows because the sum of the sampled vectors uses at most m0 coordinate directions and has unit ℓ1 norm.