{"id":"f642b063-e9c2-49c0-bcd9-8d92788da67d","arxiv_id":"2508.18060","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"FedGreed sorts client updates by loss on a server-side trusted dataset and greedily averages the best prefix, claiming Byzantine robustness without knowing attacker count.","lead":"FedGreed is a recipe for a federated learning server to decide which client updates to trust: it tests each updated model against a small server-held dataset and greedily combines the best-scoring ones. The paper claims this keeps training accurate even with many malicious clients, but the promised proof is omitted and the experiments are too thin to support the headline claim.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"FedGreed's bounded-optimality claim is vacuous in high-skew non-IID regimes: own Section IV-B concedes fS-progress may be random-noise-like, and the theorem/proof is omitted.","rationale":"The reader's rejection rests on the unsupported central claim and the empirical counterexamples. The stress-test identifies the same load-bearing point: FedGreed's formal guarantee, once the omitted proof is supplied, is at best a monotone-decrease guarantee on fS, and the paper itself concedes that this guarantee is vacuous under high Dirichlet skew and Gaussian noise. The near-chance accuracies in Table I (CIFAR-10 a=0.1 Gaussian noise: 10.15, 10.07, 10.21; FMNIST: 19.39, 11.68, 11.25) are not a peripheral artifact; they are the predicted outcome of the algorithm's selection rule when the fS-minimal client is no better than random. Because the theorem is omitted, we cannot verify whether the stated assumptions actually exclude this regime; the paper's own Section IV-B suggests they do not, since the bound 'depends explicitly on the gradient noise of individual clients, and in high skewness, this bound is so large that it manifests in non-useful accuracies.' A revised version could address this by (1) providing the full proof and stating the gradient-noise constants explicitly, (2) running more than three seeds with error bars, and (3) comparing against FLTrust and the authors' own loss-clustering baseline [17], which are the closest and most relevant baselines. However, as submitted, the central claim is not supported; my read leaves the REJECT verdict unchanged.","tokens_in":12014,"tokens_out":4535,"duration_ms":54881,"concrete_test":"Re-run the CIFAR-10 a=0.1, M=3 Gaussian-noise configuration from Table I while logging fS(xt+1), fS(xt+1_(1)), and test accuracy at every round. Additionally, compute the cosine similarity between ∇fS(xt) on the server's trusted subset and ∇f(xt) estimated on a larger held-out sample from the same distribution. If fS decreases monotonically while test accuracy stays near 10% and the cosine similarity is near zero, fS is not a reliable proxy for f in this regime, so the 'progress at least as good as a single non-attacked client' guarantee does not transfer to a non-vacuous bound on the population loss. This directly tests the load-bearing proxy assumption rather than relying on the omitted proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The headline claim—bounded optimality gaps under Byzantine attacks for non-convex and convex losses—rests on two unsecured links. First, the proof is absent: Section III says 'Detailed rigorous assumptions, theorems, and proofs are omitted here for brevity,' so no argument is available to check. Second, the mechanism's only guaranteed property is fS-monotone progress: Algorithm 1 (steps 4–6) never accepts a candidate with larger fS than the current xaux, so fS(xt+1) ≤ fS(xt+1_(1)). This is a statement about the server's empirical proxy fS, not about the population loss f. To convert it into a bounded optimality gap, one needs (i) fS to approximate f well enough and (ii) at least one honest client whose fS-minimal update is a useful descent direction for f. Section IV-B explicitly concedes the failure of (ii) under Dirichlet a=0.1: the best single client's gradient 'may resemble random noise,' and a malicious update with similar fS can be selected. The empirical consequence is visible in Table I: for CIFAR-10 with Gaussian noise and a=0.1, FedGreed accuracy is 10.15/10.07/10.21 (chance), and FMNIST is 19.39/11.68/11.25. Thus, even if the omitted theorem is true, its bound is vacuous in exactly the high-heterogeneity setting the paper claims to handle.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes FedGreed, a Byzantine-robust aggregation method for federated learning in which a trusted server holds a reference dataset. At each round, the server evaluates all client updates against the server-side loss fS, sorts them, and greedily selects the best prefix average according to fS. The authors claim that FedGreed guarantees progress in fS at least as well as the best single client, requires no knowledge of the number of malicious clients, and exhibits bounded optimality gaps under Byzantine attacks for non-convex and convex losses. Experiments compare FedGreed with Mean, Trimmed Mean, Median, Krum, and Multi-Krum on MNIST, FMNIST, and CIFAR-10 under label flipping and Gaussian noise injection, with Dirichlet-based non-IID partitions. The paper's central theoretical claim is explicitly deferred ('detailed rigorous assumptions, theorems, and proofs are omitted here for brevity'), and the empirical results show chance-level accuracy in several high-heterogeneity Gaussian-noise scenarios.","tokens_in":12372,"tokens_out":4234,"duration_ms":53198,"significance":"If the theoretical guarantees were actually derived and the empirical results were robust, FedGreed would be a meaningful contribution: it avoids the common requirement of knowing the number of Byzantine clients and leverages server-side trusted data in a computationally cheap way. The algorithmic idea is simple, and the authors provide a public codebase. However, because the main theoretical claim is unsupported and the method fails precisely in the high-non-IID regime the paper emphasizes, the contribution as it stands is not established.","major_comments":[{"comment":"The paper's headline claim—'bounded optimality gaps under Byzantine attacks'—rests entirely on the sentence 'we can show that FedGreed exhibits bounded error ... Detailed rigorous assumptions, theorems, and proofs are omitted here for brevity.' No theorem, proof, or even precise assumption list is provided. This is a load-bearing omission: the abstract and introduction claim convergence guarantees, but the manuscript does not contain them. The authors must either supply a complete theorem with assumptions and proof or remove/wordingly weaken the claim.","section":"Section III, after Algorithm 1"},{"comment":"The empirical results directly contradict the robustness claim in the high-heterogeneity regime. For Dirichlet a=0.1 under Gaussian noise, FedGreed achieves approximately chance accuracy on CIFAR-10 (10.15%, 10.07%, 10.21% for M=3,5,8) and on FMNIST (19.39%, 11.68%, 11.25%). Section IV-B concedes that under such skew the best individual client's gradient 'may resemble random noise,' and the paper acknowledges the bound is so large that it yields non-useful accuracies. Thus the claimed bounded optimality gap is vacuous in exactly the setting the paper says it handles. This is not a 'rare' vulnerability; it spans a substantial portion of the evaluated table.","section":"Section IV-B, Table I"},{"comment":"The robustness argument assumes that if a Byzantine client's update has low fS, it is harmless because it is at least as good as an honest client's update. This is only true if low fS correlates with progress toward the population loss f. A Byzantine adversary aware of fS (or able to query the server's reference dataset) could craft an update that minimizes fS while not actually improving f—e.g., by overfitting to the reference set. The experiments only consider non-adaptive label-flipping and Gaussian-noise attacks. The claim of Byzantine robustness is therefore overstated relative to the evaluated threat model.","section":"Section III, threat model"},{"comment":"The experimental comparison reports only means over three random seeds, with no variance, confidence intervals, or statistical significance testing. Statements such as 'significantly outperforms' are not supported. Moreover, the most directly relevant baseline, FLTrust (cited as [15]), which also uses a server-side trusted dataset, is not included in the experiments. Without this comparison, and without a measure of variability, the empirical advantage of FedGreed over state-of-the-art robust aggregation is not established.","section":"Section IV-A, Table I"}],"minor_comments":[{"comment":"The notation for the attacked update is inconsistent: the text defines ext+1_i as the arbitrary replacement, but the algorithm uses bxt+1_i. The relationship between ext+1_i and bxt+1_i should be clarified, and the subscripts/superscripts made consistent.","section":"Notation, Section III"},{"comment":"The stopping condition fS(xtest) >= fS(xaux) is correct but the greediness is only over prefix averages, not all subsets. The paper should explicitly note that this is a design heuristic rather than the optimal selection over arbitrary subsets, since the text states 'the goal is to select the best candidate among a much wider set' but then restricts to prefixes.","section":"Algorithm 1, step (5)"},{"comment":"The phrase 'expected averaged squared norm of the true population loss f's gradient' is imprecise. The expectation over which randomness (the server's dataset, clients' local SGD, attacker choices) is not specified. A formal statement would define all sources of randomness.","section":"Section I and III"},{"comment":"The related work mentions [17], a closely related paper by the same authors, but does not discuss the differences in enough detail. In particular, the relationship between the greedy selection of FedGreed and the K-means clustering in [17] should be clarified to position the novelty.","section":"References"}],"recommendation":"reject","confidential_remarks":"The central contribution of the paper—'bounded optimality gaps'—is not backed by any proof in the manuscript. The authors explicitly defer the proof to 'brevity,' which is not acceptable for a journal submission. Moreover, the experimental section includes multiple configurations where FedGreed performs at chance level, and the paper's own discussion acknowledges the bound is vacuous in those cases. This is not a minor fixable issue; the main claimed contribution is unsupported. I would recommend rejection, though the authors could resubmit if they provide a rigorous proof and a more honest assessment of the method's limitations."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline result you need to know: this paper claims bounded optimality gaps under Byzantine attacks, but the proofs are not in the paper — Section III says “detailed rigorous assumptions, theorems, and proofs are omitted here for brevity.” What remains is a monotone fS-progress property that is true by construction, not a convergence theorem. The stress-test note is on target: Section IV-B explicitly concedes that under Dirichlet a=0.1 the best client’s gradient “may resemble random noise,” and Table I shows FedGreed at chance accuracy on CIFAR-10 and FMNIST under Gaussian noise. That is a direct contradiction with the abstract’s claim that the method works under non-IID data.\n\nCredit where it is due: the greedy prefix-average rule in Algorithm 1 is a genuinely small but neat twist. Sorting clients by server-side loss and expanding the prefix until fS stops improving is clean, easy to implement, and requires no attack-ratio estimate. It is a close relative of FLTrust and the authors’ own loss-based clustering [17], but the specific candidate set and stopping rule are not present verbatim in those papers. The empirical study covers three datasets, two Dirichlet skews, three attack ratios, and five baselines, which is more than many papers in this area bother with.\n\nThe soft spots are proportionate to the claims. The missing proof is load-bearing, not a stylistic gap. The experiments use three seeds with no variance, and the two closest baselines — FLTrust and the authors’ own [17] — are absent. The comparison is therefore weaker than the text implies. The authors do honestly flag the high-skew vulnerability in Section IV-B, and I read that as genuine engagement with the failure mode, but it undercuts the central narrative.\n\nA revised version with the actual proofs, error bars, and those two missing baselines could plausibly become a solid conditional accept. As submitted, the strongest result in the paper is the fS-progress guarantee, which is not enough to support the stated optimality gaps. I would not send this to peer review in its current form; a serious editor would desk-reject until the theoretical claims are actually derived and the empirical evaluation is made complete.","headline":"A clean but small algorithmic variant whose headline convergence guarantee is literally omitted, and whose own experiments concede failure in the high-skew regime it claims to handle.","tokens_in":12848,"tokens_out":2072,"would_cite":false,"duration_ms":26616,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"FedGreed keeps federated learning accurate under Byzantine attacks by greedily selecting the client updates with the lowest loss on a trusted server-side dataset.","keywords":["Federated learning","Byzantine robustness","Robust aggregation","Server-side trusted dataset","Greedy client selection","Non-IID data","Label flipping","Gaussian noise attack"],"falsifier":"Run FedGreed on CIFAR-10 with Dirichlet a=0.1 and Gaussian noise attacks (the Table I setting): accuracy collapses to about 10%, chance level, directly exposing when the central guarantee fails. A sharper test: replace the server's trusted dataset with samples drawn from a different distribution than the clients' data, then check whether the per-round fS descent still tracks the true population loss; if the best-scoring client is consistently a malicious update, the proxy assumption is falsified.","tokens_in":11950,"feed_emoji":"🛡️","tokens_out":8441,"duration_ms":94198,"temperature":0.7,"pith_summary":"FedGreed is a server-side aggregation rule for federated learning that assumes the server holds a small trusted dataset, evaluates every submitted client model on that dataset, and greedily averages the best-scoring prefix of the sorted client models. The paper claims this rule needs no knowledge of how many clients are malicious, tolerates up to 80% attackers in experiments, and provides bounded optimality gaps for convex and non-convex losses. The key guarantee is per-round: the server's next model is never worse, in the trusted loss, than the single best submitted model, so the defense degrades gracefully even if the best-scoring client is an attacker. The paper also reports a concrete failure mode under extreme non-IID data with Gaussian noise, where accuracy falls to chance because the best honest client's gradient resembles random noise. If the claims hold, FedGreed offers a practical defense that only needs one honest client per round and a trustworthy reference dataset.","feed_headline":"Rank client updates by server loss to block Byzantine attacks","feed_subtitle":"A small trusted dataset on the server is all FedGreed needs to ignore malicious clients, even at 80% attack rates.","key_machinery":"The central object is the greedy prefix-average candidate set: for the ordered client models x(1), ..., x(N) by server loss fS, the candidates are (1/j) * sum_{i=1..j} x(i) for j = 1..N. FedGreed walks along this list, replacing its current candidate xaux with the next prefix-average only when fS decreases, and sets the next global model to the final xaux. This construction guarantees monotone descent in fS each round, so the worst case is the best single client, which bounds the damage from Byzantine updates. The extra cost is O(N) evaluations of fS per round, which is cheap when the server reference set is small.","core_discovery":"The central claim is that a Byzantine-robust federated learning aggregation rule can be built purely from a server-side loss function fS. At each round, FedGreed evaluates fS on each client's update, sorts the updates by that value, and considers the N prefix-averages of the sorted list. Starting from the single best-scoring model, it accepts the next client into the average only when doing so strictly decreases fS; the update applied to the global model is the accepted prefix-average. Because the algorithm only moves to a candidate with smaller fS, it makes progress in fS at least as good as the best individual client, and this progress guarantee transfers to the true population loss when f","pith_inferences":["The per-round fS-descent guarantee suggests that FedGreed could be combined with other robust estimators by feeding their outputs into the greedy comparison as extra candidates, potentially inheriting their strengths while preserving the descent guarantee.","A natural extension to address the reported high-skew failure is to evaluate short averages of the top-k clients rather than only prefixes, which would reduce the variance of the single best client's gradient direction.","The number of clients accepted into the prefix each round could be monitored as a cheap attack signal: a persistently small j indicates either heavy attack or extreme heterogeneity, prompting the server to adjust participation or request more data.","The method's reliance on fS as a proxy implies that the size and representativeness of the server-side reference dataset should be treated as a tunable resource; this is an implicit design lever the paper does not explore."],"forward_implications":["A federated server can obtain Byzantine robustness without knowing the fraction or identities of malicious clients; the only requirements are a trusted reference dataset and at least one honest update per round.","The method remains meaningful when honest clients are a minority: experiments cover up to 8 of 10 clients attacking, and the per-round fS-descent guarantee is independent of the attack ratio.","Because each round's update is a prefix-average of the fS-ranked clients, the method can be restricted to the top K candidates with no loss of robustness, trading per-round speed for fewer evaluations.","The stated convergence and optimality-gap results imply that, under reasonable fS approximation quality, the global model's error on the true population loss stays bounded despite adversarial updates.","Under extreme Dirichlet skew and Gaussian noise attacks, the paper's own experiments show the bound becomes too loose to be useful, with centralized accuracy dropping to chance on CIFAR-10 and FMNIST."],"supporting_citations":[{"why":"Supplies the FedAvg/Mean baseline and the standard server-client training loop that FedGreed replaces the aggregation step of.","marker":"[3]"},{"why":"Supplies the Trimmed Mean and Median coordinate-wise robust aggregation baselines that FedGreed is compared against.","marker":"[12]"},{"why":"Supplies the Krum and Multi-Krum distance-based aggregation baselines; FedGreed is claimed to outperform them without needing the attack count f.","marker":"[13]"},{"why":"Establishes the prior use of a server-side trusted dataset to score client updates, which FedGreed adopts and simplifies into a greedy loss ranking.","marker":"[15]"},{"why":"The authors' own loss-based client clustering method; FedGreed is presented as its successor, removing the need for a known lower bound on honest clients.","marker":"[17]"},{"why":"Provides the experimental setup and attack types (label flipping, Gaussian noise) used to benchmark Byzantine robustness.","marker":"[8]"},{"why":"CIFAR-10, one of the three benchmark datasets used to evaluate robustness under non-IID partitions.","marker":"[19]"},{"why":"FMNIST, one of the three benchmark datasets used to evaluate robustness under non-IID partitions.","marker":"[20]"},{"why":"MNIST, one of the three benchmark datasets used to evaluate robustness under non-IID partitions.","marker":"[21]"}],"fun_headline_variants":["Greedy loss ranking: the Byzantine antidote for federated learning","Small trusted dataset on server blocks Byzantine clients in FL","FedGreed: pick only the best client updates to foil attacks","No-frills robust FL: sort by loss, greedily merge"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The whole argument hinges on the server's trusted loss fS being a faithful stand-in for the true population loss, and on at least one honest client each round; under extreme data skew, the honest client's individual gradient can look like random noise, and FedGreed's bounded-error guarantee becomes too loose to prevent chance-level accuracy.","fun_headline_variants_meta":{"raw":{"variants":["Greedy loss ranking: the Byzantine antidote for federated learning","Small trusted dataset on server blocks Byzantine clients in FL","FedGreed: pick only the best client updates to foil attacks","No-frills robust FL: sort by loss, greedily merge"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000435,"raw_usage":{"total_tokens":2056,"prompt_tokens":757,"completion_tokens":1299,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":501,"completion_tokens_details":{"reasoning_tokens":1225}},"tokens_in":501,"tokens_out":1299,"duration_ms":11643,"temperature":1.0,"reasoning_tokens":1225,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T16:35:56.685611+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run FedGreed on CIFAR-10 with Dirichlet a=0.1 and Gaussian noise attacks (the Table I setting): accuracy collapses to about 10%, chance level, directly exposing when the central guarantee fails. A sharper test: replace the server's trusted dataset with samples drawn from a different distribution than the clients' data, then check whether the per-round fS descent still tracks the true population loss; if the best-scoring client is consistently a malicious update, the proxy assumption is falsified.","supporting_citations":[{"cited_title":"Communication-efficient learning of deep networks from decentralized data,","cited_arxiv_id":null,"evidence_quote":"Supplies the FedAvg/Mean baseline and the standard server-client training loop that FedGreed replaces the aggregation step of."},{"cited_title":"Byzantine-robust dis- tributed learning: Towards optimal statistical rates,","cited_arxiv_id":null,"evidence_quote":"Supplies the Trimmed Mean and Median coordinate-wise robust aggregation baselines that FedGreed is compared against."},{"cited_title":"Ma- chine learning with adversaries: Byzantine tolerant gradient descent,","cited_arxiv_id":null,"evidence_quote":"Supplies the Krum and Multi-Krum distance-based aggregation baselines; FedGreed is claimed to outperform them without needing the attack count f."},{"cited_title":"An experimental study of byzantine- robust aggregation schemes in federated learning,","cited_arxiv_id":null,"evidence_quote":"Provides the experimental setup and attack types (label flipping, Gaussian noise) used to benchmark Byzantine robustness."},{"cited_title":"Learning multiple layers of features from tiny images,","cited_arxiv_id":null,"evidence_quote":"CIFAR-10, one of the three benchmark datasets used to evaluate robustness under non-IID partitions."}],"review_version":1}