PaperlayerView exact revision on arXiv

Source-linked AI summary

Sharp approximation rates for shallow ReLU neuralnetworks on critical Besov classes

Yupeng Wang

arXiv:2609.06418v1math.NAcs.NA

TL;DR

The paper asks for sharp finite-width approximation rates under a width-independent coefficient budget, beyond what a uniform variation bound alone establishes. It combines angular and direction–bias lower bounds with a stable upper estimate, obtaining matching algebraic rates across three regimes, with specified logarithmic losses.

  • Problem

    A uniform variation bound does not determine sharp finite-width error, the transition between direction and direction–bias regimes, or matching lower bounds under the same coefficient budget.

    Source: §1 · p. 2

  • Method

    The analysis combines critical Besov sparsity and stable finite-width estimates with radial angular and direction–bias packing lower bounds.

    Source: §1 · p. 4

  • Results

    The paper establishes matching upper and lower algebraic rates in three parameter regimes, with logarithmic factors at the transition and in the direction–bias regime.

    Source: §1 · p. 4, Conclusion · p. 40

  • Takeaways & Limitations

    On the critical Besov ball, the best shallow-network approximation has a strictly larger algebraic exponent than fixed-degree finite elements under a fixed-dimensional parameter-count comparison.

    Source: §1 · p. 2

    The estimates concern normalized directions, biases in a fixed compact interval, and an outer ℓ1 coefficient budget independent of width.

    Source: §1 · p. 1

Abstract

from arXiv · show

Let $\mathbb D$ be the normalized ridge dictionary generated by $\operatorname{ReLU}^k$ on a bounded Lipschitz domain $\Omega\subset\mathbb R^d$. We determine the sharp algebraic rate of finite $n$-term approximation from $\mathbb D$ when the outer $\ell^1$ coefficient budget is independent of $n$. More precisely, let $d\ge3$, $k\in\mathbb N_+$, $0\le m\le k$, $0<p<1$, and $0<q\le1$. For the unit ball of the critical Besov space $B_{p,q}^{k+d/p}(\Omega)$, measured in $H^m(\Omega)$, the optimal algebraic exponent is \[ \min\left\{\frac{k-m+d/2}{d-1}, \frac{k-m+d/2+1/p-1/2}{d}\right\}. \] We prove two-sided estimates in the three regimes determined by the two branches of this minimum and give the corresponding logarithmic factors at and beyond the transition. The estimates coincide without logarithmic loss in the strict angular regime and at the transition when $q\le[1/2+(k-m+d/2)/(d-1)]^{-1}$. The upper estimate combines critical wavelet sparsity, localized Fourier--Radon representations, and a stable allocation of directions and biases. The lower estimates arise from two distinct obstructions, namely radial ridge approximation on the direction sphere and Gevrey localization in the joint direction--bias space. The critical smoothness is exactly the endpoint at which Besov regularity provides a uniform shallow-network variation bound without additional scale decay. The resulting representation exponent is strictly larger than the degree-limited exponent for fixed-degree isotropic finite elements under a parameter-count comparison. This last statement concerns best approximation, not training or computational complexity.

1. Introduction and main result

This section establishes sharp finite-width, best n-term approximation rates for the critical Besov ball using normalized shallow ReLU^k networks with a width-independent outer ℓ1 budget. It frames the rates as an approximation benchmark, highlighting angular and direction–bias lower-bound obstructions and the role of p < 1 Besov sparsity, rather than greedy-training convergence.

1. Introduction and main result

  • The problem fixes normalized directions, biases in a compact interval, and an outer ℓ1 coefficient budget independent of width for targets in the critical Besov class.The fixed budget connects finite networks to the measure-valued variation space and prevents rates from relying on coefficient mass that grows with width.Source: §1 · pp. 1, 4
  • Matching lower bounds arise from a radial angular obstruction on the direction sphere and a Gevrey-packet direction–bias packing obstruction.The upper estimate combines critical wavelet sparsity, localized Fourier–Radon representations, and stable allocation of directions and biases.Source: §1 · p. 4
  • At the critical smoothness s = k + d/p, Besov regularity gives uniform variation control, while the endpoint balance of sparsity and scale allocation produces the transition and logarithmic terms.The paper establishes sharp algebraic rates on the critical line and makes no optimality claim away from it.Source: §1 · pp. 4–5

1.1. Notation and statement of the main result.

  • For p ≤ p*, the angular exponent Am is sharp; for p > p*, the hard family uses both directions and biases, and the exponent changes to Gp,m.At p = p*, the bounds match exactly when q ≤ (Am + 1/2)^−1.Source: §1.1 · p. 6
  • Up to logarithmic factors, the network exponent exceeds the fixed-degree finite-element benchmark N^-k/d in the H1 energy norm.This compares best representation errors under fixed-dimensional parameter counts, not training or computational complexity; it excludes optimization and solver costs and does not cover anisotropic or hp-adaptive elements.Source: §1 · p. 3, §1.1 · pp. 6–7
  • The theorem determines best n-term error over a Besov source ball, providing a benchmark but not a convergence theorem for greedy training.Source: §1.1 · p. 7
  • For the specialized source class, Liu, Mao, and Xu’s rate n^(-τ_m/d) uses a coefficient budget growing as n^(1/(2d)), while this theorem has Γ_p,m > τ_m/d with budget independent of n [34].The comparison isolates information from p < 1 Besov sparsity; the different source classes preclude a universal dominance claim.Source: §1.1 · p. 7
  • The finite-width theorem combines an n-independent coefficient-budget upper construction, radial angular and localized Gevrey-packet lower obstructions, and fixed-atom realization of degree-at-most-k polynomials.The polynomial realization makes augmented and non-augmented formulations share the same algebraic upper rate.Source: §1.1 · p. 8

2. Lemmas for the upper bound

This section develops shared tools for upper bounds, connecting critical Besov regularity to variation control and stable finite-network approximation in the H^m error norm. It reduces Besov functions to localized atoms with controlled representation costs and establishes supporting results on polynomial corrections, ridge smoothness, discretization, and width scaling.

2. Lemmas for the upper bound

  • L2 and Hm variation representations have the same functions, representing measures, and variation norms, and bounded variation balls are closed in Hm.The parameter-to-ridge map is continuous and uniformly bounded; weak-star compactness of bounded measure sets yields compact images in Hm.Source: §2 · p. 8

2.1. Scaling and wavelet reduction.

  • A fixed finite family of dictionary ridges spans Πk, with a bounded coefficient cost for realizing polynomial corrections.Distinct always-active ridges yield ridge monomials by an invertible Vandermonde system; finitely many directions span each homogeneous polynomial space.Source: §2.1 · pp. 9–10
  • At critical smoothness, rescaled smooth bumps have uniformly bounded Besov norms and Hm size comparable to h^(k-m+d/2).The Besov bound holds for 0 < p < 1 and 0 < q ≤ 1; the Hm scaling includes a matching lower bound.Source: §2.1 · pp. 10–11
  • Compactly supported critical wavelet expansions reduce the upper-bound problem to localized templates, while the critical Besov–variation embedding controls their total representation cost [1].The templates come from a fixed finite family, and the localized-atom variation estimate is uniform in scale.Source: §2.1 · pp. 12–14
  • The measure-defined L2 representation agrees with the H^m representation without increasing measure mass; this embedding alone does not supply discretization.Source: §2.1 · p. 14
  • Stratified high-order cubature partitions charts into O(K) cells, integrates local polynomial interpolants exactly, and adds independent unbiased residual samples.The construction gives cell-level weights bounded by a constant times cell volume.Source: §2.1 · p. 15
  • The map T is C^{q0,1/2} with values in H^m(Ω), uniformly on finitely many charts; the same estimate covers q0 = 0, and local interpolation uses O(N) nodes.Source: §2.1 · p. 16
  • The variation ball admits n-term approximants with total coefficient mass bounded by C||f||L1(D), independently of network width.The theorem applies the existing approximation result after establishing parameter regularity in H^m and identifying the measure-defined and closed atomic balls.Source: §2.1 · p. 16
  • The p=1 variation baseline follows from the critical Besov embedding, which controls ||f||L1(D) by the Besov norm.This supplies the variation-space bound used to apply stable approximation to Besov functions.Source: §2.1 · p. 16

3. Proof of the upper bound

This section develops the upper-bound proof through localized, scale-wise approximation and resource allocation across ridge parameters and scales. It combines angular and bias discretization with sequence-level allocation to treat three parameter regimes under an output coefficient budget independent of n, including an extension to larger p via disjoint-coordinate splitting.

3.1. Localized atoms and resource allocation.

  • Balancing angular cells and bias samples yields a localized atom approximant with angular width factor h^(-(d-1)) and pathwise coefficient budget O(h^-k).The angular and bias errors are combined by choosing KL ≃ h^(-(d-1))z; the atom oracle is unbiased and has width O(KL).Source: §3.1 · p. 21
  • Sequence resource allocation combines independent localized atom approximants into a stable one-scale network while retaining the omitted-coordinate energy.The omitted-coordinate term is controlled using a same-scale Bessel estimate, while the active coordinates use independent atom oracles.Source: §3.1 · pp. 22–23
  • For p above the endpoint, disjoint-coordinate splitting separates each scale’s coefficients while preserving the exact sum of their ℓ1 masses.This supports combining an approximation of the p=1 component with the endpoint construction while keeping the combined budget O(B), uniformly in t and n.Source: §3.1 · pp. 23–24, §3.2 · p. 26
  • The scale-wise estimates are uniform in scale and wavelet position, but their summation changes at the threshold p*, yielding the three-regime upper bound.For p < p*, the coarse-scale error is bounded by CBn^-Am and the saturated rate has no logarithmic loss.Source: §3.2 · pp. 24, 26

3.2. The three parameter regimes.

  • The construction keeps the output coefficient budget bounded independently of n; for p < p*, it gives the saturated error rate n^-Am without logarithmic loss, while p > p* has rate n^-Gp,m with a logarithmic factor.The theorem establishes the bounds across three parameter regimes; the stated regimes identify the low-p and high-p cases.Source: §3.2 · pp. 24, 26

4. Lemmas for the lower bounds

This section develops complementary lower-bound tools, including radial and Gevrey-based tests and a packet-transform method for counting cells influenced by a width- n network. It examines how spherical averaging and radial targets interact with these tests.

4. Lemmas for the lower bounds

  • The radial-ridge obstruction uses only the direction sphere and applies without a coefficient budget; the direction–bias obstruction becomes sharp when p > p*.The two components are independent, and the second is weaker in the angularly saturated range.Source: §4 · p. 26
  • For nonzero radial φ∈S(R^d) with B(x0,4R) ⋐ Ω, the scaled scalar radial-ridge obstruction applies to at most N arbitrary biased ridge profiles when 0<h<h0 and N≤c1h^{-(d−1)}; constants are independent of a.Source: §4 · pp. 27–28
  • Spherical averaging yields a difference controlled by one derivative while preserving each ridge direction and therefore does not increase ridge count.Applied to a rescaled radial potential, this difference produces a nonzero radial profile at the same scale.Source: §4 · pp. 28–29

4.1. Gevrey localization in direction and bias.

  • Compactly supported Gevrey cutoffs provide subexponential Fourier decay for a band-pass ridgelet test whose response to one atom localizes near its direction and bias.The transform is bounded by the H^m error, and avoiding an extra factorial in Fourier-moment order is essential for absorbing packet-proof frequency powers.Source: §4.1 · pp. 29–31
  • A radial critical bump has an exact, nonzero packet response under the localized transform, with its sphere-integrated size characterized by an equivalence.Radial symmetry makes the response amplitude and width computable exactly.Source: §4.1 · pp. 33–34
  • Critical bumps along an interior cylinder are paired with packet cells for each bump and angular direction, and a width-n network can influence only a controlled number of cells.This cell-counting construction forms a direction–bias hard family.Source: §4.1 · p. 34

5. Proof of the lower bounds and completion of the main theorem

The lower-bound proof separates an angular obstruction from a fixed-budget direction–bias obstruction, then combines both with the upper theorem to identify the approximation regimes. The conclusion states where the bounds match without logarithmic loss and where gaps remain open.

5.1. The angular lower bound.

  • The angular obstruction gives a uniform lower bound of n^-Am, independent of the coefficient budget.The proof handles even Sobolev orders with scalar radial profiles and odd orders with radial gradients.Source: §5.1 · p. 35

5.2. Direction–bias cell counting.

  • The direction–bias lower bound uses target energy on parameter-space cells and the fixed coefficient budget to control neuron tails.Unlike the angular bound, this construction relies on bounded mass to make the sum of far-neuron tails small.Source: §5.2 · p. 37
  • For the one-scale bump–cell construction, γ(0)=τ_m d−1=A_m and γ(1)=τ_m+1/p−1/2; the row construction restricts α to at most 1 for disjoint bias cells in every angular direction.A bounded bias interval contains only O(h−1) disjoint h-cells. This calculation is not an optimality statement for arbitrary multiscale hard families.Source: §5.2 · p. 39

5.3. Completion of the proof of the main theorem.

  • Combining the upper estimate with both lower branches identifies three regimes, including their stated logarithmic factors.The algebraic rate is n^-Am for p < p*, and n^-Gp,m for p > p*; the transition case is treated separately.Source: §5.3 · p. 40

Conclusion

  • The estimates match without logarithmic loss for p < p* and at p = p* when q ≤ (Am + 1/2)^-1; other logarithmic gaps remain open.Above critical smoothness the upper bounds persist by embedding but need not be optimal; below it, fixed-budget representability is a different question from approximation with an increasing budget.Source: Conclusion · p. 40
Loading 2609.06418v1…