{"id":"02916002-2edb-4585-9600-8d021a2684b6","arxiv_id":"2411.14305","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Efficient sum-of-squares algorithms achieve information-theoretically optimal error for robust mean estimation for the full range of adversarial corruption rates below 1/2.","lead":"This paper gives sum-of-squares algorithms that estimate a high-dimensional mean with optimal error for every corruption rate below the breakdown point of 1/2, for bounded-covariance and certifiably bounded-moment distributions. It resolves an open problem on the optimal error rate near the breakdown point and introduces an overlap-based proof technique that also applies to sparse and Gaussian settings.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The core proofs assume SoS-certifiable moment bounds hold on the adversary's particular uncorrupted subset; the cited subset lemma does not obviously supply this for higher moments, so the main theorem is conditional on a missing subset-certifiability argument.","rationale":"The reader's weakest assumption correctly identified the concentration/certifiability of the uncorrupted samples as the delicate point. I agree that this is the most load-bearing assumption, but I would sharpen it: for bounded covariance, the condition can be recovered for every large subset by a PSD subset inequality, so that half of the paper is on solid ground. The unresolved part is the analogous statement for certifiably bounded higher moments, where the manuscript cites HL18 Fact 7.6 but does not show that the adversary's particular retained subset inherits an SoS certificate, as opposed to merely a numerical moment bound. The central construction is otherwise coherent: the identifiability argument via overlap is correctly attributed to Hop18/HL18, the SoS derivations are internally consistent assuming the inherited moment bounds, and the matching lower bounds are present. The concern is therefore not an observed contradiction but a missing justification in the proof of the higher-moment and Gaussian results. If the concrete subset-certifiability test passes, the paper should be accepted; if it fails, the main theorems for k>2 and for Gaussians would need a different argument. This is why I recommend conditional acceptance rather than rejection or unqualified acceptance.","tokens_in":58363,"tokens_out":30623,"duration_ms":317340,"concrete_test":"Set k=4, d=2, n=d^{O(4)}, and take a sample set whose full empirical distribution has an explicit SoS certificate for its fourth moments. For every subset S of size at least (1−ε)n, check whether there is a constant C=C(k,ε) and an explicit degree-4 SoS certificate for q_S(u)=C‖u‖^4 − (1/|S|)Σ_{i∈S} ⟨x_i−μ_S,u⟩^4 that is derivable from the full-sample certificate by expanding around the full-sample mean and applying SoS Hölder. If such a certificate exists for all S, the Section 2 assumption is justified and the proof can be patched; if some one-sided or adversarial subset S admits no such certificate, then the proofs of Theorems 1.5 and 2.4 are incomplete as written.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The proof of Theorem 1.5 (and hence the quasi-polynomial Gaussian corollary) bounds the term (1/n)Σ_i ⟨x_i^*−μ^*, u⟩^k using the assumption that the uniform distribution over the uncorrupted samples has certifiably bounded kth moments. The manuscript justifies this in Section 2 by saying that n=Ω(d^{O(k)}) ensures the distributional assumptions apply to the uniform distribution over the uncorrupted samples, citing Lemma C.4 and HL18 Fact 7.6. But Lemma C.4 gives only the existence of a good subset, not a guarantee about the particular subset of original samples that the adversary leaves unmodified. Since the adversary chooses which samples to corrupt after seeing all sample values, the retained uncorrupted set is an adversarially selected (1−ε)-fraction subset. For the bounded-covariance case, every large subset inherits a bounded centered empirical covariance from the full sample via 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 plausibly repairable. For kth moments with k>2, however, the paper does not supply the corresponding SoS certificate for an arbitrary large subset. A numerical L^p bound such as E_S|⟨x−μ_S,u⟩|^k ≤ C(k,ε) E_full|⟨x,u⟩|^k does not by itself give a low-degree SoS proof of the moment inequality for all directions u. Since the derivations of Theorems 1.5 and 2.4 explicitly use a certifiable moment bound for the retained uncorrupted samples, this is a load-bearing gap in the paper as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":58715,"tokens_out":16631,"duration_ms":171655,"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":[{"comment":"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.","section":"§2.3, proof of Theorem 2.4"},{"comment":"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.","section":"§2 and proof of Theorem 2.4 / Theorem 1.5"},{"comment":"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.","section":"Lemma C.4 and Theorem 1.2 sample complexity"}],"minor_comments":[{"comment":"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.","section":"Definition 1.4 and Theorem 2.4"},{"comment":"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.","section":"Theorem 2.10"},{"comment":"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.","section":"Appendix D"}],"recommendation":"major_revision","confidential_remarks":"The core ideas appear correct and the missing pieces are likely repairable within the scope of the paper. The bounded-covariance theorem is the strongest and most robust part; the higher-moment theorem needs a genuine, explicitly stated subset-certifiability lemma, and the arithmetic error in Section 2.3 must be corrected. The paper's use of KSS18, HL18, and RSS18 as tools is legitimate and does not amount to circularity. I would be willing to accept after a revision that addresses the two load-bearing points."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis paper deserves a serious look. It gives the first efficient SoS-based algorithms for robust mean estimation with optimal error for all corruption rates below 1/2, resolving the open problem from ZJS22b. For bounded covariance, the corruption-dependent error matches the information-theoretic lower bound. The technical core is an overlap-based identifiability proof (Lemma 2.3) that is SoS-ized without the cancellation step that blocked prior proofs. The authors are honest that the overlap lemma itself comes from Hopkins and Li's clustering work; the new content is the sharper SoS derivation and the optimized analysis that avoids statistical-distance decoupling. The lower bounds in Appendix A match the upper bounds, and constants are tracked. That is a solid piece of work.\n\nThe soft spots are real but not fatal. The biggest one is the phrase \"we always take sufficiently many samples so that the distributional assumptions apply to the uniform distribution over the uncorrupted samples.\" For bounded covariance this is fine: every large subset inherits a bounded empirical covariance from the full sample by a PSD inequality that is also SoS-friendly. For higher moments k > 2, the paper does not show that the adversary's particular uncorrupted subset has SoS-certifiable kth moments. It cites Lemma C.4 and HL18 Fact 7.6, but those do not obviously give a certificate for an arbitrary large subset. The stress-test concern lands here: the proof of Theorem 1.5 uses a certifiable moment bound for the retained samples, so as written the argument has a gap. I believe the gap is repairable—a full-sample moment bound plus a subset moment inequality should give the needed certificate in SoS—but the authors must write that step down. If it does not repair cleanly, Theorem 1.5 and the Gaussian corollary are weakened.\n\nThe Gaussian result is quasi-polynomial, not polynomial, and the authors say so. The paper is careful about attribution and does not oversell. The proofs are intricate and not machine-checked, so some residual risk of a subtle SoS error exists, but I did not find one.\n\nWho should read this: anyone working on high-dimensional robust statistics or sum-of-squares algorithms. It resolves a known open problem and introduces a technique (overlap-based identifiability in SoS) that will get reused. I would send it out for peer review, with the main request to the authors being to close the subset-certifiability gap.","headline":"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.","tokens_in":59270,"tokens_out":4911,"would_cite":true,"duration_ms":49323,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62G35","90C22","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["robust mean estimation","adversarial corruption","breakdown point","sum-of-squares","certifiably bounded moments","Gaussian mean","overlap identifiability","sparse mean estimation"],"falsifier":"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.","tokens_in":58154,"feed_emoji":"🎯","tokens_out":9285,"duration_ms":78906,"temperature":0.7,"pith_summary":"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.","feed_headline":"SoS proof attains optimal robust mean error for all ε<1/2","feed_subtitle":"Overlap-based analysis closes the gap at 50-percent corruption for bounded-covariance mean estimation.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Introduces the canonical sum-of-squares program and the small-$\\varepsilon$ analysis that this paper re-analyzes for large $\\varepsilon$.","marker":"[KSS18]"},{"why":"Poses the open problem of achieving optimal error near the breakdown point and supplies the filter algorithm whose error rate is improved.","marker":"[ZJS22b]"},{"why":"Supplies the framework of certified bounded moments, the sample-complexity facts, and the SoS overlap lemma used as a comparison point.","marker":"[HL18]"},{"why":"Contains the original overlap-based identifiability proof for clustering that Lemma 2.3 adapts to robust mean estimation.","marker":"[Hop18]"},{"why":"Provides an earlier filter estimator achieving optimal breakdown point with suboptimal error near $\\varepsilon=1/2$.","marker":"[HLZ20]"},{"why":"Gives the efficient near-optimal estimators for small $\\varepsilon$ that the paper complements at large $\\varepsilon$.","marker":"[DKK+19]"},{"why":"Shows polynomial-time SoS can achieve near-optimal Gaussian error for small $\\varepsilon$, a technique that the paper argues does not extend to $\\varepsilon$ near $1/2$.","marker":"[KMZ22]"},{"why":"Supplies the inefficient estimator whose optimal Gaussian error $\\sqrt{\\log(1/\\delta)}$ is matched in quasi-polynomial time.","marker":"[ZJS20]"},{"why":"Provides the robust sparse mean estimation program and moment definitions extended in Section 2.6.","marker":"[DKK+22]"},{"why":"Establishes the SoS-proofs-to-algorithms paradigm that converts the derived SoS identifiability bounds into efficient algorithms.","marker":"[RSS18]"}],"fun_headline_variants":["Overlap-based SoS proves optimal robust mean for all ε<1/2","SoS robust mean hits optimal error at any corruption < 50%","Overlap trick closes robust mean gap: SoS optimal for ε<1/2","Optimal robust mean via SoS for every ε<1/2","SoS mean estimation optimal near breakdown, ε<1/2"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Overlap-based SoS proves optimal robust mean for all ε<1/2","SoS robust mean hits optimal error at any corruption < 50%","Overlap trick closes robust mean gap: SoS optimal for ε<1/2","Optimal robust mean via SoS for every ε<1/2","SoS mean estimation optimal near breakdown, ε<1/2"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001365,"raw_usage":{"total_tokens":5569,"prompt_tokens":1011,"completion_tokens":4558,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":627,"completion_tokens_details":{"reasoning_tokens":4458}},"tokens_in":627,"tokens_out":4558,"duration_ms":31780,"temperature":1.0,"reasoning_tokens":4458,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T15:19:58.960095+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}