Pith. sign in

REVIEW 4 major objections 4 minor 24 references

FedGreed: A Byzantine-Robust Loss-Based Aggregation Method for Federated Learning

T0 review · 4 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read FedGreed keeps federated learning accurate under Byzantine attacks by greedily selecting the client updates with the lowest loss on a trusted server-side dataset.

desk verdict 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. read the letter →

arxiv 2508.18060 v1 pith:6BB5CQQI submitted 2025-08-25 cs.LG

Emmanouil Kritharakis , Antonios Makris , Dusan Jakovetic , Konstantinos Tserpes This is my paper
classification cs.LG
keywords FederatedlearningByzantinerobustnessRobustaggregationServer-sidetrusteddatasetGreedyclientselectionNon-IIDdataLabelflippingGaussiannoiseattack
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

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.

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 (4)
  1. [Section III, after Algorithm 1] 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.
  2. [Section IV-B, Table I] 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.
  3. [Section III, threat model] 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.
  4. [Section IV-A, Table I] 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.
minor comments (4)
  1. [Notation, Section III] 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.
  2. [Algorithm 1, step (5)] 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.
  3. [Section I and III] 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.
  4. [References] 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.

Circularity Check

1 steps flagged · score 4.0 of 10

fS-progress guarantee is the algorithm's own selection rule; population-loss bound is an omitted, assumption-dependent leap.

  1. self definitional [Section III, Algorithm 1 steps (4)-(6) and following paragraph]
    "Also, by construction, FedGreed guarantees progress in terms of fS at least as good as model bxt+1 (1), i.e., the current best individual model, fS-wise."

    Algorithm 1 initializes xaux to the model with the smallest fS among all client updates, bxt+1_(1), and only replaces xaux with xtest when fS(xtest) < fS(xaux). The final update xt+1 is xaux, so the inequality fS(xt+1) <= fS(bxt+1_(1)) is literally the algorithm's selection rule, not an independent result. The paper then uses this definitional fS-progress as the bridge to a claimed bounded error in the true population loss f: 'Hence, if fS is a reasonably good approximation of the target population loss f, FedGreed is expected to exhibit robustness... Indeed, under standard assumptions ... we can show that FedGreed exhibits bounded error.' The actual theorem and proof are omitted ('Detailed rigorous assumptions, theorems, and proofs are omitted here for brevity'), and the only link to f is

full rationale

The paper's only explicitly guaranteed per-round property—that FedGreed makes progress on the server-side loss fS—is self-definitional: the algorithm is defined to select the prefix-average candidate with minimal fS, so fS(xt+1) <= fS(any candidate including the best honest client) is true by construction. This is acknowledged by the paper ('by construction') and is not itself a circular deception. The central headline claim of 'bounded optimality gaps' for the population loss f is not actually derived: the theorem is stated to exist but its assumptions and proofs are omitted. That omission is an evidentiary gap, not a circular reduction. The experimental evaluation is external and self-contained, providing independent empirical grounding, and the self-citation to [17] is used only as related work, not as load-bearing support. The moderate score reflects that the one guaranteed 'progress' result reduces to the algorithm's definition, and the more ambitious f-convergence claim depends on an unquantified proxy assumption plus an omitted proof, so the derivation chain is incomplete rather than fully circular.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

FedGreed introduces no fitted constants or new entities; its claims rest on domain assumptions about the trusted dataset, honest-client presence, and loss smoothness. The absence of a stated theorem means the approximation assumptions are never made precise.

assumptions (4)
  • domain assumption The server holds a trusted dataset of i.i.d. samples from P, and its empirical loss fS is a good approximation of the population loss f.
    Invoked in Section III Eq. (2) and used to justify that selecting by fS yields robustness. The paper states this only as an assumption and notes the bound depends on "server-side data approximation quality."
  • domain assumption At each round at least one client is non-Byzantine (possibly a server-side "trusted client").
    Explicitly assumed in Section III attack model paragraph; required for the greedy selection to have an honest candidate.
  • domain assumption Losses are smooth and the SGD oracle has standard noise properties, with client losses averaging to an informative approximation of f despite non-IID data.
    Mentioned but not stated precisely: "under standard assumptions on non-convex and convex losses... and standard assumptions on SGD oracle noises"; no theorem is given.
  • domain assumption The prefix-average candidate set (4) contains an update whose fS value is indicative of population-loss progress.
    The algorithm greedily checks only ordered prefixes; the analysis is asserted to rely on this, but the assumption is not formalized.

how reviews work

0 comments
Cite this review

Pith. "Pith review of FedGreed: A Byzantine-Robust Loss-Based Aggregation Method for Federated Learning." pith.science (2026). https://pith.science/paper/6BB5CQQI

@misc{pith2026250818060,
  author       = {Pith},
  title        = {Pith review of: FedGreed: A Byzantine-Robust Loss-Based Aggregation Method for Federated Learning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6BB5CQQI}},
  note         = {Machine review of arXiv:2508.18060}
}
read the original abstract

Federated Learning (FL) enables collaborative model training across multiple clients while preserving data privacy by keeping local datasets on-device. In this work, we address FL settings where clients may behave adversarially, exhibiting Byzantine attacks, while the central server is trusted and equipped with a reference dataset. We propose FedGreed, a resilient aggregation strategy for federated learning that does not require any assumptions about the fraction of adversarial participants. FedGreed orders clients' local model updates based on their loss metrics evaluated against a trusted dataset on the server and greedily selects a subset of clients whose models exhibit the minimal evaluation loss. Unlike many existing approaches, our method is designed to operate reliably under heterogeneous (non-IID) data distributions, which are prevalent in real-world deployments. FedGreed exhibits convergence guarantees and bounded optimality gaps under strong adversarial behavior. Experimental evaluations on MNIST, FMNIST, and CIFAR-10 demonstrate that our method significantly outperforms standard and robust federated learning baselines, such as Mean, Trimmed Mean, Median, Krum, and Multi-Krum, in the majority of adversarial scenarios considered, including label flipping and Gaussian noise injection attacks. All experiments were conducted using the Flower federated learning framework.

Figures

Figures reproduced from arXiv: 2508.18060 by the authors.

Figure 1
Figure 1. Illustration of data heterogeneity in the 10-client FL setup on CIFAR-10 using Dirichlet partitioning with [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Centralized accuracy over 50 FL rounds on MNIST, [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

24 extracted references · 15 canonical work pages

  1. [17]

    Robust federated learning under adversarial attacks via loss-based client clustering,

    E. Kritharakis, D. Jakovetic, A. Makris, and K. Tserpes, “Robust federated learning under adversarial attacks via loss-based client clustering,” 2025. [Online]. Available: https://arxiv.org/abs/2508.12672

    arXiv 2025

  2. [15]

    Fltrust: Byzantine- robust federated learning via trust bootstrapping,

    X. Cao, M. Fang, J. Liu, and N. Z. Gong, “Fltrust: Byzantine- robust federated learning via trust bootstrapping,” arXiv preprint arXiv:2012.13995, 2020

    arXiv 2012

  3. [1]

    An overview of implementing security and privacy in federated learning,

    K. Hu, S. Gong, Q. Zhang, C. Seng, M. Xia, and S. Jiang, “An overview of implementing security and privacy in federated learning,” Artificial Intelligence Review, vol. 57, no. 8, p. 204, 2024

    work page 2024

  4. [2]

    Federated learning: Challenges, methods, and future directions,

    T. Li, A. K. Sahu, A. Talwalkar, and V . Smith, “Federated learning: Challenges, methods, and future directions,” IEEE signal processing magazine, vol. 37, no. 3, pp. 50–60, 2020

    work page 2020

  5. [3]

    Communication-efficient learning of deep networks from decentralized data,

    H. B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in Proceedings of the 20th International Conference on Artificial Intelligence and Statistics . PMLR, 2017, pp. 1273–1282

    work page 2017

  6. [4]

    The byzantine generals prob- lem,

    L. Lamport, R. Shostak, and M. Pease, “The byzantine generals prob- lem,” in Concurrency: the works of leslie lamport , 2019, pp. 203–226

    work page 2019

  7. [5]

    A little is enough: Circumvent- ing defenses for distributed learning,

    G. Baruch, M. Baruch, and Y . Goldberg, “A little is enough: Circumvent- ing defenses for distributed learning,” in Advances in Neural Information Processing Systems, vol. 32, 2019

    work page 2019

  8. [6]

    Fall of empires: Breaking byzantine- tolerant sgd by inner product manipulation,

    C. Xie, O. Koyejo, and I. Gupta, “Fall of empires: Breaking byzantine- tolerant sgd by inner product manipulation,” in Proceedings of the Conference on Uncertainty in Artificial Intelligence . PMLR, 2020, pp. 261–270

    work page 2020

Show all 24 references
  1. [7]

    Siren: Byzantine-robust federated learning via proactive alarming,

    H. Guo, H. Wang, T. Song, Y . Hua, Z. Lv, X. Jin, Z. Xue, R. Ma, and H. Guan, “Siren: Byzantine-robust federated learning via proactive alarming,” in Proceedings of the ACM Symposium on Cloud Computing , 2021, pp. 47–60

    2021

  2. [8]

    An experimental study of byzantine- robust aggregation schemes in federated learning,

    S. Li, E. C.-H. Ngai, and T. V oigt, “An experimental study of byzantine- robust aggregation schemes in federated learning,” IEEE Transactions on Big Data , 2023

    2023

  3. [9]

    Local model poisoning attacks to {Byzantine-Robust} federated learning,

    M. Fang, X. Cao, J. Jia, and N. Gong, “Local model poisoning attacks to {Byzantine-Robust} federated learning,” in 29th USENIX security symposium (USENIX Security 20) , 2020, pp. 1605–1622

    2020

  4. [10]

    Federated learning with extremely noisy clients via nega- tive distillation,

    Y . Lu, L. Chen, Y . Zhang, Y . Zhang, B. Han, Y .-m. Cheung, and H. Wang, “Federated learning with extremely noisy clients via nega- tive distillation,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 38, no. 13, 2024, pp. 14 184–14 192

    2024

  5. [11]

    Fedcor: Correlation-based active client selection strategy for heteroge- neous federated learning,

    M. Tang, X. Ning, Y . Wang, J. Sun, Y . Wang, H. Li, and Y . Chen, “Fedcor: Correlation-based active client selection strategy for heteroge- neous federated learning,” in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition , 2022, pp. 10 102–10 111

    2022

  6. [12]

    Byzantine-robust dis- tributed learning: Towards optimal statistical rates,

    D. Yin, Y . Chen, R. Kannan, and P. Bartlett, “Byzantine-robust dis- tributed learning: Towards optimal statistical rates,” inProceedings of the 35th International Conference on Machine Learning , vol. 80. PMLR, 2018, pp. 5650–5659

    2018

  7. [13]

    Ma- chine learning with adversaries: Byzantine tolerant gradient descent,

    P. Blanchard, E. M. El Mhamdi, R. Guerraoui, and J. Stainer, “Ma- chine learning with adversaries: Byzantine tolerant gradient descent,” in Advances in Neural Information Processing Systems , vol. 30, 2017

    2017

  8. [14]

    Byzantine-robust federated learning through spatial-temporal analysis of local model updates,

    Z. Li, L. Liu, J. Zhang, and J. Liu, “Byzantine-robust federated learning through spatial-temporal analysis of local model updates,” in 2021 IEEE 27th International Conference on Parallel and Distributed Systems (ICPADS). IEEE, 2021, pp. 372–379

    2021

  9. [16]

    Byzantine-robust federated learning: Impact of client subsampling and local updates,

    Y . Allouah, S. Farhadkhani, R. Guerraoui, N. Gupta, R. Pinot, G. Rizk, and S. V oitovych, “Byzantine-robust federated learning: Impact of client subsampling and local updates,” arXiv preprint arXiv:2402.12780, 2024

    2024 arXiv

  10. [18]

    Ensemble distillation for robust model fusion in federated learning,

    T. Lin, L. Kong, S. U. Stich, and M. Jaggi, “Ensemble distillation for robust model fusion in federated learning,” Advances in neural information processing systems , vol. 33, pp. 2351–2363, 2020

    2020

  11. [19]

    Learning multiple layers of features from tiny images,

    A. Krizhevsky, G. Hinton et al. , “Learning multiple layers of features from tiny images,” University of Toronto, Tech. Rep., 2009

    2009

  12. [20]

    Fashion-mnist: A novel image dataset for benchmarking machine learning algorithms,

    H. Xiao, K. Rasul, and R. V ollgraf, “Fashion-mnist: A novel image dataset for benchmarking machine learning algorithms,” arXiv preprint arXiv:1708.07747, 2017

    2017 arXiv

  13. [21]

    Mnist handwritten digit database,

    Y . LeCun, “Mnist handwritten digit database,” http://yann.lecun.com/ exdb/mnist/, 2010, aT&T Labs

    2010

  14. [22]

    Flower: A friendly federated learning research framework,

    D. J. Beutel, T. Topal, A. Mathur, X. Qiu, J. Fernandez-Marques, Y . Gao, L. Sani, H. L. Kwing, T. Parcollet, P. P. d. Gusm ˜ao, and N. D. Lane, “Flower: A friendly federated learning research framework,” arXiv preprint arXiv:2007.14390, 2020

    2007 arXiv

  15. [23]

    Multi-task federated learning for person- alised deep neural networks in edge computing,

    J. Mills, J. Hu, and G. Min, “Multi-task federated learning for person- alised deep neural networks in edge computing,” IEEE Transactions on Parallel and Distributed Systems , vol. 33, no. 3, pp. 630–641, 2021

    2021

  16. [24]

    Adaptive federated optimization,

    S. Reddi, Z. Charles, M. Zaheer, Z. Garrett, K. Rush, J. Kone ˇcn`y, S. Kumar, and H. B. McMahan, “Adaptive federated optimization,”arXiv preprint arXiv:2003.00295, 2020

    2003 arXiv

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.