ReLU CNNs in Korobov spaces lift the approximation order from second order to order m+1, with far weaker dimensional growth than the Sobolev case

For Korobov functions with mixed derivative of order m+1 in each direction, the authors prove that a ReLU CNN of depth about O(N log_2 N) attains Lp approximation error N^{−m−1} up to a (log_2 N)^{(m+2)(d−1)} factor, with the order increasing in m. Existing results in this direction were essentially rates O(L^{−2+1/p}) in Lp(Ω) based on the second-order mixed derivative; this work exploits higher-order Korobov regularity to extend the order to arbitrarily high order, generalizing the low-order deep-CNN results of Mao and Zhou. The conclusion is stated as Theorem 1.3 and proved in Section 4, relying on the higher-order sparse grid interpolation error (Lemma 2.4), coefficient bounds (Lemma 2.3), and the CNN approximation of polynomials (Theorem 3.5); the text notes that for m=1 and p=∞ the depth and rate in terms of N match Mao and Zhou [2022], except that the pre-factor in d becomes d^4 instead of d^2 log_2 d.

The authors give a precise ReLU product-factor decomposition of the higher-order sparse grid basis functions: each basis function ϕ^α_{l,i}(x) can be written as ∏_j∏_k ρ_{l_j,i_j,k}(x_j), where each ρ is a ReLU unit of the form σ(a x + b) and takes values between 0 and 2^{n+d−1} on [0,1]. This represents each univariate basis function of the sparse grid interpolant as a product of piecewise linear (ReLU) factors, so that the higher-order sparse grid interpolant can be realized directly by convolutional layers, which is the key step linking sparse grid approximation to CNN architecture. The decomposition is constructed explicitly in the proof of Theorem 1.3 (ϕ^2=ρ_1ρ_2 for m=2, and ϕ^{α_j}=∏_{k=1}^m ρ_k for m≥3), and is illustrated by figures of the basis function and its factors for d=1, l=4, i=3 (Figures 4 and 5).

The authors prove that CNNs can approximate polynomials with non-negative bounded input variables: for a polynomial of the form ∑_i c_i ∏_{j=1}^k y_{i,j}, there is a CNN of depth J≤(256+28U)dlk^2/(s−1)+(3U+61)k with error at most ‖c‖_∞·M^{2k−1}/2^{2U−k+2}. The text states that, to the authors' knowledge, no result existed for approximating multivariate polynomials and cardinal B-splines by CNNs; this theorem extends the approximation of the product (x,y)↦xy (including the non-negativity property, which the text says seems missing in the classical literature) to multi-factor products, and notes that multivariate polynomials and cardinal B-splines both take this form, so approximation rates for Sobolev and analytic functions by CNNs follow. The result is Theorem 3.5, proved by induction on k, with the base case using the product approximation error |e^×_{M,U}(x,y)−xy|≤M^2/2^{2U} and 0≤e^×_{M,U}(x,y)≤M^2 from Lemma 3.1, and repeated application of Lemma 3.4 to assemble the required depth.

The authors contrast the dimensional influence for CNNs approximating Korobov functions with the Sobolev case, noting that Sobolev functions W^m_p(Ω) are approximated by depth-L networks with accuracy O(L^{−2m/d}), whereas their Korobov result indicates the dimensional influence is not as substantial, thereby mitigating the curse of dimensionality. This comparison makes explicit the difference between Korobov spaces (mixed smoothness) and Sobolev spaces (isotropic smoothness) in CNN approximation rates, indicating that higher-order expressivity does not degrade severely with dimension for Korobov-type functions. The judgment rests on the error bound of Theorem 1.3 compared with the cited Sobolev approximation results (Lu et al. [2021a]; Siegel [2023]); the authors also note that the constant C_{m,d} depends exponentially on m and d.

The result applies to Korobov functions on the unit cube [0,1]^d that have mixed derivatives of order m+1 in each direction and vanish on the boundary, approximated by deep CNNs using ReLU activation and discrete convolution, with error measured in the Lp norm (1≤p≤∞). It is an existence upper bound: there exists a network of depth at most Csd^4m^3N(log_2 N) achieving this accuracy, rather than a training algorithm or parameter values. The authors note that, following the line of Yang and Zhou on CNNs and using the approximation error bounds derived here, one can establish convergence rates for learning a Korobov function with p,m≥2 by the CNN model H^{s,d}_L; the text also conjectures that for Korobov functions of order α<(d+2k+1)/2, a nearly optimal error of order O(n^{−α}) can be achieved using ReLU^k shallow networks with n neurons, to be investigated in future work.

The authors state they are currently not sure whether the proposed approximation error bound is nearly optimal, and note that Yang and Lu [2024] recently provided, using sparse grids and the bit-extraction technique, a super-approximation rate O(N^{−4}L^{−4}) (up to logarithmic factors) for Korobov functions in K^2_∞(Ω), so improving the deep-CNN rates here via bit-extraction is an open direction. The constant C_{m,d} depends exponentially on m and d, and the bound carries a (log_2 N)^{(m+2)(d−1)} logarithmic factor, whose practical effect at given dimension and smoothness still needs further analysis. This is a theoretical work with no numerical experiments reported, so how tight these bounds are at realistic network sizes remains unclear.