{"id":"c63bdee6-e03f-4a49-b7d9-bcce82efa55c","arxiv_id":"2411.18128","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"High-dimensional functions with small effective dimension can be approximated by penalized least squares in anchored low-dimensional subspaces, with error bounds in Sobolev and mixed-regularity spaces.","lead":"This paper derives error bounds for approximating high-dimensional functions that are, up to a small remainder, sums of functions depending on only a few variables. If the bounds are correct, they give a concrete route to avoiding the curse of dimensionality in parametric PDE uncertainty quantification.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Mixed-regularity log-exponents in Theorem 2.17 are stated with d but used with n; if the d-dependence is literal, the sample complexity becomes exponential in d, contradicting the central no-curse claim.","rationale":"The Reader's stated weakest assumption is an algebraic claim about Corollary 2.6, but direct substitution of √λ=F1/F2 into Theorem 2.4 yields no F2²/F1 term; the corollary's displayed bound is algebraically consistent. The substantive issue I find instead is the exponent mismatch between Theorem 2.17 and Corollary 2.18. The theorem as printed defines ρ1 and ρ2 with d, while the corollary uses them with n. Since the central tractability conclusion depends on log-powers that grow only with the truncation order n, this mismatch is load-bearing: if the d-dependence is literal, the sample complexity is exponential in d. The fix is straightforward — verify the original source and correct the statement — so I recommend CONDITIONAL rather than outright rejection. The paper's Sobolev-space results and the anchored weighted-norm estimates appear internally coherent, and the claimed mismeasured-data framework is plausible once the exponent question is resolved.","tokens_in":26047,"tokens_out":45390,"duration_ms":408122,"concrete_test":"Check Theorem 2.17 against [28, Theorem 5.6] and the derivation of the sparse-grid sampling inequality for Λ={u:#u≤n}; determine whether the log-exponents are functions of n (truncation order) or d. Then recompute Corollary 2.18 with the correct exponents and verify whether the displayed rate still gives polynomial-in-d sample complexity.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central mixed-regularity and PDE bounds rest on Theorem 2.17, whose displayed sampling inequality defines the log-powers as ρ1(σ,d)=(σ+5/2)(d−1)+1 and ρ2(d)=2d−1, i.e. as functions of the ambient dimension d. Corollary 2.18 then applies this theorem with F1(N)=(log N)^{ρ1(σ,n)}N^{−σ+1/2} and F2(N)=(log N)^{ρ2(n)}, silently replacing d by n. This is an internal inconsistency. If the d-dependence is intended, then F1(N)=N^{−τ}(log N)^{O(d)}; requiring F1(N)≤ε forces log N=Θ(d log d), hence N=exp(Θ(d log d)), which is exponential in d. That would invalidate the tractability claim in Corollary 4.7 and the abstract's assertion that the approximation does not suffer from the curse of dimensionality. If the d-dependence is a typo, the mixed-regularity analysis is salvageable, but the theorem statement and Corollary 2.18 must be reconciled. Separately, I could not confirm the Reader's algebraic objection to Corollary 2.6: substituting √λ=F1/F2 into Theorem 2.4 gives coefficient (2+cp)F1 for ‖f‖_H and (1+2cp)F2 for ‖f2‖_{ℓ²}, with no F2²/F1 term appearing.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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).","tokens_in":10,"tokens_out":29049,"duration_ms":377332,"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":[{"comment":"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.","section":"Theorem 2.17; Corollaries 2.18 and 4.7"},{"comment":"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.","section":"Corollary 4.7, Eq. (36)"}],"minor_comments":[{"comment":"The opening line says 'reproducing kernel H'; this should be the kernel K to match the subsequent notation.","section":"Theorem 2.4"},{"comment":"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.","section":"Definition 2.11"},{"comment":"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.","section":"Corollary 3.7"},{"comment":"The expression '|u‖' in the second term should be '‖u‖'.","section":"Corollary 4.7, Eq. (36)"},{"comment":"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.","section":"Section 3"}],"recommendation":"major_revision","confidential_remarks":"To the editor: the claimed algebraic failure of Corollary 2.6 in the attached review is not supported by a direct calculation; the substantive problem is the d/n inconsistency in Theorem 2.17 and the lack of an explicit sample-complexity statement for the PDE application. If the authors correct the exponent definitions and clarify the admissible (n,N) regimes, the paper is plausibly publishable after revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: I read the paper carefully. The main reason in your report for rejection—the Corollary 2.6 algebra—does not survive direct calculation. Setting sqrt(λ)=F1/F2 in Theorem 2.4 turns the coefficient of ||f||_H into (2+c_p)F1 and the coefficient of ||f2|| into (1+2c_p)F2. No F2^2/F1 term appears. Corollary 2.6 then follows by an elementary constant crush. So that objection is wrong.\n\nWhat the paper actually does: it extends the authors' earlier Λ-subspace machinery to the realistic situation where you sample f = f1 + f2, not f1, and gives a penalized least-squares estimator with explicit error in terms of F1, F2, and ||f2||. The Sobolev application (Theorem 2.13) and the weighted-norm tail criterion in Section 3 are new and appear coherent. The application to parametric PDEs is a natural combination of these tools with the Kuo–Schwab–Sloan regularity bounds. This is a genuine contribution, not a repackaging.\n\nThe soft spot is real, but it is not the one in the report: Theorem 2.17 states the mixed-regularity sampling inequality with log exponents ρ1(σ,d) and ρ2(d), while the displayed bound and Corollary 2.18 use ρ1(σ,n) and ρ2(n). If the d-version is taken literally, the number of samples needed to make F1 small grows like exp(O(d log d)), which contradicts the paper's own tractability claim. I think this is a typo—the theorem is for n-order functions and the n-version is what the rest of the paper needs—but it has to be fixed and the constants in Corollary 2.18 reconciled. The d^n and d^{τn} prefactors in Theorem 2.17 also seem to disappear in Corollary 2.18; the constants need a careful pass.\n\nThe PDE application has smaller gaps: it assumes u_G ∈ H^σ_mix without quantifying σ, and it never discusses the d-dependence of ||u_G||_{H^σ_mix}. These are fixable but should be addressed before any 'no curse of dimensionality' claim is printed.\n\nBottom line: the paper deserves a serious referee. I would send it out, asking the authors to fix the d/n inconsistency and clean up constants. The central idea is sound, and the mismeasured-data viewpoint is worth having in the literature.","headline":"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.","tokens_in":26906,"tokens_out":8055,"would_cite":true,"duration_ms":72090,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["41A25","41A30","65D15","65N75","46E22","65C20"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that functions which are effectively low-dimensional can be approximated without the curse of dimensionality.","keywords":["high-dimensional approximation","curse of dimensionality","anchored decomposition","effective dimension","reproducing kernel Hilbert space","sampling inequalities","mixed-regularity Sobolev spaces","parametric elliptic PDEs"],"falsifier":"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.","tokens_in":104,"feed_emoji":"📐","tokens_out":8325,"duration_ms":193927,"temperature":0.7,"pith_summary":"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.","feed_headline":"Low-dimensional structure defeats the curse of dimensionality","feed_subtitle":"A constructive least-squares method approximates high-dimensional functions and parametric PDE solutions with polynomial dependence on…","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the closed Λ-subspaces, anchored sampling inequalities, and the orthogonal decomposition results used throughout the paper.","marker":"[28]"},{"why":"Provides the sparse-grid sampling inequalities that underlie the mixed-regularity Sobolev bounds in Theorem 2.17.","marker":"[27]"},{"why":"Gives the parametric PDE setting, the derivative bounds for the solution map, and the construction of the product-and-order weights used in Section 4.","marker":"[17]"},{"why":"Establishes the anchored decomposition and its projection properties, which are the foundation for the Λ-subspace structure.","marker":"[19]"},{"why":"Provides the weighted pre-Sobolev framework for effective dimension that the paper adapts from ANOVA to anchored decompositions.","marker":"[24]"},{"why":"Supplies the standard Sobolev sampling inequality used in Lemma 2.7 for the low-dimensional components.","marker":"[1]"},{"why":"Extends the sampling inequalities to fractional-order Sobolev spaces, supporting the general Sobolev setting.","marker":"[2]"}],"fun_headline_variants":["Beating the curse of dimensionality with low-dimensional structure","Approximating high-dimensional functions via low-dimensional structure","Curse of dimensionality broken for effectively low-dimensional functions","Polynomial complexity for high-dimensional approximation when structure is low","Efficient approximation of high-dimensional functions with low effective dimension"],"cache_read_input_tokens":28928,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Beating the curse of dimensionality with low-dimensional structure","Approximating high-dimensional functions via low-dimensional structure","Curse of dimensionality broken for effectively low-dimensional functions","Polynomial complexity for high-dimensional approximation when structure is low","Efficient approximation of high-dimensional functions with low effective dimension"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000764,"raw_usage":{"total_tokens":3392,"prompt_tokens":948,"completion_tokens":2444,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":564,"completion_tokens_details":{"reasoning_tokens":2366}},"tokens_in":564,"tokens_out":2444,"duration_ms":16375,"temperature":1.0,"reasoning_tokens":2366,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T11:29:39.537287+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Rieger and H","cited_arxiv_id":null,"evidence_quote":"Supplies the closed Λ-subspaces, anchored sampling inequalities, and the orthogonal decomposition results used throughout the paper."},{"cited_title":"Rieger and H","cited_arxiv_id":null,"evidence_quote":"Provides the sparse-grid sampling inequalities that underlie the mixed-regularity Sobolev bounds in Theorem 2.17."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the parametric PDE setting, the derivative bounds for the solution map, and the construction of the product-and-order weights used in Section 4."},{"cited_title":"Y Kuo, I","cited_arxiv_id":null,"evidence_quote":"Establishes the anchored decomposition and its projection properties, which are the foundation for the Λ-subspace structure."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the weighted pre-Sobolev framework for effective dimension that the paper adapts from ANOVA to anchored decompositions."},{"cited_title":"Arcang´ eli, M","cited_arxiv_id":null,"evidence_quote":"Supplies the standard Sobolev sampling inequality used in Lemma 2.7 for the low-dimensional components."},{"cited_title":"Arcang´ eli, M","cited_arxiv_id":null,"evidence_quote":"Extends the sampling inequalities to fractional-order Sobolev spaces, supporting the general Sobolev setting."}],"review_version":1}