Pith. sign in

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 →

arxiv 2411.18128 v1 pith:3AOEPMWO submitted 2024-11-27 math.NA cs.NA

classification math.NAcs.NA MSC 41A2541A3065D1565N7546E2265C20
keywords high-dimensionalapproximationcurseofdimensionalityanchoreddecompositioneffectivedimensionreproducingkernelHilbertspacesamplinginequalitiesmixed-regularitySobolevspacesparametricellipticPDEs
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper establishes a constructive approximation result: if a high-dimensional function splits as f = f1 + f2, where f1 is a sum of low-dimensional terms and f2 is small, then regularized least-squares sampling can approximate f with errors that depend on the dimension only polynomially. This is proved in a general reproducing kernel Hilbert space setting and then made concrete for Sobolev and mixed-regularity Sobolev spaces. The paper also develops weighted-norm criteria for deciding when the remainder f2 is small enough to qualify the function as effectively low-dimensional. These results are applied to parametric elliptic PDEs, where they give explicit error bounds for approximating quantities of interest without the curse of dimensionality.

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.

Watch

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

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

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)
  1. [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.
  2. [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)
  1. [Theorem 2.4] The opening line says 'reproducing kernel H'; this should be the kernel K to match the subsequent notation.
  2. [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.
  3. [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.
  4. [Corollary 4.7, Eq. (36)] The expression '|u‖' in the second term should be '‖u‖'.
  5. [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

0 steps flagged · score 0.0 of 10

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 3 free parameters · 5 assumptions · 0 invented entities

The central claims rest on standard sampling inequalities and embeddings taken from the literature, on the assumption that the remainder f2 is small, and on the weight parameters chosen for the PDE application. No new physical or mathematical entities are invented.

free parameters (3)
  • smoothing parameter λ = sqrt(λ) = h^{σ-d/2} for Sobolev; sqrt(λ) = F1(N)/F2(N) for mixed regularity
    Chosen by hand to balance the approximation and data terms; the mixed-regularity choice is the source of the algebraic gap in Corollary 2.6.
  • weight parameter c = c in (1/2,1], with n=0, m=1 in Theorem 4.5
    Appears in the product-and-order dependent weights γ(c;n,m,u); the admissible range is set by the summability condition (30), not by data.
  • anchor point c = c=0 in Section 4, arbitrary fixed point generally
    The anchored decomposition and weighted norms depend on a fixed anchor; theorems are valid for any fixed anchor but the constants depend on it.
assumptions (5)
  • standard math Sampling inequalities of Lemma 2.7, Theorem 2.10 and Theorem 2.17 hold with their stated constants.
    These are cited from [1,2,27,28] and are not re-proved in full; the new bounds inherit their constants and point-set conditions.
  • standard math Sobolev embedding and RKHS properties for H^σ with σ > d/2 and H^σ_mix with σ > 1/2 hold as stated.
    Used throughout Section 2 to evaluate point values and to pass from H1 to L∞.
  • domain assumption Uniform ellipticity and summability of the coefficient fluctuations for the parametric PDE.
    Assumption (32) and Theorem 4.1 are inherited from Kuo-Schwab-Sloan [17]; they bound the weighted Bochner norm (27).
  • domain assumption The remainder f2 is small in L∞, or the anchored tail f - fΛ is small.
    This defines the class of effectively low-dimensional functions; all error bounds scale with ||f2||∞.
  • standard math H^σ_mix decomposes orthogonally as H^σ_mix,Λ ⊕ H^σ_mix,∁Λ.
    Used in Corollary 4.7 to identify f1 with the anchored truncation fΛ; taken from [28, Proposition 6.1].

how reviews work

0 comments
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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages

  1. [28]

    Rieger and H

    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

  2. [1]

    Arcang´ eli, M

    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

  3. [2]

    Arcang´ eli, M

    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

  4. [3]

    Aronszajn

    N. Aronszajn. Theory of reproducing kernels. Trans. Am. Math. Soc. , 68:337–404, 1950

  5. [4]

    C. D. Bastian and H. Rabitz. High dimensional model repre sentation as a glass box in supervised machine learning. arXiv preprint, 2018

  6. [5]

    R. Bellman. Adaptive Control Processes: A guided Tour . Princton University Press, 1961

  7. [6]

    Dynamic programming

    Richard Ernest Bellman. Dynamic programming. Princeton University Press, Princeton, 1957

  8. [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

Show all 34 references
  1. [8]

    J. Dick, I. H. Sloan, X. Wang, and H. Wozniakowski. Libera ting the weights. J. Complexity , 20:593–623, 2004

  2. [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

  3. [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

  4. [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

  5. [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

  6. [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

  7. [14]

    Hoeffding

    W. Hoeffding. A class of statistics with asymptotically normal distribution. Ann. Math. Statist. , 19:293–325, 1948

  8. [15]

    S. N. Kersey. On the problem of smoothing and near-inter polation. Math. Comput. , 72:1873–1895, 2003

  9. [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

  10. [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

  11. [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

  12. [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

  13. [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

  14. [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

  15. [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

  16. [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

  17. [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

  18. [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

  19. [26]

    C. H. Reinsch. Smoothing by spline functions. Numer. Math. , 10:177–183, 1967

  20. [27]

    Rieger and H

    C. Rieger and H. Wendland. Sampling inequalities for sp arse grids. Numer. Math. , 136:439 – 466, 2017

  21. [29]

    I. H. Sloan, X. Wang, and H. Wozniakowski. Finite-order weights imply tractability of multivariate integration. J. Complexity , 20:46–74, 2004

  22. [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

  23. [31]

    I. Sobol. Sensitivity estimates for non linear mathema tical models. Mathematical Modelling and Computational Experiments, 1:407–414, 1993

  24. [32]

    G. Wahba. Smoothing noisy data by spline functions. Numer. Math. , 24:383–393, 1975

  25. [33]

    Wendland and C

    H. Wendland and C. Rieger. Approximate interpolation w ith applications to selecting smoothing parameters. Numer. Math. , 101:643–662, 2005

  26. [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...

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.