{"id":"36bcac90-1907-4521-a006-26ec9c170362","arxiv_id":"2506.24054","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"Least squares on random points with 2x oversampling matches or beats Smolyak sparse grids on benchmark functions up to dimension 100.","lead":"This paper benchmarks Smolyak sparse-grid interpolation against two random-point least squares methods on high-dimensional function approximation, finding that least squares with twice the samples matches sparse grids in low dimensions and beats them in high dimensions. It is a practical numerical study with release code, not a new mathematical theorem.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The high-dimensional 'clear superiority' claim rests on a single fixed random LS point set per (q,d), with no seeds or repeated draws; the finding may not be statistically robust.","rationale":"The reader's weakest_assumption identifies the same load-bearing concern, and I agree with it. The paper is honest and careful in other respects: the theoretical sections are presented as background, the code is public, the methodology is described in detail, and the authors explicitly note the 'wrong scaling' caveat in Section 4.4 and the fact that their test-set error estimates are not true uniform errors. These are real limitations but they are secondary. In particular, because Smolyak and least squares are both linear in the data, a constant rescaling of a test function cannot change which method has smaller relative error; so the 'wrong scaling' caveat does not by itself threaten the ranking. What does threaten the ranking is the absence of any repeated random draws. The random LS points are the only stochastic input that affects the methods asymmetrically, and the paper provides no evidence that the single fixed realization is typical. This matters most at scale 1 and 2 in high dimensions, where the number of random points is only about twice the dimension of the polynomial space and the theoretical guarantees for iid points require logarithmic oversampling. The proposed concrete check—re-running the high-dimensional experiments with multiple seeds—is straightforward, feasible with the provided code, and would settle whether the observed advantage persists. Since the paper already received a CONDITIONAL verdict, and the concern is a fixable empirical robustness gap rather than a demonstrated error, I recommend keeping the verdict unchanged: the claims should be conditional on confirmation across independent point-set realizations.","tokens_in":24760,"tokens_out":11747,"duration_ms":145555,"concrete_test":"Using the public ApxKit repository, rerun the Section 4.4 high-dimensional protocol (d = 20, 50, 100; scales k = 1 and 2; the same nine test families and Q = 50 parameter draws) for R = 20 independent seeds of the LS point sets, keeping Smolyak and the test points fixed. For each seed compute the ratio r = ewc(SA)/ewc(LS-best), where LS-best is the better of LS-uniform and LS-Chebyshev, and also record the ratio for each LS variant separately. Report the median ratio and the fraction of seeds with r > 1 per family. If for any family the fraction is below 0.9 or the median ratio is at most 1, the 'clear superiority' claim is not robust to the random point set; if the fraction is near 1 with stable ratios, the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central contribution is empirical: LS with only 2N random points is claimed to match Smolyak in low dimensions and to be clearly superior in high dimensions. The theoretical results in Section 3 (e.g., Theorem 7) guarantee performance with high probability only when the number of samples grows like n log n, so the 2N regime used in the experiments is not covered by a probabilistic guarantee. The experiments are therefore the only evidence for the headline claim. Section 4.1 states that the random points are 'generated only once and then fixed for the rest of the simulation', with no seed reported and no averaging over point sets. Consequently, every LS entry in Tables and Figures 6–10 is a single draw. At scale 1 and high dimension, LS uses only about twice the number of basis functions (e.g., roughly 400 points and 200 basis functions at d=100); the condition of the design matrix and the resulting least-squares error can vary significantly between draws. If the original draw is atypical, the reported 'clear superiority' at scales 1 and 2 could shrink, disappear, or even reverse. The body's own caveat in Section 4.4 about 'wrong' scaling does not resolve this: a constant scaling of a test function multiplies the error of all three linear methods by the same factor and cannot flip a relative ranking. The missing statistical replicates are the real gap.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper revisits the influential comparison of Barthelmann, Novak, and Ritter (2000) and contrasts Smolyak interpolation on Chebyshev sparse grids (SA) with two least-squares variants that use 2N(q,d) random points on the same polynomial space E(q,d): unweighted least squares with uniform random points (LS-uniform) and weighted least squares with points drawn from the Chebyshev density (LS-Chebyshev). The authors survey known theoretical bounds, discuss the gap between available probabilistic guarantees (which require n log n samples) and their 2N sampling regime, and report numerical experiments on nine benchmark families for dimensions up to 100. Their main empirical claims are that at least one LS variant consistently matches SA in low dimensions, that LS is clearly superior to SA in high dimensions at small scales, and that LS is more stable under noisy data. The manuscript includes code and results on GitHub.","tokens_in":25022,"tokens_out":9230,"duration_ms":95051,"significance":"If the high-dimensional claim is robust, the paper has real practical significance: it suggests that simple random least squares with modest oversampling can outperform sparse-grid interpolation on smooth benchmark functions in high dimensions, a regime where sparse grids are often assumed to be the method of choice. The paper is also a useful service in that it repeats and extends the theoretical analysis of the BNR paper and makes all code and data publicly available, which strengthens reproducibility. The experimental protocol is internally consistent: all three methods are evaluated on the same test points and the same random functions, and the theoretical gap between the 2N sampling regime and the n log n guarantees is stated honestly. The significance is conditional, however, because the headline high-dimensional conclusion rests on a single random realization of the LS point sets and on only two small scales, so the statistical robustness of the 'clear superiority' claim is not yet established.","major_comments":[{"comment":"The central empirical claim that LS with only 2N(q,d) random points matches or beats Smolyak's N(q,d)-point interpolant rests on a single random realization of the LS point set for each (q,d). Section 4.1 states that 'these random points are generated only once and then fixed for the rest of the simulation', and no random seed is reported. Theorem 7, the only probabilistic guarantee quoted in the paper, applies to b n log(n) iid points; the 2N regime is exactly the regime where no such guarantee is available. A single atypical draw of the design matrix, for example one with a large condition number, could change the rankings in Figures 6-10. The paper should repeat each high-dimensional experiment over several independent point-set draws and report the spread (minimum/median/maximum or boxplots), and it should report seeds for full reproducibility.","section":"§4.1 and §3 (Theorem 7)"},{"comment":"The high-dimensional conclusion is based on scales k=1 and k=2 only, and the paper presents selected figures rather than complete tables for d>10. Because the headline 'clear superiority' claim is specifically about high dimensions, the authors should either provide aggregate statistics over all nine function families and all d (for example, the number of families in which each method attains the smallest ewc_max and ewc_mean as a function of d) or state explicitly that the conclusion is limited to these two small scales. As written, the conclusion is drawn largely from visual inspection of a subset of the data.","section":"§4.4"},{"comment":"The authors themselves flag that the large high-dimensional errors 'may be caused by a wrong scaling (in d) of the test functions'. A constant scaling per function cannot change the relative ranking of the three methods, so this caveat does not invalidate the internal comparison. However, several families (Discontinuous, Ridge Product, and Oscillatory) produce errors that grow exponentially with d, and the resulting comparison may reflect the benchmark design more than the typical behavior of the algorithms. The paper should either normalize the test functions (for example, to unit sup-norm or unit L2-norm) or justify explicitly why the chosen parameter scaling is representative for the claimed high-dimensional superiority.","section":"§4.4 and §4.2"}],"minor_comments":[{"comment":"The captions for the scale-1 panels read 'points LS = 2 N(q + 1, d)', which appears to be a typo for '2 N(d + 1, d)'; the scale-2 panels have the analogous issue.","section":"Figures 6-8"},{"comment":"The sentence 'with Q = 50 random functions g1, ..., gQ from each class by choosing corresponding parameters c, w ~ U[0,1]^d and rescale such that ||c||_1 = d' is grammatically incomplete and does not specify whether w is also rescaled; please clarify.","section":"§4.1"},{"comment":"The sentence 'In high dimensions, however, LS-uniform seems to be more stable than LS-Chebyshev. This is to be understood theoretically.' appears to be missing a verb; it should read 'This remains to be understood theoretically' or similar.","section":"§4.5"},{"comment":"There is a typo in 'we only discuss one part on the story here', which should be 'one part of the story here'.","section":"§3"}],"recommendation":"major_revision","confidential_remarks":"The paper is essentially an empirical study without new theorems; whether that fits the journal is an editorial question, but for a math.NA venue the systematic comparison is valuable and the theoretical discussion is competent. The main concern is statistical: the high-dimensional claim depends on a single realization of random LS points, and the 2N regime is outside the quoted probabilistic guarantees. I would advise the editor that the paper should not be accepted until the authors provide repeated-seed experiments or a clear argument that the single realization is representative. The 'wrong scaling' caveat is not fatal for the internal comparison, but it should be addressed by normalization or a more careful benchmark justification."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a useful and honest numerical comparison, but the abstract's \"clear superiority\" claim in high dimensions rests on a single fixed random point set per setting, so I would treat it as a preliminary observation until repeated draws back it up.\n\nWhat's new: a systematic comparison of Smolyak's algorithm against unweighted LS-uniform and weighted LS-Chebyshev on nine benchmark families up to d=100, with code on GitHub. The authors correctly note they know of no prior study of this kind. The protocol is fair: all methods use the same polynomial space, shared test points, and LS gets 2N points versus N for Smolyak. The low-dimensional results (d≤10, scales 1–9) are the strongest part; they show LS-Chebyshev often matches or beats Smolyak, while LS-uniform tends to struggle at larger scales. That is a useful data point for practitioners.\n\nThe soft spot is the high-dimensional section. Only scales 1 and 2 are tested, and each LS random point set is generated once and never varied. No seed is reported, and there is no averaging over draws. In the 2N oversampling regime, the known theory (Theorem 7) guarantees high-probability performance only with n log n samples, so the experiments are the only support for the headline. At d=100, scale 1, we are talking about roughly 400 points for a 200-dimensional space; a single unrepresentative draw could shift the rankings. The stress-test point about the \"wrong scaling\" caveat is also correct: a constant scaling multiplies every method's error by the same factor, so it cannot explain LS beating Smolyak. That caveat belongs in the paper but does not soften the comparison.\n\nThe body is more measured than the abstract: the bullet list says \"one LS method is as good as SA\" and LS \"often outperforms a lot,\" which is fine. I would ask the authors to either add several seeds with error bars or explicitly frame the high-dimensional results as single-realization evidence. The code is there, so this is an easy revision.\n\nWho will get value: anyone working on high-dimensional polynomial approximation or surrogate modeling. It deserves a serious referee; the missing statistical replication is a fixable gap, not a fatal one.\n\nMy recommendation: engage, but require the replication or a softened claim before acceptance.","headline":"Useful benchmark showing LS often matches Smolyak, but the high-dimensional 'clear superiority' claim needs seeds and repeated draws before it can be trusted.","tokens_in":25556,"tokens_out":2433,"would_cite":false,"duration_ms":25392,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["41A10","41A63","65D05","65D15"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper's central claim: least-squares on random points, with twice as many samples as Smolyak's sparse grid, matches its accuracy in low dimensions and clearly beats it in high dimensions on the tested benchmark families.","keywords":["polynomial approximation","sparse grids","Smolyak's algorithm","least squares","random sampling","high-dimensional approximation","Chebyshev polynomials","benchmark functions"],"falsifier":"Re-run the same pipeline with many independent point-set draws for each $q$ and $d$, say 100 seeds, and compare the distribution of least-squares errors against Smolyak's error; if under a majority of draws least squares fails to match Smolyak in high dimensions, the paper's 'clear superiority' claim would not survive.","tokens_in":24544,"feed_emoji":"🎲","tokens_out":6612,"duration_ms":73079,"temperature":0.7,"pith_summary":"The paper tries to establish that a conceptually simple least-squares estimator based on random points can replace interpolation on sparse grids (Smolyak's algorithm) for high-dimensional polynomial approximation, without losing accuracy. Both methods project onto the same polynomial space $E(q,d)$, but the least-squares methods use twice as many samples, drawn once from the uniform or Chebyshev distributions. On nine benchmark families in dimensions up to 100, at least one least-squares variant matches Smolyak in low dimensions, and in high dimensions it is often much better. The practical stakes are that random points are easy to generate in any dimension, while constructing sparse grids of prescribed cardinality is more involved, and Smolyak's method itself is not the winner in the tested high-dimensional regime.","feed_headline":"Random-point least squares beats sparse grids in high dimensions","feed_subtitle":"Even with only twice as many samples, least squares matches Smolyak's accuracy and wins as dimension grows.","key_machinery":"The load-bearing objects are the Smolyak space $E(q,d)$ from Proposition 3, the space of polynomials exactly reproduced by Smolyak's algorithm, and the two least-squares estimators (6) and (7) that project the same function onto that space from $2N(q,d)$ independent random points, uniformly distributed or sampled with the tensorized Chebyshev density. The comparison metric is the worst-case error over $Q = 50$ random instances of each benchmark family, estimated at $M$ fresh uniformly distributed test points as a maximum absolute deviation and a root-mean-square deviation. The random point sets are generated once for each $q$ and $d$ and then fixed for the whole simulation.","core_discovery":"The paper's central claim is that Smolyak's algorithm is not the method of choice for moderate-scale polynomial approximation in high dimensions. With $n = 2N(q,d)$ random sample points, the plain least-squares projection onto the same polynomial space $E(q,d)$ that Smolyak uses exactly reproduces matches or beats Smolyak's $N(q,d)$-point interpolant across all nine benchmark families, and in dimensions roughly 11 through 100 the advantage is often large, especially for the unweighted LS-uniform variant. The paper presents this as an experimental finding, extending the classical theory of sparse-grid interpolation from the earlier literature, and explicitly notes that the observed performance is not yet supported by matching theoretical error bounds.","pith_inferences":["Extension: The paper's results invite the open conjecture that $2N(q,d)$ iid random points, possibly with Chebyshev weights, are enough for least squares to match Smolyak's error on the class $F_d^s$; proving this would likely require a uniform-norm discretization that avoids the current $\\sqrt{n}$ loss.","Extension: The same experimental template could test whether deterministic low-discrepancy point sets preserve the high-dimensional least-squares advantage, which would separate the effect of randomness from the effect of point-set geometry.","Extension: If the high-dimensional least-squares advantage generalizes beyond these benchmark families, it weakens the practical case for sparse-grid interpolation in very high dimensions where only small scales are affordable, shifting attention to solving the underlying least-squares systems efficiently."],"forward_implications":["For a practitioner, the comparison says that using twice as many random points as sparse-grid points is enough to match sparse-grid accuracy, with no need for nested point sets or a prescribed grid structure.","In high dimensions (roughly $d \\ge 11$ up to 100), the unweighted uniform least-squares variant is often the best of the three methods, so a simple iid uniform sampling rule can replace carefully chosen interpolation nodes.","Smolyak's method remains much cheaper per run; least squares needs a large dense linear solve, so the accuracy advantage comes with a serious runtime and memory price.","When the data is contaminated by noise, least squares is more stable than Smolyak interpolation, with LS-uniform gaining stability in high dimension and LS-Chebyshev in low dimension."],"supporting_citations":[{"why":"Defines Smolyak's algorithm, its exactness space $E(q,d)$, and the error bounds that this paper extends and compares against.","marker":"[3]"},{"why":"Supplies the theoretical result that iid random points with suitable weights achieve optimal $L_2$-approximation rates, which motivates the least-squares estimators.","marker":"[35]"},{"why":"Provides the dimension count $N(q,d)$ that fixes the sample budget for both methods and identifies $E(q,d)$ with the relevant frequency set.","marker":"[41]"},{"why":"Gives the theory of optimal weighted least squares with the Chebyshev density, which underlies the LS-Chebyshev method.","marker":"[14]"},{"why":"Proves existence of point sets of size $4n$ that are good for approximation in all $L_p$ norms, serving as the theoretical anchor for least-squares recovery.","marker":"[32]"},{"why":"Supplies the benchmark test-function families on which the numerical comparison is based.","marker":"[48]"}],"fun_headline_variants":["Random-point least squares beats Smolyak in high dimensions","Double-sampled least squares outperforms Smolyak for large d","In high dimensions, random points outclass sparse grids","Smolyak falls behind least squares when dimension rises"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The one fixed random point set used for each $q$ and $d$ is typical, with no reported seed and no averaging over draws, so the observed least-squares advantage could in principle be an artifact of unrepresentative point sets.","fun_headline_variants_meta":{"raw":{"variants":["Random-point least squares beats Smolyak in high dimensions","Double-sampled least squares outperforms Smolyak for large d","In high dimensions, random points outclass sparse grids","Smolyak falls behind least squares when dimension rises"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000283,"raw_usage":{"total_tokens":1602,"prompt_tokens":807,"completion_tokens":795,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":423,"completion_tokens_details":{"reasoning_tokens":727}},"tokens_in":423,"tokens_out":795,"duration_ms":9253,"temperature":1.0,"reasoning_tokens":727,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T21:25:47.912424+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Re-run the same pipeline with many independent point-set draws for each $q$ and $d$, say 100 seeds, and compare the distribution of least-squares errors against Smolyak's error; if under a majority of draws least squares fails to match Smolyak in high dimensions, the paper's 'clear superiority' claim would not survive.","supporting_citations":[{"cited_title":"Cohen, G","cited_arxiv_id":null,"evidence_quote":"Gives the theory of optimal weighted least squares with the Chebyshev density, which underlies the LS-Chebyshev method."},{"cited_title":"Krieg, K","cited_arxiv_id":null,"evidence_quote":"Proves existence of point sets of size $4n$ that are good for approximation in all $L_p$ norms, serving as the theoretical anchor for least-squares recovery."},{"cited_title":"Surjanovic and D","cited_arxiv_id":null,"evidence_quote":"Supplies the benchmark test-function families on which the numerical comparison is based."}],"review_version":1}