- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies how local differential privacy (LDP) affects generalization in Byzantine-robust distributed learning. The authors show that the relationship can be non-monotonic: adding privacy noise may hurt stability in the weak-privacy regime but improve it in the strong-privacy regime. The paper derives upper and lower bounds on the algorithmic stability of Safe-DGD and connects this behavior to the membership inference capabilities of Byzantine participants. Experiments on synthetic data, MNIST, and CIFAR-10 are provided to support the theoretical findings.
Critical strengths
I think the paper studies an interesting theoretical question. The distinction between optimization error and generalization error in the privacy-robustness trade-off is meaningful. I find the connection between membership inference attacks and Byzantine-induced instability particularly interesting. It provides a useful perspective on why privacy noise may have different effects across privacy regimes. The theoretical analysis is quite detailed, and I appreciate that the authors include experiments on multiple datasets and investigate the effects of Byzantine participants, dimensionality, and data heterogeneity.
Critical weaknesses
-
My main concern is whether the theoretical results fully support the claimed non-monotonic behavior of generalization error. The analysis primarily establishes bounds on uniform stability, which provides an upper bound on expected generalization error. I think the paper should be more careful in distinguishing the behavior of stability bounds from that of the actual generalization error.
-
I have some concerns about Lemma A.1. The proof seems to treat the communication transcript as Gaussian observations with a fixed mean shift. However, in iterative learning, the gradients depend on the previous model updates and observed noise. I am not fully convinced that the claimed tight characterization of MIA success probability holds for a general algorithm without additional assumptions.
-
I find the characterization of the weak-privacy regime somewhat unclear. In particular, Eq. (8) suggests that stability scales linearly with the privacy noise, while the preceding theorems also contain terms that remain nonzero when the noise vanishes. I would like to understand whether Eq. (8) describes the overall stability or only the additional privacy-dependent term.
-
I think the experimental evaluation could be more comprehensive. Most experiments use only seven participants, SMEA aggregation, and a single Byzantine attack strategy. Also, in the strong-privacy regime, the generalization gap becomes smaller partly when the model accuracy approaches random guessing. I would like to see a clearer discussion of the relationship between the generalization gap and actual model performance.
Questions for authors
-
Could the authors clarify whether the theoretical results establish non-monotonic behavior of the expected generalization error itself, or primarily characterize worst-case algorithmic stability?
-
Could the authors explain why Lemma A.1 remains valid when the communication transcript depends adaptively on previous model updates? Is the tight MIA characterization intended only for the specific lower-bound construction?
-
Could the authors clarify the scaling in Eq. (8), especially the nonzero stability terms when the privacy noise approaches zero?
-
Would the observed non-monotonic behavior still hold under other robust aggregation methods or Byzantine attacks? I would also be interested in seeing the population risk or test accuracy reported alongside the generalization gap.
2 comments
Dear Reviewer DXBe,
With the discussion period closing soon, we wanted to check whether our rebuttal and revisions have resolved your concerns. If no concerns remain, we would greatly appreciate it if you would consider raising your score. Thank you very much for your time.
We thank the reviewer for their positive feedback and answer their questions below.
Q1. Our theoretical results primarily characterize worst-case algorithmic stability. However, as noted in Corollary 3.2.1, Boudou et al. (2026, Lemma 4.1) provide a direct link between algorithmic stability and expected generalization error. In particular, our lower bound adopts the same setting as theirs, in which they establish that the generalization error is not merely upper bounded by uniform stability, but is in fact proportional to it. This allows us to extend our theoretical characterization to the expected generalization error.
Moreover, in our experiments, we directly compute and plot the generalization error. These results (1) confirm the non-monotonic behavior predicted by our theory holds for the generalization error, and (2) demonstrate that this phenomenon is not restricted to our worst-case theoretical construction, but also manifests in practical learning problems under existing Byzantine attacks.
Q2. Lemma A.1 characterizes the power of MIA in the lower-bound construction of Theorem 3.1. Importantly, the upper bound in Equation (10) follows directly from DP and remains valid under adaptive communication. The matching lower bound, however, relies on specific properties of our construction. In particular, it uses the equality Δtraj=TΔstep (line 674), which means that the worst-case per-step sensitivity is attained throughout the entire trajectory. This need not hold in general, where the DP upper bound may not be tight. We will clarify this distinction in the statement and proof of Lemma A.1. We thank the reviewer for pointing this out.
Q3. The scaling can be found in Theorem 3.1, Eqs (4)-(5), and Theorem 3.2, Eq. (6). Corollary 3.2.1 is intended to summarize the overall behavior of the stability of Safe-DGD as σDP varies.
More precisely, as illustrated in Figure 1 and established by Theorems 3.1 and 3.2, the stability does not vanish when σDP goes to zero, but instead exhibits a strictly positive floor. This floor recovers the result of Boudou et al. (2025) when σDP=0, as also mentioned in lines 306-307.
For full rigor, Equation (8) should therefore include an additional term:
Importantly, these additional terms are negligible when CσDP∈Ω(1+n−fd1) (equivalently, ln(1/δ)ε∈O((1+n−fd)mT)). Thus, Equation (8) remains fully rigorous in this regime. We will add a footnote explaining this derivation and clarifying the non-zero stability floor for vanishing privacy noise.
Q4. First, note that the MIA principle is not fundamentally tied to any particular robust aggregation rule, as it is rooted in the (ε,δ)-LDP guarantee itself. Moreover, Theorem 3.2 holds for any (f,κ)-robust aggregation rule and any Byzantine attack, showing that the upper-bound characterization of the non-monotonic behavior is not specific to a particular aggregation rule or attack. However, this does not imply that non-monotonicity necessarily occurs for every aggregation rule or attack.
The primary motivation of our experiments is precisely to establish that the phenomenon uncovered by our theory is not merely a worst-case theoretical artifact, but can also manifest in practical learning problems under existing attacks. Although we consider a single aggregation rule (SMEA) and a single attack (Opt-IPM), observing the predicted non-monotonic behavior across various models, datasets, and parameter settings is sufficient to demonstrate its practical relevance. We do not claim that this phenomenon necessarily occurs in all settings, and agree that investigating its prevalence across other choices would be valuable. We report additional experiments using the same dataset and baseline configuration as in Figure 2, evaluating two variations: (1) replacing the aggregation rule with Component-Wise Trimmed Mean under the same Opt-IPM attack, and (2) applying the Opt-ALIE (Optimal A Little Is Enough, see González, 2025) attack while retaining the SMEA aggregation rule. Interestingly, consistent with our theoretical analysis, the empirical trends hold across both settings (see the new Appendix D.1 for full results).
Finally, we already report train and test accuracy for all experiments in Appendix D, complementing the generalization gap results with the corresponding predictive performance.