{"id":"4b9ce99a-2fe5-4d21-8892-1105281ff929","arxiv_id":"2411.15306","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Adversarially robust estimators transfer to heavy-tailed estimation for free, but heavy-tailed estimators do not transfer back to adversarial contamination.","lead":"The paper proves that any estimator robust to adversarial corruption of a constant fraction of data is automatically robust, with exponentially high probability, to natural heavy-tailed outliers. It also shows the reverse fails: some optimal heavy-tailed estimators break under adversarial corruption unless the data is pre-filtered.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the quantifier ambiguity in Theorem 2.3 is resolved because the adversary can depend on the sample, so the central claim stands; only fixable typos remain.","rationale":"The reader's conditional verdict is driven primarily by the concern that Definition 1.2, if read as 'for each adversary separately', would not imply that the set S of simultaneously robust samples has measure at least 0.9. In the strong contamination model, however, the adversary can depend on the realized sample X, so the quantifier over adversaries is a quantifier over functions of X. For a deterministic estimator, the worst-case adversary over this class realizes, pointwise on the bad set E, a corruption that makes the estimator fail; hence the supremum failure probability equals the measure of the set of samples for which some admissible corruption fails. This makes the set S in Theorem 2.3 large, and the isoperimetric argument is valid. I therefore disagree that the implicit quantification is a load-bearing obstacle. I also checked the converse direction: Theorem 3.7's deterministic statement, conditional on Algorithm 2 succeeding on a pointset, is what the black-box reduction argument needs, and the proof's steps—spread bounds, Lemma 3.5, and the construction of the stable subset I—are internally coherent. The paper does contain several typos in key displayed statements, notably the size bound in Theorem 3.7, the union-bound sign in Lemma 3.3, and some indexing in Lemma 3.4. These are substantive presentation issues that justify a revised version, but they are fixable and do not undermine the central claim. Hence I keep the reader's CONDITIONAL verdict unchanged, while noting that the identified weakest assumption is not the real risk.","tokens_in":22848,"tokens_out":40546,"duration_ms":385569,"concrete_test":"Formalize Definition 1.2 as a supremum over admissible adversaries (functions from clean X to epsilon-corruptions) of P_X(failure), and prove for deterministic A the identity sup_f P_X(A(f(X)) bad) = P_X(exists admissible corruption Y of X with A(Y) bad). Then re-derive Theorem 2.3 from Corollary 2.2 under this formalization. This directly tests whether the quantifier ambiguity breaks the positive result.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After reading the full text, I do not find a load-bearing flaw in the central claim. The reader's weakest assumption—that Definition 1.2 must secretly mean simultaneous robustness—does not land. Under the strong contamination model (Definition 1.1), the adversary inspects X and is therefore a function of X. For a deterministic estimator A, the condition 'for every adversary f, P_X(A(f(X)) in G) >= 0.9' is equivalent to 'P_X(for every admissible epsilon-corruption Y of X, A(Y) in G) >= 0.9': if a measurable set E of clean samples had, for each X in E, some bad corruption, then one adversary choosing such a bad corruption pointwise on E would have failure probability at least P(E), violating the definition. Hence the set S of fully robust samples has D^{tensor n}-measure at least 0.9, and the isoperimetric blow-up in Theorem 2.3 goes through. The converse (Theorem 3.7) also has a coherent proof structure. The main issues are typographical and should be corrected: Theorem 3.7's conclusion |I| >= 1 - c eta n should be |I| >= 1 - O(epsilon) n; Lemma 3.3's union-bound exponent appears with the wrong sign (it should be -n epsilon - j); Lemma 3.4's 'B_j = empty' claim is for large j, not small j; and Algorithm 2 has indexing typos. None of these changes the central argument.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the relationship between two outlier models: adversarial contamination, where an adversary inspects and corrupts an ε-fraction of the sample, and heavy-tailed contamination, where outliers arise naturally from a distribution with only low-order moment bounds. The first main result (Theorem 2.3) states that any deterministic estimator that is adversarially robust in the strong contamination model also achieves high-probability, sub-Gaussian-type guarantees on clean i.i.d. data, with failure probability exponentially small in n. The proof uses an isoperimetric blow-up argument on the set of samples on which the estimator is robust. Corollaries are drawn for mean estimation, covariance estimation, and linear regression. The second main result (Theorem 3.7, informal Theorem 1.12) constructs a heavy-tailed mean estimator (Algorithm 2) that is optimal in the heavy-tailed model but whose success on a pointset forces the existence of a large stable subset of that pointset. The paper concludes that any black-box reduction from adversarial to heavy-tailed mean estimation must effectively filter the data into a stable set, so heavy-tailed contamination is qualitatively weaker than adversarial contamination.","tokens_in":23102,"tokens_out":15600,"duration_ms":143685,"significance":"If the technical details are repaired, this is a significant conceptual contribution. The transfer theorem is elegant and likely correct, and it provides a black-box explanation for the observed transferability of robust estimators across the two models. The separation result, if established, answers a natural question and has implications for algorithm design in heavy-tailed estimation. The paper is largely self-contained: the main arguments use isoperimetric concentration, empirical process inequalities, and stability arguments rather than fitting the conclusion. The authors also correctly flag the determinism restriction and the limitation that the abstract transfer theorem requires the adversarial robustness condition to hold in the strong, worst-case-over-adversaries sense.","major_comments":[{"comment":"The quantification over adversaries in Definition 1.2 is left implicit. The proof of Theorem 2.3 requires the strong reading that, with probability at least 9/10 over the clean sample X, the estimator succeeds against every admissible ε-corruption of X simultaneously; otherwise the set S = {X : A is ε-robust on X} need not have D^{⊗n}-measure at least 0.9, and Corollary 2.2 cannot be applied. Under the strong contamination model this is the natural worst-case reading, but the definition should state it explicitly (for example, \"for every admissible adversary,\" or \"with probability at least 9/10 over X, A succeeds on all ε-corruptions of X\"). This is a load-bearing point because the set of fully robust samples is exactly what the isoperimetric argument blows up.","section":"Section 2, Definition 1.2 and Theorem 2.3"},{"comment":"The statement of Theorem 3.7 contains a dimensionally inconsistent conclusion: it claims |I| ≥ 1 − cηn, where η is an error in the ambient norm and the right-hand side is not a number of points in a meaningful way. The proof actually shows |I| ≥ (1 − c₁ε/2)n, with no dependence on η. The printed statement is false for small η (for example, η = 0 would force |I| ≥ 1, which the proof does not give) and does not deliver the 0.99n stable subset asserted in Theorem 1.12 unless corrected. Please replace the conclusion with the correct bound derived in the proof, such as |I| ≥ (1 − Cε)n, and align the constant notation.","section":"Section 3, Theorem 3.7"},{"comment":"The proof of Lemma 3.5 has a gap in the quantitative argument. In Case 2, after selecting the event where the weighted sum over [n]\\H is at least m*/2 and removing a set G of size at most ρn/4, the lower bound for an arbitrary I with |I| ≥ n−|H|−ρn/4 is only ((n−|H|)/n)(m*/2 − m*/8) ≥ 3m*/16, not m*/4 as claimed. Since the subsequent factor of 256 is then divided out, this yields at best 3m*/4096, which is weaker than the claimed m*/1024. In Case 1, the lower bound also appears to ignore the capacity constraint w_i ≤ 1/((1−ρ/4)n) in W_{ρ/4}; for ρ near 1/2, the good points in H can carry only a bounded fraction of the total weight, so the displayed product ρ/4 · 1/16 · m*/(64ρ) requires justification. Because Lemma 3.5 is used in the proofs of both Theorem 3.1 and Theorem 3.7, this gap is load-bearing and must be repaired or the constants must be adjusted accordingly.","section":"Section 3, Lemma 3.5"}],"minor_comments":[{"comment":"The displayed probability bound \"P{Z_j ≥ r_j} ≤ exp{−nε + j}\" has the wrong sign in the exponent; it should be exp{−nε − j}, since the preceding chain lower-bounds the exponent by nε + j. As written, the union bound over j would diverge.","section":"Section 3, Lemma 3.3"},{"comment":"The sentence \"noting that B ∪ 4nε/j=1 B_j as B_j = ∅ for j < 4nε by Lemma 3.3\" is incorrect: Lemma 3.3 shows that the annuli B_j are empty for large j (j > 4nε), not for small j. The summation range over j = 1 to 4nε is consistent with the intended meaning, but the text should be corrected.","section":"Section 3, Lemma 3.4"},{"comment":"In the display bounding spread({⟨X_i,u⟩},⟨~μ,u⟩), the expression \"sqrt(2)·(spread({⟨X_i,u⟩},⟨~μ,u⟩) + ||~μ||)\" is circular; the first term should be the spread about 0, not about ~μ. This appears to be a typographical error, as the subsequent bound uses the intended quantity.","section":"Section 3, proof of Theorem 3.1"},{"comment":"There are several indexing and notation typos in Algorithm 2: line 4 writes {⟨x_i,u⟩}_{i=1}^k instead of {⟨x_i,u⟩}_{i=1}^n, and line 5 calls \"Comparison(v)\" although Algorithm 1 is named \"Comparison\". The text also uses \"V ersions\" in the input line. These should be cleaned up.","section":"Section 3, Algorithm 2"},{"comment":"The proof uses \"for any c₁εn/16 ≤ i ≤ n−c₁εn/16\" where i is an index, not a real number; the interval should be written for integers i between c₁εn/16 and n−c₁εn/16. Additionally, the constants c and c₁ are used inconsistently in the theorem statement and the proof.","section":"Section 3, proof of Theorem 3.7"}],"recommendation":"major_revision","confidential_remarks":"The conceptual contribution is solid and the transfer theorem is clean. The main reason for major revision is the gap in Lemma 3.5, which is load-bearing for both Theorem 3.1 and Theorem 3.7, and the incorrect statement of Theorem 3.7's subset-size conclusion. These appear fixable, and the paper would then be a strong contribution. The paper's self-citation to CTBJ22 is only background and is not load-bearing."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know upfront. Theorem 2.3 is real and clean: any deterministic estimator that is adversarially robust with constant probability against ε-corruption is automatically a sub-Gaussian/heavy-tailed estimator with failure probability 1 - 2e^{-c(ε)n}, for any estimation problem with i.i.d. data. The proof is a one-page isoperimetric argument plus the triangle inequality for Hamming distance. And the separation result for mean estimation is a genuine advance: Algorithm 2 attains optimal heavy-tailed rates, yet any black-box reduction from the adversarial setting to it must output a pointset with a 0.99-fraction stable subset. This goes well beyond the algorithm-specific sufficient conditions of DKP21 and HLZ20a.\n\nThe paper earns credit for the applications (mean, covariance, linear regression), for the log tail-decay condition and quantile-smoothed spread at the core of Algorithm 2, and for an improved analysis of stability-based estimators that removes a logarithmic factor. The citation pattern is fine; the one self-citation is background and not load-bearing. The stated scope limits — deterministic estimators only, separation for mean estimation only — are acknowledged up front and reasonable.\n\nSoft spots, in proportion. The reader's main worry — that Definition 1.2 must secretly mean simultaneous robustness for Theorem 2.3 to go through — turns out not to land. Under the strong contamination model the adversary is a function of X, so 'for every adversary, P_X(success) ≥ 0.9' is equivalent to 'the set of samples that survive all ε-corruptions has measure ≥ 0.9.' That's exactly the set the proof needs. The paper should state this explicitly rather than leave it implicit, but it's a presentation gap, not a mathematical one.\n\nThe genuine problems are in Section 3's write-up. Theorem 3.7's conclusion says |I| ≥ 1 - cηn; the proof gives 1 - O(ε)n. Lemma 3.3's union-bound exponent has a sign error (should be -(nε + j)). Lemma 3.4 claims B_j is empty for small j, which is backwards. Algorithm 2 has index typos. All fixable. More substantial: the proof of Theorem 3.7 passes from spread weights to a minimum over W_{c1ε/16} without specifying the relationships among the constants in the exponential weights that make this valid. I did not find a contradiction, but that constant bookkeeping has to be made explicit before the result is fully verified.\n\nWho this is for: anyone working on robust mean estimation or on black-box reductions between contamination models. It deserves a serious referee — the central claims are novel and sound, the flaws are presentation-level. Send it out, with a push for a thorough revision of Section 3.","headline":"A genuine black-box transference theorem plus a strong separation for mean estimation; central claims hold up, but Section 3 needs a careful cleanup before it is fully verifiable.","tokens_in":23620,"tokens_out":24005,"would_cite":true,"duration_ms":203954,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62G35","62F35","62G05","60E15"],"pacs":[],"model":"deepseek-v4-flash","headline":"Heavy-tailed contamination is strictly weaker than adversarial contamination for i.i.d. estimation, provided the robustness guarantee quantifies over every corruption at once.","keywords":["heavy-tailed contamination","adversarial contamination","robust mean estimation","black-box reductions","sub-Gaussian rates","isoperimetric blow-up","stability","tail-decay condition"],"falsifier":"Construct a deterministic estimator $A$ and a distribution $\\mathcal{D}$ such that for every fixed $\\varepsilon$-corruption, $A$ succeeds with probability at least $9/10$ over the clean sample, but the set of clean samples on which $A$ succeeds simultaneously against all corruptions has $\\mathcal{D}^{\\otimes n}$-measure below $0.9$; the blow-up argument in Theorem 2.3 requires that set to have measure at least $0.9$, so such an example would break the proof.","tokens_in":22622,"feed_emoji":"📊","tokens_out":15692,"duration_ms":129914,"temperature":0.7,"pith_summary":"This paper tries to establish a strict ordering between two outlier models that have driven recent robust statistics: adversarial contamination, where an adversary inspects the sample and corrupts a constant fraction after seeing it, and heavy-tailed contamination, where outliers arise naturally because the distribution only has bounded low-order moments. Its first theorem says that any deterministic estimator that is adversarially robust in the strong sense of Definition 1.2 is automatically a high-probability heavy-tailed estimator, with failure probability at most $1-2\\exp(-c(\\varepsilon)n)$, for every estimation problem with independent and identically distributed data. From this it follows that optimal adversarially robust estimators for mean estimation, covariance estimation, and linear regression are also optimal in the heavy-tailed model in the constant-$\\varepsilon$ regime. The converse direction, proved for mean estimation, shows that a specially constructed optimal heavy-tailed estimator is not adversarially robust, and in fact any black-box reduction from adversarial to heavy-tailed mean estimation must output a pointset containing a stable subset that covers $99\\%$ of the points. The paper therefore concludes that heavy-tailed contamination is strictly easier than adversarial contamination.","feed_headline":"Heavy-tailed outliers are strictly easier than adversarial ones","feed_subtitle":"Adversarial-robust estimators transfer to heavy tails for free; the reverse needs a 99% stable subset.","key_machinery":"The proof rests on two mechanisms. The first is an isoperimetric blow-up argument in the Hamming metric: if $S$ is the set of clean samples on which the estimator succeeds against every $\\varepsilon$-corruption and $\\mathcal{D}^{\\otimes n}(S) \\ge 0.9$, then the Hamming $\\varepsilon n$-neighborhood of $S$ has measure at least $1-2e^{-c(\\varepsilon)n}$ (Corollary 2.2, from a standard concentration inequality), and by the estimator's own robustness every point in that neighborhood is also good. The second is a quantile-smoothed scale estimator (Algorithm 2) that projects the data onto every unit direction and computes an exponentially weighted spread, $\\mathrm{spread}(Y,y)=\\sqrt{\\sum_i w_i(y_{(i)}-y)^2}$, with weights $w_i$ decaying exponentially with $\\min(i,n-i)$, concentrated on the middle of the one-dimensional empirical distribution; the algorithm then perturbs a stability-based mean estimate by $\\pm\\sqrt{\\varepsilon}\\sigma_v v$. A logarithmic tail-decay condition (Lemma 3.3) guarantees this spread stays bounded on heavy-tailed samples, while any adversarially engineered outlier mass forces the spread to be large unless the input already contains a $0.99$-fraction stable subset. The analysis also sharpens the Gaussian rounding scheme used in earlier stability-based estimators, removing a logarithmic gap in prior rate guarantees.","core_discovery":"The central claim is that the adversarial contamination model is strictly stronger than the heavy-tailed model for statistical estimation with i.i.d. data. Formally, Theorem 2.3 states that any deterministic estimator satisfying Definition 1.2 -- success with probability at least $9/10$ against every $\\varepsilon$-corruption of the clean sample -- satisfies the same guarantee on clean heavy-tailed samples with probability at least $1-2\\exp(-c(\\varepsilon)n)$, and more generally is resilient to $\\varepsilon'$-corruption with probability $1-2\\exp(-n(\\varepsilon-\\varepsilon')^2)$ for $\\varepsilon'<\\varepsilon$. For mean estimation, Theorems 1.12 and 3.7 establish the converse direction fails: Algorithm 2 is an optimal heavy-tailed estimator, yet if its two outputs are both within $\\eta$ of some point $z$, then the input pointset must contain a subset $I$ of size at least $1-c\\eta n$ whose mean is within $C\\eta$ of $z$ and whose covariance is bounded by $C\\eta^2/\\varepsilon$. Any black-box reduction from adversarially robust mean estimation to heavy-tailed mean estimation, with $\\varepsilon=0.1$ and $\\log(1/\\delta)=\\Omega(n)$, therefore has to output a pointset containing a $0.99$-fraction stable subset with the stated mean and covariance bounds. Since adversarially corrupted datasets are only guaranteed to contain stable subsets of size $0.9n$, the output of any such reduction is qualitatively different from an adversarially corrupted dataset, which is what the paper means by 'heavy-tailed contamination is easier.'","pith_inferences":["Editorial inference: If the separation is correct, a practical system that wants both properties should start from an adversarially robust estimator, which transfers to heavy tails for free; starting from a heavy-tailed estimator and hoping to add adversarial robustness later would require a nontrivial pre-filter that creates a $0.99$-fraction stable set.","Editorial inference: The theorem's dependence on determinism suggests that randomized estimators with internal failure probability bounded away from zero are a separate case; the high-probability transfer would need an assumption such as failure probability $e^{-n}$ rather than a constant.","Editorial inference: The logarithmic tail-decay condition could serve as a diagnostic for adversarial corruption: on clean heavy-tailed samples the spread of every one-dimensional projection stays bounded, while a tiny adversarial cluster far from the center inflates the spread unless a large stable subset already exists.","Editorial inference: The explicit no-reduction construction is given for mean estimation; carrying out the same construction for covariance estimation or linear regression would show whether the strict separation extends beyond the simplest high-dimensional task."],"forward_implications":["In the constant-$\\varepsilon$ regime, any optimal adversarially robust mean estimator is also an optimal heavy-tailed estimator, with failure probability $\\delta\\sim e^{-\\Theta(n)}$, and no extra algorithmic work is needed.","The same transfer gives optimal heavy-tailed covariance estimation under an $L_4-L_2$ hypercontractivity assumption and optimal heavy-tailed linear regression, because each has optimal adversarial estimators whose success regions are large.","Confidence intervals proved under adversarial contamination automatically hold with high probability on clean heavy-tailed samples.","No black-box reduction from adversarial to heavy-tailed mean estimation can pass the sample through as-is; the intermediate pointset must have a stable subset of size $0.99m$ with bounded mean and covariance, which is stronger than what an $\\varepsilon=0.1$ adversarial dataset guarantees.","A heavy-tailed estimator such as Algorithm 2 that achieves optimal rates can break completely under adversarial corruption, and any reduction that tries to reuse it must do the outlier filtering itself."],"supporting_citations":[{"why":"Supplies the Hamming-distance concentration bound used to blow up the set of good samples in Corollary 2.2 and Theorem 2.3.","marker":"[BLM13]"},{"why":"Establishes the optimal heavy-tailed mean-estimation rate that adversarial estimators are transferred to in Corollary 1.6.","marker":"[LM19]"},{"why":"Provides the Gaussian rounding scheme whose refined analysis lets Algorithm 2's intermediate stability-based estimator achieve sub-Gaussian rates.","marker":"[DL19]"},{"why":"Gives the trimmed-mean analysis and tail bounds used to control truncated variances and to prove the spread estimates in Lemmas 3.2-3.6.","marker":"[LM21]"},{"why":"Introduces the stability criterion underlying Definition 1.11's $(\\gamma,\\nu)$-stable sets, which appear in Theorem 3.7.","marker":"[SCV18]"},{"why":"Analyzes the stability-based mean estimator used as the base estimate in Algorithm 2; the paper sharpens its analysis to remove a logarithmic factor.","marker":"[DKP20]"},{"why":"Prior structural transfers between adversarial and heavy-tailed mean estimation via stability, which the paper extends to black-box reductions.","marker":"[HLZ20a]"},{"why":"Provides the computationally efficient heavy-tailed mean estimator achieving optimal rates, the benchmark for the optimality claims.","marker":"[Hop20]"}],"fun_headline_variants":["Adversarial robust estimators transfer to heavy tails for free","Contrary: heavy-tailed estimators can't handle adversarial","Heavy-tailed contamination is the easier outlier model","Adversarial robustness implies heavy-tailed, not conversely","Study shows heavy-tailed contamination is strictly easier"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument assumes that Definition 1.2's $9/10$ success probability is a simultaneous guarantee: with probability at least $9/10$ over the clean sample, the estimator succeeds against every possible $\\varepsilon$-corruption of that sample, so the set of fully robust samples has product measure at least $0.9$; if the success requirement were instead applied separately to each adversary, that set need not be large and the isoperimetric blow-up step would fail.","fun_headline_variants_meta":{"raw":{"variants":["Adversarial robust estimators transfer to heavy tails for free","Contrary: heavy-tailed estimators can't handle adversarial","Heavy-tailed contamination is the easier outlier model","Adversarial robustness implies heavy-tailed, not conversely","Study shows heavy-tailed contamination is strictly easier"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000343,"raw_usage":{"total_tokens":2003,"prompt_tokens":1180,"completion_tokens":823,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":796,"completion_tokens_details":{"reasoning_tokens":749}},"tokens_in":796,"tokens_out":823,"duration_ms":8322,"temperature":1.0,"reasoning_tokens":749,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T14:28:56.337666+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a deterministic estimator $A$ and a distribution $\\mathcal{D}$ such that for every fixed $\\varepsilon$-corruption, $A$ succeeds with probability at least $9/10$ over the clean sample, but the set of clean samples on which $A$ succeeds simultaneously against all corruptions has $\\mathcal{D}^{\\otimes n}$-measure below $0.9$; the blow-up argument in Theorem 2.3 requires that set to have measure at least $0.9$, so such an example would break the proof.","supporting_citations":[],"review_version":1}