REVIEW 2 major objections 5 minor 34 references
Constructive Approximation of High-Dimensional Functions with Small Efficient Dimension with Applications in Uncertainty Quantification
T0 review · 2 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read This paper proves that functions which are effectively low-dimensional can be approximated without the curse of dimensionality.
desk verdict The reader's algebraic objection to Corollary 2.6 does not hold up, but the real problem is a d/n inconsistency in Theorem 2.17's log exponents that must be fixed; the paper is otherwise substantial and worth reviewing. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the anchored decomposition f = Σ_{u⊆D} f_{u;c}, where each component f_{u;c} depends only on the variables with indices in u and vanishes whenever one of those variables equals the anchor c. Functions admitting a representation over a downward-closed set Λ form closed subspaces, and the paper constructs a penalized least-squares estimator $Q^{{(Λ)}}$ over such subspaces. The sampling sets are anchored unions $X^{{ (d)}}$_{Λ} = ⋃_{u∈Λ} X_u of low-dimensional grids extended by the anchor. Sampling inequalities specialized to these anchored subspaces convert fill distances and point counts into L² and L∞ error bounds. Weighted mixed-regularity norms of the form ‖f‖_{$H^{{1}}$_{c;γ}} = (Σ_{u} $γ_u^{{-1}}$‖D_u f((·;c)_u)‖_{L²}^{2})^{1/2} control the size of the anchored tail terms, which is exactly what is needed to certify that f2 is small.
What would settle it
For a concrete check, take a known f1 from an anchored Λ-subspace and add a small but nonzero f2 supported on an order-(n+1) anchored term with amplitude δ. Run the paper's estimator with the prescribed smoothing parameter λ and measure the L∞ error as δ varies: the bounds in (12) and (36) predict errors that grow only linearly in δ, so an observed growth faster than linear would falsify the balancing assumption behind the method.
Extended reading notes
Core claim
The central claim is that a function f = f1 + f2, with f1 in an anchored low-dimensional subspace Λ and f2 small, can be approximated from point values of f alone, even though those point values are polluted by f2. The estimator is penalized least squares: it minimizes a block-weighted sum of squared residuals plus λ times the squared norm over f1. Theorem 2.13 gives ‖f − $Q^{{(Λ)}}$_{X,λ} f‖_{L²([a,b])} ≤ C($h^{{σ−d/2}}$_{$X^{{ (d)}}$_{Λ}}‖f‖_{$H^{{σ}}$} + ‖f2‖_{L∞}), where the fill distance h is measured on anchored point sets built from low-dimensional grids. Because the number of anchored blocks grows like binomial(d,n), the number of samples needed grows only polynomially in the ambient dimension d. In mixed-regularity Sobolev spaces, Corollary 2.18 provides a bound of the form (log N)^{ρ1} $N^{{-σ+1/2}}$‖f‖_H + √N (log N)^{ρ2}‖f2‖_{L∞}. For parametric PDEs, Corollary 4.7 combines these estimates with the anchored tail bound to show that a quantity of interest u_G can be approximated with error at most Ā[(log N)^{ρ1} $N^{{-σ+1/2}}$‖u_G‖ + √N(log N)^{ρ2}(ε/√2)^{n+1}‖u‖], so choosing n appropriately makes the approximation tractable.
Load-bearing premise
The load-bearing premise is that the remainder f2 left by a low-dimensional anchored decomposition is small enough to be absorbed by the smoothing regularization; without that quantitative smallness, the estimator cannot distinguish f1 from f2 and the stated decay rates do not follow.
Editorial extensions
If this is right
- For an order-n anchored decomposition, the number of sampling points needed grows at most polynomially in the ambient dimension d, so effective low dimensionality directly translates into tractable approximation costs.
- In mixed-regularity Sobolev spaces, the approximation error decays like (log N)^{ρ1} N^{-σ+1/2} for the low-dimensional part, and the remainder contributes a term proportional to √N (log N)^{ρ2}‖f2‖_{L∞}.
- The weighted-norm bounds in Section 3 give a quantitative criterion for deciding whether a function is effectively low-dimensional: the tail sum Σ_{u∉Λ} 2^{#u/2}γ_u^{1/2} must be small.
- For parametric elliptic PDEs with affine diffusion coefficients satisfying the summability condition, the solution and its linear functionals are effectively low-dimensional, so the constructed estimators avoid the curse of dimensionality.
- The approximation is constructive: it reduces to solving a linear system, so the method can be implemented directly once the anchored point sets and the smoothing parameter are chosen.
Reading between the lines
- The weighted-norm estimates suggest a practical heuristic for estimating effective dimension from data: compute or estimate anchored components, threshold the weighted tail contributions, and choose the smallest Λ for which the tail bound is below the target accuracy.
- The PDE result implicitly indicates that the number of active stochastic variables n may need to grow logarithmically with the number of samples N to compensate for the √N factor in front of the remainder term; this trade-off is not stated explicitly in the paper.
- A direct extension would be to adaptive anchor selection: instead of fixing Λ in advance, one could use the anchored component bounds to select which low-dimensional terms to include as more samples are collected.
- The results could be tested as an alternative to Monte Carlo for elliptic PDEs with random coefficients when the fluctuation field is dominated by low-order interactions, since the error bounds are deterministic and explicit in N, n, and d.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies penalized least-squares approximation of high-dimensional functions written as f = f1 + f2, where f1 belongs to an anchored low-dimensional subspace associated with a downward-closed set Λ and f2 is assumed to be small. Section 2 develops a generic reproducing-kernel-Hilbert-space error bound (Theorem 2.4), simplifies it under a particular choice of the smoothing parameter (Corollary 2.6), and then specializes it to standard Sobolev spaces using anchored sampling sets (Theorems 2.10 and 2.13) and to mixed-regularity Sobolev spaces using sparse grids (Theorems 2.17 and 2.18). Section 3 introduces a weighted norm on H^1_mix and derives bounds on the anchored tail in terms of weights (Theorem 3.3, Corollaries 3.6 and 3.7). Section 4 applies the mixed-regularity results to an affine parametric elliptic PDE, obtaining an error bound for a quantity of interest (Corollary 4.7).
Significance. If the bounds are correct, the paper offers a constructive approach to a natural model of effective low dimensionality, with explicit rates and point sets, and it connects these rates to tractability of parametric PDEs under a finite-noise assumption. The paper is transparent in relying on published sampling inequalities and on the Λ-subspace machinery of [28]; it does not fit free constants. I also verified a step that might be questioned: substituting √λ = F1/F2 into Theorem 2.4 gives coefficients (2+cp)F1 for ‖f‖_H and (1+2cp)F2 for ‖f2‖_{ℓ²}, not an F2²/F1 term; since cp≥1 these are bounded by 2(1+cp) times the displayed terms, so Corollary 2.6 is valid up to harmless constants. The main obstacle is an internal dimension-dependence inconsistency in Theorem 2.17, together with the absence of an explicit sample-complexity statement in the PDE application.
major comments (2)
- [Theorem 2.17; Corollaries 2.18 and 4.7] The displayed sampling inequality in Theorem 2.17 uses ρ1(σ,n) and ρ2(n), but the definition line states ρ1(σ,d) = (σ+5/2)(d−1)+1 and ρ2(d) = 2d−1. Corollary 2.18 and Corollary 4.7 then apply these exponents with n. If the definitions are taken literally, F1(N) = N^{−σ+1/2}(log N)^{O(d)}, so enforcing F1(N) ≤ ε requires log N = Θ(d log d), i.e. N exponential in d; this contradicts the abstract's no-curse claim and the tractability statement in Corollary 4.7. If the intended dependence is on n, the definitions must be corrected and the theorem restated consistently. This issue is load-bearing because the mixed-regularity and PDE results all flow through Theorem 2.17.
- [Corollary 4.7, Eq. (36)] The bound (36) contains a term ~C√N(log N)^{ρ2(n)}(ε/√2)^{n+1} that grows with N for fixed n, while the first term decays as N^{−σ+1/2}(log N)^{ρ1(n)}. The paper never states how n and N should be chosen jointly to bring the total error below a prescribed tolerance. With the corrected Theorem 2.17, ρ1 and ρ2 are linear in n, so choosing n ≈ log N to control the √N term makes the logarithmic factor in the first term behave like N^{O(log log N)}, which can overwhelm the algebraic decay. Since the paper claims efficient approximation without the curse of dimensionality, the PDE application needs an explicit admissible (n,N) regime, or a modified operator analogous to Q^{(Λ)} that removes the √N factor. As written, Eq. (36) does not by itself demonstrate tractability.
minor comments (5)
- [Theorem 2.4] The opening line says 'reproducing kernel H'; this should be the kernel K to match the subsequent notation.
- [Definition 2.11] The assertion that one may assume Xu ∩ Xv = ∅ for u ≠ v 'without restriction' deserves a short justification, because anchored extensions of low-dimensional points can produce coincident points for different index sets.
- [Corollary 3.7] In the displayed chain of inequalities, the second-to-last line omits the final factor ‖f‖_{H^1_{c;γ}}; the stated result is clear, but the derivation should be corrected.
- [Corollary 4.7, Eq. (36)] The expression '|u‖' in the second term should be '‖u‖'.
- [Section 3] The abstract says the paper derives 'efficient estimates for deciding' whether a function is effectively low-dimensional, but Section 3 provides only a priori tail bounds in weighted norms; it does not discuss how the weights are chosen or estimated from data. Please calibrate the wording to match the actual scope.
Circularity Check
No circularity: the new approximation results are derived from the paper's own generic estimates applied to external or independently published sampling inequalities; self-citations to [28] supply lemmas rather than defining the target error.
full rationale
Walking the derivation chain from Theorem 2.4 through Corollaries 2.6, 2.18 and 4.7, every claimed bound is obtained by an explicit algebraic application of a sampling inequality to the error f1 - Qf, with the smoothing parameter lambda chosen as F1/F2 or as a fill-distance power. The unknown f2 enters only as a norm on the right-hand side; it is not used to define the estimator or the data set, so the error bound is not its own input by construction. The main external ingredients are the sampling inequalities of Lemma 2.7 (cited to Arcangeli et al. and Rieger-Wendland 2017) and the Lambda-subspace sampling inequality of Theorem 2.17, quoted verbatim from the authors' published [28, Theorem 5.6]. Although [28] is a self-citation, it is an independently published, parameter-free theorem whose assumptions do not include the mismeasurement error bound being proved; the current paper even reproduces the proof of the analogous Sobolev inequality in Theorem 2.10. The orthogonal decomposition used in Corollary 4.7 is likewise a published result [28, Prop. 6.1], not a fitted ansatz. No fitted parameter is renamed as a prediction, and no uniqueness theorem is invoked to force a choice. The apparent d/n mismatch in the log-power exponents between Theorem 2.17 and Corollary 2.18 is an internal-consistency and correctness concern about the tractability claim, not a circular dependence: the exponents are not defined in terms of the quantity being bounded. Similarly, Remark 4.8's acknowledgement that N depends on n is a caveat on the tractability conclusion, not a circular step. Accordingly no circular step can be exhibited, and the appropriate score is 0.
Assumptions & free parameters
free parameters (3)
- smoothing parameter λ =
sqrt(λ) = h^{σ-d/2} for Sobolev; sqrt(λ) = F1(N)/F2(N) for mixed regularity
- weight parameter c =
c in (1/2,1], with n=0, m=1 in Theorem 4.5
- anchor point c =
c=0 in Section 4, arbitrary fixed point generally
assumptions (5)
- standard math Sampling inequalities of Lemma 2.7, Theorem 2.10 and Theorem 2.17 hold with their stated constants.
- standard math Sobolev embedding and RKHS properties for H^σ with σ > d/2 and H^σ_mix with σ > 1/2 hold as stated.
- domain assumption Uniform ellipticity and summability of the coefficient fluctuations for the parametric PDE.
- domain assumption The remainder f2 is small in L∞, or the anchored tail f - fΛ is small.
- standard math H^σ_mix decomposes orthogonally as H^σ_mix,Λ ⊕ H^σ_mix,∁Λ.
Cite this review
Pith. "Pith review of Constructive Approximation of High-Dimensional Functions with Small Efficient Dimension with Applications in Uncertainty Quantification." pith.science (2026). https://pith.science/paper/3AOEPMWO
@misc{pith2026241118128,
author = {Pith},
title = {Pith review of: Constructive Approximation of High-Dimensional Functions with Small Efficient Dimension with Applications in Uncertainty Quantification},
year = {2026},
howpublished = {\url{https://pith.science/paper/3AOEPMWO}},
note = {Machine review of arXiv:2411.18128}
}
read the original abstract
In this paper, we show that the approximation of high-dimensional functions, which are effectively low-dimensional, does not suffer from the curse of dimensionality. This is shown first in a general reproducing kernel Hilbert space set-up and then specifically for Sobolev and mixed-regularity Sobolev spaces. Finally, efficient estimates are derived for deciding whether a high-dimensional function is effectively low-dimensional by studying error bounds in weighted reproducing kernel Hilbert spaces. The results are applied to parametric partial differential equations, a typical problem from uncertainty quantification.
Reference graph
Works this paper leans on
-
[28]
C. Rieger and H. Wendland. On the approximability and cu rse of dimensionality of certain classes of high-dimensional functions. SIAM J. Numer. Anal. , 62:842–871, 2024
work page 2024
-
[1]
R. Arcang´ eli, M. Cruz L´ opez de Silanes, and J. J. Torren s. An extension of a bound for functions in Sobolev spaces, with applications to ( m, s)-spline interpolation and smoothing. Numer. Math. , 107:181–211, 2007
work page 2007
-
[2]
R. Arcang´ eli, M. Cruz L´ opez de Silanes, and J. J. Torren s. Extension of sampling inequalities to Sobolev sem-norms of fraction order and derivative data. Numer. Math. , 121:587–608, 2012
work page 2012
- [3]
-
[4]
C. D. Bastian and H. Rabitz. High dimensional model repre sentation as a glass box in supervised machine learning. arXiv preprint, 2018
work page 2018
-
[5]
R. Bellman. Adaptive Control Processes: A guided Tour . Princton University Press, 1961
work page 1961
-
[6]
Richard Ernest Bellman. Dynamic programming. Princeton University Press, Princeton, 1957
work page 1957
-
[7]
C. de Boor. Calculation of the smoothing spline with weig hted roughness measure. Mathematical Models and Methods in Applied Sciences , 11(01):33–41, 2001
work page 2001
Show all 34 references
-
[8]
J. Dick, I. H. Sloan, X. Wang, and H. Wozniakowski. Libera ting the weights. J. Complexity , 20:593–623, 2004
2004
-
[9]
A. D. Gilbert, F. Y. Kuo, and I. H. Sloan. Equivalence betw een Sobolev spaces of first-order dom- inating mixed smoothness and unanchored ANOV A spaces on Rd. Math. Comput. , 91:1837–1869, 2022
2022
-
[10]
Gnewuch, M
M. Gnewuch, M. Hefter, A. Hinrichs, K. Ritter, and G.W. W asilkowski. Equivalence of weighted anchored and ANOV A spaces of functions with mixed smoothnes s of order one in Lp. Journal of Complexity, 40:78–99, 2017
2017
-
[11]
Griebel, F
M. Griebel, F. Y. Kuo, and I. H. Sloan. The smoothing effec t of integration in Rd and the ANOV A decomposition. Math. Comput. , 82:383–400, 2012
2012
-
[12]
Hefter, K
M. Hefter, K. Ritter, and G.W. Wasilkowski. On equivale nce of weighted anchored and ANOV A spaces of functions with mixed smoothness of order one in L1 or L∞ . Journal of Complexity , 32(1):1– 19, 2016
2016
-
[13]
Equivalence of ancho red and ANOV A spaces via interpolation
Aicke Hinrichs and Jan Schneider. Equivalence of ancho red and ANOV A spaces via interpolation. Journal of Complexity , 33:190–198, 2016
2016
-
[14]
Hoeffding
W. Hoeffding. A class of statistics with asymptotically normal distribution. Ann. Math. Statist. , 19:293–325, 1948
1948
-
[15]
S. N. Kersey. On the problem of smoothing and near-inter polation. Math. Comput. , 72:1873–1895, 2003
2003
-
[16]
Was ilkowski
Peter Kritzer, Friedrich Pillichshammer, and G.W. Was ilkowski. A note on equivalence of anchored and ANOV A spaces; lower bounds. Journal of Complexity , 38:31–38, 2017
2017
-
[17]
F. Y. Kuo, C. Schwab, and I. Sloan. Quasi-Monte Carlo fini te element methods for a class of elliptic partial differential equations with random coefficients. SIAM J. Numer. Anal. , 50:3351–3374, 2012
2012
-
[18]
F. Y. Kuo, C. Schwab, and I. H. Sloan. Multi-level quasi- Monte Carlo finite element methods for a class of elliptic PDEs with random coefficients. Foundations of Computational Mathematics , 15:411–449, 2015
2015
-
[19]
Y Kuo, I
F. Y Kuo, I. H. Sloan, G. W. Wasilkowski, and H. Wozniakow ski. On decompositions of multivariate functions. Math. Comput. , 79:953–966, 2010
2010
-
[20]
G. Li, X. Xing, W. Welsh, and H. Rabitz. High dimensional model representation constructed by support vector regression. i. independent variables with k nown probability distributions. Journal of Mathematical Chemistry , 55:278–303, 2017
2017
-
[21]
Novak and H
E. Novak and H. Wozniakowski. Tractability of Multivariate Problems. Volume I: Linear In forma- tion. European Mathematical Society, Zurich, Switzerland, 200 8
-
[22]
Novak and H
E. Novak and H. Wozniakowski. Tractability of Multivariate Problems. Volume II: Standar d Infor- mation for Functionals . European Mathematical Society, Zurich, Switzerland, 201 0
-
[23]
Novak and H
E. Novak and H. Wozniakowski. Tractability of Multivariate Problems. Volume III: Standa rd Infor- mation for Operators . European Mathematical Society, Zurich, Switzerland, 201 2
-
[24]
A. Owen. Effective dimension of some weighted pre-Sobol ev spaces with dominating mixed partial derivatives. SIAM J. Numer. Anal. , 57:547–562, 2019. CONSTRUCTIVE APPROXIMATION OF HIGH-DIMENSIONAL FUNCTION S 30
2019
-
[25]
Rabitz and ¨O
H. Rabitz and ¨O. F. Ali¸ s. General foundations of high-dimensional model representations. Journal of Mathematical Chemistry , 25:197–233, 1999
1999
-
[26]
C. H. Reinsch. Smoothing by spline functions. Numer. Math. , 10:177–183, 1967
1967
-
[27]
Rieger and H
C. Rieger and H. Wendland. Sampling inequalities for sp arse grids. Numer. Math. , 136:439 – 466, 2017
2017
-
[29]
I. H. Sloan, X. Wang, and H. Wozniakowski. Finite-order weights imply tractability of multivariate integration. J. Complexity , 20:46–74, 2004
2004
-
[30]
I. H. Sloan and H. Wozniakowski. When are quasi-monte ca rlo algorithms efficient for high- dimensional integrals? J. Complexity , 14:1–33, 1998
1998
-
[31]
I. Sobol. Sensitivity estimates for non linear mathema tical models. Mathematical Modelling and Computational Experiments, 1:407–414, 1993
1993
-
[32]
G. Wahba. Smoothing noisy data by spline functions. Numer. Math. , 24:383–393, 1975
1975
-
[33]
Wendland and C
H. Wendland and C. Rieger. Approximate interpolation w ith applications to selecting smoothing parameters. Numer. Math. , 101:643–662, 2005
2005
-
[34]
Ziehn and A
T. Ziehn and A. S. Tomlin. GUI-HDMR - a software tool for g lobal sensitivity analysis of complex models. Environmental Modelling & Software , 24(7):775–785, 2009. Christian Rieger, FB Mathematik und Informatik, Philipps- Universit¨at Marburg, 35032 Marburg, Germany Email addr...
2009
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.