Unveiling the Non-Monotonic Effect of Privacy on Generalization under Byzantine Robustness
For researchers in distributed learning, this work clarifies the nuanced relationship between privacy and generalization under Byzantine robustness, revealing a non-monotonic effect.
The paper shows that the trilemma between Byzantine robustness, local differential privacy, and generalization error is not universal; in high-privacy regimes, increasing privacy reduces generalization error, while in low-privacy regimes, it degrades generalization.
Recent work has established a fundamental trilemma between Byzantine robustness, local differential privacy (LDP), and optimization error in distributed learning. We show that this trilemma does not universally extend to generalization error, but instead depends critically on the privacy regime. Specifically, in the high-noise regime (strong privacy), we prove that increasing privacy reduces the generalization error, i.e., there is no tension between robustness and privacy. In the low-noise regime (weaker privacy), however, the tension between robustness and privacy reappears and increasing privacy indeed degrades generalization. Our theory explains this surprising non-monotonic behavior of the generalization error via matching lower and upper bounds on the algorithmic stability of Byzantine-robust distributed learning under LDP constraints. We corroborate and further analyze these theoretical findings with empirical evaluations.