Pith. sign in

REVIEW 3 major objections 3 minor 17 references

Outlier-robust Mean Estimation near the Breakdown Point via Sum-of-Squares

T0 review · 3 major / 3 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read A sum-of-squares algorithm achieves the information-theoretically optimal error for robust high-dimensional mean estimation at every corruption fraction below 1/2, resolving a problem left open by prior filter-based estimators.

desk verdict Resolves a real open problem with a genuinely new overlap-based SoS proof; the main gap is a terse subset-certifiability step that looks repairable. read the letter →

arxiv 2411.14305 v1 pith:GL7WV2G2 submitted 2024-11-21 cs.DS cs.LGstat.ML

Hongjie Chen , Deepak Narayanan Sridharan , David Steurer This is my paper · ORCID
classification cs.DScs.LGstat.ML MSC 62G3590C2268Q17
keywords robustmeanestimationadversarialcorruptionbreakdownpointsum-of-squarescertifiablyboundedmomentsGaussianoverlapidentifiabilitysparse
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 argues that a single, standard sum-of-squares (SoS) relaxation can handle adversarial corruption all the way up to the statistical breakdown point, where half the samples may be adversarial. For distributions with covariance bounded by $\sigma^2 I$, it shows that with $n=\Omega(d\log d)$ samples, an $\varepsilon$-corruption can be estimated with error $O(\sigma\sqrt{\varepsilon/(1-2\varepsilon)} + \sigma\sqrt{d/n})$, and that the corruption-dependent term is information-theoretically optimal for every $\varepsilon\in[0,1/2)$. The same overlap-based technique yields the optimal rate for distributions with certifiably bounded higher moments and, by taking many moments, a quasi-polynomial-time optimal rate for Gaussian means near $\varepsilon=1/2$. A sympathetic reader would take the paper's main contribution to be the new proof mechanism—bounding mean separation through the overlap mass $1-2\varepsilon$ between sample distributions rather than through their statistical distance—and the demonstration that this mechanism lives inside SoS, so it comes with efficient algorithms.

What carries the argument

The carrying mechanism is the overlap parameter $\delta=1-2\varepsilon$ inside the SoS proof system, where SoS means sum-of-squares, a representation of polynomial inequalities as sums of squares of polynomials that serves as both a proof system and a template for semidefinite-programming-based algorithms. In the canonical program of [KSS18], indicator variables force the program distribution to agree with uncorrupted samples on at least a $1-\varepsilon$ fraction, which yields an overlap of at least $\delta$ between the two distributions; previous proofs used total-variation distance, which is $1-\delta$, to control the mean error. The new proof instead shows in SoS that if two distributions with bounded moments overlap with mass $\delta$, their means differ by at most $O(\sqrt{k}/\delta^{1/k})$, by conditioning on the overlap event and applying Hölder's inequality to the centered moments. The paper carries this out through a degree-4 polynomial in the covariance case and degree-$O(k)$ polynomials in the moment case, so the bound survives in pseudo-expectation and yields a polynomial-time estimator via the SoS-to-algorithms conversion.

What would settle it

Construct a distribution with covariance bounded by $\sigma^2 I$ and choose an adversary that corrupts $\varepsilon=0.49$ of the samples so that a degree-6 pseudo-expectation satisfying System 2.1 outputs a mean with error noticeably larger than $C\sigma\sqrt{\varepsilon/(1-2\varepsilon)}$; Theorem 1.2 predicts such an output is impossible, so reproducing it would refute the central claim.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.2: for any distribution with mean $\mu^*$ and covariance at most $\sigma^2 I$, given an $\varepsilon$-corruption for any $\varepsilon\in[0,1/2)$ and $n=\Omega(d\log d)$ samples, the canonical SoS program, rounded by taking the pseudo-expectation value of its mean variable, outputs $\hat{\mu}$ with $\|\hat{\mu}-\mu^*\|_2=O(\sigma\sqrt{\varepsilon/(1-2\varepsilon)}+\sigma\sqrt{d/n})$. The proof works by considering the overlap $\delta=1-2\varepsilon$ between the empirical distribution over the uncorrupted samples and the distribution represented by the program variables; the constraints guarantee this overlap is at least $\delta$, and the new identifiability proof bounds each mean's distance to the overlap region by roughly $\sqrt{k}/\delta^{1/k}$ for distributions with bounded $k$-th moments. Because this identifiability proof is derived as a low-degree SoS proof, the result is algorithmic rather than existential. Theorem 1.5 extends the same proof to certified $k$-th moments, and Theorem 1.7 obtains the Gaussian optimum by setting $k\sim\log(1/\delta)$ at quasi-polynomial cost.

Load-bearing premise

The proof assumes that with enough samples, the uniform distribution over the uncorrupted samples inherits the same certified covariance or moment bounds as the true distribution and that its sample mean is close to the true mean; if concentration of these certified bounds fails on the good data, the SoS derivation cannot control the uncorrupted-sample terms.

Editorial extensions

If this is right

  • For bounded-covariance distributions, the error dependence $\sqrt{\varepsilon/(1-2\varepsilon)}$ is information-theoretically optimal, closing the gap left by filter-based estimators whose error grew as $1/(1-2\varepsilon)$ or worse.
  • For distributions with certifiably bounded $k$-th moments, the optimal trade-off $\sqrt{k}\cdot\varepsilon^{1-1/k}/(1-2\varepsilon)^{1/k}$ is achieved in polynomial time, a first near the breakdown point.
  • For Gaussian means with known covariance, the optimal error $\sqrt{\log(1/(1-2\varepsilon))}$ is attained in quasi-polynomial time, matching an existing inefficient estimator.
  • The same SoS program with sparsity constraints achieves the optimal dependence $(1-2\varepsilon)^{-1/k}$ for robust sparse mean estimation while keeping sample complexity polynomial in $k$ and $\log d$.
  • All the estimators come from one rounding rule: take the pseudo-expectation of the mean variable in a constant- or slowly-growing-degree SoS relaxation of the same polynomial system.

Reading between the lines

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

  • Beyond the paper: the overlap-based argument is not tied to mean estimation and should transfer to list-decodable settings, where a small output list must contain a good estimate, because the same overlap bound identifies a candidate distribution rather than a unique mean.
  • Beyond the paper: the quasi-polynomial Gaussian result suggests a testable statistical-computational trade-off—the optimal $\sqrt{\log(1/\delta)}$ rate may be provably impossible to achieve in polynomial time as $\varepsilon$ approaches $1/2$, consistent with the paper's own open question.
  • Beyond the paper: one could extend the analysis to subgaussian distributions using the certification result cited in Appendix C.7, potentially obtaining optimal $\sqrt{\log(1/\delta)}$ error without explicitly assuming bounded higher moments, and then test it on synthetic corrupted samples near $\varepsilon=0.49$.
  • Beyond the paper: a concrete experimental check would verify whether the canonical SoS relaxation with bounded-covariance constraints achieves the predicted error on standard heavy-tailed distributions and adversarial perturbations, comparing the empirical error curve in $\varepsilon$ with the predicted $\sqrt{\varepsilon/(1-2\varepsilon)}$ shape.
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

3 major / 3 minor

Summary. The paper revisits outlier-robust mean estimation in the strong contamination model and analyzes the canonical sum-of-squares program of Kothari, Steinhardt, and Steurer (KSS18). Its central claim is that this SoS relaxation, with a new overlap-based identifiability proof and its SoS version, achieves information-theoretically optimal error for the entire corruption range ε ∈ [0,1/2). Theorem 1.2 states that for bounded-covariance distributions, n = Ω(d log d) samples suffice for error O(σ√(ε/(1−2ε)) + σ√(d/n)), matching the lower bound in Lemma 1.3 and resolving an open problem of ZJS22b. Theorem 1.5 extends the result to certifiably bounded kth moments with rate O(√k·ε^{1−1/k}/(1−2ε)^{1/k} + √(d/n)), and Corollary 2.6 derives a quasi-polynomial-time near-optimal Gaussian mean estimator with error O(√log(1/(1−2ε)) + √(d/n)). The paper also gives matching lower bounds in Appendix A and additional breakdown-point analyses in Appendix D.

Significance. If the main theorems are correct, this is a substantial advance: it resolves the previously open question of achieving optimal error efficiently for all ε up to the breakdown point, and it does so by identifying an overlap-based proof strategy that is cleaner than the previous statistical-distance-based analyses. The lower bounds in Appendix A match the upper bounds up to constants, and the proof strategy is clearly separated into a small-ε regime and a large-ε near-breakdown regime. The paper is also careful to track constants and to distinguish the sampling error term √(d/n) from the robust error term. The bounded-covariance result (Theorem 1.2) is particularly credible because the subset-inheritance issue for covariance is patchable by the PSD inequality. The higher-moment and Gaussian corollaries are the parts that need additional work.

major comments (3)
  1. [§2.3, proof of Theorem 2.4] The final square-root step is arithmetically inconsistent. The displayed inequality is δ·‖v‖^{2k} ≤ 2^k·k^{k/2}·‖v‖^k for v = μ−μ*. Applying SoS cancellation to z = ‖v‖^k gives ‖v‖^k ≤ 2^k·k^{k/2}/δ. Applying SoS square root then gives ‖v‖_2 = O(√k·δ^{−1/k}), not the printed O(k·δ^{−2/k}). Since δ^{−2/k} is strictly larger than δ^{−1/k} as δ → 0, the printed conclusion is weaker than the theorem statement's δ^{−1/k} dependence. The correct arithmetic actually matches Theorem 1.5, so this appears repairable, but as written the proof of the higher-moment theorem does not establish the claimed rate.
  2. [§2 and proof of Theorem 2.4 / Theorem 1.5] The paper assumes without proof that the uniform distribution over the particular uncorrupted samples left by the adversary inherits the SoS-certifiable moment bound. The blanket statement in Section 2 — 'we always take sufficiently many samples to ensure that the distributional assumptions also apply to the uniform distribution over the uncorrupted samples' — is not enough. Lemma C.4 guarantees the existence of some good subset, not a guarantee about the specific (1−ε) fraction that the adversary leaves unmodified; in the strong contamination model the adversary chooses which samples to corrupt after seeing all values. HL18 Fact 7.6, as cited, is a statement about a fresh iid sample and does not obviously extend to every adversarially selected large subset. For k = 2 the bounded-covariance case is saved by the PSD inequality Σ_S (x_i−μ_S)(x_i−μ_S)^T ≤ (n/|S|)Σ_all (x_i−μ_full)(x_i−μ_full)^T, so Theorem 1.2 is on solid ground. For k > 2, however, the proof of Theorem 2.4 uses a certifiable moment bound for the retained uncorrupted samples at a load-bearing point, and no subset-inheritance certificate is supplied. The authors should either prove such an inheritance lemma for every large subset or restructure the argument so that only full-sample certificates are used.
  3. [Lemma C.4 and Theorem 1.2 sample complexity] The justification for n = Ω(d log d) is stated by reference to Lemma C.4, but Lemma C.4 as written has a 1/δ factor in the empirical-covariance bound; using it directly with δ = ε would suggest n = Ω(d log d / ε), which is not what Theorem 1.2 states. The theorem is likely still true, because with n = Ω(d log d) the full empirical covariance is O(1) by standard concentration, and every (1−ε) subset has covariance bounded by O(1/(1−ε)) via the PSD inequality. The paper should state this argument explicitly instead of relying on Lemma C.4, whose stated bound does not support the uniform-in-ε sample complexity as written.
minor comments (3)
  1. [Definition 1.4 and Theorem 2.4] Definition 1.4 quantifies over all even t ≤ k, but the polynomial system in (2.4) only enforces the kth-moment inequality. The lower even moments are either implied by SoS Hölder or not needed in the proof; the paper should clarify this to avoid an apparent mismatch.
  2. [Theorem 2.10] The sparse mean estimation theorem states only the robust error term and omits the sampling-error contribution that is discussed in Section 2.6. For consistency with Theorems 1.2 and 1.5, the statement should either include the sampling term or explicitly say that it is absorbed into the sample complexity.
  3. [Appendix D] Several cross-references are broken or incomplete in the formatted text, for example 'We defer the proof of the above 2.1 to Appendix D.2' and the references to 'Theorem D.3'. This makes the appendix difficult to check and should be fixed.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main theorems are new analyses of a published SoS program with universal constants and no fitted parameters; cited prior work is used as independent tooling.

full rationale

The paper's derivation chain is self-contained relative to its stated inputs. Theorem 1.2 is proven directly from the feasibility constraints of the canonical KSS18 SoS program (System 2.1), Lemma 2.1 (which encodes the corruption-fraction constraints), and the bounded-covariance assumption; no parameter is fitted and the constants are universal. Theorem 1.5 similarly derives its bound inside SoS from the moment constraints of System 2.4 and Lemma 2.1; the only external input is the sampling/certifiability step, for which the paper cites HL18 Fact 7.6. HL18's authors do not overlap with the present authors, so this is independent evidence, not a self-citation chain. Lemma 2.3 (the overlap identifiability lemma) is explicitly attributed to Hop18/HL18, again non-overlapping, and the paper's contribution is the new SoS version plus the application to robust mean estimation. Citations to KSS18 and RSS18 are uses of an established program and framework, not appeals to an unverified uniqueness theorem. The skeptical concern about enforcing certifiably bounded higher moments on the adversary's particular uncorrupted subset is a potential correctness gap, not a circularity: the proof does not define the conclusion in terms of the assumption, and the cited concentration facts are external. No equation reduces to a fitted parameter or to the target result by construction.

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

The central claims rest on standard SoS machinery, the strong contamination model, and the assumption that the good samples inherit distributional certifiability. There are no fitted free parameters and no newly postulated entities such as new forces or particles.

assumptions (4)
  • standard math The sum-of-squares proof system is sound, and low-degree pseudo-expectations satisfying a feasible polynomial system can be found in time (n+d)^{O(l)}.
    Used throughout to convert SoS proofs into algorithms (Appendix B.1, Facts B.3 and B.4).
  • domain assumption The strong contamination model (Definition 1.1) where an adversary modifies at most an ε fraction of the samples.
    This is the problem setting for all theorems; the algorithm receives the corrupted samples and the parameter ε.
  • domain assumption The uniform distribution over the uncorrupted samples satisfies the same SoS-certifiable covariance and moment bounds as the true distribution, with n = Ω(d log d) or n = Ω(d^{O(k)}).
    Stated in Section 2 and used in the proofs of Theorems 1.2 and 1.5 to bound the uncorrupted-sample terms; relies on Lemma C.4 and HL18 Fact 7.6.
  • domain assumption Certifiably bounded k-th moments (Definition 1.4) are preserved under the low-degree SoS proof system and are satisfied by the empirical distribution over program variables.
    Used to bound the terms involving x_i and x*_i in the expansions for Theorem 1.5 and the sparse mean estimation result.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Outlier-robust Mean Estimation near the Breakdown Point via Sum-of-Squares." pith.science (2026). https://pith.science/paper/GL7WV2G2

@misc{pith2026241114305,
  author       = {Pith},
  title        = {Pith review of: Outlier-robust Mean Estimation near the Breakdown Point via Sum-of-Squares},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GL7WV2G2}},
  note         = {Machine review of arXiv:2411.14305}
}
abstract

We revisit the problem of estimating the mean of a high-dimensional distribution in the presence of an $\varepsilon$-fraction of adversarial outliers. When $\varepsilon$ is at most some sufficiently small constant, previous works can achieve optimal error rate efficiently \cite{diakonikolas2018robustly, kothari2018robust}. As $\varepsilon$ approaches the breakdown point $\frac{1}{2}$, all previous algorithms incur either sub-optimal error rates or exponential running time. In this paper we give a new analysis of the canonical sum-of-squares program introduced in \cite{kothari2018robust} and show that this program efficiently achieves optimal error rate for all $\varepsilon \in[0,\frac{1}{2})$. The key ingredient for our results is a new identifiability proof for robust mean estimation that focuses on the overlap between the distributions instead of their statistical distance as in previous works. We capture this proof within the sum-of-squares proof system, thus obtaining efficient algorithms using the sum-of-squares proofs to algorithms paradigm \cite{raghavendra2018high}.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

  1. [2]

    /u∞D4∃F1 and /u∞D4∃F2 have bounded/u1D458/u1D461ℎmoments for/u1D458/greaterorequalslant2 in the sense of Definition 1.4

    work page

  2. [3]

    |/u1D53C /u1D44B∼/u∞D4∃F1[/u1D44B] − /u1D53C /u1D44B∼/u∞D4∃F2[/u1D44B]| /greaterorequalslant √ /u1D458· /u1D>001−1//u1D458· (1 − 2/u1D>00)−1//u1D458. Proof. Take /u∞D4∃F1 to be the distribution that outputs 0 with probability 1. Tak e /u∞D4∃F2 to be the distribution that outputs samples from /u∞D4∃F1 with probability 1 − 2/u1D>00, and outputs √ /u1D458· (...

    work page

  3. [6]

    /u∞D4∃F1 and /u∞D4∃F2 are Gaussians with unit variance

    work page

  4. [7]

    |/u1D53C /u1D44B∼/u∞D4∃F1[/u1D44B] − /u1D53C /u1D44B∼/u∞D4∃F2[/u1D44B]| /greaterorequalslantΩ ( √ log 1 1−2/u1D>00 ) . Proof. Take /u∞D4∃F1 to be the standard Gaussian /u∞D4A∃ (0, 1). Take /u∞D4∃F2 to be the Gaussian /u∞D4A∃ (/u1D>0>, 1), with /u1D>0> >0 such that /u1D451/u1D447/u1D449(/u∞D4∃F1, /u∞D4∃F2) = 2/u1D>00. We consider Tsybakov’s version of the ...

    work page

  5. [8]

    □ B Preliminaries B.1 Sum-of-Squares Proofs to Algorithms Let us denote by /u1D44Ba vector or matrix of /u1D45Bindeterminates over ℝ

    ‖ /u∞D4A∃ (/u1D>0>2, /u1D>0E2 2)) = log /u1D>0E2 /u1D>0E1 + /u1D>0E2 1 + (/u1D>0>1 − /u1D>0>2)2 2/u1D>0E2 2 − 1 2 Applying this inequality for our choice of /u∞D4∃F1 and /u∞D4∃F2, we get 2/u1D>00⩽1 − 1 2 exp ( − /u1D>0>2 2 ) which after simplifying yields /u1D>0>/greaterorequalslant √ 2 · log ( 1 2 − 4/u1D>00 ) /greaterorequalslant √ log ( 1 1 − 2/u1D>00 ...

    work page

  6. [9]

    Normalization: ~/u1D53C [1] = 1

    work page

  7. [10]

    Satisifiability: ∀/u1D456∈ [ /u1D45A] : ~/u1D53C [/u1D45D/u1D456(/u1D44B) · /u1D4602(/u1D44B)] /greaterorequalslant0 for all polynomials /u1D460such that degree(/u1D45D/u1D456(/u1D44B) ·/u1D4602(/u1D465)) ⩽ℓ

    work page

  8. [11]

    Fact B.3

    Non-negativity of Squares: ~/u1D53C [/u1D45E2(/u1D465)] /greaterorequalslant0 for all polynomials such that degree(/u1D45E2) ⩽ℓ . Fact B.3. If /u∞D4∃C ℓ /u1D44B {/u1D45E(/u1D44B) /greaterorequalslant0} and ~/u1D53C [.] is a degree ℓ pseudo-expectation satisfying /u∞D4∃C, then ~/u1D53C [/u1D45E(/u1D44B)] /greaterorequalslant0. 29 Fact B.4 (SoS Algorithm). ...

    work page

Show all 17 references
  1. [12]

    When /u1D>00is large, these distributions are 2 /u1D>00far away in statistical distance and have means √ 1 1−2/u1D>00apart and

  2. [13]

    When /u1D>00is small, these distributions are /u1D>00far away in statistical distance and have means /u1D>00 √ log 1 /u1D>00apart. These lower bounds rule out any algorithm that use only speci fic bounded covariance conditions such as the one in /u∞D4∃CGauss to robustly estimat...

  3. [14]

    /u1D451/u1D447/u1D449(/u∞D4∃F1, /u∞D4∃F2) ⩽2/u1D>00

  4. [15]

    /u∞D4∃F1 is /u∞D4A∃ (0, 1) and /u∞D4∃F2 has variance bounded from above by 1 +/u1D442(/u1D6FF), where /u1D6FF= 1 − 2/u1D>00. 44

  5. [16]

    |/u1D53C /u1D44B∼/u∞D4∃F1[/u1D44B] − /u1D53C /u1D44B∼/u∞D4∃F2[/u1D44B]| /greaterorequalslant √ 1 1−2/u1D>00. Proof. Let /u∞D4∃F2 to be the distribution that outputs samples from /u∞D4∃F1 with probability 1 − 2/u1D>00, and outputs (1 − 2/u1D>00)−1/2 · (2/u1D>00)−1 with probabil...

  6. [17]

    /u1D451/u1D447/u1D449(/u∞D4∃F1, /u∞D4∃F2) ⩽/u1D>00

  7. [18]

    /u∞D4∃F1 is /u∞D4A∃ (0, 1) and /u∞D4∃F2 has variance bounded from above by 1 + /u1D>00log 1 /u1D>00

  8. [19]

    |/u1D53C /u1D44B∼/u∞D4∃F1[/u1D44B] − /u1D53C /u1D44B∼/u∞D4∃F2[/u1D44B]| /greaterorequalslant/u1D>00 √ log 1 /u1D>00. Proof. Let /u∞D4∃F2 to be the distribution that outputs samples from /u∞D4∃F1 with probability 1 − /u1D>00, and outputs √ log 1 /u1D>00with probability /u1D>00....

  9. [197]

    1021–1034

    30 [HL18] Samuel B Hopkins and Jerry Li, Mixture models, robustness, and sum of squares proofs, Proceedings of the 50th Annual ACM SIGACT Symposium on Theo ry of Computing, 2018, pp. 1021–1034. 2, 4, 5, 10, 12, 14, 15, 16, 17, 18, 19, 30 [HLZ20] Sam Hopkins, Jerry Li, and Fred...

    2020

Pith tools

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