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

arXiv:2607.01492v1 Announce Type: new Abstract: 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 betwe...