{"id":"7a8c155e-a0a1-40d1-a040-5f0387a09c1c","arxiv_id":"2501.05425","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"An efficient algorithm estimates the common mean of high-dimensional Gaussians under the subset-of-signals model with error equal to the one-dimensional optimal rate plus the standard sub-Gaussian rate, up to polylog factors.","lead":"This paper presents a new algorithm for estimating a common mean from high-dimensional Gaussian samples with unknown and varying noise levels, where only an unknown fraction of samples have bounded noise. The method is the first to achieve near-optimal accuracy efficiently in this setting, and could inform how noisy data from many sources is combined.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Claim 6.3 undercounts datasets: TournamentImprove's two batches are drawn in every RecursiveEstimate call, including base cases, so actual t = 2 + 3r(m+1); the N-sample budget is exceeded as proven.","rationale":"I reviewed the algorithm and proof with the reader's concern in mind. The reader's weakest_assumption is precise: Claim 6.3's dataset count omits the two batches drawn by TournamentImprove in every RecursiveEstimate call, including the base case. I confirmed this by tracing Algorithm 4: Line 5 draws one batch, Line 7 invokes Lemma 4.2 which draws two batches, and this happens before the dimension test in Line 8. Since each outer iteration spawns a chain of m+1 RecursiveEstimate calls, the per-iteration batch count is 3(m+1), not the 3m+1 implied by Claim 6.3. The discrepancy is not a constant factor: for m=1 it is 6r+2 vs 3r+3, so for r=20 the algorithm would need 122 batches of size N/63, i.e., about 1.94N samples. This exceeds the N-sample model, so Theorem 1.2 is not established as written. The gap is likely repairable by enlarging t and absorbing polylog factors; indeed Claim 6.2 should still hold for sufficiently large C in the log^C condition. I do not see a deeper conceptual flaw: the rejection-sampling bias analysis, subspace identification, and inductive error accumulation are coherent, and the parameter count is zero (no heavy numerical constants). The reader's CONDITIONAL verdict is appropriate; my concern is the same and does not move the verdict.","tokens_in":37830,"tokens_out":9989,"duration_ms":89329,"concrete_test":"Instrument Algorithms 1–4 for D=2, N=2^20 (so r=20, m=1): count every dataset drawn, including the two batches inside each TournamentImprove call in every RecursiveEstimate invocation. Compare the total to t=63 from Claim 6.3. If the count is 122, then n=N/63 overestimates the per-batch budget and the algorithm consumes about 1.94N samples, confirming that the theorem's N-sample guarantee requires the corrected t = 2 + 3r(m+1).","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing weakness is the dataset-counting in Claim 6.3. The proof sets t = 2 + m(3r+1) and n = N/t, asserting that the algorithm's total draw from Definition 1.1 is N = t·n samples. But RecursiveEstimate (Algorithm 4) executes Line 7, TournamentImprove, in every invocation—including the base case—and Lemma 4.2 explicitly says TournamentImprove draws two independent batches of size n. A single RecursiveEstimate call therefore draws 3 batches (Line 5 plus the two in Line 7). Each outer iteration of Algorithm 1 produces a recursion chain of m+1 calls (root plus one per dimension-halving step until d becomes polylog), so it consumes 3(m+1) batches. Adding the initial TournamentImprove in Algorithm 1 Line 7, the total is t_actual = 2 + 3r(m+1), not 2 + m(3r+1). For example, with D=2 (m=1) and r=20, the paper's t = 2 + 1·(61) = 63, but the algorithm actually uses 2 + 3·20·2 = 122 batches. With n = N/63, total samples consumed are 122·N/63 ≈ 1.94N, exceeding the model. This breaks the sample-complexity claim of Theorem 1.2 as written. The gap is repairable—set t = 2 + 3r(m+1) and absorb the extra polylog factors into the log^{O(1)} term—so the algorithmic idea is likely sound, but the proof needs a corrected count.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies high-dimensional entangled mean estimation in the subset-of-signals model, where N independent Gaussian samples share a common mean μ, an α-fraction have covariance bounded by I, and the rest have arbitrary covariance. The main result, Theorem 1.2, claims a computationally efficient algorithm whose ℓ2 error is, up to polylogarithmic factors, f(α,N) + sqrt(D/(αN)), where f is the optimal one-dimensional error from [CV24]. The algorithm uses a tournament-based warm start, an iterative rejection-sampling step that filters noisy samples, a low-variance subspace identification routine, and recursive dimension reduction. The proof is built on a series of detailed lemmas analyzing the distribution of accepted samples, the bias of the rejection procedure, and concentration of the empirical mean within the identified subspace.","tokens_in":38104,"tokens_out":10675,"duration_ms":93740,"significance":"If the proof is repaired, the result would essentially settle the information-theoretic and computational complexity of high-dimensional entangled mean estimation in the subset-of-signals model, up to polylogarithmic factors. The paper's technical core—norm calibration, subspace identification, bias analysis, and mean concentration—is proved in detail and appears internally consistent. The approach of reducing to the one-dimensional estimator of [CV24] is modular and legitimate, and the rejection-sampling plus low-variance-subspace strategy is original. However, the final proof of Theorem 1.2 contains two load-bearing errors in the sample accounting and in the failure-probability parameter, so the central claim is not established as written.","major_comments":[{"comment":"Claim 6.3 undercounts the number of datasets drawn during the execution of EntangledMeanEstimation. In Algorithm 4, Line 7 executes TournamentImprove in every call, including the base case, and Lemma 4.2 states that TournamentImprove draws two independent batches of size n. Since Line 5 draws one additional batch, each invocation of RecursiveEstimate consumes 3 batches. A single iteration of the loop in Algorithm 1 therefore consumes 3(m+1) batches (the root call plus one recursive call per dimension-halving step, ending at the base case), not m(3r+1) as the claim asserts. The total consumption is t_actual = 2 + 3r(m+1), whereas the claim sets t = 2 + m(3r+1) and defines n = N/t. With that n, the algorithm actually draws more than N samples from the model of Definition 1.1, so the sample-complexity part of Theorem 1.2 is not established by the proof as written. This is repairable by setting t = 2 + 3r(m+1) and absorbing the additional polylogarithmic factors into the log^{O(1)}(N) error term.","section":"Section 6, Claim 6.3"},{"comment":"The failure-probability parameter is set to τ = N^{-3/r} with r = ⌈log2 N⌉. Since r ≈ log2 N, this gives τ = Θ(1); for N a power of 2, τ = 1/8. Consequently, the statement after (41) that the error bound holds 'with probability at least 1−O(N^{-0.9})' does not follow from Lemma 6.1, whose failure probability contains a τ term multiplied by log2(d). With τ constant, the success probability can even become negative for large D. The proof as written thus does not establish the 0.99 success probability required by Theorem 1.2. The issue is localized: setting τ = N^{-C} for a sufficiently large constant C preserves the bound log(t/τ) = O(log N) used in Claim 6.2 and yields the claimed high-probability guarantee.","section":"Equation (40) and proof of Theorem 1.2"}],"minor_comments":[{"comment":"The text says 'after r = ⌈0.5 log2(N)⌉ iterations', but r was defined in (40) as ⌈log2 N⌉; the stated iteration count should be ⌈log2 N⌉ for the halving argument to reach sqrt(D)/N error.","section":"Proof of Theorem 1.2, after (41)"},{"comment":"The function name is given as 'Entangled Mean Estimation in High Dimension' in the pseudocode, while the text uses EntangledMeanEstimation; also the input line says 'noise-to-signal ratio α' where 'signal-to-noise ratio' is intended.","section":"Algorithm 1"},{"comment":"Several displayed equations contain corrupted radical symbols (e.g., '/radicaltp/radicalvertex/radicalvertex√'), which make the mathematics hard to read; these should be typeset correctly.","section":"Equation (4) and a few later displays"},{"comment":"The text writes 'ParitalEstimate' instead of 'PartialEstimate' when referring to Algorithm 4.","section":"Proof of Lemma 5.1"},{"comment":"The statement says 'the size of each batch is at least 0.9n', but the construction partitions N = tn samples into exactly t batches of size n; the intended guarantee is presumably that the number of good samples in each batch is at least 0.9αn, not that the batch size is 0.9n.","section":"Lemma 3.6"},{"comment":"The phrase 'divide-and-concur' should be 'divide-and-conquer'.","section":"Section 2"}],"recommendation":"major_revision","confidential_remarks":"The two major issues are confined to the final proof of Theorem 1.2 and appear readily repairable: one is a counting error in the number of batches, and the other is an inappropriate choice of the failure-probability parameter. The core algorithmic ideas and the technical lemmas are substantial and appear sound. With these fixes, the paper would be a strong contribution. No concerns about novelty or scope beyond the need for the repairs."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague, read this. Main thing: it's a genuinely new result and likely correct, but there is a concrete counting error in the sample budget that needs fixing before the theorem as stated is established.\n\nWhat's new: first poly-time algorithm for subset-of-signals mean estimation with arbitrary covariances in high dimensions, achieving error f(α,N) + sqrt(D/(αN)), which is optimal up to polylogs. The iterative rejection-sampling plus dimension-reduction scheme is not routine; the bias analysis for the accepted samples and the low-variance subspace identification are the real work. The tournament starting point is a nice adaptation of list-decodable ideas. The main lemmas are proved in detail and the internal logic mostly holds.\n\nSoft spot: Claim 6.3 miscounts datasets. It says the algorithm uses t = 2 + m(3r+1) batches of size n. But Lemma 4.2's TournamentImprove draws two batches, and Algorithm 4 calls it on Line 7 in every RecursiveEstimate call, including the base case. Each RecursiveEstimate call draws 3 batches (the Line 5 batch plus two in the tournament). With r iterations and m+1 calls per iteration, the true count is 2 + 3r(m+1), not 2 + m(3r+1). For D=1 or small D this is a large relative error; with n = N/t the algorithm consumes more than N samples, so the sample complexity claim in Theorem 1.2 is not proved. This is a real gap, not a stylistic issue.\n\nBut it is also a repairable one. Setting t = 2 + 3r(m+1) still gives t = polylog(N), and Claim 6.2's lower bounds on n would still hold with the same polylog slack. The algorithm idea and the rest of the analysis seem sound, so the theorem is very likely true with a corrected count. The paper does not fit data or tune parameters to hide this; it is just an accounting slip in the proof.\n\nWho it's for: anyone working in robust statistics, high-dimensional estimation, or sample-heterogeneity. It deserves a serious referee; the right outcome is minor revision to fix the claim. I'd bring it to reading group and would cite it once the budget is corrected.","headline":"Strong new algorithm for high-dimensional entangled mean estimation with a real but repairable sample-budget bug in the proof.","tokens_in":38697,"tokens_out":2873,"would_cite":true,"duration_ms":28006,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62G05","62G35","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"A polynomial-time algorithm achieves the near-optimal error rate $f(\\alpha,N)+\\sqrt{D/(\\alpha N)}$ for high-dimensional entangled Gaussian mean estimation in the bounded-covariance subset-of-signals model.","keywords":["entangled mean estimation","subset-of-signals model","heteroskedastic Gaussians","high-dimensional mean estimation","rejection sampling","list-decodable mean estimation","dimension reduction","robust statistics"],"falsifier":"A concrete check is to recount the dataset draws in Algorithm 4 for the case $D=1$ with one outer iteration: the call draws one batch at Line 5 and then TournamentImprove at Line 7 draws two more batches, giving three batches rather than the $t=2$ claimed in Claim 6.3; substituting the corrected total into $n=N/t$ and checking whether the inequalities of Claim 6.2 still hold would settle whether the sample-complexity guarantee follows as written.","tokens_in":37569,"feed_emoji":"📊","tokens_out":9635,"duration_ms":96844,"temperature":0.7,"pith_summary":"The paper studies the subset-of-signals model, where each of $N$ independent points in $\\mathbb{R}^D$ is Gaussian with a common mean $\\mu$ and an unknown covariance, and an unknown $\\alpha$-fraction of the covariances are bounded by the identity. It claims that the optimal error, up to polylogarithmic factors, is $f(\\alpha,N)+\\sqrt{D/(\\alpha N)}$, the one-dimensional optimal rate plus the standard sub-Gaussian error for isotropic Gaussians, and it gives a polynomial-time algorithm achieving this rate whenever $N\\ge (D/\\alpha)\\log^C(D/\\alpha)$. Both terms are shown necessary: the $f(\\alpha,N)$ term comes from embedding the one-dimensional hard instance, and $\\sqrt{D/(\\alpha N)}$ is the rate forced by the $\\alpha N$ good samples. If correct, this resolves both the information-theoretic and computational complexity of high-dimensional entangled mean estimation with arbitrary bounded covariances, a regime that was open even information-theoretically.","feed_headline":"Near-optimal mean recovery from heterogeneous Gaussians","feed_subtitle":"New algorithm matches the 1D error rate plus the sub-Gaussian dimension term in polynomial time.","key_machinery":"The load-bearing object is the Gaussian rejection-sampling identity (Fact 3.3): if $x\\sim N(\\mu,\\Sigma_i)$ is accepted with probability $\\exp(-\\|x-\\tilde{\\mu}\\|_2^2/d)$, the accepted point is distributed as $N(\\tilde{\\mu}_i,\\tilde{\\Sigma}_i)$ with $\\tilde{\\Sigma}_i=(\\Sigma_i^{-1}+(2/d)I)^{-1}$ and $\\tilde{\\mu}_i=\\tilde{\\Sigma}_i((2/d)\\tilde{\\mu}+\\Sigma_i^{-1}\\mu)$. This yields the exact bias formula $\\frac{1}{k}\\sum_i(\\tilde{\\mu}_i-\\mu)=\\frac{2}{d}\\Sigma_{\\mathrm{avg}}(\\tilde{\\mu}-\\mu)$, which is dangerous because the operator norm of $\\Sigma_{\\mathrm{avg}}$ can be as large as $d$. The subroutine FindSubSpace takes the bottom half of the eigenvectors of the empirical second-moment matrix around $\\tilde{\\mu}$, producing a subspace where $v^{\\top}\\Sigma_{\\mathrm{avg}}v=O(\\log(nd))$ for unit vectors $v$; inside that subspace the projection of the bias contracts by a $1/\\log D$ factor. Recursion onto the complementary high-variance subspace halves the dimension at each level, and the base case applies the one-dimensional estimator of [CV24] along each remaining coordinate.","core_discovery":"The central claim is Theorem 1.2: in the high-dimensional subset-of-signals model, there is a $\\mathrm{poly}(D,N)$-time algorithm whose output $\\hat{\\mu}$ satisfies $\\|\\hat{\\mu}-\\mu\\|_2 \\le \\log^{O(1)}(N)(\\sqrt{D/(\\alpha N)}+f(\\alpha,N))$ with probability at least $0.99$, provided $N\\ge (D/\\alpha)\\log^C(D/\\alpha)$. The algorithm begins with a tournament-based warm start within distance $O(\\sqrt{D})$, then iteratively refines the estimate. Each refinement step uses rejection sampling centered at the current estimate $\\tilde{\\mu}$, accepting point $x$ with probability $\\exp(-\\|x-\\tilde{\\mu}\\|_2^2/d)$; by a Gaussian identity the accepted points form new Gaussians, and the average bias of their means is exactly $(2/d)\\Sigma_{\\mathrm{avg}}(\\tilde{\\mu}-\\mu)$. The algorithm finds a low-variance subspace of half the dimension in which this bias shrinks, estimates the mean there, and recursively handles the complementary subspace until a polylog-dimensional base case where the one-dimensional estimator is run along each remaining axis. The claimed rate is tight because the two error terms are each forced by separate lower-bound constructions.","pith_inferences":["The bias-contraction mechanism is not obviously tied to exact Gaussianity: the same accept-with-$\\exp(-\\|x-\\tilde{\\mu}\\|^2/d)$ filter could be tested for sub-Gaussian inliers, potentially extending the rate $\\sqrt{D/(\\alpha N)}+f(\\alpha,N)$ beyond the Gaussian model.","The paper leaves open the regime $N