SketchGuard: Scaling Byzantine-Robust Decentralized Federated Learning via Sketch-Based Screening

Download

🎧 Podcast Summary

Listen to the narrated summary of the paper:

Abstract

Decentralized Federated Learning (DFL) enables privacy-preserving collaborative training without centralized servers but remains vulnerable to Byzantine attacks. Existing Byzantine-robust defenses are predicated on exchanging full, high-dimensional model vectors with every neighbor before filtering, an $O(d|\mathcal{N}_i|)$ communication cost incurred regardless of how many neighbors are ultimately rejected. This design choice is sustainable in small-scale experimental settings but becomes a fundamental barrier to deployment as network scale or model size grows. We propose \textsc{SketchGuard}, a framework that decouples Byzantine filtering from aggregation via sketch-based screening. Each client compresses its $d$-dimensional model to a $k$-dimensional Count Sketch ($k \ll d$), exchanges only sketches for neighbor screening, and fetches full models exclusively from accepted neighbors. This eliminates the pre-filtering communication waste of existing defenses: rejected Byzantine neighbors incur only $O(k)$ sketch cost rather than $O(d)$ full-model cost. Communication savings therefore scale with the Byzantine rejection rate: negligible extra overhead in benign conditions, rising to 50-70% total savings when 50-70% of neighbors are rejected. We prove convergence in both strongly convex and non-convex settings, establishing that Count Sketch’s distance-preservation guarantee causes sketch-based filtering to deviate from full-precision filtering by at most a $(1+O(\epsilon))$ factor in the effective threshold, a gap that can be made arbitrarily small. Experiments across three non-IID federated benchmarks, five network topologies, and four attack types confirm that \textsc{SketchGuard} matches state-of-the-art robustness (mean TER deviation $\leq$0.5 percentage points) while reducing computation by up to 82%, with robustness remaining stable across compression ratios up to 13,000:1.

Figure 1: The SketchGuard Protocol

Citation

@MISC{rangwala2025sketchguard,
      title={SketchGuard: Scaling Byzantine-Robust Decentralized Federated Learning via Sketch-Based Screening}, 
      author={Murtaza Rangwala and Farag Azzedin and Richard O. Sinnott and Rajkumar Buyya},
      year={2025},
      eprint={2510.07922},
      archivePrefix={arXiv},
      primaryClass={cs.LG},
      url={https://arxiv.org/abs/2510.07922}, 
}

Download

🎧 Podcast Summary

Abstract

Figure 1: The SketchGuard Protocol

Citation

Related material