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.
Information-theoretic lower bound
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.
ByzULDP: algorithm and mechanisms
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.
Privacy sensitivity depends on how client updates are constructed.
Convergence guarantees
ByzULDP achieves the order-optimal convergence bound for strongly-convex objectives, with vanishing error terms decaying at the optimal $O(1/T)$ and $O(1/\sqrt{T})$ rates for strongly-convex and non-convex objectives, respectively.
强凸：O(1/T)
非凸：O(1/√T)Numerical experiments
We corroborate our analysis with numerical experiments on real-world datasets across diverse privacy budgets.