Mitigating the Privacy–Utility Trade-off in Decentralized Federated Learning via f-Differential Privacy

We sincerely thank the reviewer for their comments. Below, we address the two main concerns regarding related work and experimental evaluation.

1. Related Work and Comparison with Local DP

We appreciate the reviewer’s suggestion to clarify the relationship between our work and existing DP frameworks in FL. While Section 1.1 outlines the landscape of DP approaches, we would like to emphasize that our work is primarily theoretical, aiming to improve privacy accounting via f-DP in decentralized learning. This requires us to capture privacy amplification under communication sparsity, local iterations, and correlated noise—key phenomena in such settings.

To provide additional clarity, we will append the following paragraph to the end of the "DP notions in FL" paragraph in the related work section:

However, the strong observability assumption in Local DP often necessitates large noise, leading to degraded utility in practice. In contrast, our PN-f-DP framework models privacy leakage on a pairwise basis, assuming only partial observability during peer-to-peer communication. This allows for significantly tighter privacy bounds under realistic network conditions. Likewise, our Sec-f-LDP framework incorporates correlated noise via shared secrets, enabling privacy amplification in structured collusion scenarios—an aspect not addressed by standard Local DP.

2. Experimental Evaluation and Baseline Scope

The goal of our experiments is to empirically validate the benefits of our new privacy accounting frameworks, not to benchmark full FL pipelines. Since our main contribution lies in theoretical improvements to privacy account, the experiments are designed to isolate the effect of replacing RDP with f-DP while keeping all other variables fixed.

To this end, we closely follow the setups of prior work—particularly PN-RDP in [Cyffers et al., ICML 2024] and correlated-noise protocols in [Triastcyn et al., NeurIPS 2020]—using the same random-walk communication protocols, graph topologies, noise injection strategies, and datasets. This ensures a fair and focused comparison, isolating the effect of improved privacy accounting. Across all settings, our results consistently show that the proposed f-DP accounting yields tighter $(\varepsilon, \delta)$ bounds and better utility under the same noise, validating the benefit of our theoretical framework.

We believe that expanding to more algorithmic methods, while valuable in broader empirical studies, is not necessary to validate the core theoretical message of our paper. Our current experiments sufficiently demonstrate that more refined accounting—enabled by f-DP—can meaningfully enhance the privacy–utility trade-off in decentralized FL.

Thanks for solving my concerns. I have updated the rating as in final justification.

We sincerely thank the reviewer for their thoughtful and encouraging comments. Below, we address the open questions and clarify some points raised.

W1. On originality and integration of prior work

While our work builds on existing decentralized DP mechanisms (e.g., PN-RDP and DecoR), our contribution goes beyond a straightforward adaptation. We introduce a novel integration of f-DP with random-walk–based communication, Markovian hitting-time–based amplification, and correlated noise via secret sharing—each requiring non-trivial technical innovations. A key example is our use of weighted mixtures of trade-off functions (Lemma 4.2), where the weights $w_{ij}^t$—analytically derived from Markov hitting times—reflect the communication frequency between nodes. This leads to a more precise and principled approach to privacy composition, yielding a tighter and more flexible accounting framework than prior work.

W2. On generality beyond Gaussian DP

We agree that most of our empirical evaluations use the Gaussian f-DP formulation. However, our framework is fully general within the f-DP class: the core result in Lemma 4.2 applies to any valid trade-off function, not just the Gaussian one. Theorem 4.5 holds for general f-DP mechanisms as long as the pairwise trade-off functions are valid and can be mixed.

Our use of the Gaussian trade-off function is primarily motivated by its simplicity, interpretability (via $(\varepsilon, \delta)$-DP conversion), and the asymptotic justification via the Central Limit Theorem (CLT). When noise is injected across many steps (as in iterative algorithms), the cumulative distribution often approaches Gaussian. This justifies using Gaussian f-DP as a practical approximation. For formal results supporting this approximation under composition, we refer to “A Central Limit Theorem for Differentially Private Query Answering” (Dung et al., 2021).

Q1. On tightness and potential improvements

Our accounting framework provides substantially tighter bounds than RDP-based methods (see Figure 2 and Figure 5), and already uses concentration inequalities and stopping-time arguments to capture amplification effects from random walks. While we believe our bounds are close to tight under current assumptions, proving information-theoretic lower bounds remains an open problem in decentralized settings. Future work may explore impossibility results or optimality gaps under specific communication or adversary models.

Q2. On computational cost

Computing our privacy guarantees is efficient and scalable. As noted in lines 846–848 of the appendix, all experiments were completed within 1–4 hours on standard hardware.

The most expensive step is determining the noise variance required to meet a given $(\varepsilon, \delta)$-DP target, which involves solving a scalar root-finding problem over the trade-off function (e.g., using binary search). Once the noise variance is fixed, evaluating the privacy guarantee is computationally lightweight, involving only basic operations on cumulative trade-off functions and mixing weights.

Q3. On extension to time-evolving topologies

Yes, our method naturally extends to dynamic or time-evolving graphs. The only modification needed is to update the transition matrices $W^t$ at each round. As long as these matrices are known or estimable, our framework applies directly using updated weight sequences $w_{ij}^t$ in Lemma 4.2. This makes our method particularly flexible for real-world decentralized systems where communication patterns may shift over time.

Minor comments

We appreciate the reviewer’s attention to detail and will correct the typos mentioned (missing indices in the DecoR algorithm block, ambiguity in "two datasets," and the unclear reference in line 244).

We sincerely thank the reviewer for their detailed evaluation and feedback. The following are our responses to the weaknesses and questions.

W1. On the use of the additional $\delta_{T,n}'$ term in Theorem 4.5:

1. Purpose of the term: We introduce the small slack term $\delta_{T,n}'$ to account for the uncertainty in the number of times a given user $j$ is visited during training. Specifically, with probability at least $1 - \delta_{T,n}'$, user $j$ is visited no more than $\left\lceil (1 + \zeta) T / n \right\rceil$ times, where

This bound enables us to derive a clean expression for the composed trade-off function in Theorem 4.5:

If the exact number of visits $N$ were known, we would use the more accurate bound $\left( f_{ij}^{\mathrm{single}} \right)^N$. Hence, this slack does not significantly affect our results—it simply reflects uncertainty due to using concentration bounds instead of exact visit counts.

2. Precedent in prior work: This type of slack is common in the literature. For example, in Differentially Private Decentralized Learning with Random Walks (Cyffers et al., ICML 2024), the authors aim to bound $N_u$—the number of times a user $u$ is visited—using concentration inequalities (see Appendix, second paragraph, Page 3: link). They suggest applying Theorem 12.21 from Levin & Peres (2017) to upper bound the number of visits with high probability (note that this makes the slack term polynomially decay in the iteration number $T$), and propose incorporating the small probability of exceeding that bound into the final $\delta$ when converting from RDP to $(\varepsilon, \delta)$-DP.

   A similar reasoning applies here. However, our bound is even stronger: by applying a sharper Markov chain concentration inequality [21] (Fan et al., 2021), we obtain a slack term $\delta_{T,n}'$ that decays exponentially faster in $T$ with improved dependence on the spectral gap. If their method were adapted to use our concentration bound, it would naturally include the same (but smaller) $\delta_{T,n}'$ term.

3. Truncation trick in practice: Following Cyffers et al. (2024, Remark 5), we also adopt a standard implementation trick: once a node reaches its maximum allowed number of contributions, it stops participating in updates and only adds noise if visited again. This ensures that the number of compositions per user never exceeds the analytical bound. In particular, when a cryptographically small $\delta$ requires a very large upper bound on the number of contributions, this mechanism limits the actual number of communications while still adding noise solely to preserve privacy. We apply this approach consistently in all experiments with PN-RDP (largely because our experiments are based on their codes). We will make this point more explicit in the final version.

4. Why our improvements are not due to $\delta_{T,n}'$: We stress that this small slack term is not the cause of our improved privacy-utility trade-off. Our contributions rely on two key innovations:

   • Refined weight computation using hitting times: Instead of using weights $W^t$ as in prior PN-RDP, we analytically compute a finer weight $w_{ij}^t$ by using hitting times. We argue that this alone improves a lot. As shown in Figure 1, even under RDP, using hitting-time–based weights alone yields significant improvements (orange vs. blue curves). This pattern holds across multiple datasets (e.g., Figure 2).

   • Lossless composition via f-DP: We leverage the f-DP framework to track the privacy loss as a mixture of trade-off functions (via Lemma 4.2), composed exactly in Theorem 4.5. Unlike RDP, which often overestimates cumulative privacy loss, f-DP enables tighter, lossless composition—especially important in iterative settings like DP-SGD. These benefits are evident in Figure 3. We also integrate other privacy amplification effects into the f-DP framework to further improve the accounting.

In summary: We argue that the comparison with PN-RDP is fair and consistent—both works incorporate a similar $\delta_{T,n}'$ slack and use the same practical trick to enforce the visit bound. Our improvements stem not from this slack, but from the tighter privacy accounting introduced by hitting-time-based weighting and the use of f-DP composition. We think the above responses also answer your Q1-Q3.

W2. Clarifying the Gaussian assumption in Theorem 4.7

We appreciate the reviewer’s request for clarification. Theorem 4.7 begins with the assumption that each round of the algorithm satisfies $f$-DP between two Gaussian distributions. This is justified by the structure of the Sec-f-LDP mechanism defined in Algorithm 2, where the injected noise terms $Z_{ij,t}$ and $Z_{ji,t}$ are sampled from Gaussian distributions.

As a result, the output at each iteration is a Gaussian distribution due to the linearity of gradient updates and the additive Gaussian noise. This setup is consistent with prior analyses—e.g., Allouah et al. (2024) adopt the same assumption in their RDP-based analysis of SecDP.

Moreover, as composition over $T$ iterations of Gaussian mechanisms preserves Gaussianity, the cumulative distribution of the model parameter also remains Gaussian. Hence, we can represent the final output distribution as $N(0, I)$ versus $N(\mu, \Sigma)$ and analyze the corresponding trade-off function. The choice of $N(0, I)$ is without loss of generality due to the invariance of trade-off functions under affine transformations.

We will make this justification more explicit in the revised version of the paper to improve clarity for readers less familiar with SecDP. We hope this response also answers your Q4

W3. On the tightness of using joint concavity for mixtures

We thank the reviewer for raising this subtle but important point. The joint concavity bound on the trade-off function is widely used in $f$-DP literature, and [54] provides necessary and sufficient conditions under which this bound is tight. In general, the tightness depends on the behavior of the likelihood ratio of the mixture, which in our case is determined by a complex, data-dependent walk over the graph topology.

While we acknowledge the possibility of slack in this bound, analyzing the likelihood ratio in our setting (especially with random walk–based mixing and complex noise correlation) is significantly more involved than in standard cases like subsampling. Preliminary experiments on small graphs suggest that tighter bounds may be possible, but a general and principled derivation remains an open technical challenge.

As is common in prior work (e.g., [2], [14]), we do not include lower bounds for the trade-off function in this work. We consider this an important direction for future research and will mention it in the revised discussion section.

W4. Clarification on Definition 3.4 and honest-but-curious collusion

We acknowledge that our exposition of Definition 3.4 could be clearer for readers unfamiliar with Allouah et al. (2023). In our setting, “honest-but-curious collusion at level $q$” refers to a scenario in which the adversary has access to all data and secrets except for those of $q$ users. This aligns with the adversarial model used in previous work and is a common assumption in secret-sharing–based privacy mechanisms.

Due to space constraints, we omitted a full formal treatment of SecDP in the current version. In the revision, we will include a dedicated appendix section that formally introduces the Sec-f-LDP framework, clarifies the role of “secrets,” and outlines the adversarial model explicitly.

W5. Why $f$-DP is used

We chose $f$-DP because it offers two distinct advantages:

• Lossless composition: Unlike RDP or $(\varepsilon, \delta)$-DP, $f$-DP supports exact (tight) composition of trade-off functions, which is particularly important in iterative algorithms like DP-SGD.
• Flexible integration of amplification techniques: Our use of $f$-DP allows for seamless incorporation of privacy amplification effects (e.g., from stochasticity, graph structure, or secret sharing) into the final accounting. This is especially relevant when combining multiple sources of amplification, as we do in this paper.

We convert our results to $(\varepsilon, \delta)$-DP for comparison with existing benchmarks and additionally, $f$-DP can be more interpretable for policy discussions, as noted by (https://arxiv.org/abs/2503.10945).

Thank you for your thoughtful follow-up and for raising your score to 'accept'.

We truly appreciate your careful review and constructive feedback throughout the process

We sincerely thank the reviewer for their evaluation and feedback. The following are our responses to the questions.

Q1 & W1. Extension to other decentralized FL algorithms (asynchronous, gossip-based, push-sum):

Yes, the PN-f-DP and Sec-f-LDP frameworks can be extended to other decentralized FL protocols. Our key innovation lies in using the f-DP framework to improve composition analysis and obtain tighter $(\epsilon, \delta)$ bounds compared to RDP. Since f-DP admits lossless conversions to $(\epsilon, \delta)$-DP and composes more accurately for iterative algorithms like SGD (see Dong et al., 2022 [16] for the equivalence), it provides a powerful foundation that is agnostic to the specific communication pattern.

While our current analysis focuses on random-walk-based communication, the core reasoning can generalize. For instance:

• In gossip-based protocols, users randomly select a neighbor at each round to exchange updates with. This creates multiple independent communication threads, each resembling a localized random walk starting from different nodes. In this setting, the per-step mechanism $A^t_j(D)$ in Lemma 4.2 can be interpreted as the composition of local updates followed by a randomized transmission. The resulting distribution observed by user $j$ becomes a mixture over possible communication paths. By conditioning on which thread delivers the update to $j$, we can decompose the overall trade-off function as a weighted combination of trade-off functions along each path—similar to our current use of hitting time distributions. The mixture structure and convexity of trade-off functions ensure the lemma still applies.

• In asynchronous FL, users perform updates and communicate at different times, potentially with delays. However, if we re-index the process by iteration number (i.e., treat each update as happening at some logical step $t$ rather than wall-clock time), then the sequence of updates and communications becomes a stochastic schedule over nodes. This view restores a consistent structure akin to synchronous random-walk protocols. As long as we track when each user observes the updated model and define the effective transition probabilities accordingly, the f-DP analysis—including mixture modeling and composition via Lemma 4.2—remains valid.

• Finally, push-sum protocols often use a communication matrix with stochastic weights, where nodes push weighted model updates to neighbors and update their states by aggregating received values. In certain variants, especially those using time-varying or randomized stochastic matrices, the resulting flow of information can again be modeled as a Markov process over nodes. When such randomization exists, the probability that user $j$ receives an update originally influenced by user $i$ within $t$ steps can be interpreted as a generalization of the hitting time probability $w^t_{ij}$, allowing us to adapt our PN-f-DP analysis by redefining these weights accordingly.

Thus, while each new protocol requires re-deriving the mixture weights and update structure, the f-DP accounting framework remains applicable and advantageous.

Q2. Impact of non-uniform user participation:

Our random-walk-based protocol naturally involves highly non-uniform participation, since at each step only a single user is active. Despite this, our f-DP analysis remains valid and effective, as shown in both theory and experiments. More broadly, participation patterns affect convergence rates and utility, but privacy accounting depends on how information flows through the algorithm, not on uniformity per se.

That said, if participation probabilities are known and explicitly modeled, they could be incorporated into the weight computation (e.g., adjusting the hitting time distribution or the stationary distribution of the Markov chain). This may even lead to further privacy amplification if users are active less frequently.

Q3. On the tightness of Markov hitting-time–based amplification:

We appreciate the reviewer’s question on the information-theoretic tightness of our amplification bounds. Our analysis already incorporates martingale arguments and stopping time techniques, as detailed in Lines 267–270 and Appendix D, to sharpen the privacy guarantees. In particular, we apply a Hoeffding-type inequality for Markov chains (Fan et al., 2021 [21]) to tightly bound the number of visits to each node.

While our results empirically outperform existing RDP-based bounds (including those using hitting-time approximations), we agree that the question of information-theoretic optimality—whether these are the best possible bounds in principle—remains open. One potential direction for future work is to explore lower bounds via converse results or explore alternative probabilistic tools like Doob’s optional stopping theorem or maximal inequalities for stopped processes.

W2. Limitations of the collusion model in Sec-f-LDP:

We agree with the reviewer that our current Sec-f-LDP analysis focuses on honest-but-curious adversaries who follow the protocol but may attempt to infer additional information. This choice is motivated by its practical relevance in decentralized systems with partial trust—such as device-level trusted groups or enterprise coalitions—where protocol adherence is enforced (e.g., via secure hardware or contractual agreements), but privacy concerns remain.

Addressing stronger adversaries (e.g., rational or malicious agents who deviate from the protocol) requires a fundamentally different framework, potentially integrating cryptographic primitives, game-theoretic modeling, or Byzantine-robust learning techniques. While such extensions are outside the scope of this paper, we view it as an important direction for future work, particularly for applications where secure multi-party computation or mechanism design can complement differential privacy.

W3. Assumptions on the communication graph (irreducibility and aperiodicity):

This is a great point, and we clarify that these assumptions—irreducibility and aperiodicity—are technical conditions required to apply Markov concentration inequalities for bounding the number of visits (Theorem 4.5). In practice, these conditions hold for a wide class of graphs used in decentralized FL, including expander graphs, small-world networks, and any connected graph with mild self-looping.

Nevertheless, we acknowledge that in very sparse or poorly connected graphs, convergence of the random walk may be slow or non-uniform, leading to weaker privacy amplification. In such cases, our analysis still applies but may yield looser bounds. One possible remedy is to introduce virtual self-loops (as done in lazy random walks) or to modify the transition matrix slightly to guarantee ergodicity without fundamentally changing the protocol. We plan to explore this robustness more formally in future work, especially for real-world FL networks with uneven connectivity.

We sincerely thank the reviewer for their evaluation and feedback. The following are our responses to the questions.

W1: Omission of related work on Network Shuffling (SIGMOD 2022)

We thank the reviewer for highlighting the relevant work on Network Shuffling ([A]), which we will cite and discuss appropriately in the revised version.

While [A] analyzes privacy amplification via random walks under the Local DP model, our work focuses on two important relaxations—Pairwise Network DP (PN-DP) and Secret-based DP (SecDP)—that are more tailored to decentralized federated learning (FL) scenarios. Local DP assumes that all user outputs are fully observable by an adversary, which leads to high noise and degraded utility. In contrast, PN-DP and SecDP model partial observability and structured trust (e.g., through shared secrets), allowing for tighter privacy–utility trade-offs in practical FL deployments.

We would also like to emphasize that our f-DP framework can accommodate the network shuffling setting studied in [A]. Building on the analysis in [54], one can show that if each user’s local report satisfies $\epsilon_0$-DP, then after shuffling, the overall mechanism satisfies $f_{\mathrm{shuffle}}^{\otimes N}$-DP, where $f_{\mathrm{shuffle}}$ is a trade-off function derived from [54, Theorem 4.2], and $N = \max_i N_i$ is the maximum number of reports held by each user after the random walk. This bound can be computed via the random walk transition matrix, as done in [A, Lemma 5.1].

Our framework provides stronger privacy accounting than [A] in two key ways:

• We adopt the state-of-the-art shuffle analysis from [54], which is strictly tighter than the bound used in [A] (based on Cheu et al.).
• Our use of $f$-DP yields exact and lossless composition via trade-off functions, avoiding the looseness inherent in the advanced composition theorems required for $(\epsilon, \delta)$-DP as used in [A].

In summary, while our work addresses different privacy models, it subsumes the network shuffling analysis as a special case and offers a tighter, more generalizable framework for privacy amplification in decentralized settings. We will include a discussion highlighting these conceptual and technical differences in the related work section.

W2: Limited experimental evaluation on small/synthetic graphs

Our work is primarily theoretical, with the main goal of introducing a general and tighter priva accounting framework for decentralized learning. The experimental evaluation is designed to:

• Validate the theoretical privacy bounds under various conditions (graph types, noise levels, user settings),
• Follow and align with prior setups—especially PN-RDP [Cyffers et al., ICML 2024] and DecoR [Zhu et al., 2023]—to ensure fair comparisons.

We agree that evaluating on larger, real-world graphs is valuable and will consider this for future work. However, we believe the current experiments are sufficient to demonstrate the theoretical improvements and practical gains of our accounting method over existing baselines.

W3: Inappropriate choice of $\delta$ parameter

We respectfully clarify that our choice of $\delta = 10^{-5}$ is consistent with standard DP practice, which typically requires $\delta$ to be less than the inverse of the total number of data points—not the number of users. For instance, in the MNIST setting, there are 70,000 data points, and our choice of $\delta$ satisfies $\delta$ < 1/70,000. This convention is widely adopted in prior works (e.g., [Cyffers et al., Zhu et al.]), and we will make this clarification more explicit in the final version to avoid confusion between device count and sample size.

W4: Applicability to real-world cross-device FL with millions of users

We agree that scalability to large-scale FL is an important concern. While our experiments focus on moderate-scale synthetic and benchmark datasets, this is standard in many academic studies, especially those introducing new privacy analysis frameworks. Our theoretical results—including Lemma 4.2 and Theorem 4.5—scale naturally to larger networks, since the framework is compositional and does not impose assumptions specific to small graphs.

Moreover, our analysis is independent of specific model architectures or optimizers, and applies to general decentralized SGD-style methods as long as the communication and noise injection mechanisms are well and similarly defined. While we focus on moderate-scale settings in this paper, the theoretical framework is general and may inform future applications in larger-scale FL deployments.