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.
Online Security Learning in Cooperative Multi-Agent Systems under Hidden Byzantine Attacks
This paper studies online cooperative control of multi-agent systems under hidden Byzantine attacks, establishing information-theoretic limits and proposing a robust estimation-to-decisions learner with provable regret bounds.
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.
When Clean Data Hurts: Learning with Monotone Corruptions Beyond Binary Classification
This paper demonstrates that monotone adversarial corruptions can make certain multiclass and partial binary classification problems unlearnable, providing tight bounds on corruption budgets and extending previous results on binary classification.