CS Paper Radar

Error bounds in Sobolev norms for approximations with norm constrained ReLU neural networks

Xianjun Li, Yunfei Yang

cs.LG stat.ML ·submitted 2026-09-17 09:10 UTC · v1

Abstract

Recent studies have shown that smooth functions can be well approximated by ReLU neural networks with path norm constraint on the weights. We extend these results from uniform approximation to approximation in Sobolev norm. Specifically, we analyze how well Sobolev functions in $W^{n,p}$ can be approximated by neural networks with width $W$, depth $L$ and path norm bounded by $K$, when the approximation error is measured in the $W^{1,p}$-norm. For shallow networks with depth $L=1$, we derive the approximation error bound $\mathcal{O}(\max\{W^{-(n-1)/d}, K^{-(n-1)/(s-n)}\})$, when the smoothness index satisfies $n<s=(d+3)/2$ and the input is $d$-dimensional. For deep networks, we remove the restriction on the smoothness by showing that the approximation bound $\mathcal{O}(K^{-(n-1)/(d+d/p+1)})$ holds if the width $W$ and depth $L$ are sufficiently large.

Closest papers

Nearest neighbours by meaning across the whole index.

Approximation Property of Dropout Neural Networks: Sobolev Rates and Confidence Bounds

cs.LG math.NA ·2026-09-30 ·Jia-He Yao
theory similarity 0.76
Abstract · 30 pages, 1 figure

The universal approximation property of dropout neural networks does not by itself describe the network size required for an accurate random realization. In this work, we study approximation of the unit ball of $W^{n,\infty}([0,1]^d)$ by ReLU networks whose edges are retained independently with probability $p$. The approximation error is measured uniformly over the input domain, and the guarantee holds with probability at least $1-δ$ for a single sampled network. We construct networks of constant depth and size $\widetilde O_{n,d}(p^{-9}\varepsilon^{-\max\{d/n,2\}} \log(1/δ))$. The construction combines bounded local subnetworks, localization on a successful approximation event, and a multiscale Taylor decomposition. Conversely, Sobolev capacity imposes a lower bound on the number of surviving edges, while approximation of a fixed affine function requires an output-layer cost of order $((1-p)/p)\varepsilon^{-2}\log(1/δ)$ at sufficiently high confidence. For fixed $p\in(0,1)$ and $δ<\min\{1/2,1-p\}$, the upper and lower bounds match in the accuracy exponent under a fixed or logarithmic depth budget. When $d\leq2n$, they also match in confidence up to logarithms of accuracy. We extend the lower bounds to $W^{n,r}$ targets with $L^s$ error, and distinguish this extension from the upper bound for $W^{n,\infty}$. The optimal retention dependence and logarithmic factors remain open.

0.14

Shallow neural network approximation in mixed Sobolev spaces

cs.LG math.NA ·2026-09-04 ·Yuwen Li, Guozhi Zhang
theory similarity 0.76
Abstract · 40 pages, 2 figures

We investigate the best $L_2$ approximation of mixed Sobolev spaces by shallow neural networks with $n$ neurons and general activation functions. We first establish an activation-independent Fourier-block principle: if an activation has univariate approximation order $ρ$ in the sense of the Fourier-block property, then the global approximation rate has algebraic order $\min\{α,ρ\}$ for target functions of mixed smoothness $α$, up to explicit logarithmic factors. To verify this property for concrete activations, we introduce a structured univariate approximation condition that implies the Fourier-block property with explicit parameters. For $\mathrm{ReLU}^k$, a matching algebraic lower bound identifies $\min\{α,k+1\}$ as the optimal algebraic approximation exponent in any dimension, up to logarithmic factors in the upper bound. The framework also yields the exponent $\min\{α,k+1\}$ for cardinal B-splines and soft-$\mathrm{ReLU}^k$, and the full mixed-smoothness exponent $α$ for ELU and cosine activations, again up to logarithmic~factors.

0.19

Optimal approximation of smooth functions by ReLU neural networks

cs.LG stat.MLmath.NA ·2026-10-15 ·Thomas Nagler
similarity 0.75
Abstract

We study uniform approximation of the Hölder ball $\mathcal H_1^s([0,1]^D)$ by fully connected ReLU networks. Except in the one-dimensional Lipschitz case, existing constructions remain separated from the information-theoretic efficiency limit. This article closes the gap for every $s>0$ and $D\ge1$: networks with width $O(N)$, depth $O(L)$, and parameter magnitude $O(1)$ attain uniform approximation error of order $(N^2L^2\log N)^{-s/D}$. No relation between width and depth is required. The construction uses new encoding and decoding mechanisms that exploit higher-order finite-difference bounds for local Taylor coefficients of the target function. As a statistical consequence, empirical risk minimizers over the corresponding clipped network classes attain the minimax regression rate $n^{-2s/(2s+D)}$ without additional logarithmic factors. The paper also gives a detailed exposition of the key approximation techniques, covering both established and new mechanisms.

0.19

Geometry-Dependent Approximation and Stability Properties of Shallow ReLU$^k$ Networks on Bounded Euclidean Domains

cs.LG math.NA ·2026-11-10 ·Yuqing Liu, Tong Mao, Jinchao Xu
theory similarity 0.72
Abstract

On bounded Euclidean domains, we study how hidden-parameter geometry affects shallow ReLU$^k$ networks through results on approximation rates, saturation-type lower bounds, Gram and stiffness matrix spectra, Bernstein and Marcinkiewicz--Zygmund inequalities, discrete least-squares recovery, and inverse approximation. Our analysis uses smooth localization and dyadic Fourier estimates. We quantify parameter geometry by the fill distance $h$ and antipodal separation distance $\underline h$. For the prescribed network space $L_n^k$, representative approximation estimates take the form \begin{equation*} \begin{aligned} \inf_{g_n\in L_n^k}\|f-g_n\|_{\mathcal L^2(Ω')}&\lesssim h^r\|f\|_{\mathcal H^r(Ω)},\\ \inf_{g_n\in L_n^k}\|f-g_n\|_{\mathcal L^2(Ω)}&\gtrsim \underline h^{\frac{d+2k+1}{2}}\|f\|_{\mathcal L^2(Ω')}. \end{aligned} \end{equation*} The upper bound exploits target regularity up to the critical order $\frac{d+2k+1}{2}$, while the lower bound applies asymptotically to fixed targets smoother than this order. The upper estimate holds on an interior subdomain $Ω'$, whereas the lower estimate concerns the larger domain $Ω$. We also obtain geometry-dependent spectral estimates that quantify conditioning and coefficient stability. Further results establish norm discretization and regularized recovery from function values, and infer target regularity from approximation rates under coefficient or separation conditions. Altogether, these results describe how parameter geometry governs approximation accuracy, the stability of coefficient representations, discrete recovery, and the regularity information contained in convergence rates.

0.32

On the (non-)closedness of the set of ReLU networks

cs.LG math.CAmath.FAmath.NA+1 ·2026-11-06 ·Eloi Martinet, Leon Bungert
theory similarity 0.70
Abstract · 27 pages, 6 figures

We prove that the set $\mathcal{N}_N$ of ReLU networks with one hidden layer and at most $N\in\mathbb N$ neurons is weakly closed in $W^{1,p}(Ω)$, for a bounded connected open set $Ω\subset\mathbb R^d$. Consequently, every coercive, weakly lower semicontinuous energy on this space attains its minimum over $\mathcal{N}_N$. This covers the Deep Ritz method with convex integrands, Sobolev training and Lipschitz learning. Moreover, as the weight decay parameter tends to zero, minimizers of the regularized problem converge, up to subsequences, to minimizers with minimal parameter norm. We also prove that the set of ReLU networks with two hidden layers of bounded widths is not closed in $W^{1,p}(Ω)$ or in $C(\overlineΩ)$. This disproves a conjecture of Petersen, Raslan and Voigtlaender.

0.16

Parameterized Complexity of $L_p$-Lipschitz Constants for Input Convex Neural Networks and $L_p$-Norm Maximization over Zonotopes

cs.CC cs.DMcs.LGcs.NE ·2026-08-25 ·Aritra Das, Vincent Froese, Moritz Grillo, Debayan Gupta, Christoph Hertrich +4 more
theory similarity 0.69
Abstract · 26 pages, 3 figures

Lipschitz constants are a standard way to quantify the sensitivity of neural networks to small input perturbations, but computing them is difficult even for shallow ReLU networks. We study this problem for two-layer input-convex neural networks (ICNNs), a restricted architecture where nonnegative output weights enforce convexity. Computing the $L_p$-Lipschitz constant for these networks is equivalent to maximizing the dual norm over a zonotope. While $L_1$- and $L_\infty$-norm maximization on zonotopes admit fixed-parameter and polynomial-time algorithms, respectively, the parameterized complexity of the remaining $L_p$-norms was open. We prove that, for every fixed $p\in (1,\infty)\cap \mathbb{Q}$, maximizing the $L_p$-norm over a zonotope in $\mathbb{R}^d$ is W[1]-hard with respect to the dimension $d$. Moreover, our hardness results imply that brute-force enumeration algorithms are essentially optimal for this problem under the Exponential Time Hypothesis. By duality, the same hardness results hold for computing the $L_p$-Lipschitz constant of two-layer ReLU ICNNs. Our proof first establishes the result for the $L_2$-norm and then transfers the construction to arbitrary fixed $p\in (1,\infty)\cap\mathbb{Q}$ using a suitable Taylor approximation. These results resolve the corresponding questions regarding the parameterized complexity status for zonotope norm maximization and two-layer ICNN Lipschitz constants. Our paper resolves an open problem posted at COLT'25. There are several independent concurrent papers resolving the same problem. Our paper prioritizes a clear exposition of the underlying mathematics and conceptual intuitions behind the proof. Additionally, we explicitly describe our research process including the use of LLMs.

0.37

Minimax rates for learning spectral Barron functions by deep ReLU neural networks

cs.LG stat.MLmath.NA ·2026-09-30 ·Songqiu Ma, Yunfei Yang
theory similarity 0.69
Abstract

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.

0.17

Diffusion Score Estimation with Shallow Neural Networks: Regularity, Approximation, and Finite-Sample Rates

cs.LG stat.ML ·2026-10-19 ·Fan Liu, Yahong Yang, Wei Zhu
similarity 0.68
Abstract · 64 pages, 1 figure

We study the sample complexity of estimating Ornstein--Uhlenbeck diffusion scores in $\mathbb R^d$ using denoising score matching (DSM) with finite-width shallow ReLU networks, and its implications for reverse-process sampling. Under weak differentiability and polynomial-growth conditions on normalized derivatives of the initial density, we combine complementary estimates from the Gaussian transition kernel and the initial density to obtain explicit Sobolev bounds that are uniform in time on each fixed ball. Combining these bounds with existing shallow-network approximation theory gives explicit control of the approximation error and a sufficient path-norm budget. We then use truncation and localized Rademacher complexity to establish high-probability risk bounds for path-norm-constrained empirical DSM minimizers with unbounded inputs and labels. Under additional bounded-density and sub-Gaussian assumptions, suitable choices of network width and path-norm budget yield squared $L^2(P_t)$ score risk $\widetilde O(n^{-(d+3)/(2d+3)})$ at each fixed time $t>0$, where $n$ is the number of independent training samples and $P_t$ is the forward marginal. The nonasymptotic bounds retain explicit dependence on diffusion time and the regularity and tail parameters of the initial distribution. Aggregating the score errors over a time grid and applying existing sampling theory together with an early-stopping bound yields a high-probability total-variation error $\widetilde O(n^{-(d+3)/(4d+6)})$ between the generated and original data distributions under suitable sampling parameters. Here $\widetilde O$ suppresses logarithmic factors for fixed dimension, confidence level, and initial distribution.

0.14