Unveiling the Non-Monotonic Effect of Privacy on Generalization under Byzantine Robustness
Summary
This paper reveals a non-monotonic effect of privacy on generalization error in Byzantine-robust distributed learning: in high-noise (strong privacy) regimes, increasing privacy reduces generalization error, while in low-noise (weaker privacy) regimes, increasing privacy degrades generalization.
View Cached Full Text
Cached at: 07/03/26, 05:41 AM
# Unveiling the Non-Monotonic Effect of Privacy on Generalization under Byzantine Robustness Source: [https://arxiv.org/abs/2607.01492](https://arxiv.org/abs/2607.01492) [View PDF](https://arxiv.org/pdf/2607.01492) > 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 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\. ## Submission history From: Thomas Boudou \[[view email](https://arxiv.org/show-email/020f0b6f/2607.01492)\] **\[v1\]**Wed, 1 Jul 2026 21:42:47 UTC \(201 KB\)
Similar Articles
Provable Robustness against Backdoor Attacks via the Primal-Dual Perspective on Differential Privacy
This paper introduces a framework that connects randomized smoothing to differential privacy through privacy profiles, enabling tight provable robustness guarantees against backdoor attacks that jointly affect training and inference. The approach is instantiated for DP-SGD and Deep Partition Aggregation with experiments on MNIST and CIFAR-10.
Reducing information dependency does not cause training data privacy. Adversarially non-robust features do
This paper challenges the prevailing view that rote memorization causes training data exposure to reconstruction attacks, showing instead that adversarial non-robust features are the true cause. The authors introduce AntiAdversarial Training (AT-AT) that intentionally learns non-robust features to achieve superior reconstruction defense and higher accuracy.
From Privacy to Generalization: Linear Max-Information Bounds for DP-SGD
This paper proves a finite-sample bound on the approximate max-information of DP-SGD that is at most linear in dataset size, yielding PAC-Bayes generalization bounds for models trained with differential privacy.
Unlearning with Asymmetric Sources: Improved Unlearning-Utility Trade-off with Public Data
This paper introduces Asymmetric Langevin Unlearning (ALU), a framework that leverages public data to improve the privacy-utility trade-off in machine unlearning. It demonstrates that ALU reduces unlearning costs and enables mass unlearning while maintaining high model utility.
On Privacy Leakage in Tabular Diffusion Models: Influential Factors, Attacker Knowledge, and Metrics
This research paper investigates privacy leakage in tabular diffusion models, quantifying how training setups, synthesis choices, and attacker knowledge impact privacy risks. It reveals that adversaries can succeed without perfect knowledge or massive resources and highlights pitfalls in heuristic privacy metrics.