cs.LGNov 7, 2026

Optimal Byzantine-resilient Federated Learning with User-level Differential Privacy

Authors: Ming Xiang, Stratis Ioannidis, Edmund Yeh, Carlee Joe-Wong, Lili Su

Organizations: Northeastern University, Boston, MA, USA · Carnegie Mellon University, Pittsburgh, PA, USA

Abstract

Real-world deployment of federated learning (FL) requires resilience against adversarial clients and data privacy. Byzantine fault captures the worst-case behavior of adversarial clients, while differential privacy (DP) provides statistical guarantees against privacy loss. In particular, user-level DP guards a client's entire contribution and provides more realistic protection against information leakage. Despite intensive efforts, the minimax-optimal convergence bound of Byzantine-resilient FL with user-level DP remains open. We establish an information-theoretic lower bound for any Byzantine-resilient empirical risk minimization problem under user-level DP and heterogeneous clients. We propose ByzULDP, a central DP algorithm featuring a two-level momentum across the client and server. Client-side momentum mitigates stochastic gradient variance during robust aggregation. Unlike the fault-free case, naively combining non-linear Byzantine-resilient aggregation with central DP noise can be insufficient to guarantee convergence to a bounded neighborhood of a stationary point. Our key contribution is a server-side momentum that leverages a property specific to user-level DP, where privacy sensitivity depends on how client updates are constructed, to empower convergence. ByzULDP achieves the order-optimal convergence bound for strongly-convex objectives, with vanishing error terms decaying at the optimal O(1/T)O(1/T) and O(1/T)O(1/\sqrt{T}) rates for strongly-convex and non-convex objectives, respectively. We corroborate our analysis with numerical experiments on real-world datasets across diverse privacy budgets.

Figures & tables

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Byzantine-Robust and Differentially Private Federated Optimization under Weaker Assumptions

    Mar 24, 2026Rustem Islamov, Grigory Malinovsky, Alexander Gaponov +3Byzantine-Robust Federated LearningDifferentially Private Federated Learning

  2. Robust Decentralized Personalized Federated Learning via Prediction-Constrained Neighborhood Collaboration

    Sep 7, 2026Xiao Ma, Hong Shen, Hui Tian +2Federated Learning AggregationByzantine-Robust Federated Learning