{"id":"537d019b-7887-4a40-a7b2-4309161796bf","arxiv_id":"2506.15264","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Nearly tight worst-case bounds for Byzantine-robust centroid approximation under box and convex validity, with a new algorithm matching the convex lower bound.","lead":"This paper derives worst-case accuracy limits for Byzantine-robust federated averaging, showing how close a server can get to the true average when some participants send arbitrary vectors. It reports matching lower and upper bounds for common validity conditions and tests the algorithms on MNIST.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Advertised box lower bound is false as stated: n=6,t=1,d=100 yields claimed 5 vs Lemma 3.9 upper 4.90; Lemma 3.11's own construction forces only ≈√q.","rationale":"The paper's central advertised contribution is the box-validity lower bound. As written, that bound is internally inconsistent with the paper's own upper bound, and the proof of Lemma 3.11 contains a concrete norm error and a construction that supports only a square-root-scale lower bound, not the stated min{(n−t)/t,√d}. This is a correctness issue about the main claim, not a matter of stylistic preference or disagreement with the literature. The reader's concern about Lemma 3.13 is also legitimate and concerns the convex-validity upper bound, but the box lower bound is the primary contribution and is where I would focus the required revision. I would keep the conditional verdict: the paper's ideas may be fixable, and a corrected lower bound of order √min{(n−t)/t,d} could still be a meaningful contribution, but the current text must be revised before the stated theorems can be accepted.","tokens_in":15991,"tokens_out":63842,"duration_ms":710948,"concrete_test":"Independently compute the exact minimum enclosing ball of the set S_q={a∑_{k=1}^q e_k} ∪ {a∑_{k≠j}e_k : 1≤j≤q}, with a=tx/(n−t), for q=5,t=1,n=6. Show the radius is a√((q−1)/q), hence the ratio forced by Lemma 3.11's own construction is q/√(q−1)=2.5, not 5. Separately re-derive the two-centroid distance in Lemma 3.11 to verify it is √2·a, not 2·a; this alone invalidates the displayed proof. Then compare with Lemma 3.9's 2√6<5 to confirm the internal contradiction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing concern is the advertised box-validity lower bound. Abstract and Table 1 state a lower bound of min{(n−t)/t,√d}. For n=6, t=1, d=100 this says every box-valid algorithm has approximation ratio at least 5, while Lemma 3.9 states the Box/RB-TM algorithm has ratio at most 2√min{n,d}=2√6≈4.90. Both cannot be true. The proof of Lemma 3.11 does not rescue the claim. In its construction (non-faulty vectors x·e_k for k=1..q and t Byzantine origin vectors), the two centroids it subtracts differ by (tx/(n−t))(−e_1+e_q), whose Euclidean norm is √2·tx/(n−t), not 2·tx/(n−t) as written. Moreover, with t=1 the exact minimum covering ball of the resulting SCent has a simple closed form: the q+1 points a∑e_k and a∑_{k≠j}e_k have radius a√((q−1)/q), so the forced approximation ratio of that very construction is q/√(q−1)≈√q, not q. For n=6,q=5 this ratio is 2.5, so the lemma's construction cannot be the source of a 5 lower bound. The square-root form near √((n−t)/t) may be salvageable, but the stated min{(n−t)/t,√d} is not supported and contradicts the paper's own upper bound.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies aggregation for Byzantine federated learning and evaluates aggregators by the 'centroid approximation' ratio from Cambus and Melnyk [9]: the distance from the aggregator output to the centroid of the non-faulty vectors divided by the radius of the smallest ball covering all centroids of subsets of size n−t. The authors analyze which distributed-computing validity conditions imply a bounded ratio, claim a lower bound min{(n−t)/t,√d} for box validity, an upper bound 2√min{n,d}, and a 2d-approximation algorithm under convex validity that would match a known lower bound. They also claim that the bounds transfer to peer-to-peer networks and present FedSGD/FedAvg experiments. The paper is clearly written, but the main lower-bound claim is not supported by the proofs and is contradicted by the paper's own upper bound.","tokens_in":16305,"tokens_out":19160,"duration_ms":191720,"significance":"The conceptual framing is useful: measuring aggregation quality relative to the input-dependent covering-ball radius is a sensible way to separate Byzantine effects from data heterogeneity, and the experiments illustrate the behavior of the Center-of-ball, MDA, and Box algorithms. If the box-validity lower bound and the convex-validity upper bound were correct, they would be valuable first tightness results. However, the abstract's advertised lower bound min{(n−t)/t,√d} is false: the proof of Lemma 3.11 yields only a square-root expression, and the exact evaluation of that construction gives q/√(q−1)≈√q, not q. Lemma 3.12's convex upper bound is also not proven as stated, since the proof concludes 2d+1 and relies on an unproven counting lemma. The paper does not provide machine-checked proofs or code, and the correctness of the central claims is not established.","major_comments":[{"comment":"The advertised lower bound min{(n−t)/t,√d} is unsupported and contradicted by the paper itself. Lemma 3.11 proves only √(1/2·min{⌊(n−t)/t⌋,d}), which is roughly min{√((n−t)/(2t)),√(d/2)}, not min{(n−t)/t,√d}. For n=6, t=1, d=100 the abstract's bound is 5, while Lemma 3.9 gives an upper bound of 2√6≈4.90. Moreover, in the construction of Lemma 3.11 with q=min{⌊(n−t)/t⌋,d}, the trimmed trusted hyperbox is the single point 0, so every box-valid algorithm must output 0; for n=6, t=1, q=5, the candidate centroids are aΣe_k and aΣ_{k≠j}e_k, whose covering ball has radius a√((q−1)/q), giving an exact ratio of 5/2=2.5. Thus this construction cannot yield a lower bound of 5. The square-root lower bound may be salvageable, but the claimed min{(n−t)/t,√d} bound is false as stated.","section":"Abstract, Table 1, Lemma 3.11"},{"comment":"The proof derives |CH[k]| ≥ (t/(n−t))|TTH[k]|, which implies |TTH[k]| ≤ ((n−t)/t)|CH[k]|, the opposite of the 'TTH diagonal at most t/(n−t) times CH diagonal' used in the next paragraph. The stated worst-case bound (1+t/(n−t))2√d is false: for n=6, t=1, d=1, take non-faulty inputs {0,0,0,100,100} and Byzantine input 0; the algorithm that always outputs the lower endpoint of the trimmed trusted hyperbox is box-valid and outputs 0, while Cent⋆=40 and Radcov=10, so the ratio is 4, exceeding (1+1/5)·2=2.4. The claim that box validity alone guarantees a bounded approximation may still be true via Lemma 3.9, but this lemma's proof and statement need correction.","section":"Section 3.1, Lemma 3.4"},{"comment":"The upper-bound proof for convex validity is incomplete. The chain at the end gives x/Radcov+1 ≤ 2(n−t−l)/t+1 ≤ 2dt/t+1 = 2d+1, but the lemma claims a 2d-approximation. The missing factor is not a typo, because the only bound on l comes from Lemma 3.13, whose proof is a sketch that sums 'at most t vectors' over q faces without correcting for vectors that lie outside several faces; the claimed 'at most qt points' is therefore not established. Since this is the only argument for tightness of the known convex lower bound, the 2d upper bound is unproven as stated.","section":"Section 3.2, Lemma 3.12 and Lemma 3.13"},{"comment":"The displayed norm of the difference between the two centroids is incorrect; the vector is (tx/(n−t))(−e_1+e_q), whose Euclidean norm is √2·tx/(n−t), not 2·√((tx/(n−t))^2). With the corrected value, the lemma's stated lower bound √(q/2) is consistent, so this is a proof error rather than the source of the false abstract claim, but it must be fixed.","section":"Section 3.2, proof of Lemma 3.11"},{"comment":"The new analysis for n<d does not prove the claimed 2√n upper bound. From the fact that Conv(SCent) touches all 2d′ faces of its minimal hyperbox, the proof selects centroids on the d′ faces containing the origin and infers that some centroid lies in the intersection of at least d′/n faces; it then concludes Radcov ≥ √(d′/n)/2. Touching a face only places a point at distance √k/2 from the hyperbox center, and without a second point far from it this does not lower-bound the radius of the minimum covering ball. A rigorous argument for the n<d case is missing.","section":"Section 3.2, Lemma 3.9"},{"comment":"The extension of the 2d lower bound from [9] to all n>(d+1)t is only a sketch; the claims that the non-faulty centroid is at distance td/(n−t) and the covering radius is t/(2(n−t)) are not derived and appear to confuse t√d/(n−t) with td/(n−t). Since this lemma is the matching lower bound for Lemma 3.12, it needs a complete proof.","section":"Section 3.2, Lemma 3.8"}],"minor_comments":[{"comment":"The box-validity lower-bound cells should be updated to the floor and square-root form actually proved in Lemma 3.11; currently they repeat the unsupported min{(n−t)/t,√d} form.","section":"Table 1"},{"comment":"The notation is inconsistent: the text says 'exactly q (q−1)-faces ... denoted H1,...,Hd' and 'go through sd'; these should be q hyperplanes H1,...,Hq and the vertex s_v.","section":"Lemma 3.13 proof"},{"comment":"The description of the adversarial layout is ambiguous: 't vectors are at coordinate e_k = x·u_k, ∀k∈[...]' should say that for each of the q axes there are t non-faulty vectors at x·u_k and the remaining n−t−qt non-faulty vectors are at the origin.","section":"Lemma 3.11 construction"},{"comment":"The model allows m received messages with n−t≤m≤n, but Lemma 3.4 and Lemma 3.11 silently take m=n; the proofs should state which case they cover.","section":"Definition 2.7 and Lemma 3.10"},{"comment":"The experimental section reports single runs without standard deviations or multiple seeds, so statements such as 'MDA shows more instability' and 'Box algorithm appears to be more stable' are not supported quantitatively; also, the Figure 3c caption contains a typo ('cnon-faulty').","section":"Section 4"}],"recommendation":"reject","confidential_remarks":"The manuscript contains a false main theorem and a false lemma with an explicit counterexample; in my assessment the central claims cannot be repaired by local editing. The square-root lower bound might be salvageable, but the paper as submitted does not establish its advertised contribution and would need substantial reworking before resubmission."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the paper has a real kernel, but the headline result as advertised is not supported. The abstract and Table 1 claim a lower bound of min{(n−t)/t, √d} under box validity; Lemma 3.11 actually proves something weaker, √(1/2 · min{⌊(n−t)/t⌋, d}), and there's a direct contradiction with the paper's own upper bound: for n=6, t=1, d=100, the claimed lower bound is 5 while Lemma 3.9 gives an upper bound of 2√6 ≈ 4.90. That's not a subtle mismatch; it's a false statement.\n\nWhat's genuinely new: the box-validity lower bound construction (in essence, a square-root bound), the n<d analysis of the Box algorithm, and the convex-validity upper bound. The framework of centroid approximation under validity conditions is carried over from the authors' prior work, but the new pieces are not in the cited literature. The weak/strong validity negative results are simple but correct. So the paper is not empty.\n\nThe soft spots are mostly proof constants, but they're load-bearing. Lemma 3.11's computation has an error: the two centroids differ by √2·tx/(n−t), not 2·..., and the exact minimum covering ball of the construction gives a ratio of q/√(q−1) ≈ √q rather than q. The lemma's stated square-root bound may be salvageable, but the proof as written doesn't establish it. Lemma 3.12's proof ends with 2d+1, not 2d, and the abstract says √(2d) — three different constants for the same claim. Lemma 3.4 inverts the CH/TTH inequality; the proof concludes the diagonal of TTH is at most t/(n−t) times that of CH, but the inequality shown implies the opposite. And Lemma 3.13, which underpins the convex upper bound, is only a sketch; the counting of vectors across faces is not rigorous. The empirical section is illustrative only, no error bars, no code.\n\nNone of these are fatal to the underlying ideas, but together they mean the paper as written cannot be accepted. The authors need to correct the constants, either prove or retract the min{(n−t)/t, √d} claim, and tighten Lemma 3.13.\n\nI'd still send this to a serious referee rather than desk reject: the questions are interesting and a careful review could help the authors produce a correct version. But I wouldn't cite it in its current state. Bring it to reading group if you want a good case study in why advertised theorems need to be checked against the paper's own lemmas.","headline":"The paper's advertised box-validity lower bound is contradicted by its own upper bound; the underlying ideas are new and possibly fixable, but the write-up needs major repair.","tokens_in":16884,"tokens_out":8529,"would_cite":false,"duration_ms":74438,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves a first lower bound for box-valid Byzantine-tolerant averaging: every such rule has centroid approximation ratio at least about $\\sqrt{\\min\\{(n-t)/t, d\\}}$, with matching upper bounds of $2\\sqrt{\\min\\{n,d\\}}$.","keywords":["Byzantine fault tolerance","federated learning","centroid approximation","box validity","convex validity","trimmed trusted hyperbox","robust aggregation","approximate agreement"],"falsifier":"To test the box-validity lower bound, instantiate the Lemma 3.11 construction for $n=6$, $t=2$, $d=2$ with $x=1$, enumerate all candidate centroids, and compute the exact minimum covering radius; the ratio of the origin-to-centroid distance to that radius must be at least $1$, and a box-valid rule that beats that ratio on this instance would refute the lower bound. To test the convex-validity claim, search small dimensions for a configuration where a hyperplane touching the safe area leaves more than $q\\cdot t$ vectors on the other side; one such configuration would invalidate Lemma 3.13 and the $2d$ upper bound.","tokens_in":15781,"feed_emoji":"🛡️","tokens_out":12337,"duration_ms":117245,"temperature":0.7,"pith_summary":"The paper studies a federated-learning server that averages client updates when up to $t$ of $n$ clients may be Byzantine. It measures an aggregation rule by its centroid approximation ratio: the distance from the rule's output to the true average of the honest clients, divided by the radius of the smallest ball that contains the average of every possible subset of $n-t$ clients. The central claim is that the widely used box validity condition---the rule must output inside the coordinate-parallel box spanned by the honest updates---carries an unavoidable worst-case cost: every box-valid rule has approximation ratio at least about $\\sqrt{\\min\\{(n-t)/t, d\\}}$ (the paper proves $\\sqrt{\\tfrac{1}{2}\\min\\{\\lfloor (n-t)/t\\rfloor, d\\}}$). The paper also settles the convex-validity setting by giving a $2d$-approximation algorithm that matches an existing $2d$ lower bound, and reanalyzes the $n<d$ case to show that box-valid rules can achieve a $2\\sqrt{\\min\\{n,d\\}}$ approximation.","feed_headline":"Box-valid averaging cannot beat a √d gap to the honest centroid","feed_subtitle":"New lower and upper bounds show exactly how much Byzantine safety costs in federated averaging.","key_machinery":"The central object is the centroid-approximation ratio, built from the smallest ball containing all candidate centroids $\\mathrm{SCent}$---the averages of every subset of $n-t$ of the $n$ input vectors---whose radius is called $\\mathrm{Rad}_{\\mathrm{cov}}$. The proof machinery is the trimmed trusted hyperbox (TTH): with up to $t$ Byzantine reports per coordinate, any box-valid rule must output inside the interval left after removing the $t$ largest and $t$ smallest values in each coordinate. The lower bound collapses the TTH to a single point while the honest centroid sits away from that point. The convex-validity upper bound projects all input vectors onto the line between the safe area (the intersection of the convex hulls of every subset of $n-t$ vectors) and the covering ball, then bounds the number of projected vectors on each side of a separating hyperplane via Lemma 3.13.","core_discovery":"On its own terms, the paper establishes an almost-tight tradeoff between Byzantine safety and accuracy. The lower-bound construction places $t$ client vectors on each of $k=\\min\\{\\lfloor (n-t)/t\\rfloor, d\\}$ coordinate axes and the remaining vectors at the origin, then lets the Byzantine clients report the origin; since Byzantine reports are indistinguishable from honest ones, any box-valid rule is forced to output the origin. The honest centroid lies about $\\sqrt{k}\\cdot \\frac{tx}{n-t}$ away, while the minimum covering radius of the candidate centroids is at most $\\sqrt{2}\\cdot \\frac{tx}{n-t}$, giving the ratio $\\sqrt{k/2}$. The paper complements this with a $2\\sqrt{\\min\\{n,d\\}}$ upper bound for box-valid rules, using the Box and RB-TM algorithms with a new analysis for $n<d$, and a $2d$-approximation algorithm for convex validity, matching the known $2d$ lower bound. It then shows that all these bounds transfer to fully connected peer-to-peer networks by running an exact Byzantine agreement step before applying the aggregation rule.","pith_inferences":["The $\\sqrt{d}$ floor suggests that any Byzantine-tolerant averaging scheme that insists on staying coordinate-wise within honest reports will degrade with model size; if outlier robustness is the priority, a weaker validity condition or a rule allowed to step outside the trusted box is worth exploring.","The box-validity lower bound only needs Byzantine clients to report the all-zero vector, the same value as some honest clients, so the bound is independent of how sophisticated the Byzantine attack is and likely survives even if Byzantine reports are audited after the fact.","One could test the convex-validity algorithm's constant empirically in the regime $n>(d+1)t$, which is unusual for federated learning; the paper's own experiments do not implement it because their models have $d=200$ dimensions.","The $2\\sqrt{\\min\\{n,d\\}}$ box-validity upper bound may be improvable to $\\sqrt{\\min\\{n,d\\}}$ in the $n<d$ case, since the lower-bound construction realizes only about half that value there and the proof's averaging argument leaves room for a tighter constant."],"forward_implications":["Any box-valid aggregation rule, no matter how clever, has worst-case centroid approximation at least about $\\sqrt{\\min\\{(n-t)/t, d\\}}$; in high-dimensional models this grows as $\\sqrt{d}$.","The box-validity gap is almost closed: the upper bound is $2\\sqrt{\\min\\{n,d\\}}$, leaving only the constant and the precise $n<d$ behavior open.","For convex validity, the existing $2d$ lower bound is tight when $n>(d+1)t$: the safe-area projection algorithm achieves $2d$, settling that regime.","Weak and strong validity guarantee only constant approximation ($1$ and $2$ respectively), while convex validity alone gives no bounded guarantee without the safe-area algorithm.","All bounds carry over to synchronous peer-to-peer federated learning, because an interactive-consistency round lets every client agree on the same set of vectors before aggregating."],"supporting_citations":[{"why":"Introduces the centroid-approximation ratio, the Box algorithm's intersection argument, the convex-validity $2d$ lower bound, and the observation that convex validity alone leaves the ratio unbounded.","marker":"[9]"},{"why":"Supplies the MDA algorithm (with the RB-TM variant) whose single-round analysis gives the $2$-approximation under strong validity and the $2\\sqrt{\\min\\{n,d\\}}$ box-validity upper bound.","marker":"[19]"},{"why":"Defines the safe area and the $n>(d+1)t$ condition that convex-validity guarantees depend on.","marker":"[39]"},{"why":"Provides the box-validity condition and the approximate-agreement setting whose trimmed-trusted-hyperbox argument is an extension.","marker":"[16]"},{"why":"Gives the exact Byzantine agreement protocol that lets every peer-to-peer client agree on the same vector set before applying the aggregation rules.","marker":"[41]"}],"fun_headline_variants":["Byzantine safety costs a √d gap in federated averaging","Tight bounds on Byzantine-robust federated averaging","√d gap is the price of Byzantine tolerance in federated learning","First tight tradeoff between Byzantine robustness and averaging accuracy","Near-optimal centroid approximation under Byzantine faults"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The convex-validity upper bound rests on Lemma 3.13's claim that a hyperplane touching a $q$-dimensional safe area leaves at most $q\\cdot t$ input vectors on its far side; the paper's proof counts $q$ faces at a vertex without fully accounting for vectors that lie on several faces, so the $2d$ approximation collapses if that count is wrong.","fun_headline_variants_meta":{"raw":{"variants":["Byzantine safety costs a √d gap in federated averaging","Tight bounds on Byzantine-robust federated averaging","√d gap is the price of Byzantine tolerance in federated learning","First tight tradeoff between Byzantine robustness and averaging accuracy","Near-optimal centroid approximation under Byzantine faults"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00062,"raw_usage":{"total_tokens":2936,"prompt_tokens":1064,"completion_tokens":1872,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":680,"completion_tokens_details":{"reasoning_tokens":1791}},"tokens_in":680,"tokens_out":1872,"duration_ms":12858,"temperature":1.0,"reasoning_tokens":1791,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T19:40:06.492064+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"To test the box-validity lower bound, instantiate the Lemma 3.11 construction for $n=6$, $t=2$, $d=2$ with $x=1$, enumerate all candidate centroids, and compute the exact minimum covering radius; the ratio of the origin-to-centroid distance to that radius must be at least $1$, and a box-valid rule that beats that ratio on this instance would refute the lower bound. To test the convex-validity claim, search small dimensions for a configuration where a hyperplane touching the safe area leaves more than $q\\cdot t$ vectors on the other side; one such configuration would invalidate Lemma 3.13 and the $2d$ upper bound.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the MDA algorithm (with the RB-TM variant) whose single-round analysis gives the $2$-approximation under strong validity and the $2\\sqrt{\\min\\{n,d\\}}$ box-validity upper bound."},{"cited_title":"Mendes, M","cited_arxiv_id":null,"evidence_quote":"Defines the safe area and the $n>(d+1)t$ condition that convex-validity guarantees depend on."},{"cited_title":"Dolev, N","cited_arxiv_id":null,"evidence_quote":"Provides the box-validity condition and the approximate-agreement setting whose trimmed-trusted-hyperbox argument is an extension."},{"cited_title":"Pease, R","cited_arxiv_id":null,"evidence_quote":"Gives the exact Byzantine agreement protocol that lets every peer-to-peer client agree on the same vector set before applying the aggregation rules."}],"review_version":1}