Convergent Differential Privacy Analysis for General Federated Learning

We greatly appreciate the positive feedback and for raising a insightful academic question. We have provided a detailed response to this issue below. We have broken down your question into the following sub-questions and will address them one by one.

A1: FL vs PFL.

We thank the reviewer for bringing up this point. While there may be room for academic discussion regarding the categorization of FL methods, we would like to clarify the classification context adopted in our work during the writing process.

FL vs PFL

FL generally focuses on training a global model by:

and PFL generally focuses on training a list of local model by:

where $\phi(\cdot)$ is a reguralization term. Usually, classical terms like $\sum_{i,j} \Vert w_i - w_j \Vert^2$ or $\sum_i \Vert w_i - \overline{w}_i \Vert^2$ are adopted to address the consistency.

What does FedProx do?

FedProx solves the FL optimization problem instead of PFL's. It transfers the general FL problem to a consistency-constrained optimization problem:

Subsequently, this method employs a penalty-based approach (adopting $\Vert w_i - w \Vert^2$ as the penalization of equation $w_i = w$) to alternately optimize the local surrogate function and the consistency constraint:

We agree that FedProx shares similarities with certain personalized PFL methods. However, in our work, we classify FL based on whether the optimization objective is a single global model $w$, which is a strict optimization definition. From this perspective, FedProx remains a standard FL method, as its goal is still to optimize a global model across clients. This definition is also consistent with the original description in the their paper [P1].

[P1] Federated Optimization in Heterogeneous Networks

Why did this paper select noise-FedAvg and noise-FedProx as examples?

We thank the reviewer for raising this question. Our core objective is to address the challenge that interpolation techniques developed for SGD cannot be directly applied to FL, due to the presence of multi-step local training on local clients.To overcome this, we introduce a new technique that performs shifted interpolation at the global level, and proposes a finer-grained sensitivity analysis at the local level by decoupling model and data sensitivity. This enables us to capture the privacy dynamics of FL training more precisely under practical conditions.

We select the FedAvg and FedProx because they represent two main branches from the perspective of FL optimization:

(a) directly solve the primal problem (like FedAvg, SCAFFOLD, FedAdam)

(b) solve the surrogate problem or the primal-dual problem (like FedProx, FedPD, FedDyn, FedADMM)

These two classes of methods are fundamentally disjoint in their analytical frameworks, as they adopt different assumptions and requirements when handling local training procedures. Consequently, their corresponding optimization analyses also differ significantly. The goal of this work is to provide the first convergent privacy analysis for two mainstream optimization paradigms in FL, thereby offering strong theoretical support for understanding and improving its privacy guarantees.

We believe the reviewer's suggestion is highly valuable. A more comprehensive exploration of variance reduction techniques and globally adaptive methods used in FL could indeed deepen our understanding of the evolving privacy capabilities of FL. However, as the first work to provide convergent privacy guarantees for FL, we would like to focus on two foundational algorithms that represent the mainstream optimization paradigms in the field. In our view, if privacy cannot be guaranteed even in these fundamental settings, it would be even more challenging to ensure it in their advanced variants. This is also the main reason why we chose to start from fundamental algorithmic research.

We truly believe that engaging in further discussion with you will help us improve our submission. We are very happy to share more insights and clarifications regarding our work, and would be glad to continue the discussion should you have any further questions.

We sincerely thank the reviewers for their positive feedback and valuable suggestions. In this round of discussion, we will address each of the raised questions in detail.

Q1: Could the proposed analysis be extended to the client sampling setting?

We sincerely thank the reviewer for raising this important question. The core objective of our work is to demonstrate that FL methods can maintain provable privacy guarantees even under long local training and multi-client settings. More importantly, we show that with carefully chosen hyperparameters, FL can naturally provide stronger privacy protection than standard centralized SGD, aligning with the original design philosophy of FL.

It is worth emphasizing that privacy guarantees are even stronger under partial client participation, because when the client containing the neighboring datapoint is not selected in a round, the global sensitivity is solely determined by the amplified model sensitivity, without any contribution from local data sensitivity.

Therefore, it suffices to apply a simple probability-weighted correction to the model sensitivity lemma in order to extend our results to the partial participation setting. This extension is incremental and natural, and we will explicitly include a remark after each main theorem to discuss the implications under partial client participation.

Q2: What are the main challenges when adopting f-DP and shifted interpolation technique to analyze DP-FL?

We appreciate the insightful comment on this matter. We believe that the main challenge lies in the fact that interpolation-based analyses developed for Noisy-SGD cannot be directly applied to local training in FL. Such analysis must simultaneously account for both the number of communication rounds $T$ and the local update interval $K$. In contrast to standard Noisy-SGD, where interpolation can be applied per step, local training in FL requires using a fixed interpolation coefficient at each aggregation step to ensure model correctness. This constraint significantly complicates the process of identifying the worst-case privacy. In fact, our early attempts also indicate that a direct extension of interpolation analysis under this setting is nearly intractable.

To bridge the gap caused by the heterogeneous nature of multi-node local training in FL, we have further developed auxiliary technique that explicitly measure data and model sensitivities during local training (Figure 1 (right) and Section 4.2 of our paper). Additionally, due to the difficulty of solving the minimax problem for the worst-case privacy loss, we propose a relaxation approach (Section 4.3). Together, these contributions the convergent privacy theory to the FL.

Q3: Is there any new insight for analyzing DP-FL?

We thank the reviewer for raising this exploratory question. To the best of our knowledge, our work provides the first convergent privacy analysis under the non-convex FL training paradigm. Furthermore, our results provide two insightful points to help dispel two common misconceptions about privacy in FL:

(a) Privacy loss does can still converge with the number of local invertals, contrary to the common belief that longer local training necessarily leads to weaker privacy.

(b) FL naturally provides stronger privacy guarantees than standard SGD, since SGD corresponds to the special case where the number of $m=1$ and $K=1$. In fact, as the total number of clients increases, the privacy amplification becomes weaker due to the reduced per-client influence.

These two findings clarify that the privacy advantages of FL are not merely due to the absence of direct access to local data, but are instead supported by rigorous theoretical guarantees. Our analysis thus reinforces the original motivation behind FL design, providing a principled foundation for its privacy-preserving properties as it continues to evolve. In addition, we provide a theoretical justification for the privacy benefits of a commonly used proxy regularization term in FL, which further deepens the understanding of privacy dynamics during local model training.

We truly believe that engaging in further discussion with you will help us improve our submission. We are very happy to share more insights and clarifications regarding our work, and would be glad to continue the discussion should you have any further questions.

Thank you for your response. My concerns have been addressed. I suggest that the authors add the discussion about the client sampling setting in the final version. I'll keep my positive rating.

We sincerely appreciate the positive feedback and are also grateful for the valuable suggestions for improvement. These comments are of great significance for further refining our submission. In this rebuttal discussion, we will address the questions one by one.

Q1: How do the contributions of this paper go beyond prior analyses of DP-SGD?

We would like to thank the reviewer for sharing a recent ICLR 2025 work and will cite this work in our submission.

First, we would like to point out that the convergent privacy guarantees established in earlier works for convex and strongly convex functions arise naturally, as their global sensitivity does not diverge. However, this conclusion cannot be directly extended to non-convex functions. Therefore, all the key technical contributions discussed below focus on the non-convex setting.

Challenges in the analysis from SGD to FL

We would like to clarify that the analysis from SGD to the FL setting is not straightforward; the final results cannot be derived merely by simply assembling certain existing lemmas or linearly scaling the local training length $K$. In contrast to standard Noisy-SGD, where interpolation can be applied per step, FL requires using a group of specific interpolation coefficient at each aggregation step. This constraint significantly complicates the process of identifying the worst-case privacy. In fact, our early attempts show that a direct extension of interpolation analysis under the local training setting is nearly intractable.

Existing techniques and our contributions

As noted by the reviewer, the interpolation technique for SGD under the f-DP framework is not our original contribution; we have properly cited the paper in our manuscript. However, this technique cannot be directly applied to the FL setting. To bridge the gap caused by the heterogeneous nature of multi-node local training in FL, we have further developed auxiliary technique that explicitly measure data and model sensitivities during local training (Figure 1 (right) and Section 4.2 of our paper). Additionally, due to the difficulty of solving the minimax problem for the worst-case privacy loss, we propose a relaxation approach (Section 4.3). Together, these contributions the convergent privacy theory to the FL.

Our novel findings

In addition to providing the first convergent privacy guarantee for non-convex FL-DP settings, we also prove that increasing the number of clients also leads to stronger privacy protection, which has not been discussed in previous related work. Moreover, our paper systematically analyzes the impact of local training interval, participating clients, and learning rates. These results challenge some common conclusions in previous works and provide new insights into privacy for FL-DP.

Q2: Could the authors clarify the impact of this relaxation on the final privacy bound?

We sincerely appreciate the reviewer for raising this highly professional academic question. The validity of our relaxation can be supported by comparison with existing studies, particularly the discussion in Bok et al., 2024 regarding DP-SGD. The core difficulty lies in the fact that, when measuring the worst-case privacy loss, the minimization of the privacy w.r.t. both $t_0$ and ${\lambda_t}$ is a NP-hard problem. To achieve effective estimation, Bok et al. directly assume that the diameter of the entire optimization space is $D$. Therefore, the global sensitivity at any $t_0$ is upper bounded by $D$, which is a constant.

In contrast, our proof avoids making such an assumption. We directly evaluate the outcome of the relaxed formulation. Regarding the reviewer's concern about the tightness of our bound, we would like to clarify that when $m=1$ and $K=1$, FL-DP degrades to DP-SGD, and our results is consistent with the bound presented in Bok et al.

Why not assume that the global sensitivity at $t_0$ is a constant?

While this is an optimization trick, this projection is seldom adopted in real-world training. If $t_0$ were an identifiable constant, then this assumption would certainly hold. However, if $t_0$ grows with the total number of steps $T$, the assumption may no longer be valid.

Global sensitivity corresponds to the stability bound in generalization analysis. In the non-convex setting, existing results have not proven that such stability bounds are convergent, and they still diverge as $T$ increases. To avoid introducing additional ambiguity, we chose not to follow the assumption made in Bok et al. (2024). Instead, we directly derive a relaxed upper bound. From our results, this relaxation is effective when $T$ is sufficiently large.

Q3: The experimental results are encouraging, but I have suggestions to bolster them.

We sincerely appreciate the reviewer's suggestions regarding the experiments. Due to the sudden change in the NeurIPS rebuttal policy, we are only able to present our experiments in the form of tables. We acknowledge that tabular presentation may be less intuitive, and we would be more than happy to provide additional detailed explanations if there are any further questions.

More clients

We increase the number of clients to 500 to measure how the sensitivity evolves with respect to time $T$.

It can be observed that the convergence trend aligns with our results.

Results on ViT-Small

We conducted tests on ViT-Small, and the results show a similar trend to ResNet-18, although the sensitivity is higher, the convergence behavior remains largely consistent.

setup: m=50, K=5, V=10, to ensure satisfactory convergence of the ViT-Small model, we increased the number of training steps to $T=1000$

Sensitivity of ResNet-18 converges after approximately 600 steps, while that of ViT-Small converges after 800 steps.

Budget $\epsilon$

We show the theoretical budget $\epsilon$ under the following setup and analyzed its variations under different studies.

Setup: m=50, K=5, V=10, simga=1

Due to the limited time during the NeurIPS rebuttal period, we have only been able to complete the experiments presented above. If the reviewers have further suggestions regarding the experiments, we will add more experiments in the final version.

[P1] Differentially private federated learning with local regularization and sparsification. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 10122-10131, 2022.

[P2] Dp-norm: Differential privacy primal-dual algorithm for decentralized federated learning. IEEE Transactions on Information Forensics and Security, 2024.

Q4: Further analysis and explanation of the key hyperparameters.

We appreciate the reviewer for raising this point. We fully agree that theoretical advancements should aim to provide principled analyses of key hyperparameters. Below, we offer detailed clarifications and additional explanations regarding the specific aspects mentioned by the reviewer.

Proxy coefficient $\alpha$ in Noisy-FedProx

Essentially, this is an optimization problem of identifying the largest possible $\alpha$ that still ensures convergence. In fact, proxy terms like this frequently appear in various FL methods. For models such as ResNet, setting $\alpha=0.1 / 0.05$ often yields good convergence behavior. These values are commonly adopted in related works and have also proven to be optimal ranges based on our extensive experimental experience. When the number of clients $m$ increases, $\alpha$ can be slightly increased, but it generally should not exceed $0.5$. For larger models, this term typically needs to decay to $0.01$ or even smaller (e.g., $0.001$) to maintain effective convergence.

Clipping norm $V$ and local interval $K$ in Noisy-FedAvg

To enhance privacy, the clipping threshold $V$ should ideally be kept small; however, this can significantly constrain the gradient norm. From an optimization perspective, $V$ serves to suppress extreme fluctuations—such as loss spikes caused by bad data that lead to gradient explosions with norms exceeding $100$. The commonly used setting is $V = 10$, but in practice, this value is often reduced as model size increases. For instance, in LLM training, it is now common to set $V = 1$. This trend not only improves training stability but also benefits privacy protection.

The number of local training steps $K$ plays a key role in reducing the frequency of communication rounds and thereby alleviating communication overhead. However, its impact can be counteracted by the choice of local learning rate, as demonstrated in Table 1 in our paper. When an iteratively decaying learning rate is applied, $K$ no longer affects the worst-case privacy guarantees. In fact, within Noisy-FedProx, even a constant learning rate does not compromise worst-case privacy as long as $\alpha$ satisfies certain conditions. Therefore, the choice of $K$ can be fully driven by optimization considerations, provided that an appropriate learning rate schedule is used.

We truly believe that engaging in further discussion with you will help us improve our submission. We are very happy to share more insights and clarifications regarding our work, and would be glad to continue the discussion if you have any further questions.

We sincerely appreciate the reviewer's conscientious efforts and the insightful academic suggestions. We will provide detailed responses to each of the issues raised in the rebuttal discussion.

Q1: How big is the loss when you force $t_0=0$ in the $\lambda_t$ optimization? Does this gap fade as the ratio $T/t_0$ gets large?

We sincerely appreciate the reviewer for raising this highly professional academic question. The validity of our relaxation can be supported by comparison with existing studies, particularly the discussion in Bok et al., 2024 regarding DP-SGD. The core difficulty lies in the fact that, when measuring the worst-case privacy loss, the minimization of the privacy w.r.t. both $t_0$ and ${\lambda_t}$ is a NP-hard problem. To achieve effective estimation, Bok et al. directly assume that the diameter of the entire optimization space is $D$. Therefore, the global sensitivity at any $t_0$ is upper bounded by $D$, which is a constant.

In contrast, our proof avoids making such an assumption. We directly evaluate the outcome of the relaxed formulation. Regarding the reviewer's concern about the tightness of our bound, we would like to clarify that when $m=1$ and $K=1$, FL-DP degrades to DP-SGD, and our results is consistent with the bound presented in Bok et al when $T/t_0\rightarrow\infty$.

Why not assume that the global sensitivity at $t_0$ is a constant?

While this is an optimization trick, this projection is seldom adopted in real-world training. If $t_0$ were an identifiable constant, then this assumption would certainly hold. However, if $t_0$ grows with the total number of steps $T$, the assumption may no longer be valid. Although our proof introduces a relaxation in the upper bound, comparison with their results shows that the complexity of our bound differs from theirs by only a constant factor. As $T/t_0\rightarrow\infty$, this gap vanishes and becomes small enough.

Q2: If each client picks its own $\alpha$, does the nice independent of $K$ privacy result still hold?

We sincerely thank the reviewer for raising this question. When each private client is associated with a different $\alpha_i$, we need to consider two cases. The first case is straightforward, namely, $\min(\alpha_0, \alpha_1, \cdots,\alpha_m) > L$, then, by defining the notation $\alpha=\min(\alpha_0, \alpha_1, \cdots,\alpha_m)$, the results/theorems still hold. A more refined expression for $\alpha_i$ can also be obtained, but this does not affect the main conclusion (it only changes the result by a constant factor).

The other case is relatively more complex, namely when there exists $\alpha_i < L$. We note that the reviewer also mentioned the analysis of $\alpha < L$ in Q5, and the discussion of these two cases overlaps. Therefore, we defer the analysis to our response to Q5.

Q3: Can some comments be given about possibilities in incorporating adaptive per-round clipping into current sensitivity analysis?

We thank the reviewer for the great question! We first provide an intuitive understanding of the gradient clipping parameter $V$. According to its definition, gradient clipping works as $g_{\text{clip}}=\frac{g}{max(1, \Vert g\Vert/V)}$, which makes:

(case 1) if $\Vert g\Vert \leq V$, $g = g$;

(case 2) if $\Vert g\Vert > V, g = V\cdot g/\Vert g\Vert$.

One of its practical roles is to ensure stability during training by preventing sudden large gradients from causing training to crash. Another important role is to bound the maximum update distance per round, thereby providing a stable upper bound for the change in global sensitivity. In current practice, the vast majority of gradient clipping methods use a constant threshold.

In existing theoretical analyses, it is common to use Case 2 as a unified upper bound that covers both Case 1 and Case 2, which implies that the global sensitivity of any single-step update is upper bounded by $O(\eta_t V)$. Therefore, any adaptive change to $V$ can be equivalently represented through a change in the learning rate $\eta_t$.

If, in the future, more refined assumptions on the gradients can be made, such that Case 2 is no longer used as a unified upper bound when measuring global sensitivity, and instead Case 1 is further decomposed with greater precision, then incorporating adaptive $V$ would become highly meaningful.

The above shares our current understanding about this question. As this is still an open problem, we would greatly appreciate any further insights or suggestions from the reviewer in the discussion.

Q4: Can more validation regarding be provided (more different values of $m$). See also the Weakness part.

We sincerely thank the reviewer for raising this question. We have supplemented our experiments with a smaller setting of $m=20$ and a larger setting of $m=500$, and further evaluated the behavior of global sensitivity under $m=500$. Due to the recent change in the NeurIPS rebuttal policy, we presented the results using multi-point sampling in a tabular format instead of figures, which may be less intuitive. We would be happy to further discuss the experimental results if the reviewer has any questions or concerns.

m=20 and 500

We evaluate the different $K$ and $\sigma$ when $m=20$ and $500$.

We increase the number of clients to 500 to measure how the sensitivity changes with respect to time $T$.

It can be observed that the convergence trend aligns with our analysis.

More Results on ViT-Small

We conducted tests on ViT-Small, and the results show a similar trend to ResNet-18, although the sensitivity is higher, the convergence behavior remains largely consistent.

setup: m=50, K=5, V=10, to ensure satisfactory convergence of the ViT-Small model, we increased the number of training steps to $T=1000$

Sensitivity of ResNet-18 converges after approximately 600 steps, while that of ViT-Small converges after 800 steps.

Q5: Can some comments address what would happen if $\alpha < L$ and possibilities to avoid the condition? See also the first point of Weakness.

We thank the reviewer for raising this question. $\alpha > L$ is an ideal condition that enables the Noisy-FedProx method to maintain a convergent worst-case privacy guarantee even under a constant learning rate. When $\alpha < L$, we can ensure the convergence of the privacy upper bound by using an iteratively decaying learning rate, similar to the ID case of Noisy-FedAvg in Table 1.

Our lemma 8 is not affected. We provide the proof of Lemma 9 under a decaying learning rate. For the line 758, Since $\alpha < L$ is negative in this case. For the clarity, we define $\alpha_s = -\alpha_L > 0$. Therefore, we have:

Let $\eta_{k,t}=\frac{\mu}{tK+k+1}$ be the iteratively decaying learning rate, the upper bound of the second term can be derived by referring to the corresponding proof under the same learning rate in Noisy-FedAvg, where this term has been bounded independently of $K$. Here, we provide the proof of the the first term:

Similarly, this term remains independent of $K$. Substituting the full expression of $\eta(K,t)$, we can easily show that the Noisy-FedProx method achieves a convergent privacy that is slightly smaller but of comparable complexity to that of the Noisy-FedAvg method. Of course, the proofs for both methods are essentially very similar in nature.

We summarize the conclusions as follows for Noisy-FedProx.

Then we answer the case of adaptive $\alpha_i<L$ in Q2.

We recommend using iteratively decaying learning rate for training, which can also ensure convergent privacy guarantees.

We would like to emphasize that the condition $\alpha > L$ is an additional property we identified in our analysis, which ensures privacy convergence even under relaxed learning rate schedules. However, this does not imply that privacy convergence strictly depends on this condition. With a decaying learning rate, privacy convergence can always be guaranteed.

Typos

We will correct this in the next version; the value should be $m = 50$. Additionally, we will include experiments for $m = 20$ and $m = 500$.

We truly believe that engaging in further discussion with you will help us improve our submission. We are very happy to share more insights and clarifications regarding our work, and would be glad to continue the discussion should you have any further questions.