{"id":"4c578e5d-6fff-4fcb-965d-ba6d217d1e12","arxiv_id":"2506.18020","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For f misbehaving workers among n, data poisoning degrades the uniform stability of robust distributed (S)GD by Θ(f/(n-f)), while Byzantine failures degrade it by at least Ω(√(f/(n-2f))) for f ≥ n/3, implying strictly worse generalization.","lead":"This paper proves that Byzantine failures, where misbehaving workers can send arbitrary updates, cause a fundamentally larger degradation of generalization than data poisoning, where workers only corrupt their local data, in robust distributed learning. It provides matching tight bounds showing a strict rate gap for most adversarial fractions, giving a theoretical explanation for a known empirical phenomenon.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Byzantine lower-bound proof hinges on a threshold test that as printed never triggers β; fix to strict inequality, and restrict abstract claim to f≥n/3.","rationale":"The reader's weakest-assumption analysis identifies the same threshold inconsistency in Algorithm 1 that I find most load-bearing. The theorem's lower bound depends entirely on Byzantine workers adapting their message based on whether worker 1's gradient is exactly C (unperturbed) or (m-1)/m C (perturbed). With the printed '≤' condition, both values satisfy the test, so the Byzantine workers never send β and the claimed adversarial subset selection cannot occur; the proof as written does not establish the Ω(√(f/(n-2f))) stability gap. This is a concrete, checkable defect rather than a stylistic concern. The remedy is a one-character fix, and the surrounding algebra in Section C.3 is consistent with the strict-inequality version, so the underlying theorem is very likely salvageable. However, because the central claim of the paper relies on this lower bound and the abstract overstates the regime by omitting the f ≥ n/3 restriction, I do not see grounds to move beyond the reader's CONDITIONAL verdict; the paper should be corrected before acceptance. My independent reading found no deeper circularity or fitting issue: the upper bounds, the data-poisoning lower bounds, and the generalization-gap connection are all internally coherent, and the numerical section honestly discloses that the low-f regime remains empirically supported rather than theoretically proven. Thus the reader's conditional recommendation stands unchanged.","tokens_in":40453,"tokens_out":8102,"duration_ms":79903,"concrete_test":"Implement the one-dimensional construction from Section C.3 with n-f even, f ≥ n/3, and m ≥ 2. Run GD with SMEA for T iterations under two versions of the Byzantine trigger: (a) the printed 'if g_1 ≤ C' and (b) the corrected 'if g_1 < C'. For each version, verify at every iteration which subset SMEA selects in the unperturbed and perturbed runs, and compute |θ_T - θ'_T|. The lower bound Ω(γC²T√(f/(n-2f))) should be reproduced with the corrected trigger, while the printed trigger should fail to produce the claimed selection and divergence. This check isolates whether the concern is a proof typo or a genuine flaw in the lower-bound argument.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing concern is the Byzantine lower-bound construction in Section C.3 (Theorem 3.2). Algorithm 1 as printed uses the condition 'if g_1 ≤ C'. In the unperturbed run worker 1 sends g_1 = C, and in the perturbed run g_1 = (m-1)/m C < C, so the condition is true in both runs and the Byzantine workers always return the arbitrarily high value; they never send β. Consequently the claimed SMEA selection of Select_{n-2f}(H+) ∪ B in the unperturbed run does not follow, and the stated divergence θ_T = -γCT(1 + 1/2√(f/(n-2f))) is not a consequence of the printed algorithm. The proof needs the strict test 'if g_1 < C' (or an equivalent identity-based trigger) so that the Byzantine workers can distinguish the two neighboring runs. This is a localized, correctable defect, but it sits exactly at the hinge of the Byzantine-versus-poisoning separation for f ≥ n/3, because without this trigger the lower bound reduces to the negligible O(γCT/((n-f)m)) term. A secondary issue is that the abstract states the separation without the f ≥ n/3 restriction that Theorem 3.2 and Theorem 4.2 actually require; for f < n/3 the paper presents only numerics and an upper-bound/lower-bound gap that does not establish an order-of-magnitude separation.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the uniform algorithmic stability of robust distributed (S)GD with the SMEA aggregation rule under two threat models: data poisoning and Byzantine failures. It proves matching upper and lower bounds for data poisoning—Θ(γC²T(f/(n−f)+1/((n−f)m))) in the convex case and Θ(C²/μ(f/(n−f)+1/((n−f)m))) in the strongly convex case—and a Byzantine lower bound Ω(γC²T(√(f/(n−2f))+1+1/((n−f)m))) for n/3≤f<n/2. Theorem 4.2 converts these stability bounds into a generalization-error gap of order (n−f)/√(f(n−2f)) between Byzantine failures and data poisoning. The appendix contains detailed proofs of all results, and numerical experiments illustrate the gap.","tokens_in":40678,"tokens_out":20800,"duration_ms":189919,"significance":"If the results hold, this is the first theoretical explanation for the empirically observed worse generalization of Byzantine attacks compared with data poisoning in robust distributed learning, and the data-poisoning bounds are genuinely tight with explicit constructions. The stability framework for (f,κ)-robust aggregation rules and the proof technique of comparing robust updates with honest averaging are useful contributions that go beyond the specific SMEA case. The main caveats are that the Byzantine lower bound and the generalization-gap theorem are proved only for f≥n/3, and that the load-bearing Byzantine trigger construction in Section C.3 contains a localized but correctable defect.","major_comments":[{"comment":"The Byzantine trigger condition 'if g_1 ≤ C' is satisfied in both the unperturbed run (where worker 1 sends g_1 = C) and the perturbed run (where g_1 = (m−1)/m C < C). Consequently the Byzantine workers always return the arbitrarily high value and never send β. The claimed SMEA selection of Select_{n−2f}(H+) ∪ B and the divergence θ_T = −γCT(1 + (1/2)√(f/(n−2f))) are therefore not consequences of the printed algorithm, and the lower bound reduces to the negligible O(γCT/((n−f)m)) term. The proof should use a strict inequality (e.g., 'if g_1 < C then return high, else return β') so that the trigger fires only in the perturbed run. This is a load-bearing defect because the Byzantine-versus-poisoning separation for f ≥ n/3 rests precisely on this trigger.","section":"Section C.3, Algorithm 1 and Theorem 3.2"},{"comment":"The abstract states the Byzantine degradation is Ω(√(f/(n−2f))) without any restriction on f, and the conclusion claims a fundamental gap between the two threat models in unqualified form. However, Theorem 3.2 and Theorem 4.2 hold only for n/3 ≤ f < n/2. For f < n/3 the paper supplies only a weaker lower bound Ω(γC²T f/(n−2f)) (Section C.3, case iii) and numerical evidence; no order-of-magnitude separation is established in that regime. The abstract and conclusion should explicitly restrict the strong separation claim to f ≥ n/3, or state precisely what is known for smaller f.","section":"Abstract, Section 1, Theorems 3.2 and 4.2"},{"comment":"The proof asserts that a single choice of honest data distributions with pivot p₁ = (1/2)δ₀ + (1/2)δ₋C makes the two possible honest datasets align with both the worst-case Byzantine and data-poisoning lower-bound scenarios. But the Byzantine construction in Section C.3 uses a pivot whose two values are C and 0 (with m=1), while the data-poisoning construction in Section D.2.1 uses pivot values 0 and −C and different values for the other honest workers. These are different distributions, so the proof as written does not show that the two lower bounds can be realized on the same {pᵢ}. The theorem can be repaired by using the general two-point-pivot form of Lemma 4.1 (which holds for any support {a,b} with |a−b|=C) and applying the data-poisoning upper bound from Theorem 3.3 to the distribution chosen for the Byzantine construction, but that step needs to be made explicit.","section":"Section 4, proof of Theorem 4.2 and Lemma 4.1"}],"minor_comments":[{"comment":"The statements contain a typo: 'sup_z E_A[|ℓ(A(S');z)−ℓ(A(S');z)|]' should read 'ℓ(A(S);z)−ℓ(A(S');z)' in both theorems; the proofs use the correct difference.","section":"Theorems 3.1 and 3.3"},{"comment":"The phrase 'Consider the setting of Theorem 4.1' is confusing because no Theorem 4.1 appears in the paper; the reference should be to Lemma 4.1 or to the setting of Section 4 more generally.","section":"Section 4, Theorem 4.2"},{"comment":"The uniform stability inequality should include an absolute value, i.e., sup_z |E[ℓ(A(S);z)−ℓ(A(S');z)]| ≤ ε, to avoid sign ambiguity; the subsequent proofs and Proposition 2.1 use the absolute value implicitly.","section":"Definition 2.4"},{"comment":"The notation for the neighboring datasets is terse: for S, worker 1 has z^{(1,1)} = −C and all other samples 0, while for S' all samples of worker 1 are 0. The text should state clearly which dataset the primed quantities refer to, especially because the proof then writes g^{(1)}_t = −C/m.","section":"Section D.2.1, dataset construction"}],"recommendation":"major_revision","confidential_remarks":"The paper is in scope for the journal and the core idea is sound, but the three issues above need to be fixed before publication. The Algorithm 1 defect is likely a typo and is easily corrected, and the abstract overclaim is a presentation fix. The mismatch in Theorem 4.2's proof requires a careful rewrite of the argument, not merely a wording change. I see no concern about citation practices or novelty relative to prior work; the reliance on Allouah et al. is acknowledged."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core of this paper is good: it gives the first theoretical explanation, via uniform stability, for why Byzantine failures hurt generalization more than data poisoning in robust distributed learning. The matching upper and lower bounds for data poisoning are real contributions, and the Byzantine lower bound for f ≥ n/3 is the key new result. The generalization-gap construction in Lemma 4.1 is clever and does what it claims: it makes the stability gap show up directly as a gap in expected generalization error. The proofs are detailed, the constructions are explicit, and there is no sign of fitted parameters or circular reasoning. Relying on the κ bounds from Allouah et al. is fine; that is standard equipment, not a hidden assumption.\n\nThat said, the stress-test concern is correct and it lands exactly where it matters. Algorithm 1 in Appendix C.3 uses the condition \"if g1 ≤ C\". In both neighboring runs the honest worker's gradient satisfies that inequality, so the Byzantine workers always return the arbitrary large value and never send β. As printed, the claimed SMEA selection and the divergence θ_T = −γCT(1 + 1/2 sqrt(f/(n−2f))) do not follow. The fix is obvious—use g1 < C, or any identity-based trigger—and the proof sketch in the main text already describes the intended trigger correctly. This is a localized typo, not a structural flaw, but it sits at the hinge of the Byzantine lower bound, so it must be corrected before the paper is trusted.\n\nThe second issue is milder but still real. The abstract states the Byzantine lower bound and the generalization gap without the f ≥ n/3 condition. The theorems themselves have that condition, and for f < n/3 the paper only has a weaker lower bound plus numerics. The experiments are suggestive, but they do not establish an order-of-magnitude separation in that regime. The abstract overclaims.\n\nOverall: this paper deserves a serious referee. The main idea is sound, the f ≥ n/3 separation is likely correct once the threshold is fixed, and the work fills a genuine gap in the literature. I would send it to peer review with a request to fix Algorithm 1 and to restrict the abstract and any summary claims to the regime actually proved.","headline":"First real theoretical separation between Byzantine and poisoning generalization, but the Byzantine lower-bound proof as printed has a threshold bug and the abstract claims more than the f≥n/3 theorem proves.","tokens_in":41251,"tokens_out":2167,"would_cite":true,"duration_ms":24030,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Byzantine failures cause strictly worse generalization than data poisoning in robust distributed learning.","keywords":["uniform stability","Byzantine failures","data poisoning","robust distributed learning","SMEA","generalization gap","convex optimization","algorithmic stability"],"falsifier":"On the paper's one-dimensional construction ($\\ell(\\theta;z)=z\\theta$, workers split between $+C$ and $-C$, and Byzantine workers running the pseudo-code as printed), change one honest sample from $C$ to $0$ and run GD with SMEA for $T$ steps. Under the printed condition `if $g_1 \\le C$`, the Byzantine workers return the huge value on both trajectories, so the perturbed run will not diverge at the rate $\\gamma C T/((n-f)m)$; observing no such divergence would falsify the claimed $\\Omega(\\gamma C^2 T \\sqrt{f/(n-2f)})$ lower bound.","tokens_in":40213,"feed_emoji":"📉","tokens_out":8192,"duration_ms":77175,"temperature":0.7,"pith_summary":"The paper asks whether two standard attack models in distributed learning—Byzantine failures, where workers may send arbitrary messages, and data poisoning, where workers can only corrupt local data—differ in how much they hurt generalization. It proves they do: for robust distributed (S)GD with SMEA under smooth convex losses, uniform stability degrades by $\\Theta\\!\\left(\\frac{f}{n-f}\\right)$ under data poisoning, but by $\\Omega\\!\\left(\\sqrt{\\frac{f}{n-2f}}\\right)$ under Byzantine failures when $n/3 \\le f < n/2$. Because uniform stability controls the gap between empirical and population risk, this gives a concrete generalization gap: Byzantine attacks can make the generalization error a factor $\\Omega\\!\\left(\\frac{n-f}{\\sqrt{f(n-2f)}}\\right)$ larger than any data poisoning attack. The difference comes from the extra regularity of poisoned updates, which remain gradients of a smooth loss, while Byzantine updates are arbitrary and adaptive.","feed_headline":"Byzantine attacks hurt generalization worse than poisoned data","feed_subtitle":"New tight stability bounds show the gap is fundamental, not just an artifact of weak poisoning attacks.","key_machinery":"The central object is SMEA (smallest maximum eigenvalue averaging), the robust aggregation rule that averages the $n-f$ worker updates whose empirical covariance has the smallest spectral norm. The argument is carried by uniform stability: replacing one honest sample must move the output loss by at most $\\varepsilon$, and the paper bounds $\\varepsilon$ by comparing the robust update to the honest-average update. Under data poisoning, every update—including the poisoned ones—is a gradient of a smooth loss, so the analysis can intersect the two SMEA-selected subsets and charge the instability to the $f$ workers that swap: an additive $\\frac{f}{n-f}$ term. Under Byzantine failures, corrupted vectors have no regularity, forcing the comparison to go through the $(f,\\kappa)$-robustness coefficient $\\kappa$; since $\\kappa \\ge \\frac{f}{n-2f}$, the additive term is $\\sqrt{\\frac{f}{n-2f}}$. SMEA also violates the loss's co-coercivity inequality because its selected subset changes with the parameters, and this violation is exactly where the additive instability enters.","core_discovery":"On its own terms, the paper claims a fundamental, unavoidable separation between the two threat models. Under data poisoning, the uniform stability of GD/SGD with SMEA is tightly characterized: $\\Theta(\\gamma C^2 T (\\frac{f}{n-f} + \\frac{1}{(n-f)m}))$ in the convex case and $\\Theta(\\frac{C^2}{\\mu}(\\frac{f}{n-f}+\\frac{1}{(n-f)m}))$ in the strongly convex case. Under Byzantine failures for $n/3 \\le f < n/2$, the paper constructs a linear-loss instance where SMEA discards a whole block of honest gradients and an adaptive Byzantine switch makes the two neighboring runs diverge, yielding a lower bound $\\Omega(\\gamma C^2 T(\\sqrt{\\frac{f}{n-2f}} + \\frac{1}{(n-f)m}))$. The upper bounds match these rates up to constants, and Theorem 4.2 converts the stability gap into a generalization-error ratio. The author's claim is that this gap is structural: data poisoning is strictly less harmful to population risk than Byzantine failure, even when both are designed optimally.","pith_inferences":["The proof identifies a design criterion for robust aggregation: preserving co-coercivity of the loss would eliminate the worker-swapping term entirely; the open question of whether such a rule exists becomes a concrete route to closing the gap.","The same comparison—regular poisoned gradients vs arbitrary adaptive Byzantine vectors—should reappear in momentum, variance reduction, or multi-step local-update methods, since the recursions only rely on the boundedness and smoothness of the updates.","A practical test on heterogeneous federated benchmarks: fix a strong Byzantine attack and a near-optimal poisoning attack, vary $f$, and measure test accuracy; Theorem 4.2 predicts the gap should scale roughly like $(n-f)/\\sqrt{f(n-2f)}$ rather than staying constant."],"forward_implications":["Algorithms with optimal optimization guarantees under both threat models will still show different population risk; test error, not just training error, must be the benchmark.","Under data poisoning, the $\\Theta(\\frac{f}{n-f})$ stability degradation is unavoidable for SMEA, so any attempt to get better generalization under poisoning must change the aggregation rule.","As $f$ approaches $n/2$, the Byzantine generalization gap grows without bound, while the poisoning penalty stays bounded by $\\frac{f}{n-f}$, so the two threat models separate most sharply in the high-Byzantine regime.","In the strongly convex case, both gaps appear as a one-time $O(1/\\mu)$ term rather than accumulating over iterations, which predicts that the relative harm of Byzantine failures is largest in early or convex regimes."],"supporting_citations":[{"why":"Provides the expansivity recursion and classic stability bounds that both upper-bound proofs extend to the robust setting.","marker":"Hardt et al. (2016)"},{"why":"Defines $(f,\\kappa)$-robustness, proves the lower bound $\\kappa \\ge f/(n-2f)$, and shows matching optimization error for both threat models.","marker":"Allouah et al. (2023a)"},{"why":"Introduces SMEA and bounds its robustness coefficient, setting the scale $\\sqrt{f/(n-f)}$ used for tightness.","marker":"Allouah et al. (2023b)"},{"why":"Gives the uniform-stability-to-generalization transfer that Proposition 2.1 applies.","marker":"Bousquet and Elisseeff (2002)"},{"why":"Establishes the optimization-error equivalence between the two threat models, which this paper contrasts with a generalization gap.","marker":"Farhadkhani et al. (2024b)"},{"why":"Supplies the co-coercivity inequality whose violation by SMEA is the mechanism behind the additive instability.","marker":"Bach (2024)"}],"fun_headline_variants":["Byzantine failures harm generalization more than data poisoning","First proof: Byzantine attacks degrade generalization more","Byzantine vs poisoning: generalization gap is fundamental","Tight stability bounds show Byzantine failures worse for generalization"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The Byzantine lower bound assumes the attacker can observe a single honest gradient and switch between a crafted value $\\beta$ and an arbitrarily large value exactly when one sample changes; the paper's printed pseudo-code uses the trigger `if $g_1 \\le C$`, which is satisfied in both neighboring runs, so the proof as written depends on that comparison being implemented as a strict inequality.","fun_headline_variants_meta":{"raw":{"variants":["Byzantine failures harm generalization more than data poisoning","First proof: Byzantine attacks degrade generalization more","Byzantine vs poisoning: generalization gap is fundamental","Tight stability bounds show Byzantine failures worse for generalization"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000533,"raw_usage":{"total_tokens":2557,"prompt_tokens":927,"completion_tokens":1630,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":543,"completion_tokens_details":{"reasoning_tokens":1569}},"tokens_in":543,"tokens_out":1630,"duration_ms":11968,"temperature":1.0,"reasoning_tokens":1569,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T18:56:20.859791+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On the paper's one-dimensional construction ($\\ell(\\theta;z)=z\\theta$, workers split between $+C$ and $-C$, and Byzantine workers running the pseudo-code as printed), change one honest sample from $C$ to $0$ and run GD with SMEA for $T$ steps. Under the printed condition `if $g_1 \\le C$`, the Byzantine workers return the huge value on both trajectories, so the perturbed run will not diverge at the rate $\\gamma C T/((n-f)m)$; observing no such divergence would falsify the claimed $\\Omega(\\gamma C^2 T \\sqrt{f/(n-2f)})$ lower bound.","supporting_citations":[],"review_version":2}