Pith. sign in

REVIEW 2 major objections 6 minor 3 references

Entangled Mean Estimation in High-Dimensions

T0 review · 2 major / 6 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read 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.

desk verdict Strong new algorithm for high-dimensional entangled mean estimation with a real but repairable sample-budget bug in the proof. read the letter →

arxiv 2501.05425 v1 pith:SRO3VWKX submitted 2025-01-09 cs.DS cs.LGmath.STstat.MLstat.TH

Ilias Diakonikolas , Daniel M. Kane , Sihan Liu , Thanasis Pittas This is my paper · ORCID
classification cs.DScs.LGmath.STstat.MLstat.TH MSC 62G0562G3568W20
keywords entangledmeanestimationsubset-of-signalsmodelheteroskedasticGaussianshigh-dimensionalrejectionsamplinglist-decodabledimensionreductionrobuststatistics
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

The sample-complexity proof rests on the exact count of independent batches the algorithm draws, and that count appears to be too small by a small constant factor: each call to RecursiveEstimate draws a batch at Line 5 and then two tournament batches at Line 7 before any base-case shortcut, so the total sample usage may exceed the promised $N$ samples.

Editorial extensions

If this is right

  • If Theorem 1.2 is correct, high-dimensional entangled Gaussian mean estimation with arbitrary bounded covariances has error rate, up to polylogarithmic factors, equal to the one-dimensional optimal rate plus the isotropic sub-Gaussian rate, with no extra polynomial factor in the dimension.
  • The sample requirement $N\ge (D/\alpha)\log^C(D/\alpha)$ is not an artifact of the construction: the paper argues that any estimator achieving error below a constant needs $N=\Omega(D/\alpha)$ even when the identities of the good samples are revealed.
  • The two components of the error bound are simultaneously necessary, so the rate $\sqrt{D/(\alpha N)}+f(\alpha,N)$ is information-theoretically tight, up to polylogarithmic factors, in the parameter regime covered by the theorem.
  • Because the algorithm runs in polynomial time, the result is a computational resolution, not merely an existence or information-theoretic statement.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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<D/\alpha$; a natural next question is whether some estimator can achieve the same error with fewer than $D/\alpha$ samples, or whether the $\Omega(D/\alpha)$ barrier is fundamental for all constant-error estimators.
  • A practical implementation could stop recursion in directions that already reach the base-case error and keep only the low-variance subspace path, which may reduce the polylogarithmic factors in runtime while preserving the stated rate.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 6 minor

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.

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 (2)
  1. [Section 6, Claim 6.3] 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.
  2. [Equation (40) and proof of Theorem 1.2] 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.
minor comments (6)
  1. [Proof of Theorem 1.2, after (41)] 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.
  2. [Algorithm 1] 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.
  3. [Equation (4) and a few later displays] Several displayed equations contain corrupted radical symbols (e.g., '/radicaltp/radicalvertex/radicalvertex√'), which make the mathematics hard to read; these should be typeset correctly.
  4. [Proof of Lemma 5.1] The text writes 'ParitalEstimate' instead of 'PartialEstimate' when referring to Algorithm 4.
  5. [Lemma 3.6] 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.
  6. [Section 2] The phrase 'divide-and-concur' should be 'divide-and-conquer'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the high-dimensional algorithm is a genuine reduction to the external one-dimensional estimator of [CV24], with all central claims proved from stated assumptions.

full rationale

I traced the derivation chain of Theorem 1.2. The upper bound is obtained by an explicit algorithm (Algorithms 1-4) whose error is analyzed in Lemma 5.1 and Lemma 6.1 by bounding empirical-mean concentration, rejection-sampling bias, low-variance subspace identification, and the base-case one-dimensional estimator. The term f(alpha,N) in the theorem is the error of the external [CV24] one-dimensional estimator, used as a black-box subroutine; the algorithm does not define f in terms of its own output, and the lower bound for the f term is a separate embedding of the [LY20] one-dimensional hard instance. The tournament subroutine cites [DKK20] only as inspiration, and Lemma 4.1 is proved directly from the one-dimensional estimator and elementary geometry. No parameter is fitted to a subset of the data and then reported as a prediction of a closely related quantity. The only substantive issue I found is the sample-accounting in Claim 6.3: RecursiveEstimate draws two batches in TournamentImprove (Line 7) in every call, including the base case reached at Line 8, so the total number of batches is 2 + 3r(m+1) rather than 2 + m(3r+1), and the stated N-sample budget is not established as written. This is a correctness or budget bug that affects the proof of Theorem 1.2, but it is not circularity: it does not make any theorem statement an input to its own derivation. The mathematical reduction itself is self-contained apart from the legitimate external one-dimensional result.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters or invented entities. The central claim rests on the external 1-d estimator [CV24], standard concentration inequalities, and the Gaussian rejection sampling fact.

assumptions (5)
  • domain assumption The one-dimensional estimator of [CV24] (Theorem 3.7) achieves error f_delta(alpha,n) with probability 1 - 1/n^delta.
    Invoked in Lemma 4.1, Lemma 4.2, Corollary 3.8, and the base case of Algorithm 4. The high-dimensional guarantee is directly composed from this external result.
  • standard math Gaussian rejection sampling preserves Gaussianity: accepting x ~ N(mu, Sigma) with probability exp(-||x - tilde_mu||^2/d) yields distribution N(tilde_mu_i, tilde_Sigma_i) as in Fact 3.3.
    Used throughout Section 5 to compute bias (Lemma 5.12) and the accepted-sample distributions.
  • domain assumption Covariance matrices can be assumed to satisfy Sigma_i >= I/2 via preprocessing x' = (x + y)/sqrt(2).
    Remark 3.4 transforms the model; it is valid because the transformation preserves the subset-of-signals structure with mean scaled by 1/sqrt(2), but it changes the problem slightly.
  • standard math Matrix Bernstein inequality (Fact 3.2).
    Used in Lemma 5.11 for spectral concentration.
  • standard math Negative association of permutation indicators and Chernoff bounds for negatively associated variables.
    Used in Lemma 3.6 to show that random splitting preserves the signal-to-noise rate.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Entangled Mean Estimation in High-Dimensions." pith.science (2026). https://pith.science/paper/SRO3VWKX

@misc{pith2026250105425,
  author       = {Pith},
  title        = {Pith review of: Entangled Mean Estimation in High-Dimensions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SRO3VWKX}},
  note         = {Machine review of arXiv:2501.05425}
}
abstract

We study the task of high-dimensional entangled mean estimation in the subset-of-signals model. Specifically, given $N$ independent random points $x_1,\ldots,x_N$ in $\mathbb{R}^D$ and a parameter $\alpha \in (0, 1)$ such that each $x_i$ is drawn from a Gaussian with mean $\mu$ and unknown covariance, and an unknown $\alpha$-fraction of the points have identity-bounded covariances, the goal is to estimate the common mean $\mu$. The one-dimensional version of this task has received significant attention in theoretical computer science and statistics over the past decades. Recent work [LY20; CV24] has given near-optimal upper and lower bounds for the one-dimensional setting. On the other hand, our understanding of even the information-theoretic aspects of the multivariate setting has remained limited. In this work, we design a computationally efficient algorithm achieving an information-theoretically near-optimal error. Specifically, we show that the optimal error (up to polylogarithmic factors) is $f(\alpha,N) + \sqrt{D/(\alpha N)}$, where the term $f(\alpha,N)$ is the error of the one-dimensional problem and the second term is the sub-Gaussian error rate. Our algorithmic approach employs an iterative refinement strategy, whereby we progressively learn more accurate approximations $\hat \mu$ to $\mu$. This is achieved via a novel rejection sampling procedure that removes points significantly deviating from $\hat \mu$, as an attempt to filter out unusually noisy samples. A complication that arises is that rejection sampling introduces bias in the distribution of the remaining points. To address this issue, we perform a careful analysis of the bias, develop an iterative dimension-reduction strategy, and employ a novel subroutine inspired by list-decodable learning that leverages the one-dimensional result.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

3 extracted references · 2 canonical work pages

  1. [2009]

    Mathematics and picturing of data

    [1] [Tuk75] J. Tukey. “Mathematics and picturing of data”. Proceedings of the International Congress of Mathematicians (ICM). Vol. 6. 1975. [2] [Ver18] R. Vershynin.High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press, 2018. [13] [Wei69] L. Weiss. “The asymptotic distribution of quantiles from mixed s...

    work page 1969

  2. [2020]

    Robust Estimators in High Dimensions without the Computational Intractability

    [8] [DKKLMS16] I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart. “Robust Estimators in High Dimensions without the Computational Intractability”. Proc. 57th IEEE Symposium on Foundations of Computer Science (FOCS) . 2016. [6] [DKKLT22] I. Diakonikolas, D. M. Kane, D. Kongsgaard, J. Li, and K. Tian. “Clustering Mixture Models in Alm...

    arXiv 2023

  3. [2024]

    Estimating location parameters in entangled single-sample distributions

    [2] [LL22] A. Liu and J. Li. “Clustering mixtures with almost optimal separation in polynomial time”. Proc. 54th Annual ACM Symposium on Theory of Computing (STOC) . 2022. [1] [LRV16] K. A. Lai, A. B. Rao, and S. Vempala. “Agnostic Estimation of Mean and Covariance”. Proc. 57th IEEE Symposium on Foundations of Computer Science (FOCS) . 2016. [6] [LY20] Y....

    work page Pith review arXiv 2007

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.