{"id":"e0b17d9b-e077-4a26-8f23-59187420b3c3","arxiv_id":"2508.08683","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":5.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":1,"one_line_summary":"HeteroChebtrunc approximates functions from heteroskedastically noisy samples with a provably tighter infinity-norm error bound than NoisyChebtrunc at roughly linear cost.","lead":"This paper describes a faster algorithm, HeteroChebtrunc, for reconstructing a function from noisy samples when the noise level varies across the domain, and claims a provably better worst-case error than the existing NoisyChebtrunc method. A numerical analyst would read it for the new high-probability error bound and for a reusable lemma on how well sample variances are estimated.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The tighter-bound result depends on a uniform plug-in variance estimate; the sampling model and the N_hat scaling needed for that estimate are unspecified, so the central guarantee is not yet checkable.","rationale":"The reader's weakest assumption was that variance estimates concentrate uniformly near sigma(x)^2; I agree this is the fragile bridge. I sharpen it to two concrete, checkable requirements: pointwise identifiability of sigma(x)^2 given the sampling design, and the N_hat/log N scaling needed for a uniform union bound. The corrupted body makes it impossible to resolve whether the paper addresses these, so the correct verdict remains UNVERDICTED. I do not move to REJECT because the abstract-level claim is plausible and the failure modes I identify are standard conditions a careful paper would state explicitly once the text is readable. The concern is not about novelty or consensus, but about whether the theorem's hypotheses cover the actual plug-in procedure.","tokens_in":14932,"tokens_out":4708,"duration_ms":59871,"concrete_test":"Reconstruct the variance-estimation lemma and the HeteroChebtrunc error theorem from the original PDF, then re-derive the sup-norm bound with estimated variances in place of true sigma^2. Specifically check: (1) what sampling model supplies multiple observations for each estimated variance; (2) whether the proof's high-probability event requires |hat_sigma_i^2/sigma_i^2 - 1| <= eps for all i=0..N; and (3) whether the resulting failure probability and N_hat growth are compatible with the stated O(N + N_hat log N_hat) complexity. If the variance estimate has bias or requires N_hat >= C log N, the claimed tighter bound and complexity both need qualification.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The abstract claims HeteroChebtrunc beats NoisyChebtrunc in sup-norm with high probability under heteroskedastic noise, and separately claims a high-probability relative-error bound for the sample variance estimator. The second claim is load-bearing: the algorithm must plug variance estimates into its weights. Two conditions are needed for that bridge to work, and neither is stated in the abstract. First, sigma(x)^2 must be estimable pointwise from the sampling model. If the model is N+1 independent observations with one sample per design point, a sample variance at a single x_i does not exist; one would need repeated measurements, local binning, or residual-based estimates, each of which introduces bias or dependence not covered by a generic subgaussian sample-variance lemma. Second, the plug-in weights must be uniformly good across all N points. A relative-error bound of the form |hat_sigma_i^2 / sigma_i^2 - 1| <= eps typically requires sigma(x) bounded away from zero and N_hat (or local sample size) growing at least logarithmically in N. The abstract only says N_hat << N; if the proof needs N_hat = Omega(log N / eps^2), the complexity claim is incomplete. Because the supplied body text is corrupted, the theorem statements and proofs cannot be inspected, so this is an unresolved gap rather than an observed contradiction.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes HeteroChebtrunc, a near-linear-time algorithm for approximating a function on [-1,1] from N+1 samples under heteroskedastic subgaussian noise. The abstract claims that, with high probability, HeteroChebtrunc attains a tighter infinity-norm error bound than NoisyChebtrunc, and that it runs in O(N + \\hat{N} log \\hat{N}) operations with \\hat{N} << N. A second, independent contribution is claimed: a high-probability non-asymptotic relative error bound for the sample variance estimator of subgaussian variables. The provided full text is almost entirely corrupted (mojibake), so no theorem statement, proof, assumption, algorithm description, or experimental protocol can be inspected. This report can therefore only assess the abstract and the overall structure of the submission.","tokens_in":15253,"tokens_out":4268,"duration_ms":43507,"significance":"If the claims are correct, the paper would fill a real gap: an O(N log N) algorithm with a rigorous uniform error guarantee for heteroskedastic function approximation is not currently standard, and the sample-variance concentration result would be of independent interest in high-dimensional probability. The claimed complexity and the explicit comparison against NoisyChebtrunc are concrete and falsifiable. However, the current copy gives the referee no accessible derivations, no stated assumptions, no reproducible code, and no machine-checked proofs. The central technical content is therefore unverifiable as submitted. The contribution is potentially significant, but the manuscript in its present form cannot be evaluated.","major_comments":[{"comment":"The body of the manuscript is mojibake: no theorem, lemma, proof, or assumption can be read. This is the primary load-bearing problem. The abstract's claims are not self-evident; they depend on nontrivial high-dimensional probability arguments, on the precise definition of HeteroChebtrunc, and on the dependence of the error bound on \\hat{N}. A resubmission must contain a readable, complete version so that the proofs can be checked.","section":"Full text (corrupted)"},{"comment":"The sampling model for variance estimation is unspecified. The abstract says the method uses heteroskedastic variances \\sigma(x)^2, and the claimed comparison must involve plug-in variance estimates. But if the data are N+1 independent observations with one observation per design point, a pointwise sample variance at x_i does not exist. The paper needs to state whether repeated measurements, local binning, residual-based estimates, or another model is used. Without this, the high-probability relative error bound for the sample variance estimator has no domain of applicability. No such statement is visible in the provided copy.","section":"Abstract"},{"comment":"The tighter infinity-norm bound requires the estimated variances to be uniformly close to the true variances at all N nodes. A relative-error bound of the form |\\hat{\\sigma}_i^2/\\sigma_i^2 - 1| \\le \\epsilon typically requires \\sigma(x) to be bounded away from zero and the local sample size / \\hat{N} to grow at least logarithmically in N. The abstract states only \\hat{N} << N. If the proof requires \\hat{N} = \\Omega(\\log N / \\epsilon^2), then the complexity claim O(N + \\hat{N} \\log \\hat{N}) is incomplete without stating that scaling. The theorem statement must make this dependence explicit.","section":"Abstract"},{"comment":"The comparison against NoisyChebtrunc is not well defined in the material available. NoisyChebtrunc is an external baseline; the claim that HeteroChebtrunc yields a 'tighter infinity-norm error bound' requires specifying whether NoisyChebtrunc receives the same samples, whether it uses known or estimated variances, and whether the comparison is of high-probability bounds or of realized errors. If NoisyChebtrunc is prior work by the same authors, the comparison is self-relative unless the baseline is precisely fixed. The corrupted text does not allow this to be checked.","section":"Abstract"},{"comment":"The numerical experiments cannot be assessed: figure and table captions, axis labels, and the experimental protocol are unreadable in the provided copy. The claimed 'improved uniform error' needs reproducible experiments with stated error metrics, baselines, and parameter choices (including the choice of \\hat{N}). Without these, the empirical support is not checkable.","section":"Full text (figures/tables)"}],"minor_comments":[{"comment":"The phrase 'an O(N log N) algorithm for this problem has not yet been found in the current literature' is a strong claim. It should be supported by a citation or a focused literature discussion.","section":"Abstract"},{"comment":"The text contains an unrelated line 'arXiv:2508.08685v1 [cs.CV] 12 Aug 2025'. This appears to be a leftover from another document and should be removed.","section":"Title page/full text"},{"comment":"The parameter \\hat{N} is introduced without a definition. Its role as a truncation parameter and its relationship to the approximation space should be defined in the introduction.","section":"Abstract"},{"comment":"All figure and table captions should be restored in the resubmission; the current copy does not permit even a qualitative reading of the experiments.","section":"Full text (captions)"}],"recommendation":"major_revision","confidential_remarks":"The central obstacle is the corrupted file; if a clean, complete version is provided, the technical concerns listed above can be checked. The paper should also clarify the provenance of NoisyChebtrunc: if it is the authors' own prior algorithm, the contribution should be framed as an incremental improvement and the comparison should include independent baselines where possible."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The one thing you should know: this paper has a plausible and potentially useful abstract, but the copy I have is heavily corrupted — the body is mojibake, so I can only judge the claims, not the math. That limits everything below.\n\nWhat it's claiming is reasonable. HeteroChebtrunc is an adaptation of NoisyChebtrunc, with a high-probability sup-norm bound tighter than the original under heteroskedastic noise, in O(N + N_hat log N_hat) time. There's also a separate non-asymptotic relative-error bound for sample variance of subgaussian variables, which sounds like it could be a genuinely reusable side result. If those proofs are right, it's a solid incremental contribution to a real problem: I don't know of many near-linear-time algorithms for heteroskedastic function approximation, and the abstract's claim that this is missing from the literature is credible, though I can't audit the related work from the corrupted text.\n\nThe main soft spot is exactly the one the stress-test flags: the algorithm needs to know or estimate sigma(x)^2 pointwise, and the abstract doesn't say how the sampling model supports that. If you only get one observation at each x_i, a pointwise sample variance doesn't exist — you need repeat measurements, local binning, or residual-based estimates, and each of those introduces bias or dependence that a generic subgaussian variance lemma won't cover. The abstract also only says N_hat << N; if the proof requires N_hat = Omega(log N / eps^2) for uniform variance estimates, the complexity claim is incomplete. This isn't a contradiction I've found, because I can't read the theorem statements, but it's a load-bearing gap in what the abstract advertises.\n\nThere's also a strange artifact: the full text embeds an arXiv header for a different paper ID under cs.CV, which might be a PDF extraction glitch but is worth flagging before taking the paper at face value.\n\nBottom line: this is a paper I'd want to read properly, but not one I can rely on yet. If a clean PDF surfaces, it deserves serious referee time — the claims are specific, the algorithm is well-defined in principle, and the variance lemma could be worth citing. Right now, I'd hold off citing it and would not bring it to reading group until the authors fix the PDF. My recommendation: get an intact version and send it to peer review, but with a warning that the sampling-model assumptions need to be explicit.\n\nFor me: would_accept_peer_review yes, would_cite false until I see the proof, serious_thinker unclear because the text is unreadable.","headline":"Abstract-level claim is plausible but the body is unreadable (mojibake), so I can't vouch for the proof; the variance-estimation bridge is the key unverified spot.","tokens_in":15730,"tokens_out":2159,"would_cite":false,"duration_ms":25325,"reading_group":"maybe","serious_thinker":"unclear","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65D15","41A10"],"pacs":[],"model":"deepseek-v4-flash","headline":"A new Chebyshev-based algorithm, HeteroChebtrunc, provably attains a tighter infinity-norm error bound than NoisyChebtrunc when noise levels vary with position, in near-linear time.","keywords":["heteroskedastic noise","function approximation","Chebyshev interpolation","infinity-norm error","sample variance estimation","subgaussian concentration","near-linear-time algorithm","NoisyChebtrunc"],"falsifier":"Run HeteroChebtrunc and NoisyChebtrunc on the same smooth $f$ with $N+1$ samples where $\\sigma(x)^2$ is, say, $10^6$ times larger on a small subinterval than elsewhere; repeat for many noise draws and growing $N$. If HeteroChebtrunc's empirical $\\|\\cdot\\|_\\infty$ error beats NoisyChebtrunc's with probability that does not approach 1, or if its runtime exceeds $O(N+\\hat{N}\\log\\hat{N})$ by a growing factor, the paper's central claim is falsified.","tokens_in":14825,"feed_emoji":"","tokens_out":6486,"duration_ms":69002,"temperature":0.7,"pith_summary":"The paper addresses a basic numerical problem: recover a function $f$ on $[-1,1]$ from $N+1$ noisy samples when the noise level $\\sigma(x)^2$ changes with location. Its proposed algorithm, HeteroChebtrunc, adapts the existing NoisyChebtrunc method to use local variance information instead of assuming constant noise. The central claim is that, with high probability over the noise draws, HeteroChebtrunc achieves a smaller worst-case, infinity-norm error than NoisyChebtrunc under heteroskedastic noise, while running in $O(N+\\hat{N}\\log \\hat{N})$ operations with $\\hat{N}\\ll N$. The proof relies on high-dimensional concentration of sample variance estimators for subgaussian noise, and this bound is presented as a standalone result of independent interest. If the paper is right, it closes the gap of a rigorous fast algorithm for heteroskedastic function approximation.","feed_headline":"HeteroChebtrunc beats NoisyChebtrunc when noise varies by position","feed_subtitle":"A variance-aware truncation method achieves tighter worst-case error with high probability—at almost the same cost.","key_machinery":"Chebyshev coefficient truncation weighted by per-location noise variance estimates, together with high-dimensional probability bounds on subgaussian sample variances. The variance concentration bound converts local knowledge of $\\sigma(x)^2$ into a global uniform error guarantee, and the truncation rule is what makes the improved infinity-norm bound possible.","core_discovery":"HeteroChebtrunc exploits the noise variance function $\\sigma(x)^2$ at the sample locations to make the Chebyshev coefficient truncation variance-aware, so high-noise samples have less influence on the reconstructed spectrum. The paper's main formal result is a high-probability infinity-norm error bound showing that this heteroskedastic-aware truncation is never worse, and is typically strictly better, than the constant-noise NoisyChebtrunc algorithm. A secondary result is a high-probability non-asymptotic relative error bound for the sample variance estimator of subgaussian variables; this concentration estimate is what lets the algorithm treat estimated variances as trustworthy, and the aut","pith_inferences":["The paper's fixed-grid analysis suggests a natural extension the authors do not pursue: allocate more samples where $\\sigma(x)^2$ is large, converting variance information into a sampling strategy rather than only a weighting strategy.","Because the error control rests on uniform concentration of sample variances, a challenging regime is noise that nearly vanishes on a large subinterval; there the variance estimate is relatively unstable, and the practical guarantee may need repeated samples at those points.","The variance-aware truncation idea should transfer to other orthogonal polynomial bases and domains, making heteroskedastic-aware spectral approximation a template beyond Chebyshev polynomials."],"forward_implications":["Any data source with known or reliably estimated per-location noise can use HeteroChebtrunc to get uniform-error guarantees at a cost dominated by reading the $N+1$ samples.","Heteroskedastic problems no longer have to default to constant-noise truncation: this method is asymptotic-cost-compatible with NoisyChebtrunc while promising a tighter worst-case error.","The standalone subgaussian sample-variance bound gives other algorithms a ready-made concentration tool for estimating noise levels at a point.","The parameter $\\hat{N}$ cleanly separates the arithmetic cost from the sample count: once samples are read, the computation scales with a much smaller chosen truncation parameter."],"supporting_citations":[],"fun_headline_variants":["HeteroChebtrunc tightens error when noise varies across samples","Variance-aware truncation beats constant-noise method for uneven noise","Exploit noise variance to sharpen function approximation error","HeteroChebtrunc: better worst-case error under heteroskedastic noise","New method uses noise variance to improve Chebyshev approximation"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"The central bound assumes the noise is independent and subgaussian with variance function $\\sigma(x)^2$ that is known or estimated well enough that every local variance estimate stays within a controlled factor of the truth; if that uniform concentration fails, the noise weights fed into the truncation are miscalibrated and the tighter error bound can break.","fun_headline_variants_meta":{"raw":{"variants":["HeteroChebtrunc tightens error when noise varies across samples","Variance-aware truncation beats constant-noise method for uneven noise","Exploit noise variance to sharpen function approximation error","HeteroChebtrunc: better worst-case error under heteroskedastic noise","New method uses noise variance to improve Chebyshev approximation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000753,"raw_usage":{"total_tokens":3182,"prompt_tokens":738,"completion_tokens":2444,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":482,"completion_tokens_details":{"reasoning_tokens":2353}},"tokens_in":482,"tokens_out":2444,"duration_ms":15958,"temperature":1.0,"reasoning_tokens":2353,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T21:24:36.823663+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run HeteroChebtrunc and NoisyChebtrunc on the same smooth $f$ with $N+1$ samples where $\\sigma(x)^2$ is, say, $10^6$ times larger on a small subinterval than elsewhere; repeat for many noise draws and growing $N$. If HeteroChebtrunc's empirical $\\|\\cdot\\|_\\infty$ error beats NoisyChebtrunc's with probability that does not approach 1, or if its runtime exceeds $O(N+\\hat{N}\\log\\hat{N})$ by a growing factor, the paper's central claim is falsified.","supporting_citations":[],"review_version":1}