Search papers, labs, and topics across Lattice.
This paper introduces Projected Dimensionality Reduction (PDR), a framework to accelerate Byzantine-robust federated learning by compressing gradients into a lower-dimensional subspace using sparse random projections before aggregation. PDR reduces server-side computational complexity to O(Mp), matching the theoretical lower bound, and provably maintains convergence rates of O(1/鈭歍) for non-convex and O(1/T) for strongly convex functions. Empirically, PDR provides orders-of-magnitude speedups when integrated with existing robust aggregators, with a theoretically bounded impact on the Byzantine error floor.
Byzantine-robust federated learning can be sped up by orders of magnitude with provable convergence guarantees and minimal impact on error floors, simply by projecting gradients into a drastically smaller subspace before aggregation.
Federated Learning (FL) enables multiple clients to collaboratively train models without sharing raw data, but it is highly vulnerable to Byzantine attacks. Existing robust approaches can neutralize these threats but incur substantial computational overhead during high-dimensional gradient aggregation, an overhead that scales poorly with model size and increasingly dominates the training cost as modern models grow larger. To address this computational bottleneck, we propose Projected Dimensionality Reduction (PDR), a universal acceleration framework for vector-level distance-based robust aggregators, which performs robust aggregation by compressing gradients into a drastically smaller subspace via sparse random projection to efficiently compute reliability weights. This approach reduces the server computational complexity to an optimal $ \mathcal{O}(Mp) $, where $ M $ is the number of clients and $ p $ is the model dimension, matching the theoretical lower bound required merely to read the gradients. We establish convergence guarantees under standard FL assumptions in prior Byzantine-robust FL analyses. By leveraging the Subspace Embedding Theorem, we show that PDR achieves optimal convergence rates of $ \mathcal{O}(1/\sqrt{T}) $ for non-convex functions and $ \mathcal{O}(1/T) $ for strongly convex functions, where $ T $ denotes the number of iterations. Crucially, we mathematically demonstrate that this massive acceleration comes almost for free, merely inflating the inherent Byzantine error floor by a bounded, tunable factor of $ \frac{1+蔚}{1-蔚} $. Experimental results on benchmark datasets confirm that integrating PDR with existing aggregators yields orders of magnitude speedups in time efficiency while maintaining highly competitive convergence performance.
