Making Distance-Based Robust Aggregation Fast: A Server-Side Embedding Wrapper

Distance-based robust aggregators such as Krum, Bulyan, Geometric Median, and MCA defend Federated Learning against Byzantine clients, but they are slow on the server: Krum costs $\mathcal{O}(M^{2}p)$, and related pairwise geometry is likewise super-linear in the model dimension $p$. Existing JL and sketch protocols mainly reduce communication or cryptographic overhead; they do not accelerate the standard centralized interface in which clients still upload full-dimensional gradients. We propose Projected Dimensionality Reduction (PDR), a plug-and-play server-side wrapper: after full-dimensional uploads, the server applies a sparse embedding, computes reliability weights in ${\mathbb{R}}^k$, and reconstructs the update in ${\mathbb{R}}^p$, reducing aggregation to $\mathcal{O}(Mps+C_{\mathrm{RAgg}}(M,k))$. For this wrapper we prove that the usual robust-FL rates $\mathcal{O}(1/\sqrt{T})$ (non-convex) and $\mathcal{O}(1/T)$ (strongly convex) are retained, with the Byzantine error floor inflated only by $\frac{1+ϵ}{1-ϵ}$. Experiments show large reductions in server wall-clock time while tracking the accuracy of the wrapped aggregators. To our knowledge, PDR is the first server-side sparse-embedding wrapper for existing distance-based RAggs under full-dimensional uploads, together with a convergence analysis of that wrapper.