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

AI summary

Overview

• Research area: Privacy-preserving machine learning — specifically privacy accounting for differentially private decentralized federated learning.
• Technical level: Advanced. The paper assumes familiarity with differential privacy, Rényi divergence, hypothesis-testing interpretations of privacy, Markov chains, and stochastic optimization.
• Scope: The paper introduces two $f$-differential privacy accounting frameworks for decentralized federated learning (pairwise network communication and shared-secret correlated noise) and shows they give tighter $(\epsilon,\delta)$ bounds than Rényi DP-based methods, with better utility at a fixed privacy level.

What This Paper Is About

Decentralized federated learning lets users train a shared model by passing updates along a communication graph instead of through a central server, but quantifying exactly how much privacy each user gets is hard because updates are spread over random walks, repeated local steps, and potentially correlated noise. The paper's goal is to build a finer-grained privacy accounting framework for two decentralized algorithms — decentralized DP-SGD with random-walk communication and DecoR-style DP-SGD with correlated noise — so that practitioners can add less noise for the same privacy guarantee. It does this by replacing the commonly used Rényi DP or $(\epsilon,\delta)$-DP analyses with $f$-DP, which is described as lossless thanks to its hypothesis-testing interpretation.

Key Contributions

1. Two new $f$-DP notions for decentralized FL. Pairwise Network $f$-DP (PN-$f$-DP), which quantifies privacy leakage between specific user pairs under random-walk communication and supports both user-level (Theorem 4.1) and record-level (Theorem E.1) guarantees; and Secret-based $f$-Local DP (Sec-$f$-LDP), which extends $f$-DP to settings with correlated noise injected via shared secrets, as in DecoR-style algorithms (Theorem 4.2).
2. Refined privacy guarantees for two concrete algorithms. The paper analyzes (i) decentralized DP-SGD where updates propagate by a random walk (Algorithm 1), generalizing prior work that only handled $K=1$ local step to the case $K \geq 1$; and (ii) DP-SGD with correlated noise (Algorithm 2, DecoR), where user pairs add structured noise through shared secrets.
3. A random-walk analysis that captures three amplification sources. For Algorithm 1, the PN-$f$-DP analysis accounts for communication sparsity, local iteration updates, and Markov hitting times, using joint concavity of trade-off functions plus Markov chain concentration. The paper states that the hitting-time-based weighting is a departure from prior work that used matrix entries $(W^t)_{ij}$, and that this shift produces tighter bounds.
4. Demonstrated tighter bounds and better utility. The abstract reports that experiments on synthetic and real datasets show consistently tighter $(\epsilon,\delta)$ bounds and improved utility relative to Rényi DP-based approaches, indicating that less noise is needed for a given privacy level.

Main Findings

• Hitting times give tighter accounting than matrix powers. The paper defines the weight $w_{ij}^t$ as $\mathbb{P}[\tau_{ij} = t]$, the probability that user $j$ first observes the model at step $t$, rather than as the $(i,j)$ entry of $W^t$. The authors report that converting their $f$-DP guarantees back into RDP yields improved bounds, attributed primarily to this more accurate modeling of communication timing.
• Mixture privacy loss is bounded by a convex combination of per-step trade-offs. Lemma 4.1 shows that the trade-off function of the first-observed snapshot $\mathcal{A}j^{\mathrm{single}}$ is lower bounded by a weighted combination of per-visit trade-offs $f{ij}^t$ with the hitting-time weights, plus a term $w_{ij}^{T+1}(1-\alpha_{T+1}(s))$ for the possibility that the model never reaches $j$ within $T$ steps.
• Per-visit privacy depends on convexity. For $m$-strongly convex, $M$-smooth losses with $c = \max{|1-\eta m|, |1-\eta M|}$, Lemma 4.2 gives $f_{ij}^t \geq G_{\mu_t}$ with $\mu_t = \sqrt{c^{2K(t-1)} \cdot \frac{1+c}{1-c} \cdot \frac{(1-c^K)^2}{1-c^{2Kt}}} \frac{\Delta}{\sigma}$ for $0<c<1$, and $\mu_t = \frac{\sqrt{K}\Delta}{\sigma\sqrt{tK+1}}$ when $c=1$. For non-convex losses, Lemma 4.3 gives the looser $f_{ij}^t \geq G_{\sqrt{K}\Delta/(\sqrt{tK+1}\sigma)}$.
• Visit counts are controlled by a Markov chain concentration inequality. With probability at least $1-\delta'{T,n}$, user $j$ is visited no more than $\lceil (1+\zeta)T/n \rceil$ times, where $\delta'{T,n} = \exp\left(-\frac{1-\lambda_2}{1+\lambda_2}\cdot 2\zeta^2 T/n^2\right)$ and $\lambda_2$ is the second-largest eigenvalue of the transition matrix. The final user-level guarantee is $(f_{ij}^{\mathrm{single}})^{\bigotimes \lceil (1+\zeta)T/n \rceil}$ (Theorem 4.1), under irreducibility, aperiodicity, and symmetry of $W$.
• Record-level privacy adds subsampling amplification. Lemma 4.4 replaces each $f_{ij}^t$ with $\widetilde{f}{ij}^t$, using a sum-sampling operator $C_p$; for strongly convex losses the bound is $G\left(\frac{2\sqrt{2}c^{(t-1)K}b_K}{\eta\sigma}\right) \otimes \left[\bigotimes{k=1}^{K} C_{b/m_i}\left(G\left(\frac{2a_k}{\eta\sigma}\right)\right)\right]$ for $t>1$, where $m_i$ is user $i$'s sample size and the sequences ${b_k, a_k}$ follow stated recursions with $b_0 = 0$ and $0 < \gamma_k < 1$.
• Record-level PN-$f$-DP is a relaxation of weak federated $f$-DP. Remark 3.1 states that satisfying record-level PN-$f$-DP implies weak federated $\widetilde{f}$-DP with $\widetilde{f} = (\min_{i,j} f_{ij})$ passed through the double convex conjugate operator.
• Secret sharing sharpens local guarantees under limited collusion. Definition 3.3 formalizes Sec-$f$-LDP as a hypothesis test where the secret set $\mathcal{S}_{\mathcal{I}}$ is hidden; the special case $f = T(\mathcal{N}(0,1), \mathcal{N}(\mu,1))$ defines Sec-$\mu$-GLDP. The analysis of Algorithm 2 models honest-but-curious collusion at level $q$, where up to $q$ users pool information including their shared secrets.
• Not reported in the provided content: the names and sizes of the real and synthetic datasets, the specific $(\epsilon,\delta)$ values, model architectures, and utility metrics from the experiments. The truncated text only reports qualitatively that the bounds are consistently tighter than Rényi DP-based approaches and that utility improves.

Methodology in Plain English

The paper reframes the privacy question as a hypothesis-testing problem. Instead of asking "what is $\epsilon$?", it asks "given the outputs of two runs on datasets differing in one user's data, how well can any adversary tell them apart?" The answer is summarized by a trade-off function $f$ that describes the best possible balance between false positives and false negatives. This $f$-DP lens is called lossless because it retains the full trade-off curve rather than collapsing it into a single number.

To handle random-walk communication, the authors decompose the analysis into two stages. First, they consider the moment when a particular user $j$ sees the model for the very first time, and express that observation as a mixture over all possible first-arrival times, weighted by hitting-time probabilities. Joint concavity of trade-off functions lets them lower-bound the mixture's trade-off function by a weighted combination of the individual per-visit trade-offs. Each per-visit trade-off is itself derived by composing the noise injections from the $K$ local steps, using privacy amplification by iteration when losses are strongly convex and plain composition otherwise. Second, they bound how many times the walk returns to user $j$ over $T$ rounds, using a Hoeffding-style concentration inequality for Markov chains; composing the per-visit bound that many times yields the final guarantee.

For correlated noise, they generalize the same hypothesis-testing machinery to a setting where neighboring users share secret randomness and inject noise that cancels across the pair, while still adding independent noise to protect the gossip average. This lets them account for partial trust and structured collusion rather than assuming an adversary sees everything.

Why This Matters

• Impact on research: The paper shows that $f$-DP, previously applied mostly to centralized or shuffled mechanisms, is a workable and productive framework for decentralized learning. It provides a template for converting random-walk, hitting-time, and iteration effects into composable trade-off functions, and it establishes that the choice of DP notion itself, not just the noise level, controls how tight the accounting can be.
• Real-world applications:
  • Edge computing deployments where devices train collaboratively without a reliable or trusted server.
  • Peer-to-peer learning networks where communication is costly and only sparse device-to-device contact occurs.
  • Settings with partial trust, such as user pairs who already share secrets and can coordinate noise injection.
  • Deployments that need record-level rather than user-level guarantees, since the paper provides both granularities.
• Industry relevance: Tighter accounting translates directly into less noise for the same privacy budget, which means better model accuracy at the same stated privacy guarantee. For operators of federated systems — mobile keyboards, sensor fleets, distributed analytics platforms — that trade-off between a stated privacy budget and model quality is the central engineering constraint, and shifting the accounting from Rényi DP to $f$-DP is a change at the analysis layer rather than the system layer.

Future Directions

• Extending beyond Gaussian lower bounds. Remark 4.3 notes that Lemma 4.1 holds for any valid trade-off function, and that the paper focuses on Gaussian bounds for simplicity and asymptotic universality. Applying other trade-off function families, where mixture distributions remain efficiently computable, is a natural extension.
• Generalizing the network and communication models. The user-level theorem assumes an irreducible, aperiodic, symmetric transition matrix with a positive spectral gap. Handling directed, time-varying, or non-symmetric graphs, and asynchronous activation patterns, remains open.
• Handling non-convexity more sharply. For non-convex losses the paper falls back on standard composition, which the authors describe as a more conservative bound. Bringing privacy amplification by iteration to non-convex objectives in this decentralized setting is unresolved (the paper notes only a partial extension in Lemma E.2 without iteration-based amplification).
• Broadening the collusion model. The Sec-$f$-LDP analysis treats honest-but-curious collusion at level $q$ with shared secrets. Whether stronger or differently structured adversaries, or secret-sharing schemes with more complex topologies, fit the same framework is an open question.
• Full empirical characterization. The truncated content does not report the experimental setup details; reproducing and extending the reported tighter $(\epsilon,\delta)$ bounds and utility comparisons across more algorithms, graph topologies, and datasets would test how broadly the improvement holds.

Target Audience

Researchers and graduate students working on differential privacy, federated and decentralized optimization, or both; privacy engineers at organizations deploying federated systems who need to justify a privacy budget; and theoretically inclined practitioners who want to understand why the choice of privacy notion — Rényi DP versus $f$-DP — changes how much noise a real system must inject. Readers will need solid background in differential privacy and stochastic optimization, since the paper's results are stated as trade-off function inequalities, tensor products, and Markov chain concentration bounds.

Authors’ abstract

Differentially private (DP) decentralized Federated Learning (FL) allows local users to collaborate without sharing their data with a central server. However, accurately quantifying the privacy budget of private FL algorithms is challenging due to the co-existence of complex algorithmic components such as decentralized communication and local updates. This paper addresses privacy accounting for two decentralized FL algorithms within the $f$-differential privacy ($f$-DP) framework. We develop two new $f$-DP-based accounting methods tailored to decentralized settings: Pairwise Network $f$-DP (PN-$f$-DP), which quantifies privacy leakage between user pairs under random-walk communication, and Secret-based $f$-Local DP (Sec-$f$-LDP), which supports structured noise injection via shared secrets. By combining tools from $f$-DP theory and Markov chain concentration, our accounting framework captures privacy amplification arising from sparse communication, local iterations, and correlated noise. Experiments on synthetic and real datasets demonstrate that our methods yield consistently tighter $(ε,δ)$ bounds and improved utility compared to Rényi DP-based approaches, illustrating the benefits of $f$-DP in decentralized privacy accounting.