Optimal Byzantine-resilient Federated Learning with User-level Differential Privacy
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 and 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
| The norm of a given vector . | |
|---|---|
| The sigma algebra generated by randomness up to round . | |
| A -dimensional vector space, where denotes the dimension. | |
| A set . | |
| A set of honest clients. | |
| A set of clients suffering from Byzantine attacks . | |
| An all one vector . |
| The global model at the beginning of round in Algorithm 1 . | |
|---|---|
| The local objective function at client . | |
| The global objective function defined in ( 1 ): . | |
| The local stochastic gradient function at client taken with respect to . | |
| The clipped local stochastic gradient function at client taken with respect to . | |
| The client-side momentum at client in round . | |
| An average over the client-side momentum for clients in in round . |
| Lipschitz constant in Assumption 2 . | |
|---|---|
| The upper bound of the stochastic gradient variance. | |
| The variance of DP noise in round . | |
| Parameters that capture the averaged local-global gradient dissimilarity. | |
| A uniform upper bound on the stochastic gradient norm. | |
| The number of clients in the FL system. | |
| The number of local data points at each client in the FL system. |
| Robust Aggregator | Trimmed Mean | Coordinate Median | Geometric Median | Krum | CClip | Average (fault-free) |
|---|---|---|---|---|---|---|
| Sensitivity |
| Dataset | MNIST / Fashion-MNIST |
|---|---|
| Neural network | CNN |
| Model architecture ∗ | C (1,16,8,2,3) – T – M (2,1) – C (16,32,4,2) – T – M (2,1) – L (512,32) – T – L (10) |
| Loss function | Cross-entropy loss |
| Number of global rounds | 800 |
| Batch size | 20 |
| Datasets | Attack | Settings | CWTM | CClip | GM | CWMED |
|---|---|---|---|---|---|---|
| MNIST | ALIE | % | % | % | % | |
| % ({\color[rgb]{0,0,1}\uparrow}2.6\%) | % ({\color[rgb]{1,0.65,0.3}\downarrow}-1.4\%) | % ({\color[rgb]{0,0,1}\uparrow}18.9\%) | % ({\color[rgb]{1,0.65,0.3}\downarrow}-17.3\%) | |||
| BitFlip | % | % | % | % | ||
| % ({\color[rgb]{0,0,1}\uparrow}19.6\%) | % ({\color[rgb]{0,0,1}\uparrow}8.7\%) | % ({\color[rgb]{0,0,1}\uparrow}11.6\%) | % ({\color[rgb]{0,0,1}\uparrow}15.9\%) | |||
| Mimic | % | % | % | % | ||
| % ({\color[rgb]{0,0,1}\uparrow}15.8) | % ({\color[rgb]{0,0,1}\uparrow}2.5) | % ({\color[rgb]{0,0,1}\uparrow}38.7) | % ({\color[rgb]{0,0,1}\uparrow}40.3) |
Federated Learning
Federated learning trains shared models across data holders without requiring them to pool their raw data.
See all 1,027 papers