Source-linked AI summary
Minimax rates for learning spectral Barron functions by deep ReLU neural networks
Songqiu Ma, Yunfei Yang
TL;DR
Prior minimax results for smooth function classes suffer from the curse of dimensionality, leaving rates for spectral Barron functions of interest. The paper develops approximation bounds for deep ReLU networks and uses them to study learning these functions. It reports that the learning rate is minimax optimal up to logarithmic factors.
Problem
Prior minimax results for smooth function classes suffer from the curse of dimensionality, limiting their relevance to high-dimensional data.
Source: §1 · p. 2Method
Results
The learning rate for spectral Barron functions is minimax optimal up to logarithmic factors.
Source: §1 · p. 3Takeaways & Limitations
The paper provides a characterization of minimax rates for learning spectral Barron classes.
Source: §1 · p. 3Whether the super-approximation rate also holds for spectral Barron functions remains an open question for future study.
Source: §2 · p. 6
Abstract
from arXiv · showhide
We study how well deep neural networks approximate and learn spectral Barron functions. Recent studies have shown that these function classes can be efficiently approximated by shallow neural networks without suffering from the curse of dimensionality. We complement these results by providing new approximation bounds for deep networks with ReLU activation and establishing the minimax rates for learning these function classes. Specifically, we show that $d$-dimensional spectral Barron functions with smoothness index $s>0$ can be approximated by deep ReLU neural networks with approximation rate $\widetilde{\mathcal{O}} (S^{-\frac{1}{2}-\frac{s}{d}})$, where $S$ denotes the number of nonzero parameters in the network. Using this approximation result, we further show that deep ReLU neural networks can learn spectral Barron functions in a fast rate $n^{-\frac{d+2s}{2d+2s}}$ with $n$ training samples. Finally, we prove that this convergence rate is minimax optimal up to logarithmic factors.
1 Introduction
The introduction situates spectral Barron functions among approaches to reducing dimensionality challenges in approximation and learning, and identifies open questions about deep ReLU networks. It presents approximation bounds and minimax learning rates as the paper’s contributions.
1 Introduction
- Existing approximation and learning results for classical smooth function classes suffer from the curse of dimensionality, motivating structural assumptions on the data or target function.Examples include low-dimensional data, compositional targets, and anisotropic or mixed smoothness.Source: §1 · p. 2
- Barron spaces arise from variation spaces whose dictionaries are parameterized by neural-network activation functions.The introduction places spectral Barron functions within this broader family of function spaces.Source: §1 · p. 2
- Prior work established shallow-network approximation results for spectral Barron spaces, while deep ReLU results covered only a limited smoothness regime, leaving improved approximation rates and minimax learning rates open.The cited deep ReLU bound applies when 0 < sL ≤ 1/2.Source: §1 · p. 3
- The paper gives deep ReLU approximation rate O(S^(-1/2-s/d)(log S)^(3/2+s/d)) for spectral Barron functions, with S nonzero parameters.It also proves lower bounds implying optimality up to logarithmic factors in certain cases.Source: §1 · p. 3
- Deep ReLU networks achieve learning rate n^(-(d+2s)/(2d+2s)) with n training samples, and the paper proves this rate minimax optimal up to logarithmic factors.The analysis combines the approximation bound with statistical learning theory.Source: §1 · p. 3
2 Main results
The section studies nonparametric regression when the regression function lies in the unit ball of a spectral Barron space. It gives deep-ReLU approximation bounds and learning rates, with lower bounds establishing optimality in stated settings.
2 Main results
- The analysis assumes f0 lies in the unit ball of the spectral Barron space; its estimator is least squares over a sparse, bounded-parameter ReLU network class.The network class is parameterized by width, depth, number of nonzero parameters, and a bound on parameter magnitudes.Source: §2 · pp. 4–5
- With S nonzero parameters, deep ReLU networks achieve an approximation rate O(S^(-1/2-s/d)(log S)^(3/2+s/d)) for spectral Barron functions.The cited construction uses width and depth with L ≲ (log S)^2, network size WL ≍ S, and bounded weights.Source: §2 · p. 5
- For constructed networks with depth L ≲ (log S)^2 and bounded weights, a lower bound makes the approximation rate optimal up to logarithmic factors.A separate width-bounded lower bound leaves open whether very deep networks can improve the rate through super approximation.Source: §2 · p. 6
- For spectral Barron functions with smoothness s>0, deep ReLU least squares achieves a learning rate n^(-(d+2s)/(2d+2s)) up to logarithmic factors.The rate is reported to be faster than n^-1/2 for every s and to approach n^-1 as s increases.Source: §2 · p. 7
- The learning rate is minimax optimal up to logarithmic factors when the covariates are uniform on Ω and the noise is Gaussian with positive variance.The lower-bound result is stated for any s>0.Source: §2 · p. 7
3 Approximation error
The section constructs deep ReLU approximators for spectral Barron functions and establishes approximation lower bounds for two network settings. Its upper-bound construction truncates frequencies and approximates trigonometric components with ReLU subnetworks.
3.1 Upper bounds
- The upper-bound construction approximates a frequency-truncated spectral representation by combining linear phase subnetworks with ReLU approximations to cosine and sine.The cosine approximation uses fixed width and depth that grows with the requested accuracy; the sine subnetwork has the same asymptotic complexity.Source: §3.1 · pp. 8–10
- The upper-bound proof reduces approximation of the target to finite trigonometric sums, then controls the error from approximating their components with ReLU networks.The construction represents real-valued targets using cosine and sine terms and truncates frequencies at a chosen cutoff.Source: §3.1 · pp. 8–10
3.2 Lower bounds
- The section establishes approximation lower bounds using metric-entropy arguments for networks with sparsity and weight constraints and for networks with bounded width and depth.For the constrained setting, the proof compares packing numbers of the spectral Barron class and the network class.Source: §3.2 · pp. 11, 13, 14, 16
- The lower-bound argument constructs many well-separated functions in the spectral Barron class, making their packing complexity the basis for ruling out arbitrarily small network approximation error.The constructed dictionary uses cosine functions that are orthogonal in L2(Ω).Source: §3.2 · pp. 12–13
4 Generalization error
The section analyzes least-squares learning with deep ReLU networks and establishes a minimax lower bound for spectral Barron functions. It bounds estimation error through local complexity and shows the derived convergence rate is optimal up to logarithmic factors.
4.1 Convergence rates
- The least-squares analysis controls estimation error using local complexity, alongside an approximation term supplied by the network approximation result.The proof uses a local-complexity bound for the network class and an error decomposition for excess risk.Source: §4.1 · pp. 16, 18
- The analysis handles potentially unbounded noise by truncating it at a threshold and conditioning on the event that all observed noise values stay below that threshold.The threshold is chosen so this event has probability at least 1 − exp(−ρ).Source: §4.1 · p. 20
4.2 Optimality
- The convergence rate derived for the least-squares estimator is minimax optimal up to logarithmic factors under the stated learning setting.The lower bound is established for estimating spectral Barron functions under the L2(Ω) norm.Source: §4.2 · pp. 21–22
- The minimax lower-bound proof frames estimation as testing among separated functions and uses information-theoretic bounds to control testing error.The testing family consists of functions separated in L2(Ω).Source: §4.2 · p. 21