Unveiling the Non-Monotonic Effect of Privacy on Generalization under Byzantine Robustness

Prior work has established a fundamental trilemma between Byzantine robustness, local differential privacy (LDP), and optimization error in distributed learning. We show that the trilemma does not extend to generalization error as such, but instead depends on privacy regimes. In the high-noise (strong privacy) regime, we prove that increasing privacy reduces the generalization error, i.e., there is no tension between robustness and privacy. In the low-noise (weaker privacy) regime, however, there is a tension between robustness and privacy, i.e., increasing privacy indeed degrades generalization. We characterize this non-monotonic behavior rigorously by providing matching lower and upper bounds on the algorithmic stability of Byzantine-robust distributed learning subject to LDP. Our characterization leverages a novel connection between the strength of Byzantine attacks and their ability to perform membership inference attacks. Through numerical experiments, we further show that this behavior is not confined to the theoretical worst case, but also manifests in real learning problems under existing Byzantine attack.