{"id":"d76a8923-f494-4120-8da2-e6cf7c460dfe","arxiv_id":"2507.02215","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":1,"one_line_summary":"A two-stage least-squares algorithm combining Christoffel sampling with experimental-design-based allocation of repeated evaluations improves sample complexity for learning noisy conditional expectations.","lead":"This paper introduces a hybrid least-squares method that first picks evaluation points optimally, then allocates repeated noisy samples among those points to average out large noise. The method gives sample-complexity bounds that improve on standard randomized least squares, and the authors test it on synthetic functions and option pricing.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The known-σ assumption is the load-bearing hinge; the pilot-estimation analysis in Appendix B.3 leaves the near-zero-variance regime without a guarantee, so the practical improvement quantified in (5.5) is conditional on an unproven variance-estimation case.","rationale":"The reader's weakest_assumption identifies exactly the same soft spot: the central theorem assumes known σ, and the pilot-estimation guarantee in Appendix B.3 covers only subgaussian noise away from zero variance. I agree with that assessment. The central mathematical result, Theorem 5.1, appears correct: the allocation in Lemma 4.1 is the Neyman allocation for the variance sequence, the expectation computation in (5.3) is clean, and the comparison to Theorem 1.1 via (5.6) is valid. The reweighted case is honestly qualified by the J_n/δ OPT term and the discussion after Theorem 5.1. The extension to random subspaces is a separate contribution with its own proofs. The practical gap is real but explicitly acknowledged, and the paper provides a rigorous perturbation analysis in the regime it claims to cover. Since the central claim is for known σ and the practical limitation is clearly scoped, I do not think the verdict should change; the paper remains acceptable with the noted caveat. The proposed concrete test would clarify whether the near-zero-variance case is a genuine barrier or merely an unanalyzed edge case.","tokens_in":27435,"tokens_out":15782,"duration_ms":190660,"concrete_test":"Run the Section 7.1 synthetic experiment with σ(x) chosen to vanish or nearly vanish on a subregion, e.g., σ(x) = ε·dist(x, ∂Ω)^α with ε > 0 small, and compare HLS-1 using the oracle σ with HLS-1 using pilot estimates for R ∈ {10, 50, 200} at fixed L. Check whether the pilot estimates satisfy the relative-error bound (B.9) for a target κ = 0.2, and whether the MSE of pilot-based HLS-1 stays within the factor (1+κ)/(1−κ) of the oracle-σ HLS-1 predicted by Theorem B.1. If the relative-error condition fails or the MSE ratio exceeds the predicted factor, the unanalyzed near-zero-variance case is a real limitation of the practical sample-complexity claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 5.1, the paper's central claim, assumes the conditional variance σ²(x) is known exactly. The allocation p*n in (4.2) and the resulting complexity bound (5.5) are both computed from this σ, and the improvement over Theorem 1.1 is precisely the factor in (5.6) that follows from the Neyman allocation. For the practical Algorithm 5.1, σ is estimated from Rm pilot samples. The only rigorous guarantee for the estimated allocation is Theorem B.1, which requires the relative-error condition (B.9) for every i, and this condition is obtained from a uniform subgaussian assumption on ε(x)/σ(x) with R ≳ log m/κ². When σ is small at some design points, sample variance estimates can be zero or badly scaled, (B.9) is not guaranteed to hold, and the paper explicitly states that there is no rigorous analysis for that case. Since a misspecified σ directly changes the optimal allocation, the claimed sample-complexity gain in (5.5) may vanish or even reverse if the pilot estimates are unreliable in regions of small variance. The theory is sound when σ is given, but the practical deliverable's central advantage is only as secure as the variance-estimation step, which has a documented gap.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes a hybrid least-squares method for approximating a function f from noisy point evaluations y(x) = f(x) + ε(x). The method first draws m points from the Christoffel sampling measure associated with an n-dimensional approximation space V_n, then allocates a total budget L of noisy evaluations among these points according to a Neyman allocation (non-reweighted) or an A-optimal design (reweighted) that accounts for the conditional variance σ²(x). The main theoretical result, Theorem 5.1, gives conditional error bounds showing that the total evaluation budget L required to achieve error η is approximately n[log n + (noise factor)/η], where the noise factor is no larger than the corresponding factor in the standard Christoffel-sampled least squares bound (Theorem 1.1). The paper also extends the results to convexity-constrained approximation and to adaptively chosen random subspaces when f is the expectation of a random field, and it provides numerical experiments on a synthetic polynomial example and on basket option pricing in a Black–Scholes model.","tokens_in":27670,"tokens_out":19130,"duration_ms":200866,"significance":"The paper makes a worthwhile contribution to noisy function approximation. The two-stage idea of using Christoffel sampling for the design and experimental-design-based allocation for repeated evaluations is natural and is analyzed carefully. The proofs are detailed and largely self-contained: Lemma 4.1 rigorously identifies the cond²-approximate optimal allocation, Theorem 5.1 provides explicit error bounds with absolute constants, and the pilot variance estimation analysis in Appendix B.3 gives a concrete guarantee under a subgaussian assumption. The comparison with Theorem 1.1 is quantified through the ratio in (5.6), which is ≤ 1 by Jensen's inequality, and the numerical experiments support the theory. The main weakness is the reliance on known σ²(x) for the central theorem and the restricted conditions under which variance estimation is analyzed; the authors are transparent about this limitation, but it should be more prominently qualified in the main text.","major_comments":[{"comment":"The practical version of Algorithm 5.1 estimates σ²(x) from Rm pilot samples, and the only rigorous guarantee for this step is Theorem B.1, which requires the relative-error condition (B.9) for every i. This condition is derived under a uniform subgaussian assumption on ε(x)/σ(x) with R ≳ log m/κ². As the authors note at the end of Appendix B.3, when this assumption is violated (e.g., at points where σ(x) is very small and the noise is heavy-tailed), the sample variance can be zero or badly scaled and there is no rigorous analysis. Because the optimal allocations p*_n and q*_n are computed from the estimated variances, the sample-complexity improvement in (5.5) is not guaranteed in this regime. The abstract and Section 1.2 state the improvement without this caveat. I recommend either supplying a rigorous treatment of the small-variance case (for example, using a regularized variance estimator with a floor) or explicitly qualifying the claims in the main text so that the scope of the theoretical guarantees is clear.","section":"Appendix B.3, Theorem B.1"}],"minor_comments":[{"comment":"The sentence 'For HLS-1 and HLS-2. For each x, we estimate σ(x) from R = 50 MC simulations offline' contains an extra period after 'HLS-2'; it should read 'For HLS-1 and HLS-2, for each x, we estimate ...'.","section":"Section 7.1"},{"comment":"The bound '24√rτr+1' is ambiguous; it should be typeset as '24√(r τ_{r+1})' to clarify that the square root applies to the product r·τ_{r+1}.","section":"Theorem 6.3"},{"comment":"The constants c' and C1 are not explicitly related; the authors should state that C1 is chosen large enough (e.g., C1 ≥ 2c') so that the constructed function f_n lies in the sparse set \\bar{V}_{n,k}, as the proof relies on this implicitly.","section":"Proof of Theorem 6.3"},{"comment":"The total evaluation complexity L in (5.5) is stated for the case of known σ; a sentence noting that the pilot variance estimation cost Rm is additional (as quantified in Appendix B.3) would improve clarity, since the complexity comparison with Theorem 1.1 otherwise omits this overhead.","section":"Section 5.1, Equation (5.5)"}],"recommendation":"minor_revision","confidential_remarks":"The paper is technically sound and the central theoretical result (Theorem 5.1) is a solid contribution. The main point of contention is the gap between the known-σ theory and the practical variance estimation step; another referee might view this as a reason for major revision. I recommend the authors address the caveat clearly in the main text and consider a small numerical demonstration for non-subgaussian or near-zero-variance noise. The paper's scope fits well in a numerical analysis or scientific computing journal."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague, the key thing to know is that this paper's central claim holds up, but the practical headline is more conditional than the abstract suggests. The two-stage combination of Christoffel sampling for point placement and Neyman-style allocation of replicated evaluations is genuinely new, and Theorem 5.1 is a real result: with known conditional variance, the hybrid method beats the standard Christoffel-sampled least squares bound in the large-noise regime, and the computed expectation in (5.3) is clean. The proof route, subspace embedding from Cohen–Migliorati plus a bias–variance split, is standard and correct. The numerics, especially the basket-option example, support the comparisons; HLS-1 is a clear win over ERM in both accuracy and linear-algebra cost.\n\nThe soft spot is exactly the one your reader flagged. Theorem 5.1 assumes sigma is given. The practical Algorithm 5.1 estimates it with Rm pilot samples, and the only rigorous guarantee (Theorem B.1) needs the relative error bound (B.9) at every point, obtained from a uniform subgaussian assumption on epsilon/sigma. The paper explicitly says there is no rigorous analysis when the estimated variance is near zero. That matters because the complexity gain in (5.5) is driven by the Neyman allocation; if sigma is misspecified where it is small, the allocation is off and the gain is not guaranteed. This is a genuine gap, but it is in the practical deliverable, not in the conditional theory. It should be stated more prominently and, if possible, patched with a small-variance correction or a caveat.\n\nTwo minor points. First, the reweighted variant HLS-2 is only advantageous when the approximation bias OPT is sufficiently small; the paper is honest that the trade-off analysis is beyond scope, but that means the clean complexity comparison is for the non-reweighted variant only. Second, the random subspace results in Section 6 are plausible and Theorem 6.3's proof uses a standard truncation argument, but it is dense and could use a bit more exposition. No reproducibility red flags; no code is released, but the experiments are small and described in enough detail to reproduce.\n\nWho this is for: researchers in UQ and computational finance who need surrogates from noisy conditional-expectation simulators. It deserves a serious referee. I would send it to review, with the variance-estimation gap as a major comment and the HLS-2 scope as a minor one.","headline":"Solid new hybrid least-squares method; the main bound is correct, but the practical gain rests on a variance-estimation step that is only guaranteed under subgaussian assumptions away from zero variance.","tokens_in":28205,"tokens_out":3377,"would_cite":true,"duration_ms":35028,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65C05","65C60","65D15","62K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"A hybrid least-squares algorithm that combines Christoffel sampling with variance-aware allocation provably reduces the sample budget needed to learn functions from heavily noisy data.","keywords":["hybrid least squares","Christoffel sampling","optimal experimental design","noisy function approximation","conditional expectations","sample complexity","random subspaces","convexity constraints"],"falsifier":"On a problem with known heteroscedastic noise, compare the empirical MSE of HLS-1 with standard Christoffel-sampled least squares at a fixed total budget $L$ with $L/n$ large: if the MSE ratio does not approach $\\left\\|\\sigma\\sqrt{\\Phi_n/n}\\right\\|^2_{L^1_\\mu}/\\left\\|\\sigma\\sqrt{\\Phi_n/n}\\right\\|^2_{L^2_\\mu}$ or does not stay at or below one, the asymptotic efficiency claim in (5.5)--(5.6) is contradicted.","tokens_in":2035,"feed_emoji":"🎯","tokens_out":1973,"duration_ms":83475,"temperature":0.7,"pith_summary":"The paper studies least-squares approximation of a function $f$ from noisy point evaluations $y(x)=f(x)+\\varepsilon(x)$, where the noise may be large and spatially heterogeneous. It proposes a hybrid procedure: first use Christoffel sampling to choose $m$ sample points that keep the least-squares system well conditioned, then spend the remaining evaluation budget $L$ on repeated weighted Monte Carlo averages at those points, allocating replicates according to the local noise level. The main result is that this allocation makes large-noise learning cheaper: the total evaluations needed for target error $\\eta$ grow like $n\\log n$ plus a variance term that is never larger than the corresponding term in the standard Christoffel-sampled bound. The same two-step idea is extended to convexity-constrained approximations and to data-driven random subspaces, with numerical evidence on a synthetic problem and a basket-option pricing problem.","feed_headline":"Hybrid sampling cuts sample cost for noisy least squares","feed_subtitle":"Christoffel sampling plus variance-aware allocation resolves large noise with fewer evaluations than ordinary designs.","key_machinery":"The load-bearing object is the Christoffel function $\\Phi_n(x)=\\sum_{i=1}^n v_i(x)^2$ on an orthonormal basis of the approximation space $V_n$, which defines the induced sampling measure $\\nu(dx)=\\Phi_n(x)\\,d\\mu/n$ used to draw the $m$ sample points. On top of this, the allocation vector $$p^*_{n,i}=\\frac{w(x_i)\\$\\sigma$(x_i)\\sqrt{\\Phi_n(x_i)}}{\\sum_{j\\in[m]} w(x_j)\\$\\sigma$(x_j)\\sqrt{\\Phi_n(x_j)}}$$ assigns replicate samples proportionally to the local noise-variance contribution. The analysis is carried by the variance functional $G(p)=\\frac{1}{L}\\sum_{i=1}^m \\frac{w^2(x_i)\\sigma^2(x_i)\\Phi_n(x_i)}{m^2p_i}$: $p^*_n$ minimizes $G(p)$, and the closed-form expectation of the minimized value produces the sample-complexity formula.","core_discovery":"The paper's central result, Theorem 5.1, is that for the non-reweighted allocation $p^*_n$, the conditional expected squared error satisfies $$\\mathbb{E}_{X,y}\\big[\\|\\hat f-f\\|^2_{$L^{2}$_\\mu}\\mid A\\big] \\lesssim \\mathrm{OPT} + \\mathbb{E}_X[G(p^*_n)],$$ where $A$ is the event that the weighted design matrix has spectrum in $[0.9,1.1]$ and $$\\mathbb{E}_X[G(p^*_n)] = \\frac{n}{L}\\left[\\frac{1}{m}\\|\\$\\sigma$\\|^2_{$L^{2}$_\\mu} + \\left(1-\\frac{1}{m}\\right)\\left\\|\\$\\sigma$\\sqrt{\\Phi_n/n}\\right\\|^2_{$L^{1}$_\\mu}\\right].$$ Because $\\|\\sigma\\sqrt{\\Phi_n/n}\\|^2_{L^1_\\mu}/\\|\\sigma\\sqrt{\\Phi_n/n}\\|^2_{L^2_\\mu}\\le 1$, the implied total budget for error $\\eta\\ge\\mathrm{OPT}$ is asymptotically at least as efficient as the standard bound $L \\sim n\\max\\{\\log n, \\|\\sigma\\|^2_{L^2_\\nu}/\\eta\\}$. The paper also treats a reweighted allocation $q^*_n$ based on A-optimal design, shows that projecting onto a closed convex set preserves the error bounds up to a factor of two, and proves approximation-capacity results for random subspaces built from evaluations of the random field defining $f$.","pith_inferences":["The allocation $p^*_n$ is essentially a variance-proportional design, so the same two-stage idea could be applied to other estimators where replicate sampling at selected points is cheaper than drawing new design points; the paper does not explore such generalizations.","The efficiency gain is largest when the noise variance is concentrated at points where $\\sigma(x)\\sqrt{\\Phi_n(x)}$ is large relative to the sampling density; mapping this condition on the domain could lead to a priori rules for when hybrid sampling helps.","For near-zero variance regions, the paper's pilot estimator can return zero variance and the guarantees are not covered; a shrinkage or regularized variance estimate could fill this gap and is a natural testable extension.","The random-subspace analysis assumes subgaussian Karhunen-Lo\\`eve coefficients; a heavy-tailed generalization would broaden the applicability to more realistic stochastic processes and would be a direct follow-up."],"forward_implications":["For a target error $\\eta$, the hybrid method needs $L \\sim n\\log n + \\frac{n}{\\eta}\\left(\\frac{1}{m}\\|\\sigma\\|^2_{L^2_\\mu} + (1-1/m)\\left\\|\\sigma\\sqrt{\\Phi_n/n}\\right\\|^2_{L^1_\\mu}\\right)$ total evaluations, matching the noiseless $n\\log n$ count when noise is small.","Compared with standard Christoffel-sampled least squares, the large-noise regime is improved: the variance factor is asymptotically no larger than the standard $\\|\\sigma\\|^2_{L^2_\\nu}$ factor, so the method is never worse and can be better.","The reweighted allocation $q^*_n$ can reduce variance further when the approximation space $V_n$ is highly expressive, at the cost of amplifying the oracle bias by a factor that depends on the regularization parameter $\\delta$.","Convexity constraints, such as preserving positivity of a financial pricer, can be enforced by post-projection with the same theoretical guarantees up to a constant factor.","When $f$ is the expectation of a random field, random subspaces spanned by field realizations give provable approximation capacity, including a bound that depends on tail decay of the covariance eigenvalues."],"supporting_citations":[{"why":"Supplies the Christoffel-sampling subspace-embedding result used in the proof of Theorem 5.1.","marker":"[11]"},{"why":"Establishes the stability decomposition for noiseless least-squares approximation that underlies the oracle error term.","marker":"[10]"},{"why":"Introduces the Christoffel-function-weighted least-squares sampling design used in the first step of the hybrid algorithm.","marker":"[29]"},{"why":"Provides the A-optimality criterion that motivates the reweighted allocation problem.","marker":"[37]"},{"why":"Gives the boosting procedure used to keep the weighted design matrix well conditioned in the numerical experiments.","marker":"[17]"},{"why":"Supplies the discrete Christoffel sampling strategy used when the subspace is built from random field evaluations.","marker":"[4]"},{"why":"Provides the random-basis approximation estimate that Theorem 6.1 extends.","marker":"[38]"},{"why":"Matrix concentration inequality used to control the smallest eigenvalue in the random-subspace analysis.","marker":"[41]"}],"fun_headline_variants":["Noisy data? Hybrid least squares learns with fewer samples","Christoffel sampling plus optimal design beats noise","Hybrid scheme reduces sample complexity for noisy fitting","Efficient function recovery from heavily polluted data","Smart sampling strategy for least squares under noise"],"cache_read_input_tokens":30336,"weakest_assumption_plain":"The guarantees require that the conditional variance $\\sigma^2(x)$ be known or estimated accurately enough to set the allocations; if the pilot variance estimates are badly off, or if $\\sigma$ vanishes at sampled points, the computed allocations are miscalibrated and the stated sample-complexity improvement is not assured.","fun_headline_variants_meta":{"raw":{"variants":["Noisy data? Hybrid least squares learns with fewer samples","Christoffel sampling plus optimal design beats noise","Hybrid scheme reduces sample complexity for noisy fitting","Efficient function recovery from heavily polluted data","Smart sampling strategy for least squares under noise"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000591,"raw_usage":{"total_tokens":2808,"prompt_tokens":1021,"completion_tokens":1787,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":637,"completion_tokens_details":{"reasoning_tokens":1716}},"tokens_in":637,"tokens_out":1787,"duration_ms":15287,"temperature":1.0,"reasoning_tokens":1716,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T20:36:40.279792+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a problem with known heteroscedastic noise, compare the empirical MSE of HLS-1 with standard Christoffel-sampled least squares at a fixed total budget $L$ with $L/n$ large: if the MSE ratio does not approach $\\left\\|\\sigma\\sqrt{\\Phi_n/n}\\right\\|^2_{L^1_\\mu}/\\left\\|\\sigma\\sqrt{\\Phi_n/n}\\right\\|^2_{L^2_\\mu}$ or does not stay at or below one, the asymptotic efficiency claim in (5.5)--(5.6) is contradicted.","supporting_citations":[{"cited_title":"Cohen and G","cited_arxiv_id":null,"evidence_quote":"Supplies the Christoffel-sampling subspace-embedding result used in the proof of Theorem 5.1."},{"cited_title":"Cohen, M","cited_arxiv_id":null,"evidence_quote":"Establishes the stability decomposition for noiseless least-squares approximation that underlies the oracle error term."},{"cited_title":"Narayan, J","cited_arxiv_id":null,"evidence_quote":"Introduces the Christoffel-function-weighted least-squares sampling design used in the first step of the hybrid algorithm."},{"cited_title":"Pukelsheim, Optimal design of experiments , SIAM, 2006","cited_arxiv_id":null,"evidence_quote":"Provides the A-optimality criterion that motivates the reweighted allocation problem."},{"cited_title":"Haberstich, A","cited_arxiv_id":null,"evidence_quote":"Gives the boosting procedure used to keep the weighted design matrix well conditioned in the numerical experiments."},{"cited_title":"Adcock and J","cited_arxiv_id":null,"evidence_quote":"Supplies the discrete Christoffel sampling strategy used when the subspace is built from random field evaluations."},{"cited_title":"Rahimi and B","cited_arxiv_id":null,"evidence_quote":"Provides the random-basis approximation estimate that Theorem 6.1 extends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Matrix concentration inequality used to control the smallest eigenvalue in the random-subspace analysis."}],"review_version":1}