ML Mathematics: Information-Theoretic Limits

Job: establish the minimax-optimal rates for nonparametric regression with neural-network classes — the classical \(n^{-2s/(2s+d)}\) curse-of-dimensionality rate for \(C^s\) (Stone) vs the dimension-free \(n^{-1/2}\) rate for Barron-space functions (matching the approximation rate) — state the information-theoretic lower bounds (Fano / Le Cam) and the no-free-lunch theorem (no estimator beats the curse without structural assumptions), and survey the analogy with sparse recovery and the open beyond-NTK gap.

Core

Minimax rates for nonparametric regression

The nonparametric regression model: \(y_i=f(x_i)+\varepsilon_i\), \(i=1,\dots,n\), with \(x_i\in[0,1]^d\), \(\varepsilon_i\) i.i.d. \(\mathcal{N}(0,\sigma^2)\), and \(f\) in a function class \(\mathcal{F}\). The minimax risk is

\[ \mathcal{R}_n(\mathcal{F})=\inf_{\hat f}\sup_{f\in\mathcal{F}}\mathbb{E}_f\|\hat f-f\|_{L^2}^2, \]

the infimum over all estimators \(\hat f\) (NN or otherwise) of the worst-case mean-squared error.

Function class \(\mathcal{F}\) Minimax rate \(\mathcal{R}_n(\mathcal{F})\) Curse of dim.? Estimator achieving it
\(C^s([0,1]^d)\), \(s\) smooth \(\Theta(n^{-2s/(2s+d)})\) yes (exponent depends on \(d\)) kernel / splines / local polynomial; deep ReLU (Yarotsky)
\(W^{s,p}([0,1]^d)\) \(\Theta(n^{-2s/(2s+d)})\) yes kernel / splines
Barron \(\mathcal{B}\) (\(\|f\|_{\mathcal{B}}\le C\)) \(\Theta(n^{-1/2})\) no (dimension-free) shallow NN, empirical risk minimization (Barron)
Barron\(^s\) (tensor Barron) \(\Theta(n^{-2s/(2s+d)})\) partial (improved) tensor NN
Compositional / tree-structured \(\Theta(n^{-2s/(2s+\sum k_i)})\) beaten if local \(\sum k_i\) bounded deep NN matched to tree
\(k\)-sparse in a basis \(\Theta(n^{-2s/(2s+k)})\) no (depends on \(k\), not \(d\)) sparse estimator / LASSO
Lipschitz on \([0,1]^d\) (no structure) \(\Theta(n^{-1/(d+2)})\) yes (worst) kernel; no NN beats this

Theorem (Stone 1980, classical minimax). For \(\mathcal{F}=C^s([0,1]^d)\) (Hölder / Sobolev smoothness \(s\)), the minimax rate is \(\mathcal{R}_n(\mathcal{F})=\Theta(n^{-2s/(2s+d)})\), achieved by local polynomial / kernel estimators and by deep ReLU nets (Yarotsky) of appropriate width / depth. The exponent \(2s/(2s+d)\) deteriorates with \(d\) — the curse of dimensionality: for fixed \(s\) and \(d\to\infty\), the rate tends to \(n^0=1\) (no learning).

Theorem (Barron 1993 + minimax). For the Barron class \(\mathcal{B}_C=\{f:\|f\|_{\mathcal{B}}\le C\}\), the minimax rate is \(\Theta(n^{-1/2})\) — dimension-free, matching the \(O(1/\sqrt{m})\) approximation rate (see Approximation Theory). The upper bound is achieved by empirical risk minimization over a Barron-norm-bounded NN class with \(m\sim n\) neurons; the lower bound (below) shows the rate is optimal.

The gap between the \(C^s\) curse (\(n^{-2s/(2s+d)}\)) and the Barron dimension-free (\(n^{-1/2}\)) is the "beating the curse of dimensionality" phenomenon: it is not a property of NNs per se but of the structural assumption \(\|f\|_{\mathcal{B}}<\infty\). The NN is the right estimator for the Barron class because its approximation rate matches; for \(C^s\) it gives the same curse rate as classical methods.

Information-theoretic lower bounds: Fano / Le Cam

Theorem (Fano's inequality, minimax form). If \(\mathcal{F}\) contains a finite subset \(\{f_1,\dots,f_M\}\) with \(\|f_i-f_j\|_{L^2}\ge 2\delta\) for \(i\ne j\) (a \(\delta\)-packing) and the Kullback–Leibler divergences satisfy \(\mathrm{KL}(P_i\|P_j)\le \alpha n\) (the distributions of the \(n\) samples under \(f_i\) vs \(f_j\)), then $$ \mathcal{R}_n(\mathcal{F})\ge\delta^2\left(1-\frac{\alpha n+\log 2}{\log M}\right). $$ Choosing \(M\approx e^{cn}\) and \(\delta\approx n^{-1/2}\) for the Barron class (constructing a \(2\delta\)-packing of size \(e^{cn}\) in \(\mathcal{B}_C\)) gives \(\mathcal{R}_n(\mathcal{B}_C)\ge c'/n\)... adjusted to \(\Omega(n^{-1/2})\) in the \(L^2\)-squared norm: \(\mathcal{R}_n\ge c\,n^{-1/2}\) (the packing / Fano constants yield the dimension-free lower bound).

Theorem (Le Cam's two-point method). For a pair \(f_0,f_1\in\mathcal{F}\) with \(\|f_0-f_1\|_{L^2}\ge 2\delta\) and the total-variation distance \(\mathrm{TV}(P_0^{\otimes n},P_1^{\otimes n})\le\alpha<1\), the minimax risk is \(\mathcal{R}_n(\mathcal{F})\ge\delta^2(1-\alpha)\). For the Lipschitz class, choosing \(f_0=0\), \(f_1=\delta\varphi(x/\eta)\) a bump of width \(\eta\sim n^{-1/(d+2)}\) gives the curse rate \(\mathcal{R}_n\ge c\,n^{-1/(d+2)}\).

No-free-lunch and the necessity of structure

Theorem (no-free-lunch / curse for Lipschitz). For the class of all 1-Lipschitz functions on \([0,1]^d\), the minimax rate is \(\mathcal{R}_n=\Theta(n^{-1/(d+2)})\) (curse — exponent \(1/(d+2)\to 0\) as \(d\to\infty\)), and no estimator (NN, kernel, or otherwise) can beat this rate uniformly over the class. The NN approximation advantage is entirely from the inductive bias matching the target structure: for Barron-bounded targets, NNs achieve the dimension-free rate; for arbitrary Lipschitz targets (no structure), they are no better than kernels.

The implication: the deep-learning advantage is the inductive bias, not the architecture alone. Without a structural assumption on the target class (Barron norm, composition, smoothness matched to depth), the curse of dimensionality is inescapable — any estimator, including a deep NN, is minimax-optimal at the curse rate and cannot improve. The NN is the right tool when the target class is matched to the architecture (Barron / compositional / smooth); otherwise it is no better than classical methods.

Analogy with sparse recovery and high-dimensional statistics

The Barron norm plays the role of sparsity in the approximation / estimation theory of NNs. The analogy:

Sparse recovery NN / Barron estimation
\(k\)-sparse signal in \(\mathbb{R}^d\) Barron-bounded \(f\) on \([0,1]^d\)
Rate \(n^{-2s/(2s+k)}\) (depends on \(k\), not \(d\)) Rate \(n^{-1/2}\) (dimension-free)
Compressed sensing (LASSO) Empirical risk minimization over Barron-bounded NN class
Sparsity assumption enables beating the curse Barron norm assumption enables beating the curse
Without sparsity: \(n^{-1/d}\) curse Without structure: \(n^{-1/(d+2)}\) curse

The parallel: the "effective dimension" in sparse recovery is \(k\) (the sparsity), and in Barron estimation it is \(O(1)\) (the Barron norm being bounded makes the function live in a low-complexity subspace, regardless of \(d\)). The dimension-free rate is the analog of the sparse rate — both are consequences of a structural complexity hypothesis, not of the ambient dimension.

The beyond-NTK gap

Open problem (beyond NTK). The NTK-regime (see NTK & Optimization) gives a dimension-free upper bound on the test error for the lazy regime — but the NTK regime is a fixed-kernel method, and its RKHS is a strict subset of the Barron class (the NTK RKHS depends on the initialization, not on the target). The minimax lower bound for the NTK RKHS class is typically worse than the Barron \(n^{-1/2}\) (the NTK RKHS has a different, kernel-dependent metric entropy), so the NTK regime does not achieve the Barron optimal rate in general — the feature-learning regime is conjectured to achieve it (by adapting the features to the target), but the rigorous optimality of feature-learning deep nets for the Barron class (matching the Fano lower bound) is open.

The gap: the NTK regime gives a rigorous dimension-free upper bound (lazy training converges to a kernel method with a dimension-free RKHS rate for some kernels), but the matching lower bound for the NTK class is at a different rate, and the feature-learning regime — which is conjectured to achieve the Barron-optimal \(n^{-1/2}\) — lacks a full rigorous convergence / minimax theorem in the general deep case. This is the "beyond-NTK" question: prove (or disprove) that feature-learning deep nets achieve the Barron minimax rate, beating the NTK regime.

See it

Barron-space minimax: the \(n^{-1/2}\) upper and lower bound. Upper bound: for the Barron class \(\mathcal{B}_C=\{f:\|f\|_{\mathcal{B}}\le C\}\), the empirical risk minimizer \(\hat f_n\) over a Barron-bounded shallow NN class with \(m=n\) neurons satisfies, by the Rademacher complexity of the Barron class \(\mathfrak{R}_n(\mathcal{B}_C)=O(C/\sqrt{n})\) (the Barron norm controls the Rademacher complexity dimension-free, by the same variation-norm argument as the approximation rate),

\[ \mathbb{E}\|\hat f_n-f\|_{L^2}^2\le O(\mathfrak{R}_n(\mathcal{B}_C)^2)=O(C^2/n)=O(n^{-1}), \]

matching (up to \(L^2\) vs \(L^2\)-squared) the dimension-free \(n^{-1/2}\) rate. Lower bound via Fano: construct a \(2\delta\)-packing \(\{f_1,\dots,f_M\}\) of \(\mathcal{B}_C\) with \(M=e^{cn}\) and \(\delta\sim n^{-1/2}\) (the packing is built from \(M\) random sign patterns of \(m\sim n\) Barron basis elements — \(\sigma(w_j\cdot x+b_j)\) with random \(w_j\) and Rademacher signs \(c_j\in\{\pm 1\}\), giving \(2^m\approx e^{cn}\) functions of Barron norm \(O(\sqrt m)\le C\) with \(L^2\) separation \(\Theta(\sqrt{m/n})=\Theta(n^{-1/2})\)). The KL divergence between the Gaussian regression distributions under \(f_i,f_j\) is \(\mathrm{KL}\le\|f_i-f_j\|_{L^2}^2/(2\sigma^2)\le O(1/n)\cdot n=O(1)\) per sample, so \(\mathrm{KL}(P_i^{\otimes n}\|P_j^{\otimes n})\le O(1)\ll\log M=cn\). Fano gives \(\mathcal{R}_n\ge\delta^2(1-O(1)/(cn))=\Omega(n^{-1/2})\). Hence the upper and lower bounds match: the Barron class has minimax rate \(\Theta(n^{-1/2})\), dimension-free, optimal for empirical risk minimization over Barron-bounded NNs. This is the prototypical "NN estimation is minimax-optimal for the Barron class" computation — the dimension-free rate is the joint content of the approximation (Barron) and the estimation (Rademacher + Fano).

Check

State the precise condition under which a deep NN beats the curse of dimensionality, and explain why 'the architecture is deep' alone is insufficient.

A deep NN beats the curse iff the target \(f\) lies in a function class whose complexity is dimension-free — i.e. \(f\in\mathcal{B}\) (Barron-bounded), or \(f\) is compositional / tree-structured with bounded local dimension \(\sum k_i\), or \(f\) is \(k\)-sparse in a suitable basis. The architecture being deep alone is not sufficient: for a generic Lipschitz target on \([0,1]^d\) (no structural assumption), the minimax rate is \(n^{-1/(d+2)}\) (curse), and no estimator — deep NN or otherwise — beats it; the deep NN achieves the same curse rate as kernels / splines in this case (Yarotsky's \(C^s\) rate recovers the curse for \(C^s\) targets). The structural assumption is what makes the dimension-free rate possible: the Barron norm bounds the variation of \(f\) (an intrinsic complexity), the compositional structure bounds the local input dimension (an intrinsic tree-complexity), etc. Without it, the curse is inescapable by the no-free-lunch theorem.

Identify the precise gap between the NTK-regime upper bound and the Barron minimax lower bound, and state the open question that 'beyond-NTK' refers to.

The NTK regime gives an upper bound on the test error of a lazy-trained net: the dynamics converges to kernel regression with the NTK \(K\), and the test error is the kernel-regression error at the NTK RKHS — a dimension-free rate for kernels with dimension-free RKHS complexity, but the rate depends on the NTK RKHS, not on the Barron class. The NTK RKHS is a strict subset of the Barron class (the NTK RKHS depends on the initialization distribution, and its metric entropy gives a different, typically worse, minimax rate than the Barron \(n^{-1/2}\)). The Barron lower bound (Fano, \(\Omega(n^{-1/2})\)) applies to the Barron class, which is larger than the NTK RKHS, so the NTK upper bound is not at the Barron minimax rate — the NTK regime is suboptimal for the Barron class. The open "beyond-NTK" question is: does the feature-learning regime (mean-field / Wasserstein GF, where the neuron directions move) achieve the Barron minimax rate \(n^{-1/2}\), beating the NTK regime? The conjecture is yes (feature-learning adapts features to the target, realizing the Barron approximation advantage), but a full rigorous convergence + minimax-optimality theorem for deep feature-learning nets matching the Barron lower bound is open in the general deep case.

Pitfalls

  • NNs do not beat the curse without structural assumptions: the no-free-lunch theorem for Lipschitz functions gives the curse rate \(n^{-1/(d+2)}\), and no estimator (NN included) beats it uniformly. The "deep learning beats the curse" claim is only true with a structural hypothesis (Barron / compositional / smooth).
  • The \(C^s\) minimax rate is the curse even for deep NNs: Yarotsky's deep ReLU approximation gives \(\varepsilon^{-d/s}\) for \(C^s\), recovering the curse rate — the deep NN is no better than kernels for generic \(C^s\) targets; the advantage requires the target to be in the Barron / compositional class.
  • The Barron \(n^{-1/2}\) needs the Barron-norm hypothesis: a generic \(C^s\) function is not Barron (the Barron class is a strict subspace); the dimension-free rate applies only to \(\|f\|_{\mathcal{B}}<\infty\).
  • The NTK regime does not achieve the Barron minimax rate: the NTK RKHS is a strict subset of the Barron class, and its minimax rate is typically worse; the feature-learning regime is conjectured to achieve the Barron rate but the theorem is open in the general deep case. Do not state "NTK regime is minimax-optimal for the Barron class."
  • Fano / Le Cam lower bounds need a packing: the \(n^{-1/2}\) lower bound requires a \(2\delta\)-packing of size \(e^{cn}\) in the Barron class; without the packing (which uses the Barron-norm-bounded structure) the bound degenerates. The packing is the geometric content of the lower bound.
  • The beyond-NTK gap is open, not a theorem: the conjecture that feature-learning deep nets are minimax-optimal for the Barron class is supported by partial results (2-layer nets, specific scalings) but is not a proven theorem in full generality; cite it as a research frontier, not as established.

Refs

  • Stone, Optimal rates of convergence for nonparametric estimators (Annals Stat. 1980)
  • Barron, Universal approximation bounds for superpositions of a sigmoidal function (IEEE TIT 1993); Barron–Bursek—Minimax analysis via Rademacher / Fano
  • Yang–Barron, Information-theoretic determination of minimax rates (Annals Stat. 1999) — metric entropy / Fano for general classes
  • Tsybakov, Introduction to Nonparametric Estimation (Fano / Le Cam lower bounds, minimax)
  • Wainwright, High-Dimensional Statistics: A Non-Asymptotic Viewpoint (Rademacher, metric entropy, NN bounds)

Next

Approximation Theory · NTK & Optimization · Generalization · ML Mathematics index · Information theory · Statistics · Probability · Optimization