acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

Prior work has established a fundamental trilemma between Byzantine robustness, local differential privacy (LDP), and optimization error in distributed learning. We show that the trilemma does not extend to generalization error as such, but instead depends on privacy regimes. In the high-noise (strong privacy) regime, we prove that increasing privacy reduces the generalization error, i.e., there is no tension between robustness and privacy. In the low-noise (weaker privacy) regime, however, there is a tension between robustness and privacy, i.e., increasing privacy indeed degrades generalization. We characterize this non-monotonic behavior rigorously by providing matching lower and upper bounds on the algorithmic stability of Byzantine-robust distributed learning subject to LDP. Our characterization leverages a novel connection between the strength of Byzantine attacks and their ability to perform membership inference attacks. Through numerical experiments, we further show that this behavior is not confined to the theoretical worst case, but also manifests in real learning problems under existing Byzantine attack.

Primary area:
learning theory
Keywords:
Algorithmic Stability, Byzantine Robustness, Differential Privacy, Generalization

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_DXBeOpenReview ↗
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
  1. 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.

  2. 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.

  3. 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.

  4. 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
  1. 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?

  2. 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?

  3. Could the authors clarify the scaling in Eq. (8), especially the nonzero stability terms when the privacy noise approaches zero?

  4. 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

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\Delta_{\mathrm{traj}}=\sqrt{T}\Delta_{\mathrm{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\sigma_{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\sigma_{DP} goes to zero, but instead exhibits a strictly positive floor. This floor recovers the result of Boudou et al. (2025) when σDP=0\sigma_{DP} = 0, as also mentioned in lines 306-307.

For full rigor, Equation (8) should therefore include an additional term:

  • Θ(γC2T(1(n−f)m+fn−2f))\Theta(\gamma C^2 T (\frac{1}{(n-f)m}+\sqrt{\frac{f}{n-2f}})) when n3≤f<n2\frac{n}{3} \leq f < \frac{n}{2}
  • Ω(γC2T(1(n−f)m+fn−2f))\Omega(\gamma C^2 T ( \frac{1}{(n-f)m} + \frac{f}{n-2f})) when f<n3f < \frac{n}{3}.

Importantly, these additional terms are negligible when σDPC∈Ω(11+dn−f)\frac{\sigma_{DP}}{C} \in \Omega(\frac{1}{1+\sqrt{\frac{d}{n-f}}}) (equivalently, εln⁡(1/δ)∈O((1+dn−f)Tm)\frac{\varepsilon}{\ln(1/\delta)} \in \mathcal{O}((1+\sqrt{\frac{d}{n-f}})\frac{\sqrt{T}}{m})). 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 (ε,δ)(\varepsilon, \delta)-LDP guarantee itself. Moreover, Theorem 3.2 holds for any (f,κ)(f,\kappa)-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.

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.

Reviewer_MS8aOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates the relationship between local differential privacy (LDP), Byzantine robustness, and generalization in distributed learning. Unlike previous studies focusing on optimization error, this paper establishes upper and lower bounds on algorithmic stability and shows that privacy noise can have a non-monotonic effect on generalization. The theoretical analysis connects Byzantine attacks with membership inference attacks (MIA), and this paper shows empirical results with synthetic data, MNIST, and CIFAR-10.

Critical strengths
  • This paper provides an interesting theoretical perspective on the privacy–robustness–generalization relationship, extending previous analyses that primarily focused on optimization error. The non-monotonic behavior is a meaningful finding that improves our understanding of generalization under Byzantine robustness.

  • It theoretically derives both upper and lower stability bounds and provides an MIA-based interpretation of the relationship between privacy and Byzantine attacks. The experiments across different datasets and model settings also provide useful empirical support for the predicted non-monotonic behavior.

Critical weaknesses
  • Although the paper establishes lower bounds on algorithmic stability, their connection to the empirical results remains somewhat unclear. The lower bounds rely on specifically constructed loss functions and MIA-based Byzantine attacks, whereas the experiments use logistic regression or CNN models under Opt-IPM attacks. Moreover, Figure 1 indicates that tightness is not established in the intermediate privacy regime. This makes it difficult to assess how well the theoretical bounds characterize the observed generalization behavior beyond the worst-case setting.

  • Some assumptions in Theorem 3.1 seems to be restricted, where it raise concerns about the validity and applicability of the theoretical results. Specifically, the condition f/(n−f)∈[αmin⁡,1/2)f/(n-f)\in[\alpha_{\min},1/2) implies f<n/3f<n/3, whereas the subsequent result additionally assumes n/3≤f<n/2n/3\leq f<n/2. These conditions cannot hold simultaneously. Moreover, the additional dimensionality, participant-count, and iteration constraints in Assumption C.3 may limit the applicability of the lower bounds, particularly to the strong-privacy regime and the reported experimental settings.

<I may raise the score if these concerns are resolved.>

Questions for authors
  • The lower bounds in Theorem 3.1 appear to be established under a rather specific worst-case construction, while the experiments consider different loss functions and attack strategies. It seems to be clarified that how the theoretical lower bounds relate to the empirical results in Figures 2–5. It would be helpful to explain whether the predicted scaling behavior or privacy-regime transition can be quantitatively connected to the existing experimental settings.

  • There seem to be some inconsistencies in the assumptions of Theorem 3.1. Specifically, as mentioned previously, f/(n−f)<1/2f/(n-f)<1/2 implies f<n/3f<n/3, which conflicts with the subsequent assumption n/3≤f<n/2n/3\leq f<n/2. Thus, in my perspective, it should be clarified that the intended conditions and whether this affects the validity of the lower bounds. It would also help to explain how the additional conditions in Assumption C.3, including the noise-dependent restriction on TT, affect the claimed tightness in the strong-privacy regime.

  • The theoretical analysis relies on an MIA-based Byzantine attack to explain the non-monotonic generalization behavior, whereas the empirical evaluations use Opt-IPM attacks without explicitly performing MIA. Please clarify the intended connection between the MIA-based theoretical construction and the practical attack settings. Especially, to what extent can the observed non-monotonic behavior be attributed to the reduced ability of Byzantine participants to infer training data, rather than the direct effect of increasing privacy noise on the learning process?

<I may raise the score if these concerns are resolved.>

5 comments

We thank the reviewer for their feedback and answer their questions below.

Q1. (1) The lower bounds in Theorem 3.1 appear to be established under a rather specific worst-case construction, while the experiments consider different loss functions and attack strategies. It seems to be clarified that how the theoretical lower bounds relate to the empirical results in Figures 2–5. (2) It would be helpful to explain whether the predicted scaling behavior or privacy-regime transition can be quantitatively connected to the existing experimental settings.

(1) The theoretical MIA-based construction and empirical evaluation serve complementary purposes.

The MIA-based construction is specifically designed to establish a worst-case lower bound on algorithmic stability in Theorem 3.1 and thereby characterize the non-monotonic effect of privacy. It is not intended to repesent a practical attack, nor is it necessarily applicable beyond this worst-case construction. Importantly, our upper bound in Theorem 3.2, unlike the lower-bound construction, holds for arbitrary attacks and thus provides a general guarantee on the generalization error.

The experiments serve a different purpose: we evaluate a state-of-the-art, off-the-shelf attack (Opt-IPM) across different models and datasets, and observe the same non-monotonic behavior. This demonstrates that the phenomenon identified theoretically is not merely an artifact of the worst-case scenario, but can also arise under practical attacks and realistic learning settings.

We will clarify this distinction in the revised version: the MIA-based construction establishes the worst-case theoretical behavior, our general upper bound applies to arbitrary attacks, and the experiments demonstrate the practical relevance of the non-monotonic phenomenon. This agreement between theory and empirical observations further supports the significance of our findings.

(2) The change of regime observed in Figures 2-5 occurs around σbase⁡=kCTm\sigma_{\operatorname{base}} = k \frac{C\sqrt{T}}{m}, with kk ranging from 1/21/2 to 88, in agreement with the transition predicted by our theory. Regarding the scaling behavior of the generalization gap, the empirical results also qualitatively follow our theoretical bounds, as illustrated in Figure 1. In particular, the generalization gap increases with the noise magnitude in the weak-privacy regime (low noise), but decreases with it in the strong-privacy regime (high noise). It also increases with the dimension and the number of Byzantine participants, as illustrated in Figures 3(a)-(b). We refer the reviewer to lines 426-431 and 459-462 in Section 4 for a more detailed discussion.

Q2. There seem to be some inconsistencies in the assumptions of Theorem 3.1. [...] It would also help to explain how the additional conditions in Assumption C.3, including the noise-dependent restriction on TT, affect the claimed tightness in the strong-privacy regime.

This is indeed a typo. The condition should be f/(n−f)<1f/(n-f) < 1 which is equivalent to f<n/2f < n/2, as required for learning to be possible under Byzantine failures. We thank the reviewer for pointing this out.

As explained after Theorem 3.1 in the main text, the assumption on the number of iterations and Assumption C.3, although technical, are relatively mild and primarily needed to establish concentration inequalities used in our proof. Specifically:

  • Assumption on TT: The condition T∈O(ecmin⁡(d+n−f−1)2)T \in \mathcal{O}\big(e^{c_{\min}(\sqrt{d}+\sqrt{n-f-1})^2}\big) simply requires that the number of iterations does not grow faster than exponentially in the dimension or the number of participants (e.g., it excludes factorial growth in the dimension). This is a very mild restriction, as such growth is neither encountered in practice nor desirable in theoretical analyses.
  • Assumption C.3, Point 3: This is the most technical condition, for which we provide an interpretation in lines 1427–1437. It requires a sufficiently large number of honest participants (n−f−1≥Nmin⁡n-f-1\ge N_{\min}) and a sufficiently large dimension-to-participant ratio (dn−f≥μ>μmin⁡\frac{d}{n-f}\geq\mu>\mu_{\min}). These conditions control random matrix fluctuations and ensure the spectral separation needed in our proof. Importantly, Nmin⁡N_{\min} is constant for fixed problem parameters and therefore imposes no additional asymptotic scaling restriction. Furthermore, the condition μ>μmin⁡\mu>\mu_{\min} is specific to our high-dimensional analysis: we also establish the lower bound for d=1d=1 without any restriction on the number of honest participants. This further suggests that these assumptions are technical requirements of our proof rather than fundamental limitations of the setting.

We would be happy to incorporate this discussion into the main text if the reviewer considers it helpful.

Q3. (1) The theoretical analysis relies on an MIA-based Byzantine attack to explain the non-monotonic generalization behavior, whereas the empirical evaluations use Opt-IPM attacks without explicitly performing MIA. Please clarify the intended connection between the MIA-based theoretical construction and the practical attack settings. (2) Especially, to what extent can the observed non-monotonic behavior be attributed to the reduced ability of Byzantine participants to infer training data, rather than the direct effect of increasing privacy noise on the learning process?

(1) See our answer to Q1. Importantly, MIA is a theoretical tool used to establish our tight lower bound (Theorem 3.1), rather than a necessary component of practical Byzantine attacks. Our experiments complement this construction by showing that the predicted non-monotonic behavior also occurs with practical attacks that do not explicitly perform MIA.

(2) We agree that increasing privacy noise can also directly affect learning. However, our theoretical analysis distinguishes this effect from Byzantine-induced instability: when f=0f=0 (hence κ=0\kappa=0), our stability bound is independent of the privacy noise σ\sigma, whereas the presence of Byzantine participants introduces a noise-dependent instability term. This supports the role of Byzantine participants in the non-monotonic behavior.

Intuitively, practical attacks such as Opt-IPM bias the update based on the honest gradients, to the extent permitted by the robust aggregation rule. Increasing privacy noise has two competing effects: it allows Byzantine participants to introduce a larger bias in magnitude, but also blurs the direction they seek to bias. Thus, even without explicitly performing MIA, Byzantine participants become less able to adapt their attack to the underlying data as privacy increases. This provides an interpretation of the non-monotonic behavior observed experimentally.

Dear Authors,

Thank you for the detailed responses. Most of my concerns have been addressed, and I appreciate the clarification.

However, still one concern remains regarding the assumptions. It seems like that Assumption C.3 in Appendix C.3.2 still specifies α=f/(n−f)∈[αmin⁡,1/2)\alpha=f/(n-f)\in[\alpha_{\min},1/2), which appears to conflict with the case n/3≤f<n/2n/3\leq f<n/2. Here, I want the authors to clarify whether the same correction applies to Assumption C.3 and whether the theoretical results, especially the lower bound in Theorem 3.1, remain valid under the corrected condition?

This is my only remaining concern. If this issue is sufficiently clarified and the theoretical results are sufficiently validated, I will increase my score.

Again, thanks for the responses.

 

P.S. As I selected a low confidence score, I am not fully familiar with differential privacy. Yet, I just want to clarify whether these mathematical derivations contain any fundamental logical flaws or only minor issues that would be acceptable in the context of deep learning research. So, please don't hesitate to make your claims or arguments.

Reviewer_4uPvOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
3(+1)
Read review
Paper summary

This paper investigates how local differential privacy and Byzantine-robust distributed learning interact. Specifically, the paper takes Safe-D(S)GD as a representative algorithm to study the relationship between privacy guarantees and generalization error under Byzantine robustness. The major theoretical findings characterize different behaviors in weak/strong privacy regimes.

Critical strengths
  • It is an interesting problem to investigate the interplay between LDP and Byzantine robustness in distributed learning.

  • The theoretical analysis seems sound and rigorous.

Critical weaknesses
  1. The findings in this paper have already been reflected in some previous work on other types of tasks. For example, Li et al.[a] have investigated the consistency of security and privacy in distributed statistical estimation. In addition, it is expected that the work in this paper will be connected with a broader scope of works on poisoning attacks against LDP protocols, which also consider the relationship between LDP and Byzantine robustness under the active poisoning attack setting.

  2. The idea of taking MIA as a component for Byzantine participants is intuitive but under justified. The reasons why such an MIA is necessary and how the MIA is deployed have not been clearly defined. More importantly, what is the difference between this setting and the white-box setting for Byzantine participants in poisoning attacks.

  3. Although Safe-D(S)GD could be viewed as a representative algorithm, a demonstration of the applicability of the theoretical results to other algorithms is also required. Otherwise, this paper may need to narrow its scope to an analysis of Safe-D(S)GD instead of claiming fundamental results for distributed learning.

[a] X. Li, N. Li, W. Sun, N. Z. Gong, and H. Li, "Fine-grained poisoning attack to local differential privacy protocols for mean and variance estimation," in Proc. USENIX Secur. Symp., 2023, pp. 1739–1756.

Questions for authors

Please see the Weaknesses.

4 comments

We thank the reviewer for their questions, which gives us the opportunity to clarify important points.

Q1. Li et al. is an interesting work, but it addresses a fundamentally different problem from ours. Specifically, it investigates targeted poisoning attacks against LDP protocols for scalar mean and variance estimation, focusing on how privacy affects the ability of an attacker to manipulate the estimated mean and variance toward predefined targets. In contrast, we consider arbitrary Byzantine failures in general machine learning problems and establish matching stability bounds characterizing the non-monotonic effect of privacy on the generalization gap.

Thus, although both works study the interplay between privacy and adversarial attacks, their research questions and main findings are fundamentally different. In particular, showing that stronger privacy can mitigate certain targeted poisoning attacks does not establish or imply the non-monotonic relationship between privacy and generalization that we uncover. We therefore respectfully disagree that our findings have already been reflected in Li et al. or the related line of work on targeted poisoning attacks against LDP protocols.

If the reviewer could point us to specific references establishing our main finding, namely, the non-monotonic effect of privacy on generalization under Byzantine failures, we would be happy to discuss them. Otherwise, we respectfully maintain that the novelty of our contribution remains distinct.

Q2. Our threat model allows Byzantine participants to observe all communications from honest participants and to know all their data except for one sample, but not the added random noise. This follows the standard DP threat model, which aims to protect against membership inference even under such worst-case adversarial knowledge.

The use of MIA in our lower-bound construction follows naturally from the objective of stability analysis: stability is defined by comparing the outputs obtained on neighboring datasets differing in a single sample. We therefore construct a Byzantine attack that uses MIA to distinguish between these neighboring datasets and adapt its behavior accordingly. MIA quantifies the adversary's ability to make this distinction, thereby capturing how the uncertainty induced by privacy noise limits its ability to adapt its attack. This allows us to establish a lower bound on algorithmic stability that explicitly accounts for the effect of privacy.

Regarding the distinction from the "white-box setting", if the reviewer means that Byzantine participants can also remove or bypass the privacy noise, this would constitute a stronger threat model than ours, and one that effectively disregards the privacy guarantee. In this case, our lower bound in Theorem 3.1 would remain applicable even in the strong-privacy regime, leading to a monotonic increase in instability rather than the non-monotonic behavior we establish under LDP. If the reviewer has a different white-box setting in mind, we would be happy to clarify the distinction further.

We emphasize that MIA is not necessary for Byzantine participants to affect generalization. Rather, it is a component of our specific theoretical construction, designed to establish a worst-case lower bound on stability. We explain its role in detail in the paragraph Key intuition: MIA limits Byzantine adaptation (lines 226–252).

Finally, our experiments serve a complementary purpose: they demonstrate that the phenomenon predicted by our theory also arises in realistic learning settings, under practical attacks that operate with a weaker threat model and do not rely on MIA. Specifically, we evaluate a state-of-the-art, off-the-shelf attack (Opt-IPM) across different models and datasets, and observe the same non-monotonic behavior. This shows that the phenomenon is not merely an artifact of our worst-case construction.

For further discussion, we refer to our answers to Q1 and Q3 of Reviewer MS8a and Q4 of Reviewer DXBe.

Q3. As explained in lines 180–188, Safe-D(S)GD is the natural algorithm to study, as it combines the two standard ingredients for ensuring LDP and Byzantine robustness in distributed learning: local noise addition for privacy and robust aggregation for Byzantine resilience. Moreover, it achieves optimal optimization error (Allouah et al., 2023b), making it arguably the de facto standard approach to jointly addressing these two challenges. We therefore believe that our results reveal fundamental limitations of this approach, rather than limitations specific to an arbitrary algorithm.

Furthermore, our upper bound (Theorem 3.2) holds for any (f,κ)(f,\kappa)-robust aggregation rule.

We can make the focus on Safe-D(S)GD more explicit in the introduction if the reviewer believes it is needed.

Thank you for the clarifications. My concerns regarding Q1 and Q2 have been largely addressed. My remaining concern is the broader applicability and significance of the theoretical results.

The response reasonably explains why Safe-D(S)GD is a natural algorithm to study, but does not establish the broader applicability of the findings. In particular, optimality in optimization error does not imply optimality in stability or generalization, and therefore does not by itself justify characterizing the results as fundamental limitations of the broader approach.

I would like to understand whether the central findings also apply to other algorithms ensuring both LDP and Byzantine robustness in distributed learning. If Safe-D(S)GD is effectively the only algorithm to which the theoretical characterization applies, then the scope and broader significance of the contribution would be substantially limited. Simply emphasizing that this algorithm is a standard choice does not resolve this concern.

We acknowledge the reviewer's concern regarding the scope of our analysis, which focuses on the Safe-D(S)GD family of algorithms. To make this scope clear upfront, we revised the abstract to state explicitly: "We characterize this non-monotonic behavior rigorously by providing matching lower and upper bounds on the algorithmic stability of Safe-D(S)GD, a Byzantine-robust distributed learning algorithm with optimal optimization error under LDP."

That said, we would like to emphasize why our findings remain relevant to a broad and foundational class of methods:

  • To the best of our knowledge, Safe-D(S)GD is the only family of algorithms proposed in the literature that simultaneously provides provable Byzantine resilience and LDP for first-order iterative learning algorithms. Virtually all such methods rely on robust gradient aggregation, for which (f,κ)(f,\kappa)-robustness provides a unifying abstraction covering a large class of aggregation rules. Similarly, adding Gaussian noise to gradients is the predominant way of achieving DP in SGD-style algorithms. Thus, Safe-D(S)GD captures a broad class and representative class of methods combining these two principles.
  • Importantly, our upper bound applies to the entire class of (f,κ)(f, \kappa)-robust aggregation rules. It matches, in order, our lower bound, which is established for SMEA, an (f,κ)(f, \kappa)-robust rule with κ∈O(f/n)\kappa \in \mathcal{O}(f/n). Consequently, our results establish a fundamental instability bound for the entire class of (f,κ)(f, \kappa)-robust aggregation rules: this bound cannot be further improved without imposing additional assumptions on the aggregation rule beyond (f,κ)(f, \kappa)-robustness. Furthermore, our additional numerical experiments in Appendix D.1 demonstrate that the non-monotonic behavior also occurs with another aggregation rule, namely Component-Wise Trimmed Mean aggregation (CWTM).
  • The underlying lower-bound construction and our MIA framework are also quite general (in particular, the MIA step (Lemma A.1) stems almost directly from the definition of LDP itself). While the exact derivation is technically involved, and requires careful handling of concentration inequalities, it can be extended to other privacy mechanisms than the Gaussian mechanism and other aggregation rules than SMEA. We feel that incorporating this additional layer of generality, while interesting, would add technical overhead without changing the core takeaway of our findings in the current manuscript.

We would like to thank the reviewer once again for their review and for engaging with our work. We hope these clarifications better convey both the scope and the broader significance of our theoretical results.

Thank you for the further clarification and for revising the abstract to make the scope explicit. In light of the authors' clarifications, I will increase my soundness score to 3.

My remaining concern is primarily about the significance of the contribution. The statement that Safe-D(S)GD is the only known algorithm family providing both provable guarantees offers a reasonable justification for choosing this framework. However, its uniqueness within the specified setting does not, by itself, establish the broader importance of that setting or the foundational significance of the resulting characterization. In particular, being the only available approach does not necessarily make it a broadly influential one.

While the response helps clarify the scope and strengthens the evidence within the studied framework, I remain unconvinced that the significance of the resulting insights is sufficient to support acceptance at ICLR. I therefore respectfully maintain my overall score.

Comments on the paper

1 comment

We thank the reviewers for their feedback and valuable suggestions. We have incorporated the suggested changes throughout the manuscript, and all revised passages are marked in orange font for ease of tracking (main text; Appendix A; Appendix D.1).

In summary we:

  • Added the Li et al. reference and discussed it in the introduction (Reviewer 4uPv, Q1);
  • Corrected a typo that led Reviewer MS8a (Q1) to question the assumptions of Theorem 3.1 (specifically, the condition is f/(n−f)<1f/(n-f) <1, equivalent to f<n/2f < n/2, and not 1/21/2);
  • Clarified Lemma A.1 to directly address Reviewer DXBe (Q2);
  • Added a footnote clarifying that a stability floor indeed exists when σDP\sigma_{DP} as established in the main text and Theorems, which was previously ambiguous in Corollary 3.2.1 (Reviewer DXBe, Q3);
  • Agreed with Reviewer DXBe (Q4) that investigating whether this behavior generalizes to other attacks and aggregation rules would be valuable; accordingly, we added new experiments in Appendix D.1 evaluating an additional attack and another aggregation rule to strengthen our numerical analysis.

Below, we provide a point-by-point response to each comment.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.