Mitigating the Privacy–Utility Trade-off in Decentralized Federated Learning via f-Differential Privacy
Authors: Xiang Li
Chendi Wang
Buxin Su
Qi Long
Weijie J Su
Venue: NeurIPS 2025 spotlight ()
Keywords: f-Differential Privacy
Decentralized FL
Privacy–Utility Trade-off
Random Walks
Correlated noises
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: We develop a fine-grained f-DP analysis for decentralized federated learning, improving privacy–utility trade-offs under random walk communication and extending to settings with dependent noise.

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 $(\epsilon, \delta)$ bounds and improved utility compared to Rényi DP–based approaches, illustrating the benefits of $f$-DP in decentralized privacy accounting.

Mitigating Privacy-Utility Trade-off in Decentralized Federated Learning via J-Differential Privacy
Xiang Li" University of Pennsylvania 1x100770upenn. edu
Buxin Su* University of Pennsylvania subuxin@upenn. edu
Chendi Wang"t
Xiamen University
University of Pennsylvania chendi wang@xmu edu.
Qi Long'
Weijie Su University of Pennsylvania suw@wharton, upenn edu
University Pennsylvania qlong@upenn edu
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 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-S-DP), which quantifies privacy leakage between user pairs under mandmm-wll communication, and Secret-based f-Local DP (Sec-f-LDPP, 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 (c, 5) bounds and improved utility compared Rényi based approaches, illustrating the benefits of f-DP in decentralized privacy accounting.
Introduction
Federated Learning (FL) has emerged powerful paradigm for enabling user devices to collaboratively train models without sharing raw data [88 31). In scenarios
machine learning,
where a central server is unavailable, untrusted, communication is expensive, decentralized FL
becomes a compelling alternative. Algorithms such as decentralized SGD 42 41 offer scalability and low communication overhead, making them well-suited for edge computing and peer-to-peer
applications [52] 69 56
37
59
34
64. 62).
Despite its decentralized nature, FL remains susceptible privacy leakage. Even without access to raw data, model updates can reveal sensitive information 55
67], especially under inference
reconstruction attacks [50 27 Differential Privacy (DP) 19 offers formal and principled
solution by bounding the effect of any individual data on model outputs. widely used approach is differentially private stochastic gradient descent (DP-SGD), which adds noise stochastic gradients to ensure privacy
77. In general, more accurate privacy accounting, i.e., quantifying cumulative
"Equal contribution. "ooresponding authors.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

privacy loss over multiple training rounds, allows for adding less noise to achieve the same privacy guarantee, thereby improving utility. However, in decentralized Beatinggs-heet users communicate parveelyprivvccy over graphs, activate randomly, and share information sparsely privacy accounting remains significant challenge
21].
A key factor influencing the difficulty of privacy accounting is the choice of privacy notion, which governs how adversarial capabilities are modeled and how much noise must be added ensure privacy. Several existing decentralized DP-SGD protocols adopt strong privacy notions such as local differential privacy (Local DP)
33 63 46 which assume adversaries can observe all local updates. While offering strong protection, Local DP requires injecting substantial noise, significantly degrading model performance. To address this limitation, recent work has proposed relaxed notions like Pairwise Network DP (PN-DP) [3] which better capture the partial observability inherent in decentralized systems. In parallel, the Secret-based Local DP (SecL.DP) framework [2 (0) considers scenarios where user pairs conspire and share secrets with their neighbors and coordinate to add correlated noise to their updates, enabling improved aullity-privacy trade-offs under limited collusion.
[22
However, existing analyses of both PN-DP and SecLDP rely on Rényi differential privacy (RDP) [49] or (e, ODP, whose privacy bounds are often especals for iterative algorithms. Given the prevalence of iterative algorithms such as DP-SGD, we ask: Is it possible to develop a fine-grained privacy accounting framework for decentralized FL that consistently improves the privacy-utilig trade-off across different algorithmic designs?
Contribution.
Our answer is affirmative: we show that f-differential privacy (f-DP) 17 provides unified and effective analytical framework for privacy accounting in decentralized FL. We summarize contribution below.
1. New f-DP notions for decentralized FL.. To enable tight privacy accounting, we introduce two f-DP- based notions tailored to decentralized settings: (1) Pairwise Network f-DP (PN-f-DP) extends PN-DP to quantify fine-grained privacy loss between user pairs in random walk communi- cation, supporting both user-level (Theorem 4.1) and record-level (Theorem E.I) guarantees; (2) Secret-based f-Local DP (Sec-f-LDP) generalizes f-DP to regimes with correlated noise and shared secrets, as in StyoR- algorithms (Theorem
Refined privacy guarantees via f-DP. To illustrate, we analyze two representative and practical variants of DP-SGD: (1) Decentralized DP-SGD with random-walk communication (Algorithm [ where updates propagate via a random walk a communication graph [15]; and (2) DP-SGD with correlated noise (Algorithm 2 where user pairs inject structured noise via shared secrets (2). For moudom-walkk communication, we develop a FN-f-DP analysis that captures privacy amplification from: (i) communication sparsity, (ii) local iteration updates, and (ii) Markov hitting times. Our approach leverages the joint concavity of trade-off functions and Markov concentration to yield tighter (c, 5) bounds than RDP. For correlated-noiss methods, we extend f-DP via Sec- f-DDP to account for secret sharing and partial trust, producing sharper bounds under limited collusion.
3. Improved privacy-utility trade-offs. Empirical results on both real and synthetic datasets show that f-DP-basee accounting consistently yields tighter (c, bounds than existing methods, requiring less noise for given privacy level and leading to significantly improved model utility.
1.1 Related works
Local DP assumes all local models are observable by potential attackers 43 45). However, this strong observability assumption often requires injecting substan- tial noise, which severely degrades utility in practice. To mitigate this issue, Pairwise Network DP (PN-DP) was recently proposed [16] 15). PN-DP relaxes the Local DP assumption by modeling only pairwise
DP notions in FL..
22
33
63
can access the local model involved in each decentralized communication round, rather than all local models. The prefix "PN" reflects that data exchange occurs pairwise between connected nodes in a network. This relaxation enables the privacy amplifica- tion by decentralization [14), providing more fine-gratd ane-grai DP guarantees and improving utility in decentralized learning. Building upon this line of work, our PN-f-DP framework extends PN-DP by adopting the f-DP formalism [17, which provides lossless privacy accounting through a hypothesis testing interpretation. Existing PN-DP analyses rely mainly on Rényi DP (PN-RDP) [4), which often yields loose bounds, while f-DP achieves tighter characterization. Furthermore, unlike previous federated fDD formulations [70], our FN-f-DP captures the additional privacy amplification arising

---

from decentralization, random walks, and iterative communication crucial algorimithic components in realistic networked settings.
In some decentralized scenarios, users may further collude and share secrets 54 60
creating
correlations in their local randomness. This behavior is formalized as Secret-based Local DP (SecLDP) by [2), which allows the injection of correlated noise to align the privacy-utility trade-off' with that of central DP. Extending this idea, our Sec-f-LDP framework leverages shared secrets to incorporate correlated noise, thereby achieving additional privacy amplification in structured collusion scenarios an aspect not addressed by standard Local DP.
Privacy amplification in FL. The privacy analysis of decentralized DP-SGD is intricate due to potential privacy amplification from randomized data processing. Privacy amplification refers to techniques that enhance privacy protection by reducing the amount of information an attacker can infer from the output. It can result from both shuffling [3] 24 25
35 61 and decentralization
[6 [5]. Beyond these, the latest privacy analysis of decentralized DP-SGD by [15] incorporates the effects of iterative processes and random walks. In the case of iterative processes, only the final model parameter is revealed, not the intermediate ones, which influences the random noise applied to gradients, leading to privacy amplification by iteration 26 This phenomenon has been further explored in DP-SGD 3 68) and extended into the f-DP framework via shifted interpolated process [8]. The iterative process is closely related to the intermittent communication in FL, where multiple local updates occur between consecutive communication rounds without revealing any information. On the other hand, the privacy impact of random walks has only been studied under RDP [15), and it remains unclear how to capture this effect within the finer f-DP framework.
2 Preliminaries
2.1 Preliminaries on differential privacy
Differential Privacy 19 is formal framework designed to protect individual data records by ensuring that the output of randomized algorithm remains nearly unchanged when single entry in the dataset modified. Formally, let D = {2 } C Z be a dataset of size n drawn from some data domain Z. The classical definition of (c, 5)D is as follows:
Definition 2.1 ()-P). A randomized algorithm A satisfies O)DP if, for all neighboring datasets D and D' differing in most one entry, and for any measurable set S 8, it holds that
P[A(D) S] < eFP(A(D) e +8.
Intuitively, small values of e and 6 imply that the distributions of A(D) and A(D') are nearly indistinguishable. As result, the presence or absence of any individual data point has limited influence on the algorithm's output, thereby preserving privacy. Rényi Differential Privacy (RDP) 49 extends this notion by measuring privacy loss using the Rényi divergence between A(D) and A(D).. This formulation enables more precise privacy accounting under composition, often yielding cleaner and tighter bounds than standard composition results for (e, 6DDD.
Definition 2.2 (Rényi DP (49). A randomized mechanism A satisfies (a, c)-Réyi DP ((a, cD-PDP if, for D and D' that differ in one element, we have R., (A(D)) I c, for all a > 1, where
RR (PllQ) = - log
p(ar) [(x]
q(z)dx is the Rényi divergence between distributions P and Q.
Besides different divergences, the distinguishability between A(D) and A(D") can be measured using the hypothesis testing formulation [66] 32 (58 and is systematically studied as f-DP by [17]. More specifically, consider a hypothesis testing problem Ho : data ~ P versus H : data ~ Q and rejection rule & E [0, 1]. We define the type I error as Ep(Ø), which represents the probability of mistakenly rejecting the null hypothesis Hy- The type Il error, 3g := 1 Eq (6). is the probability of incorrectly accepting the alternative hypothesis H₃. The trade-off function T(P, Q) denotes the minimal type error at level a of type error, expressed as: (a).Q)(a) = inf { as aa).
Definition 2.3 (f-DP and Gaussian DP 17). A mechanism A said to satisfy fDDP if for any datasets D and D' that differ in one element, the inequality (TA(D),A(D)) > holds pointwisely. In particular, A satisfies j-Gaussian DP (μ-GDP) if it G,P with (z) Φ - x) - 1*)
where de denotes the cumulative distribution function (cdf) of the standard normal distribution.
3

---

A mechanism satisfying f-DP is considered more private when its associated trade-off function f larger. In the extreme case where A(D) and A(D)) are indistinguishable. the trade-off function attains its maximum: the identity function Id(x)) = - x. Therefore, any valid trade-off function must satisfy f S Id pointwise. Q(P,Q) = T(Q, P). As shown by [17], any trade-off function can be symmetrized. Throughout this paper, we assume all trade-off functions are symmetric unless stated otherwise. Finally, the composition of DP mechanisms admits natural interpretation in f-DP: it corresponds to the tensor product of trade-off functions (see Def. 2.4).
trade-off function f T(P; Q) is said to be symmetric
Definition 2.4 (Tensor product of trade-off functions 17). For two trade-off functions f= QPP.Q) and f = T(P', Q"), the tensor product between f and f is defined as f & f = T(P x Qx Specifically, the n-fold tensor product of itself is denoted as f@n.
2.2 Pairwise network differential privacy
Communication graph. In decentralized FL, we assume that communications take place through a connected communication graph 9 = (V, E), where V = {1,-.. .n) represents a set of vertices (or nodes). Each node i E V corresponds to local user, and every local user i holds a local dataset D,. Collectively, these datasets are represented as = - Dj. Communication between users is facilitated by edges: if an edge (2, E E exists, users i and j can exchange information. To model these interactions, we introduce a transition matrix W E R=x" which is a Markov matrix satisfying for any i E [n). Each entry Wij reflects the probability of transmitting a message (such as model updates) from node i to node j in the next step. Specifically, for the communication otherwise.
Σj=1 Wij
graph (V. E), we have Way > 0 if (i.j) E. and Wi
Two DP levels. We consider two DP notions with different granularities in decentralized learning: user-level DP, which bounds the influence of any single user's entire dataset the algorithm's 's output [40 22), and record-level DP, which limits the impact of changing a single data point within a user's s dataset 170 12 In user-level DP, datasets D and D' are adjacent (denoted D D' D ~2 D') if they differ in all records of a single user i, offering stronger privacy. In contrast, record-level DP defines adjacency (denoted D D' or D =; D') based DP provides stronger protection but lacks certain benefits like privacy amplification by sub-sampling, which can enhance record-level DP guarantees but does not apply when entire user datasets differ.
difference in just one record. User-level
Pairwise network differential privacy (PN-DP). PN-DP is recent relaxation of local DP tailored for decentralized FL [15). It applies to settings where user has limited visibility of the overall algorithm output. PN-DP quantifies the privacy leakage from user i's data to user j by bounding the distinguishability of AD)D) and (T')), where D ~r D' are user-level adjacent datasets. Here, Ay (D) denotes user j's view of the algorithm's 's output. Existing work focuses on user-level PN-DP using RDP tools [14 [6 15). In Section 3 we develop our own fN-f-DP framework and also incorporate record-level analysis for finer privacy guarantees.
Definition 2.5 (User-level pairwise network RDP, or PN-RDP [6). For function e: V V -> R++, an algorithm A satisfies (o. c) -aairrise network RDP if for all pairs (i.j) E V x V and for two datasets D ~ D', R. (A, (D)))))))) S (i.
2.3 Private Decentralized SGD with local updates
We study two representative algorithms in decentralized differentially private learning: decentralized DP-SGD (Algorithm D and DecoR (Algorithm (
Algorithm describes decentralized DP-SGD with local updates. At each communication round t, the active user 4 performs K local SGD steps using mini-batch gradients Jk.t, each perturbed with Gaussian noise Zz,1 ~ (0 o²) scaled by the fz-sensitivity A. These updates are optionally projected onto a convex set IC via Ikg, though we focus on the unconstrained case. After K steps. the model 0x is sent to a new user j ~ W., based on the random walk transition matrix W. and the process continues with 2 = j. We analyze the general case of K 2 1, extending prior work focused on K 1 15
Algorithm 2 (DECOR) describes a parallel variant where each user i clips its gradient norm A, adds structured moise--orrellan
noise shared with neighbors (Zij,t = - Zz, and independent Tpp (appaa)aan and updates its model. Users then average their intermediate models via mixing matrix W. This design enables a decentralized implementation of SecLDP 2 improving privacy-utiiity trade-offs under limited trust assumptions.
noise Z,,, ~ (

---

Algorithm 1: Decentralized DP-SGD
Algorithm 2: DECOR: DP-SGD with Corr. Noise
Input: Transition matrix W, communication rounds T, K, K., start node io! init 80.0. stepsizes 7). batch size b,
Input: User i initializes 8,,0; transition matrix W; communication rounds T, stepsizes 7/.
sensitivity A, Ceors ØDP. {e: for == 0 to T- do
sensitivity A, c. Her
for t = to 7-1 do
for i = 1 to do Sample data point and compute Gi.t ( A);
// in parallel
for k = 0 to K-11 do Sample mini-batch ge.t with E[ga,s] = Vl:, (0x,,); Sample ZR, (0,,o0))
for N do
// neighbors of i
| Sample Z55,t = -Zju,t ~ NN d Ta);; end
Update Ox+1,1
IIx (0s.1 7(vu: + Zx,1));
gr.t == gt + ΣJEN, Z,y, + (N
end
0 0, + 0..t 701..i
Sample Win: Send 0x.e to j; Set le+1 + ji
0 + Eg W Wa 3,++35
end
end Output: 0K.T
end
Output: 0K.T
3 f-Differential Privacy Notions for Decentralized Learning
To obtain tighter privacy guarantees for A we introduce Pairwise Network J-Differential Privacy (PN-f-DP), We first focus on user-level privacy, where two datasets D and D' are adjacent at the user level (D ~e D'). Let A(D) denote the output of Algorithm on dataset D, and let (D) represent user j's view-i.e., all intermediate messages received by J during training.
V V x [0, 1] + [0, 1] be such that fúj == j(i trade-off function for any i.j E V. A decentralized algorithm A(D) = (A,(D)) satisfies user-level pairwise network f-differential privacy if (A) Aj (D)) 2 fig for all nodes i.j e V
Definition 3.1 (User-level PN-f-DP). Let :
and two user-level neighboring datasets D ~ D'.
We similarly define the record-level variant, where Ri D' denotes datasets differing in exactly one record held by user i.
Definition 3.2 (Record-level PN-f-DP). V [0, is a trade-off function for any i.j E V. A decentralized algorithm A(D) = (A,(D)) jev satisfies record-level pairwise network f-differential privacy if (D), i,j E V and two record-level neighboring datasets D R3; D'.
(0. 1] be such that fy f(i,
2 fúg for all nodes
Remark 3.1. Our definition of record-level SN- is relaxation of weak federated f-DP in 770 Specifically, a mechanism A satisfies record-level PN-/-DP, then it also satisfies weak federated f-DP, where f = (min., fay) with (.) the double convex conjugate operator. Note that for function 9: RR R, its convex conjugate is defined by g (v) max (ry- 9(=)).
In some decentralized learning scenarios, a pair of users (i,j) may share sequence of secrets S.y. Privacy analysis can be performed by relaxing local differential privacy and introducing the concept of SecLDP, discussed in (2] Users with secrets may injected correlated noise before gossip averaging and use uncorrelated noise to protect the gossip average, as shown in Algorithm 2 proposed by [2].
Definition 3.3 (Sec-f-LDPP Let Sz = iS. E V) be a set of secrets with some in- dices I C V. We say a randomized decentralized algorithm A satisfies Sy-See-f-LDP ((A is hidden, S( is hidden) > f. for any neighboring datasets D, D'. Specifically, if = T(N(O, (p, 1)), we say A satisfies Sy-Sec-u-GLDP (secret Gaussian local differential privacy).
4 Privacy Analysis
This section presents the privacy guarantees for the two proposed algorithms. For Algorithm J.ction[4T]Jaallyye the user-level privacy guarantees, while Section 4.2 focuses on the record-level ones. For Algorithm 2
Section 4.3 investigates the f-D characterization under correlated noise.
5

---

4.1 User-level Privacy Analysis
The privacy analysis of Algorithm|] T divided into two steps, following the spirit in [15. the first step, we bound the privacy loss incurred each time the algorithm visits node j. To obtain tighter bound, we leverage f-DP techniques that account for the mixture mechanisms and iterative structure induced by the random walk and updates in Algorithm I In the second step. we analyze the total number of node visits using a recently developed Hoeffcing-tpp inequality for Markov chains [23] The overall privacy loss is then obtained by composing the per-visit guarantees across all visits. A detailed proof is provided in Appendix D
Mixture distributions from random walks. We now present the first step of our analysis. Consider a random variable, Aginlo (D), which represents the model first observed by the user j after has been updated using data from some node i. Let A)(D) denote the model observed by user j at time t for the first time. By the properties of random walks, the probability that the model reaches node from node i for the first time at time I is given by wfy :- [ra = f. where Tay is the hitting time from i If Téj 2 T 1, then user j does observe the model within T steps, ensuring perfect privacy: A7 A (D) = = for all D ~ D'. We define wii+ := P(T.j 2 T + 1] = 1 - Σi= w/y as the probability that the model is not observed by node j within steps. Hence, the distribution of the one-time snapshot Agingle (D) can be expressed as a mixture over (D)) with weights {wighe- 1 reflecting the timing of the first visit.
To analyze the privacy of the mixture mechanism Aginghe (D), we leverage the joint concavity of trade- off functions established in [6]] Let Pf and Q3 denote the distributions of AJ (D) and A)()", with respective densities pf and qf.- and define the corresponding trade-off function as fíy := T(P) 23) for D ~ D'. The key insight is that the overall privacy dess-despite arising from a random and time-dependent mixture- can be lower bounded by a convex combination of the per-step trade-offs fij s, weighted by the same weight {w 17+1 This is formalized in the following lemma.
Remark 4.1. The idea of focusing on a single observation Aptingee (D) is inspired by 15 However, unlike their approach, which defines the weights wty as the matrix entries (W")aj. we instead define wfy based on the hitting time distribution. This subtle shift better captures the random walk dynamics and leads to tighter bounds. As shown in our experimental results in Section5) converting our f-DP guarantees back into RDP yields improved bounds, primarily due to the more accurate modeling of communication timing via hitting times.
Lemma 4.1. For any D ~i D', we have T T Apinelo (D') 2 Jij defined as follows: for all s E (0),
psingle, where Sij
psingle is
s (a(s)) = Σ
w (()(())))()) + w I+1 (1 ar+1(s)),
t=1
(x) (x()) > $ for any t, as)+(()) = [1c1]] and ass) = ET+ w())
with (s(s) = Prx~ps
Remark 4.2. The joint concavity (lower) bound fij psingle for trade-off functions in Lemma 4.1 is
widely used in f-DP literature, and [6] provides necessary and sufficient conditions under which this bound is tight. general, the tightness depends on the behavior of the likelihood ratio of the mixture, which in our case is determined by complex, data lata-dependent walk over the graph topology.
Computation of the weights w/y- A remaining issue is how to compute the weights w/y. Recall that wi, PlT, t). which denotes the probability that user observes the model for the first time the (-th iteration. To compute wot recursively, we begin with the base case: for = the model transmitted directly from user to user j. so wi W For f > 1, we decompose the event 1) based on the first step of the random walk. If the model is sent to a user k: + j in the first step, the event {ú, = k Tij = {) is equivalent to [Tkk = ( 1}. meaning the model must reach from in exactly t -- steps, without visiting j beforehand. By the Markov property, we obtain the recurrence: wi, Ent, Wawky1 The initialization satisfies wo. = 1 and w = for j A i, as the model starts at user i.
{Tyy =

---

(strongly convex case) or Computation of individual trade-off fij- To compute each trade-off function fíj. we apply the composition rule of f-DP, which accounts for the cumulative privacy effect of local updates. Since noise is added at each step, these updates offer privacy protection. When the loss functions are strongly convex, we apply privacy amplification by iteration in f-DP [8, which leverages both the contraction effect and repeated noise injection to yield tighter trade-off functions. In contrast, for general non-convex loss functions, we use the standard composition rule from Def. 2.4 resulting in a more conservative privacy bound. The following lemmas summarize both cases.
Lemma 4.2. Assume that the loss functions Es are m-strongly convex and M-smooth. Let
e max vpml, nMI3. Then, for
c < 1, we have l'g 2 Gy, with pe =
(2((t11)
1tc. (1-ck)2 I-c 1-E2RF When c= has μt. oVER+I
.KA
Lemma 4.3. For non-convex loss functions with gradient sensitivity A we have flg 2 G
VRA
VIR
Final privacy guarantee: Combining all components together.
With Saj from Lemma 4.1
and lower bound on each fú, from Lemma 4.2 or 4.3 we can compute valid lower bound on the trade-off function T T (D), A (D')) 2 fo single This bounds the privacy leakage from user i user j the time when the model first observed by j. Since Algorithm ( repeatedly updates and transmits the model, this process may occur multiple times. Thus, it suffices to compose the per-visit trade-off function fūj fejuugle according to the number of visits user j. To bound this number, we apply a concentration inequality for Markov chains (23). Details are deferred in the Appendix.
Combining these components yields the final privacy guarantee in Theorem Although it lacks a dlosed-form expression, the bound can be efficiently computed numerically.
Theorem 4.1. Assume the transition matrix W is irreducible, aperiodic, and symmetric, with spectral gap 1- X2 > O, where X2 is the second-larged eigenvalue of W (see Appendix for definitions). Then, for D mes D', under the assumptions in Lemma 4.2 Lemma (non-convex case), we have
[[(+C)T/x]
((A,
(saingle)
with probability 1 nr any Ç > and = exp taken over the randomness of the random walk initialized from the stationary distribution.
(- exp
222 The probability is
Remark 4.3. Lemma 4.1 holds for any valid trade-off function fiz- In this work, focus on the Gaussian lower bound (in Lemmas 4.2 or 4.3) for its simplicity and (asymptotic) universality [18] Consequently, Theorem 4.. also applies to general lower bounds of trade-off functions, provided that they are valid and their mixture distributions can be efficiently computed.
Remark 4.4. The slack term 6',,, accounts for uncertainty in the number of times a user j is visited during training [15. With probability at least 1 - 57,,, ., user is visited no more than [(1 + <)T/n times, yielding the composed trade-off function ( [++<<)7// in Theorem 4.1 If the exact
visit count N were known, the bound (J (Éelngle 8 would apply instead. Thus, 8T,, merely captures uncertainty from concentration bounds without materially affecting the results.
4.2 Extension to Record-level Privacy
Our analysis naturally extends to the record-level setting, which provides finer-grained privacy by protecting individual data records rather than entire users. In this case, each user computes stochastic gradient using a random subset of their local data, which reduces the probability that any given record is selected- thus amplifying privacy. Technically, this effect can be captured using privacy amplification by sub- sampling [33 S 65 [7]. We consider two datasets D and D' that differ by single record belonging to user i, denoted D= D'.
s;
The record-level analysis mirrors the user-level analysis, with each ft replaced by a new Fr However, sub-sampling interacts with privacy amplification by iteration, making the analysis more intricate. To characterize Mi we adopt a sum-sampling operator Cp defined by Definition E.1 The full proof is provided in Appendix
7

---

Lemma 4.4. Define the trade-off function Fij = (() AI(D)) for D R; D'. If each loss function is m-strongly convex, M-smooth with gradient sensitivity A. Then, for any 1j E (0, 2/M),
122 226(2126) (2
GG (((2a)) 2ak
110 ))
Vt 1,
110
where m, is the sample size of user and e max is given by bk+1 max {cby, (1-74+1) (cbx + n})}, ax+1 7k+1 (cby: + +n)) with bo 0, and
Here, the sequence {bx, aş.
0 7/ < 1. If each loss function is non-comvex, we have fuj @ C (G&)
We obtain the record-level privacy guarantee by replacing fú in Lemma 4.1 and Theorem 4.1 with
fij. with details can be found Appendix Moreover, our result can be extended to the non-convex case without considering privacy amplification by iteration, as detailed in Lemma E.2
4.3 Secret f-DP with Related Noise
Our f-DP framework can be naturally extended to settings where users share secrets coordinate noise addition, as proposed in Algorithm 2 We refer to this setting Sec-f-LDP, formally defined in Definition 3.3 To formalize this, we consider honest-but-curion coalition of up to y users may pool their information, including the shared secrets they have access to. This formulation models a practical threat scenario where partial trust exists across the network: users behave according to protocol but may attempt to extract additional information through collusion. We analyze privacy for Algorithm 2 which incorporates both independent Gaussian noise and pairwise correlated noise via shared secrets. The following theorem provides a quantitative guarantee under the Sec- f-LDP framework. The proof is given in Appendix
collusion level q 22, where any
H2
Theorem 4.2. Algorithm SecGDP with
2
against honest-but- users colluding level q satisfies (μ, S)-
1
1 V (n DD t2g
where, oB and dearr are the variance of the independent and dependent noise correspondingly and L is Laplacian matrix of the gruph and x2 is the second largest eigen-value of matrix.
collusion at level q" refers to a setting where the adversary can access all data and secrets except those of q users. This follows the adversarial model adopted in [2] and is standard in secret-sharing based privacy mechanisms. See Appendix for further details.
Remark 4.5. In Theorem 4.2 Phonest-but-curiee
Experiments
In this section, we present numerical experiments to demonstrate the performance of the proposed privacy accounting methods on both synthetic and real datasets. The codes are available at hhttps //github. com/1x10077/PP/ 0w00000077000-00000000 DD The goal is to examine how replacing previous RDP-based accounting methods with our f-DD- approach affects the privacy-utility trade-off under different network settings. We first compare PN-f-DP with PN-RDP on synthetic graphs, then evaluate their performance on two private classification tasks, and finally analyze the improved trade-off achieved with correlated noises, Additional results other graph structures and parameter settings are provided in Appendix due to space limitations.
Comparison with PN-RDP on synthetic graphs. Following the experiment setup in [5] we generate several synthetic graphs and report the privacy parameter when we convert PN-f-DP or PN-RDP to (e, 8)DP for given value of 8. For fair comparison, we fix the total iterations T, local updates K- = 1, and noise variance a² = 1. We set T = O log ), which is the number of steps required for the random walk to converge to minimal precision level. We use the numerical composition method in (29 36] to convert fN-f-DP to (c, DD- When numerically converting PN-RDP to (D, we adopt the method in 8 which computes the minimum e among the four
existing conversion methods [10 49
4)
We report results on hypercube graph with n = 32 nodes in Figure T and include similar results on two other synthetic graphs and one real graph in Appendix H Figure ((a) provides visualization

---

Curs
plot
192
Crpr
RDP
10
10
201
IUP (Milin tivel
10
15
(a) Hypercube graph.
(b) Pairwise privacy budget with 10-5
(c) (c, o)-erres..
Figure 1: Comparisons by converting PN- and PN-RDP to IN-(e,6)-DD on Hypercube. See
more experimental results in Appendix H.1
of the hypercube graph. Figure ((b) shows the pairwise privacy budgets (for 5 = 10-5) derived by converting PN-f-DP and PN-RDP to (e, 6)-DP. Across nearly all node pairs, the values from than those from PN-RDP, indicating stronger
PN-f-DP are noticeably privacy guarantees. In Figure [[c] we further examine the privacy leakage from user I to user a as a function of 5. In this plot, we also evaluate refined RDP baseline that uses the exact hitting time, as opposed to the upper bound in [15]. Even with this tighter baseline, our PN- f-DP method consistently yields the smallest e, demonstrating its effecttiveness in achieving tighter privacy guarantees.
saalllr-appearingg
Better performance on private classification. We then evaluate the impact of our tighter privacy ac- counting on downstream performance of DP-SGD through two classification tasks. The first is a logis- tic regression model trained on binarized version of the UCI Housing dataset and the second is an MNIST image classification (38] task using a sim- ple convolutional neural network. To meet target (c, 6)DD guarantee, we compute the required gradi- noise variance using different privacy accounting methods. We follow the experimental setup of (15).
Graph
RDP
RDP (HT)
Ours
Complete
10
0.867
0.884
0.891
Complete
8
0.854
0.876
0.885
Complete Expander
0.813
0.852
0.869
10
0.797
0.823
0.854
Expander 8
0.763
0.797
0.840
Expander
5
0.647
0.706
0.792
Table 1: Test accuracy on MNIST classifica-
tion with 5 10-5, Bold denotes the best.
including standardizing feature vectors, normalizing data points, and splitting each dataset randomly into 80% training and 20% test sets. The training data is then distributed across n = 2 users, each holding 64 local samples, according to an expander graph topology. We compare three approaches: decentralized DP-GD, local DP-GD, and our random- seaddoowwll--baane walk-based DP-GD under different noise variances. We focus on the privacy loss from user user 2, fixing (c (10, 10 -5) and record both objective values and test accuracy every 100 iterations. Results are presented in Figure 2 As seen, the wundom-walk-balee walk-based based method with fDD consistently achieves the best performance. This improvement is due to the tighter noise calibration enabled by f-DP, which allows us to meet the same (c, 6D guarantee with lower noise variance- thus enhancing the privacy-utilic trade-off. Table ] presents the test accuracy results for the MNIST classification task under varying graph structures and privacy budgets e. As shown, our method consistently yields higher accuracy across settings. The same pattern holds for logistic regression when increasing the number of users to n 2 or reducing the privacy budget to e = 5 or 3. These additional results are reported in Appendix H.2
Better performance on related noises. Finally, we demonstrate how our fDD method improves the privacy-utility trade-off for decentralized FL. with related noises. Our experimental setup follows (2). We consider n = 16 users on two standard network topologies with increasing connectivity: a ring and a 2D torus (grid). Each experiment is repeated with four random seeds for reproducibility. We compare against two baselines: SecLDP [2] and local DP. Figure 3 shows the results for logistic regression on the a9a dataset [I]. As seen, our method (red curves) consistently achieves a better privacy-utility trade-off across different values of the privacy budget and both network topologies.
Conclusions
We introduced two new differential privacy notions for decentralized federated learning: PN- PN- and Sec-f-I.DD extending the fDP framework to settings with independent and correlated noise, respectively. These enable tighter and composable privacy analysis for various decentralized protoooss.
Available at http:////w..ooo.o././/ooooooooaa

---

104
Lood 48h wi11
sericss
BS DEOOO with
(a) Expander graph.
(b) Objective function.
(c) Testing accuracy.
Lood DIPACD
SCD Dereccted
(d) Complete graph.
(c) Objective function.
(f) Testing accuracy.
Figure 2: Top: Performance private logistic regression on the Housing dataset. Bottom: Perfor-
mance of private MNIST classification using neural network.
Evolution
4
LDP
Alponitm
Optimalty gap
30
SecLDP
3x10-1
Sec LLP
Topolegy
Grid
Ring
2.10
10-1
10-0
Usar-level
Step
Figure Left: Privacy-utility trade-offs for our f-DP, DECOR, and LDP when converted the same (c, 10-P)-DP. Right: Optimality gap vs. iteration steps for Alg. 2 using different privacy accounting methods with 3. Similar results for other values of e (5, 7, 10} are provided Appendix H.3
Using PN- f-D,, we derived user- and record- guarantees for decentralized DP-SGD with random- walk communication, while Sec-/-LDP was applied to correlated-nove noise algorithms such as DecoR. Experiments synthetic graphs and the UCI housing dataset show that f-DD-based accounting consistently achieves stronger privacy-utility trade-off than RDP-based methods. Our framework readily generalizes to dynamic virc-ng graphs by updating the transition matrices W each round and applies to other decentralized FL algorithms--ae such as gossip-based, asynchronous, or push-sum protocols-by defining suitable W' and update rules. It also accommodates non-uniform or partial participation, and known participation probabilities can be incorporated into the weighting scheme for additional privacy amplification. Extending these ideas and establishing information- theoretic lower bounds remain promising directions for future work.
Acknowledgments
This work was supported in part by NIH grants U0ICA274576 and RO1EB036016. NSF grant DMS- MMM-223 Meta Faculty Research Award, and Wharton Al for Business. The content is solely the responsibility of the authors and does necessarily represent the official views of the NIH.
References
[1] M. Abadi, Chu, I. J. Goodfellow, H. B. McMahan, Mironov, K. Talwar, and Zhang. Deep learning with differential privacy. In E. R. Weippl, S. Katzenbeisser, C. Kruegel, A. C.
10

---

Myers, and S. Halevi, editors, Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24-28, 2016, pages 308-318, ACM, 2016.
[2] Y. Allouah, A. Koloskova, A. E. Firdoussi, M. Jaggi, and R. Guerraoui. The privacy power of correlated noise in decentralized learning. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024.
[3] J. M. Altschuler and K. Talwar. Privacy of noisy stochastic gradient descent: More iterations without more privacy loss. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and
A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information P Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November
28- December 2022, 2022.
[4] S. Asoodeh, J. Liao, F. P. Calmon, O. Kosut, and L. Sankar. Three variants of differential privacy: Lossless conversion and applications. IEEE J. Sel. Areas Inf. Theory, 2(1):208-22) 2021.
[5] B. Balle, G. Barthe, and M. Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. In S. Bengio, H. M. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 6280-6290, 2018.
[6] B. Balle, G. Barthe, M. Gaboardi, Hsu, and T. Sato. Hypothesis testing interpretations and Rényi differential privacy. In S. Chiappa and R. Calandra, editors, The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy], volume 108 of Proceedings of Machine Learning Research, pages 2496 2506. PMLR, 2020.
[7] R. Bassily, A. D. Smith, and A. Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 464-473. IEEE Computer Society, 2014.
[8] J. Bok, W. Su, and J. M. Altschuler. Shifted interpolation for differential privacy. CoRR, abs/24033.0027,, 2024.
[9] K. A. Bonawitz, V. Ivanov, B. Kreuter, A. Marcedone, H. B. McMahan, S. Patel, D. Ramage, A. Segal, and K. Seth. Practical secure aggregation for privacy-preserving machine learning. In B. Thuraisingham, D. Evans, T. Malkin, and D. Xu, editors, Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, Dallas, TX, USA, October 30- November 03, 2017, pages 1175-1191. ACM, 2017.
[10] M. Bun and T. Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. M. Hirt and A. Smith, editors, Theory of Cryptography 14th International Conference, TCC 2016-B, Beijing, China, October 31 November 3, 2016, Proceedings, Part I, volume 9985 of Lecture Notes in Computer Science, pages 635-658, 2016.
[11] C.-C. Chang and C.-J. Lin. LIBSVM: library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3):1127, 20
[12] S. Chen, Q. Zheng, Q. Long, and W. J. Su. Minimax estimation for personalized federated learning: an alternative between FedAvg and local training? J. Mach. Learn. Res., 24:Paper No. [262], 59, 2023.
[13] A. Cheu, A. D. Smith, J. R. Ullman, D. Zeber, and M. Zhilyaev. Distributed differential privacy via shuffling. In Y. Ishai and Rijmen, editors, Advances Cryptology EUROCRYPT 2019 38th Annual International Conference on the Theory and Applications of Cryplogruphic Techniques, Darmstadi, Germany, May 19-23, 2019, Proceedings, Part I, volume 11476 of Lecture Notes in Computer Science pages 403. Springer, 2019.

---

[14] E. Cyffers and A. Bellet. Privacy amplification by decentralization. In G. Camps-Var Valls, F. J. R. Ruiz, and Valera, editors, International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Research, pages 5334-5353 PMLR, 2022.
[15] E. Cyffers, A. Bellet, and J. Upadhyay. Differentially private decentralized learning with random walks. Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024.
[16] E. Cyffers, M. Even, A. Bellet, and L. Massoulié. Muffliato: Peer-to-peer privacy amplifica- tion for decentralized optimization and averaging. In S. Koyejo. S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Anmual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28- December 9, 2022, 2022.
[17] J. Dong, A. Roth, and W. J. Su. Gaussian differential privacy. J. R. Stat. Soc. Ser. Stat. Methodol,, 84(1):3-54, 2022. With discussions and a reply by the authors.
[18] J. Dong, W. Su, and L. Zhang. A central limit theorem for differentially private query answering. Advances in neural information processing systems, 34:14759-14770, 2021.
[19] C. Dwork. Differential privacy. In M. Bugliesi, B. Preneel, V. Sassone, and I. Wegener, editors, Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part II, volume 4052 of Lecture Notes in Computer Science, pages 1-12. Springer, 2006.
[20] E. Estrada and P. A. Knight. A first course in network theory. Oxford University Press, USA, 2015.
[21] M. Even. Stochastic gradient descent under markovian sampling schemes. In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, editors, International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolula, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 9412-9439. PMLR, 2023.
[22] A. V. Evfimievski, J. Gehrke, and R. Srikant. Limiting privacy breaches in privacy preserving data mining. In F. Neven, C. Beeri, and T. Milo, editors, Proceedings of the Twenty-Sccond ACM SIGACT-SIGMOD-SICE
Symposium on Principles of Database Systems, June 9-12, 2003, San Diego, CA, USA, pages 211-222. ACM, 2003.
[23] J. Fan, B. Jiang, and Q Sun. Hoeffding's inequality for general Markov chains and its applica- tions to statistical learning. J. Mach. Learn. Res., 2aper No. 139, 35, 2021.
[24] V. Feldman, A. McMillan, and K. Talwar. Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 954 964, IEEE, 2021.
[25] V. Feldman, A. McMillan, and K. Talwar. Stronger privacy amplification by shuffling for Rényi and approximate differential privacy. In N. Bansal and V. Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium Discrete Algorithms, SODA 2023, Florence, Italy, January SIAM, 2023.
22-25, 2023, pages
[26] V. Feldman, I. Mironov, K. Talwar, and A. Thakurta. Privacy amplification by iteration. In M. Thorup, editor, 59th IEEE Anmual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018 pages 521-532. IEEE Computer Society, 2018
[27] J. Geiping, H. Bauermeister, H. Dröge, and M. Moeller. Inverting gradients how easy is it to break privacy in federated learning? In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 12, 2020, virtual, 2020.
12

---

[28] B. Ghazi, R. Kumar, and P. Manurangsi. User-level differentially private learning via correlated sampling. In M. Ranzato, A. Beygelzimer, Y. N. Dauphin, P. Liang, and W. Vaughan. editors, Advances in Neural Information Processing Systems 34; Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 20172-20188 2021.
[29]
S. Gopi, Y. T. Lec, and L. Wutschitz. Numerical composition of differential privacy. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems 34: Anmual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 11631-11642, 2021.
[30] B. Johansson, M. Rabi, and M. Johansson. randomized incremental subgradient method for distributed optimization in networked systems. SIAM J. Optim., 20(3): 151-1170710 2009.
[31] Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. A. Bonawitz, Z. Charles, G. Cormode, R. Cummings, R. G. L. D'Oliveira, H. Eichner, S. E. Rouayheb, D. Evans, J. Gardner, Z. Garrett, A. Gascón, B. Ghazi, P. B. Gibbons, M. Gruteser, Z. Harchaoui, C. He. L. He. Z. Huo, B. Hutchinson, J. Hsu, M. Jaggi, T. Javidi, G. Joshi, M. Khodak, J. Konečný, A. Korolova, F. Koushanfar, S. Koyejo. T. Lepoint, Y. Liu, P. Mittal, M. Mohri, R. Nock, A. Özgür, R. Pagh, H. Qi, D. Ramage, R. Raskar, M. Raykova, D. Song, W. Song, S. U. Stich, Z. Sun, A. T. Suresh, F. Tramèr, P. Vepakomma, J. Wang, L. Xiong, Z. Xu, Q. Yang. F. X. Yu, H. Yu, and S. Zhao. Advances and open problems in federated learning. Found. Trends 2021.
Mach. Learn., 14(1-2):
[32] Kairouz, S. Oh, and Viswanath. The composition theorem for differential privacy. IEEE Trans. Inform. Theory, 63(6):4037-400 2017.
[33] S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. D. Smith. What can we learn privately? SIAM J. Comput., 40(3):793-826, 2011.
[34] A. Koloskova, S. Stich, and M. Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In International Conference on Machine Learning, pages 3478-3487. PMLR, 2019.
[35] A. Koskela, M. A. Heikkilä, and A. Honkela. Numerical accounting in the shuffle model of differential privacy. Trans. Mach. Learn. Res., 2023, 2023.
[36] A. Koskela, Jälkö, and Honkela. Computing tight differential privacy guarantees using FFT. In S. Chiappa and R. Calandra, editors, The 23rd International Conference Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy], volume 108 of Proceedings of Machine Learning Research, pages 2569. PMLR, 2020.
[37] G. Lan, S. Lee, and Y. Zhou. Communication-efficienn algorithms for decentralized and stochastic optimization. Mathematical Programming, pages 1-48, 2017.
[38] Y. LeCun, C. Cortes, C. Burges, et al. MNIST handwritten digit database, 2010.
[39] D. A. Levin and Y. Peres. Markov chains and mixing times. American Mathematical Society, Providence, RI, 2017. Second edition of MR2466937), With contributions by Elizabeth L. Wilmer, With a chapter on "Coupling from the past" by James G. Propp and David B. Wilson.
[40] D. Levy, Z. Sun, K. Amin, S. Kale, A. Kulesza, M. Mohri, and A. T. Suresh. Learning with user-level privacy. In M. Ranzato, A. Beygelzimer, Y. N. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processiny Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 18466-124799 2021.
[41] X. Li, K. Huang, W. Yang. S. Wang, and Z. Zhang. On the convergence of fedavg non-iid data. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
13

---

[42] X. Lian, C. Zhang, H. Zhang, C.-J. Hsieh, W. Zhang, and J. Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. In Advances in Neural Information Processing Systems (NIPS), 2017.
[43] S. P. Liew, T. Takahashi, S. Takagi, F. Kato, Y. Cao, and M. Yoshikawa. Network shuffling: Privacy amplification via random walks. In Proceedings of the 2022 International Conference on Management of Data, pages 773-787, 2022.
[44] C. G. Lopes and H. Sayed. Incremental adaptive strategies over distributed networks. IEEE Truns. Signal Process., 55(8):40644400 2007.
[45] Y. Ma and H. Yang. Optimal locally private nonparametrie classification with public data. J. Mach. Learn. Res., 25:167:1-167:6: 2024.
[46] Y. Ma, H. Zhang, Y. Cai, and H. Yang. Decision tree for locally private estimation with public data. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.
[47] X. Mao, K. Yuan, Y. Hu, Y. Gu, A. H. Sayed, and W. Yin. Walkman: A communication- efficient random-walk algorithm for decentralized optimization. IEEE Trans. Signal Process., 68:2513-2522 2020.
[48] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas. Communication- efficient learning of deep networks from decentralized data. In A. Singh and X. J. Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017, 20-22 April 2017, Fort Lauderdale, FL, USA, volume 54 of Proceedings of Machine Learning Research, pages 1273-1282. PMLR, 2017.
[49] I. Mironov. Rényi differential privacy. In 30th IEEE Computer Security Foundations Symposium, CSF 2017, Santa Barbara, CA, USA, August 21-25, 2017, pages 263-275. IEEE Computer Society, 2017.
[50] M. Nasr, R. Shokri, and A. Houmansadr. Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning. In 2019 IEEE Symposium on Security and Privacy, SP 2019, San Francisco, CA, USA, May 19-23, 2019, pages 739-753. IEEE, 2019.
[51] D. Pasquini, M. Raynal, and C. Troncoso. On the (in) security of pper-toopeer decentralized machine learning. In 2023 IEEE Symposium on Security and Privacy (SP), pages 418 436. IEEE, 2023.
[52] S. S. Ram, A. Nedić, and V. V. Veeravalli. Asynchronous gossip algorithm for stochastic opti- mization: Constant stepsize analysis. In Recent Advances in Optimization and its Applications in Engineering, pages 51-60. Springer, 2010.
[53] M. Roberts Jr. Correspondence analysis of two-mode network data. Social Networks, 22(1))65-72, 2000.
[54] C. Sabater, A. Bellet, and J. Ramon. An accurate, scalable and verifiable protocol for federated differentially private averaging. Mach. Learn.,
2022.
[55] R. Shokri, M. Stronati, C. Song, and V. Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE Symposium on Security and Privacy, SP 20/7, San Jose, CA, USA, May 22-26, 2017, pages 3-18. IEEE Computer Society, 2017.
[56] B. Sirb and X. Ye. Consensus optimization with delayed and stochastic gradients decentral- ized networks. In 2016 IEEE International Conference on Big Data (Big Data), pages 76-85. IEEE, 2016.
[57] D. M. Sommer, S. Meiser, and E. Mohammadi. Privacy loss classes: The central limit theorem in differential privacy. Proc. Priv. Enhancing Technol., 2019(2) 2019.
14

---

[58] B. Su, J. Su, and C. Wang. The 2020 United States decennial census is more private than you (might) think. CoRR, abs/2410.09296, 2024.
[59] H. Tang, X. Lian, M. Yan, C. Zhang, and Liu. D2: Decentralized training over decentralized data. arXiv preprint arXiv: htw:::80300000 803.07068, 2018.
[60] S. Vithana, V. R. Cadambe, F. P. Calmon, and H. Jeong. Correlated privacy mechanisms for differentially private distributed mean estimation. arXiv preprint arXiv:2407.03229, 2024.
[61] C. Wang, B. Su, J. Ye, R. Shokri, and W. J. Su. Unified enhancement of privacy bounds for mixture mechanisms via f-differential privacy. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.
[62] C. Wang, Y. Zhu, W. J. Su, and Y. Wang. Neural collapse meets differential privacy: Curious behaviors of noisygd with near-perfect representation learning. In Forty-firsl International Con- ference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024.
[63] D. Wang, M. Gaboardi, and J. Xu. Empirical risk minimization in non-interactive local differential privacy revisited. In S. Bengio, H. M. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages 973-982, 2018.
[64] J. Wang, A. K. Sahu, Z. Yang, G. Joshi, and S. Kar. Matcha: Speeding up decentralized SGD via matching decomposition sampling. arXiv preprini 1905.v99000094533 2019.
[65] Y. Wang, B. Balle, and S. P. Kasiviswanathan. Subsampled Rényi differential privacy and analytical moments accountant. J. Priv. Confidentiality 10(2), 2020.
[66] L. Wasserman and S. Zhou. A statistical framework for differential privacy. J. Amer. Statist. Assoc., 105(489) 2010.
[67] J. Ye, A. Maddi, S. K. Murakonda, V. Bindschaedler, and R. Shokri. Enhanced membership inference attacks against machine learning models. In H. Yin, A. Stavrou, C. Cremers, and E. Shi, editors, Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, CCS 2022, Los Angeles, CA, USA, November 7-11, 2022, pages 3093-3106. ACM, 2022.
[68] J. Ye and R. Shokri. Differentially private learning needs hidden state (or much faster con- vergence). S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Anmual Conference on Neural Informa- tion Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28- December 2022, 2022.
[69] K. Yuan, Q. Ling, and W. Yin. On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 1835))1838-8544 2016.
[70] Q. Zheng, S. Chen, Q. Long, and W. J. Su. Federated f-differential privacy. In A. Banerjee and K. Fukumizu, editors, The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event, volume 130 of Proceedings of Machine Learning Research, pages 2259- PMLR, 2021.
[71] Y. Zhu, J. Dong, and Y. Wang. Optimal accounting of differential privacy via characteristic function. G. Camps-Valls F. J. R. Ruiz, and Valera, editors, International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, volume
151 of Proceedings of Machine Learning Research, pages 4782-4817 PMLR, 2022.
[72] Y. Zhu and Y. Wang. Poission subsampled Rényi differential privacy. K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning, ICMI. 2019, 9- June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 7634-7644 PMLR, 2019.
15

---

A Preliminaries on Markov Chains
Here, we summarize several properties of Markov chains that will be utilized in our proof, detailed in standard Markov chain texthooks, such as [39].
Definition A.1 (Irreducible). A Markov chain with transition matrix W is called irreducible if there exists / > O such that W > 0 for any i, E [n].
For probability distribution т supported on [n] with pmf { (i.e., my 2 0 and Σi= To = 1) and transition matrix W, we define T (W) as
(T = Σ Wey 2=1
for any j [n]]
Definition A.2 (Stationary distribution). For Markov chain with transition matrix W, we say x is stationary distribution of W is ((W)= W.
Proposition A.1 (Existence of a stationary distribution). For an irreducible Markov chain with transition matrix W, there is probability such that π xW) W, i.e., π is stationary distribution o. W.
Let (1)) (t 2 1: (W"), > 0} be the set of all times when the probability of the chain starting from node returns to node i. The period of node defined as the greatest common divisor of ((i). Definition A.3. We say Markov chain is aperiodic if the period of every node i is 1.
B Useful Properties of f-DP
B.1 Joint Concavity of Trade-Off Functions
As the random walk implies a mixture distribution, we first provide f-DP guarantees for mixture mechanisms using the joint concavity of trade-off functions introduced by [6]].
Let [P and { be two sequences of probability distributions and let p; and gi be the pdf of P. and Qi, correspondingly. A mixture distribution Pw that is mixture of {P. 1m with weights
w = { 1 has pdf Pw "m= wiP;. Similarly, let Qw denote the mixture of [Q with the
same weights w [w;)m i.c., Qw has a pdf given by qw = =Ei wtYi
Lemma B.1 (Joint concavity of trade-off functions[611 61]). For two mixture distributions Pw and Qw. holds
m Σ
T(Pw, Qw)
N
w wTP,P, (a)(tt),))
where (o.t,c))PPxx =
p. (X)
+CP +CPx X-R
(X)
1 is the type error for testing P; v.s. Q:
pt
using the likelihood ratio test and (tt, Σm (t,,, c).
According to [61, Lemma B. implies the joint convexity of Fidivergences, including the scaled exponentiation of the Rényi divergence and the hockey-stick divergence.
B.2 Privacy Amplification by Iteration
Consider the DP-SGD algorithm defined iteratively as
0 = 1T [0x (9x (0x) + +N(0,
with some initialization do some closed and convex set KC, and some gradient map gk. The effect of iteration the Gaussian noise has been studied by (26). which is termed privacy amplification by iteration. This is further investigated by 3 688 which shows that the privacy budget of DP-SGD may converge the iteration goes. Here introduce recent f-DP result for privacy amplification by iteration g which will be adopted in our privacy analysis.
For map σ, we say @ is contraction & is c-Lipschitz for some 0 < < 1. When e = 1, we say & is non-expansive. The following conclusion is well-known result to guarantee that the gradient map 0 + 0 (0) is non-expansive.
16

---

Lemma B.2. Consider loss function that is convex and M-smooth. Then, the gradient descent
update (xx) --1 f() non-expansive for each rj [0, 2/ . If f is additionally m-strongly convex and
(0, (0,,/M), then Φ is c-Lipschitz with max (11 -pml, 1/Mi) <1.
The iteration of DP-SGD relates to the contractive noisy iteration.
Definition B.1 (Contractive noisy iterations (CNI)). The contractive noisy iterations CNI( fo hee()), MEje) XC) corresponding to a sequence of contractive functions {Ør ke())) a sequence noise distributions {Ex kEle)- and a closed and convex set K, is the stochastic process
8k+1 II ( (0k) + Zk+1),
(I)
where Zk+1 Sk+1 is independent of (0o....,0) Ok)-
For CNI, one can consider the privacy amplification by iteration. Here, we apply the f-P guarantee in the following lemma from g
Lemma B.3 (Privacy amplification by iteration, Lemma C.3 in (8). Let 02 and f respectively be the output of CNI(0o. {or heeq (O( o I K.) and CN1(0o, t hettt o2( K.) such that each Øk. & Lipschitt and || &x I sk for all ls e [t]. Then for any intermediate time T and shift parameters "141,'"" T E [0. 1] with " = 1,
T(O., 02) G
Σ of k=T+1
where 03+1 = (cbs + 8841), bx41 = (1 1 + Sk+1), and 110, 0,11 S by-
B.3 Additional Useful Properties
Post- Post-processing property of f-DP (17). An important property of DP is its resistance to data- independent post-pnn pooss-procssing. For f-DP, this post-processing property described in the following proposition.
Proposition B.1. For any probability distributions P, P.Q and any data data-independent post-processing Proc, it holds
T(Proc()), Proc(Q)) 2 T(P.Q).
From f-DP to (e, DDD and back [1]. On one hand, f-DP mechanism with symmetric trade-off function f is (,, -D for all > 0 with
5(c)
(-c)))
On the other hand, if a mechanisms is (e, (()) then it is f-DP with f sup fe,s where
fes(a) = max (0, e'a (((---a))))
From f-DP to RDP 17). An f-DP mechanisms is (a, ((()) where
<)())) a a log ( [f(x))
In particular, a GDGDP mechanism (a, 11²a))-DP. It is worth mentioning that converting RDP back to fDP is challenging.
C Additional Details on the Extension to Record-Level Privacy
D Proofs of Section 4.1
The proof of the user-level analysis can be divided into the following steps: first, we prove Lemma which deals with the mixture distributions caused by random walk; then, we study the privacy
amplification of Algorithm]] I and prove Lemma 4.2 the last step is to prove Theorem 4.1
17

---

D.1
Proof of Lemma 4.1
Recall the random variable Aj A (D) that represents the model visits user j for the first time after passing user i and (D) which represents the model visits user j for the first time at the t-th iteration. Thus, one has
PlA (D) (D) 1]() = = w/y. for all 1 S S.
where Trj is the hitting time from i to j. There is a chance that the model will not be observed after T steps, which is represented by random variable A3+1 (D). And we have
PlA (D) (D) - Af P(Te > -
Σ w = w
T+1
for 1 1S1ST.
By the definition of mixture distributions, one has Agingle (D) is mixture of (D) with weights fult (w We finish the proof by applying the joint convexity in Lemma B.1 to the mixture above.
Tt=1-
D.2 Proof of Lemma 4.2
Recall that fiy is the privacy loss when the model is observed in the user j after t steps. Note that, after t steps, Algorithm has been run for tk iterations. Thus, the trade-off function fiy can be bounded by adopting privacy amplification by iteration in [8] Using Lemma B.3 we have the following iteration results for Algorithm]] !
Lemma D.1 (Privacy amplification for decentralized DP-SGD). Under assumptions in Lemma 4.2 for any 7,, NYK E [0, 1] with "nk- = L, it holds
etK Jig 2 G
VE
where 0x+1 -7++1 (chg + 8k+1), bx+1 (1 Tk+1 (ebe + 8k+1) with bn 0, 8
1 for
1 I k K. and sy 0 for K + S S Kt. Here G VEVE, is the Gaussian trade-off
function G₁ with μ 1 > KK
az.
Proof. The proof based on Lemma B.3 To obtain the final result, we need to clarify the choice of parameters 8ą and by in Lemma B.3 with
Recall that s4 the upper bound on || &loo.
where (x) == x - ///b Ei= (x( represents the gradient map and dy. := x - n/bb Ei= (*(()) is another gradient map obtained by modifying the dataset held by (1 S k < K) the iteration is running with user i's dataset. Thus, 8% is upper bounded 7 where A is the sensitivity of the sub-sampled gradient.
In the first K steps
After iterations, for K + 1 k S tK, the model has been sent to other users and changing the data records in user will not change the gradient. Thus, 8ę becomes O. There is possibility that the model might be sent back to user i again for 2K + < k I tK before it reaches user j. However, the privacy loss of the second pass accounted for using other ftj esingle functions within the total number
[T/n+ of trade-off functions psingle and will considered using composition in Theorem 4.1 Therefore, multiple passes through user i will not affect the privacy of the current single pass and we still have $ą = 0 even though might be sent back to user again for 2K + < k < tk. We finish the proof by replacing in Lemma B.3 with nar as there is a scalor 77 of the Gaussian noise in Algorithm
The finish the proof of Lemma 4.2 motivated by [8. is enough to minimize the term Lemma D.I. which is given in the Tollowing lemma.
Σ o in
Lemma D.2. Given 0 < < 1, the optimal value of
tK
min
0
Amm
18

---

subject to
ax+1 7k+1 + sk+1) 2 0, bu+1 (1 mcbi](ch, sk+1) 20, bo = 0, bek =
0 7 S 1, 8/: = 8, for 0 I k I K,
and 8k. = 0, for K + - - tk,
(2((-11) ع- T-o
y2
T- 3
Proof. Note that
iK
iK
buk
+
- ax = bo +
- 8k+
ck
and
1=1
k=
tk
- ck
Ik - Ok c k(t-1)
1 -
By the Cauchy-Schwand inequality, we have
E cK kks))as) )
tk
Dk c2(tK 2K((-1). 1+c (1 (1- k32
1 1 221 8²
A=1
where the equality holds when 7t 1, Og for S k s K and 7
0. a2
for
K K+15 k < Kt.
We finish the proof of Theorem 4.1 by taking 7/ in Lemma D.2 and combining Lemma D.2
with Lemma D.I
D.3 Proof of Lemma
Lemma D.3. For two random variables X, X' satisfying T(X,X') 2 T(G,5) with Ç N(0. of) N(,,of) for some p > O, we have T(X + E, X' + E) 2 T(S E.5' + g) for E ~ ((0,
Proof. By Theorem 2.10 in 177. have X proc({) and X' proc((") for some post pese-processing map proc. The proof is done by noting that there is new post-processing new processing proc' E proc(() proc())((
such that X { proc' (S + E)-
Proof of Lemma 4.3 After K iterations in user i, we have f 2 Gp with Pi,K
VKA/o. Rewrite GHa, T(N(0, N o²). By Lemma D.3 we have f/ 2 = GGn with in = Hi,K/ /V. If f 2 GpeK-1 with Pax-1 write GpIK-1 T(V(O, V.
(0, (op,,,
V2.
Kg.K/ L.///tK. Then,
Vto?)). Thus, by Lemma
D.3 obtain fú 2 T(N(O, (tK (( (tK + 1)o²)) = Gp.. We finish the proof by induction.
D.4 Proof of Theorem 4.1
Lemma D.4 (Hoeffding's inequality for Markov chain, Theorem I in (23).. Let (Yt)es be a Markov chain with transition matrix W and stationary distribution æ. For any T > and a sequence of bounded functions [ffeT such that sup,, [f(()) & M, it holds
T Σ
(- - X2 TM2
X2 2C²
P
(F(()) - Ey (f((t)) 2 2 $ exp
for any <> > 0, where de is the second largest eigen-value W.
19

---

Let fo be an indicator function that equals if Xt visits j at time t, and O otherwise. Then Ei= (f:( is the total number of visits to the user j. which means the model observed at user j for (f=i))( times and the total privacy loss is Ei= (J(())) composition of fejnnle. Under assumptions of Theorem 4.1 the stationary distribution и is uniformly distributed on [v]] (cf., Exercise 1.7 in (39). Thus, we have FEy~=(Je(Y)) 1/n in Lemma D.4 Note that oo < .M 1. As result of Lemma D.4, one has 21=1((( 2 (1 + C)T/n with
Proof of Theorem 4.7
probability exp
1- 2 and finish the proof.
1+22 n
Remark D.I. When converting f-DP to (c, 6)-DP, Sy.n contributes additional term 8. The proof employs Hoeffding's s inequality for general Markov chains [23], which achieves faster exponential decay of 8,,, by exploiting the spectral gap, improving upon the polynomial decay the classical result (Theorem 12.21 in (39).
E Proofs of Section 4.2
The formal statement of Theorem H.I is given below.
Definition E.1 (p-sampling operator of f-DP 17).. For trade-off function f and sampling
parameter 0 < < 1, we let fp = =f (1 p) The p-sampling operator Cp that maps a trade-off
function to another trade-off function is defined as Cp(f) = (min fp fp' where (-) the
left inverse of a non-increasing function and (-)* is the double convex conjugate of a function.
Theorem E.1. Assume the conditions of Theorem hold. For all s E [0, oo),
fij Fainglo(a(s))
paingle (a(s)) = Σ Wiy (an(s))
Tht (1 (1- (1-a)+1(s)).
where (s(8) and ass) are the same defined in Lemma 4.1 Then, for D R, D', we have ((), (fs
pingle) @I4+C)7/))
with probability n any < > O.
The proof of record-level privacy in Theorem E. necessitates iteration analysis with subsampling. The proof closely follows the approach in (8) However, in federated learning, subsampling affects only the first K iterations, as the subsequent (t 1)K iterations do not use the dataset from user i, which differs from [8] Due to subsampling, the Gaussian mechanisms might be influenced by a Bernoulli distribution. Therefore, we begin by introducing the following lemma from (8).
Lemma E.1 (Lemmaa C.12 in (). For 0 and 0 p S let
R(s, a,p) (TVW VW Z) V Bern(p),|[]),, [W']| s. ~ oN(O,
where the infimum is taken pointwisely and over independent V, W. W Z. Then, one has R(s, a. p) 2 (G)))
The proof of Lemma 4..4 requires the following proposition. We adopt the notation from g and divide the minibatch subsample into two subsets, R2 and Ck, as follows. For z", data record that might be changed by an attacker under the setting of record-level DP, we use the following definition of R2 and Cj from [
1. Sample set A₁ of size b in D, P.Ve {x*} uniformly at random.
2. Sample element A₂ from A, uniformly at random. This element will serve as candidate to be (potentially) replaced by x*.
3. Let R4 = Ai \ (A2), M42,,Ca Cs = A2.
Following g we also define the following stochastic version of the CNI. the k-th iteration, D and D' differ by single data record held by the user i. Denote the record as C% when used in the k-th iteration, and as C₁ when not used in the mini-bateh of the k-tth iteration. Let the index of (Re, C²). Let Eg be the loss function
the mini-bate of size 5 be S₃ (Re, Ck) [m.]] or St
20

---

corresponding to single datapoint 2. Denote
Us (0) (Vcc (l2)
RE
d's, (8) (Vec +
"
Σ
(e))
ZER
Ss. (0) 0 b
Σ
(ez(0).
SERGUCL
Proposition E.1. Assume that the loss functions are m-strongly convex, M-smooth loss gradient sensirivity A. Then, for any E (0, (0,2/M), t 1, Algorithm is f-DP, where
2 2/2cbuk-11
tK-1
2ak
=
Cpe
R=
for any sequence {bx, ak, s23 given by
bk+1 = max(cbb: (1 (cb1)(cbxx + sk)},
0k+1 7k+1 (cbx + sk)
8k max(1l v.s. 10:: 110s; - -vs;,l1 [1
and bo 0, S * < 1, c max{11- m/m1 |1 nd }. 8p 0, ps b/m, for 1 S k K and Pk = 0 for any > K.
Proof.
The iterates of Noisy SGD with respect to {ee and { heD are given by
0k+1 1kx(vs. (0x) Vilés, vsss + Zx+1),
0,41 = [Tx(s/s (0% Vi((d's Vis (8%) + *
where ZR+1, 2 (000))"001aa) and VR, Vi Beru(px). For any 7 1, consider shifted interpolated processes introduced by []] which is defined as
0z+1 = [x (0x) +h+ (ols,, (0x) v.s. (0x)) + Z
0 0+1 1cx(vs; (0)) Th+1 Vo's's (0)) Uus (0%) *
with 0, = 0n. Using Lemma C.14 in 8 we have the trade-off function between 0xx-1 and
kK given by
100
KK -1
Opu
(G]
2aa 1/0
for any sequence (bu, ags $x}
bx+1 max(cbb, (1 (cbx + sx)},
0k+1 7++1 (eby + st),
8 max max((1 v.s. 1o,o 1|/s; v.s |1x0);
with by = 0 and S 7A < 1. By the ralationship between the original iteration and the interpolation
(Section C.3 ) one has
22/2cbrk
T(0k 0xx) 2
1/0
This completes the proof of Proposition
E.I
21

---

Proof of Lemma Similar to the proof of Lemma D.I. for Algorithm 1 we have Sü 0 for any K + 1 S S Kt and 8 = n for any k I K. In the first K steps (1 - k S K) the iteration is running with two datasets, D) and D/ which differ by single data record belonging to user i. Thus, Pk = b/m; for k v K is the probability of selecting different data in the mini-batch of size b from all my data belonging to user i. After K iterations, for K + I l I tK, the model has been sent to other users and changing a single data record user will not change the gradient. Thus, pk becomes O.
Therefore, Lemma 4.4 follows directly by letting 8 O, pk- 0 for any k and 8% nA. P = b/ my for any k S K. Overall, we obtain
2 2cbak-1
20k
f =
Cpa
G
no
no
h=1
2v 2cbek-
K
2ak
Kt-1
tk Σ
Cpe
G
110
170
k=
k=K+1
k=
22 (ift--1JKp by
K
2ak
=
Cee
G
170
110
This completes the proof of Lemma 4.4
Lemma E.2. For non-convex loss functions, we have
My 2 T(A)(D)) + Kio"), A9((D) (lo)))
Proof of Lemmal E.2 After K iterations in user i, we have T. = T(43(D). >
k=1 Cb/m: (G According to Lemma D.3 we have
B 2 T(A)(D)) + (lo A9(D') (((,)
F Details of Secrect-based DP
F1
Details Secret-Based Local Differential Privacy
In the framework of secret-based differential privacy (DP) (2) the objective is to safeguard user data privacy against an adversary capable of eavesdropping on all communications. Fach connected pair of users j E V shares sequence of secrets Sij. which are realizations of random variables known exclusively to the two corresponding nodes. In practice, these secrets can be locally generated from shared random seeds exchanged during an initial round of encrypted communication [. Conceptually, one may view the secrets themselves as these shared randomness seeds. We denote by S = (St j V} the collection of all such secrets. For subset of nodes I C V, we denote by Sz = [S.g, E V.i,j & I) the set of secrets hidden from all users I. Based on Sz, we can formally introduce Definition 3.3 We consider honest-but-coee but-cuuiouuuuaeeuuuuuuuuuuuuuuut setting, where any subset of users of size q < n may collude by sharing all the secrets to which they have access.
Definition F.1 (Sec-f-LDP against -utcu-obut-curious users colluding at level q.). We say an al- gorithm A satisfy Sec-f-LDP against honest-but-curion users colluding at level y if it satisfies Sy-Sec- f-DD for any I with [[] 5 q.
F22
Proof of Section
Proof of Theorem 4.2 Suppose there are out of n users that are colluding. We assume that each round of the algorithm satisfies /-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.j. and Zi., are sampled from Gaussian distributions. As result, the output at each iteration is Gaussian distribution due to the linearity of gradient updates and the additive Gaussian noise. This
22

---

setup is consistent with prior analyses e.g., adopt the same assumption in their RDP-based analysis of SecDP.
Therefore, by definition, Algorithm
2 is Sec- f- with
/ = T(W(0, E), E));
for some vector with || = A. Here, the covariance E has the form
Σ 0 L Dr-n-
where ooor is the correlated noise, hp is the independent gaussian noise, and L is the Laplician matrix of the graph.
suffices figure the expression of μ in order lower bound the above f by the trade-off function between Gaussian distributions. A straightforward calculation shows that
T(N(0, (p,, Σ)) GDP).
= 1/2 In-9)) Glj
where G|AA| = (ON 1), (1 1)) is the trade-off function for the Guassian case (i.e., ||
Note that the the eigenvalues of Σー can be sorted as Tp to An T with each eigenvalue smaller than or
Moreover, the largest eigenvalue 7pp can be achieved since Σ-11 dbn 1, where 1 is vector of ones. As result, using the Spectral decomposition, have
A
M = n -
A
sup
Σ x
(n
Do
DP
x=|==1,*110
Since
sup
σ + A2 cor
||x|=1,> 211xxx111 1=0
we obtain
|a S A (n (n- T)
o + (L)
G Technical Details for Converting f-DP to (e, DDD
When converting f-D to 8)-P), particularly for addressing composition in Theorem employ the Privacy Loss Random Variable (PRV) and leverage numerical composition techniques as detailed in [57 36 29). Recall the hockey-stick divergence H--(-11) that corresponds to the (c, dD-P.
Theorem G.1 (Privacy loss random variable for mixture distributions). For mixtures distributions
P Em w. P. and Q = Ei= w, W.Qu it holds (=l(Q()) S H (XI))) where
X = i log (:(w)
p.(w)
~ Ps
q: (w)
Y| = i~ log
W ~ qs
pi (:(w)
with being the indices such that P[]
wi
Remark. In Theorem G.I X and Y are called privacy loss random variables in 29 Thus, we can
the numerical composition method in 29 to compute the composition in Theorem 4.1
To apply the numerical composition in 29), it is enough to clarify the CDF Y. Note that is mixture of log pe(C.) C Q, with weights w;. As each f is a Gaussian trade-off function, both X and Y are mixture of Gaussian distributions.
alGa)
23

---

Corollary G.1. Let P: = ((0,1) 1) and Q - N 1) (thus, T(P,, Qi) is pDGDP), For the privacy loss random variable Y defined in Theorem G.I the edf of Y Fy Di= Fiy) with Fi(y) 40
Here & is the edf of standard normal distribution.
Corollary G.2. The PRV for lsg
psingl is Yig Piş where Pij has cdf Et=1 w/y 1 (
with pie
being defined in Lemma 4.2
Proof Theorem Let E and Çr be the random variable such that Ey] iN P; and T/
Qi Then, according to [1]. the right-hand-side of s.mma.B.1js ((1,,)) and T(P,Q) 2 (Sr Cr). By the Blackwell Theorem, the privacy loss of and Q bounded by that of čr and Sr and is enough to specify the PRVs of & and {,. We denote by P and Q the distribution of & and ( with pdf's and q, correspondingly. Then, according to [29], the PRV X for and Er is
((Er)
X, = log P(E))
& ~ P.
Now clarify the distribution of X. By the law of total probability, have
n
P
w,P[X S t/. s).
We end the proof by noting that
7
T= i
P(Er)
9i (E:)
with Ei = EI i) P..
Ps
H
Additional Experiments
H.1
Comparison with RDP-based Methods
Comparison with RDP on synthetic graphs. compare the performance of our f-DP-based account with the previous RDP-based one, we consider several synthetic (and real-life) graphs with their details Table For completeness, we visualize the synthetic graphs in Figure
Interestingly, the structure of the privacy budget matrices from both methods aligns with the com- municability matrix, originally introduced by (15). Defined as eW, this matrix quantifies how well-connected any two nodes are and is commonly used to detect local structures in complex net- works 220 While our fD- analysis does not yield closed-form expression in terms of w the empirical patterns suggest that the underlying graph topology plays similar role in shaping the privacy guarantees.
Graph name
# nodes
# edges
Aa
T
Results
Hypereube
80
0.33333
275
Figure
Cliques
18
48
0.05634
1300
Top row in Figure
Regular
24
36
0.10124
320
Bottom row Figure
Expander(8)
28
1280
0.22222
2 104
Top in Figure
South
89
0.08209
110
Figure
Expander(11)
211
13312
0.16666
2 1
Figure
Table 2: Details of the considered graphs.
24

---

Hyperembe
Cleypes
Reguler
Expadde;:
Figure 4: Visualization of synthetic graphs.
303
Commurassbby
plct
53
Dxse (illligg
10-
-5
1G
16
38
(a) Pairwise privacy budget for 10
(b) Communicability
W
(c) for different 6's.
Curs
RDP
Communssiiity
125-
200-
25
10
RDP
1001 (etinng SD4)
20
20
10
20
(d) Pairwise privacy budget for 8 = 10-5.
(c) Communicability w
(f) for different 8*s.
Figure 5: Comparison of the numerical conversion to (e,6) on the clique (top) and regular (bottom) graphs.
Ouns
RDP
0
6
30
30
10
20
30
10
20
30
Our
RDP
(a) Pairwise privacy budget for 8 = 10
(b) Mean privacy budget for ó = 10
Figure 6: Enhanced privacy budget by our PN-f-DP methods on Davis Southern women's 's social network.
Privacy budget on a real graph. Finally, we consider a real-world graph well-suited for community detection; the Davis Southern women's 's social network [53]. has 32 nodes which corresponds to bipartite graph of social event attendance by women and has been previously used by [51] 34 [5]. We present matrix of pairwise privacy budgets in Figure ((a) and the corresponding mean privacy budget (the average of fj,j across all nodes i linked to node j) in Figure 6(b) our PN-f-DP privacy accounting method consistently produces a smaller privacy budget, as indicated by the lighter colors compared to the RDP results.
25

---

H.2 Details and Results on Private Classification
Baselines and setups. Our work primarily theoretical, with the main goal of introducing a general and tighter privacy accounting framework for decentralized learning. The experimental evaluation serves two purposes: (i) to validate the theoretical privacy bounds under various conditions (graph structures, noise levels, and user settings), and (ii) to ensure fair comparisons by following prior setups-partticulayy PN-RDP [55 and DecoR
To exclude the effect of the slack parameter Nn we adopt the standard implementation strategy suggested in [15 Remark 5]. Specifically, once node reaches its maximum allowed number of contributions, it stops participating in updates and only adds noise if revisited. This mechanism guarantees that the number of compositions per user never exceeds the analytical bound. In particular, when cryptographically small &r,, requires very large upper bound on the number of contributions, this approach limits the actual number of communications while still preserving privacy by adding noise as needed. We apply this mechanism consistently in all PN-RDP experiments (largely because our implementations build upon their released code).
More results private logistic regression. The results for smaller network with 2 and e = 10 are presented Figure 2 Figure shows the corresponding results for n 2 under other privacy levels e E (8, 5, 3}. where we observe a similar pattern. The counterparts for larger network with n = 2 are shown in Figure 7 All experiments are conducted on a CPU cluster with 200 GB of memory. Computing the privacy budget for all node pairs takes approximately 1-4 hours, depending on the graph structure, while the logistic regression itself completes within 2-3 minutes.
1.0
(oo tolee"
6x
Local DP-CI
0.9
TW EP-GD with RDP
DP-CD (hittix tims) RDP suse
0.-
1x
IW DPVGD wabh J-DP wotes
0.6
Ubjetivv
10"10"1
Decostrilzed DP-GD (co siaec]
Local SGD
0.3
TWW BPFGD with (lerting time) RRP soler
DP-SCD J.DP
2500
5000
T100
12000
12000
15000
19600
2000
0
2500
5000
T003
12500
1500
2000
Deration
Derition
(a) Objective function.
(b) Testing accuracy.
Figure 7: Private logistic regression the Houses dataset with 2 I. 0.4 and 8.
More results on private image classification. In addition to the previous private logistic regression experiment, we further evaluate our methods on an image classification task using the MNIST dataset The noise variance used for private training are listed in Table 3 and the evaluation follows the same privacy setting and plotting conventions.
338
The model we use is a simple convolutional neural network (CNN) with two convolutional layers followed by two fully connected layers. Specifically, the first convolutional layer applies 16 filters of size 8 x 8 with stride 2 and padding 3. The output is passed through a ReLU activation and a 2 x 2 max pooling layer with stride The second convolutional layer applies 32 filters of size 4 with stride 2, again followed by ReLU activation and another 2 x 2 max pooling layer with stride 1. The resulting feature maps are flattened and passed through fully connected layer with 32 hidden units and ReI.U activation, and finally mapped to 10 output logits corresponding to the digit classes.
The PyTorch implementation of the model is shown below.
class MNIST_CH CNN (nn Module):
def __init__ (aelf):
super ()._inntt__. ()
self convi mn. Conv2d (1, 16, 8, 2, padding-3)
self conv2 mn. Conv2d (16, 32, 4, 2)
self.fc1 nn. Linear (32 4 4, 32)
26

---

Locd DP SGD
0.5
ISW DP-SGG with RDP
FSk nP-Son with F-P onde
Acumery
x 1.r..
Traning
0.3
Decentmiizd DP Uso 20lo)) Local DPFSGD
0.1-
4
DE-SGD RDP
IBV DP SCD with (Litiing tins)) RDP uckeo
SCD with
0.1
2000
3000
7200
10000
12500
15000)
17700
210033
2200
3000
7200
10020
12500
15000
17500)
2000
Beeaaton
Beeaaonn
(a) Objective function.
(b) Testing accuracy.
107
1.0-
noiee)
Local DESSGD
IW DP-SGD weth HDP
DP-SCD
0.5
IWV DP SUDD waz J-DX mike
Traning olu
Brrosttaalins IM (no (ndee)
Locnl DDV-9GD
ESW DP-SCD with (hittins, tinse) RED mie
BOW UP-SUD
5000
3000
75/0
10000
13500
15000)
17500
200000
2500
5000
7500
10000
12500
18000
17500
23000
Tirration
Iteration
(c) Objective function.
(d) Testing accuracy.
107
1.2
Decortalind DP (un mose)
Locel DMAGG
IW DP-SGD with (lanting time) RDP srder
RW DI-SCDD f-DP
Thes Arnmay
Traniing Loee
Decostmlaed DP (so anios)
6.4
4x
JBW 3P SCD with RDP usiee
BWV DP DP-SCD with (Lirting time) RDP ocier
0.2-
/-D2
2500
3000
7500
12500
15000)
17700
20000
15000
17500
Becation
(e) Objective function.
(I) Testing accuracy.
Figure 8: Private logistic regression on the Houses dataset with n = 2 and J. = 0.4. Results are shown for (top), e (middle), and (bottom).
self . fc2 nn Linear (32, 10)
def Servard(sel: x):
= p.relu(self convi (x))
[B 16, 14. 14]
F.max_pool2ddz, 2, 1)
[B. 16, 13,
13]
11
F.relu conv2 (x))
[B, 32, 5, 5]
10
F.max_pool2d(x, 2, 1)
[B, 32, 4, 4]
13
x.view 32 4 4)
[B, 512]
A.relussel fel ffl.fffci00 (x)) (x))
[B, 32]
self (x)
[B, 10]
More results related noises 2² For a detailed comparison, the computed noise variances are reported Table shown, our f-DP-based privacy accounting method consistently requires smaller noise variance achieve the same differential privacy guarantee. This improvement arises
27

---

1.0-
1.6
Excettmmzed DP (20 asis))
Res Amcunos
Deoentraliodd D? (oo miba))
066
Tribinn
20V DP-SCD with RDF ooeer
F0 DP-SGD with RDP mase
T0V DP-SGD with (bitring RDP
FOR DP-SGD with (bitting rink RE57
D
gstel
8.3-
0.0
20001
9000
0000
50000
10020
12h00
14000)
2000
4070
C4000
.500
20000
12000
19000
Iterotion
(a) Objective function.
(b) Testing accuracy.
1.0-
2.-
0.8-
Deeestmmized
Acconey
Droestraleed
Local SGD
Local DP-SCD
30 UP-SCD with RDF nobic
BW DP SP-SGD with RDP miee
2.0
(bitcieg
20 DP-SCD wills J.P uolse
BW DP-SCD with J-DP adko
02-
0.0
20001
4000
0000
10020
12400
140m)
2000
4000
650m
10000
12100
Eneraction
Investton
(c) Objective function.
(d) Testing accuracy.
10"
Decertrsitod TIP motee)
Lacal DPP SGDD
20
DF-SCD RDP
DP-SGD (bitring time) oution JIW DP-SUD wits S.P wole
1.5
Docutralaed (so misc)
Toof ACMEOSS
Local BP-00
Thaiding
DD-SGD (henting Emme
BW DP SCD with /-DP sose
0.5
1000
(c) Objective function.
(f) Testing accuracy.
Figure 9: Private logistic regression the MNIST dataset with n 2 and L = 1. Results are shown for (top), c (middle), and (bottom).
from the tighter nature of f-DP accounting, which provides a more accurate characterization of privacy loss than RDP-based methods. Consequently, the added noise causes less degradation the non-private algorithm, leading to better overall utility.
Additional studies on 8. In the main text, set 8 10-5 to align with standard DP practice, where 5 is typically chosen to be smaller than the inverse of the total number of data points. For example, in the MNIST dataset, which contains 70,000 samples, choice satisfies 8 = 10 10-5 1/70,000. This convention is widely adopted prior work.
One potential concern is that this choice of corresponds to instance-level privacy, where the replacement of a single data sample is considered. contrast, our main analysis focuses on user-level differential privacy, common setting in FL, where the entire local dataset of a user may be changed.
28

---

Data
Decent. DP-GD
Local DP-GD
RDP noise
RDP noise (hitting time)
J-DP noises
2
10
0.4
House
5.20637
0.81593
0.74999
0.32468
2
10
0.4
House
15.8605
1.21531
0.77421
0.74468
2
8
0.4
House
19.0823
3.62771
3.20279
0.88906
28
5
0.4
House
28.6394
5.54329
4,89283
1.30494
28
3
0.4
House
45,4803
8.92327
7.87766
2.01376
2
10
MNIST
39.6513
2,98459
2.63431
1.86179
2
8
MNIST
47.7058
3.62772
3.20279
2.22045
2
5
MNIST
71.5985
5.54275
4.89298
3.26196
Table 3: Computed a for all involved algorithms.
In such cases, should instead be defined relative to the number of users rather than the total number of data samples.
To address this concern, we conducted additional experiments using 1/ /nmumberr of users) instead of 1 //numberr of total samples). This adjustment results in larger 6, effectively relaxing the privacy constraint. As expected, this leads to improved utility. The updated results, summarized in the table below (to be included in the revised manuscript), show that our method continues to perform strongly under this revised setting. Notably, RW DP-SGD with f-DP noise consistently outperforms all baselines, confirming its effectiveness in achieving favorable privacy-utility trade-off.
No Noise
Local
RW DP-SGD
RW DP-SGD
RW DP-SGD (f-DP)
#Nodes
SGD
SGD
(RDP)
(Hitting RDP)
2
3
0,9614
0.7407
0.8242
0.7829
0.9534
2
5
0.9618
0.8196
0.8912
0,8673
0.9574
28
3
0.9615
0.5445
0.8328
0,8298
0.9551
28
5
0.9615
0.5969
0,9004
0,8994
0.9577
Table 4: Comparison of test accuracies on MNIST dataset under varying and number of nodes.
H.3
Details and Results for Correlated Noises
Evolution the loss
Evoludoo of Loss
SerttP LD>
LSP
1000
2009
1950
20:0
500e
4001
5000
Step rumber
Step number
Agarow
Agaattm
3x22
20000-
Sec4ADP
Secioo
Ang
2xt04
Fing
Step number
Figure 10: Optimality gap vs. iteration steps for Alg. accounting methods with =3 (left upper), 5 (right upper), (left bottom), and 10 (right bottom). Our methods perform well when the budget e is small.
2 on logistic regression using different privacy
Our experimental setup for correlated noise follows 2
We evaluate our method on the MNIST dataset [38), partitioned among 16 users simulate decentralized learning environment. Two network topologics with different levels of connectivity considered: ring and 2D torus (grid).
29

---

The Massings mixing matrix is utilized for model averaging across these topologies. All experiments are conducted over 5000 communication rounds for logistic regression, and 1000 communication rounds for MNIST classification. Each user updates their model parameters and exchanges information with neighbors defined by the network topology. We repeat each experiment with four different random seeds to ensure reproducibility. We use their code in our evaluation: https://gg thub com/ S..firduussiaab/DDI iteration steps for Algorithm 2 on logistic regression with privacy budgets E {3, 5, 6, 7). As evident from the plots, our method performs particularly well in the low-privacy regime, achieving smaller optimality gaps when the privacy budget is small.
Figure [goure[[0shin shows the optimality gap versus
I Broader Impacts
This paper proposes improved privacy accounting techniques for decentralized federated learning (FL), which can positively impact user data protection in sensitive applications such healthcare, finance, and mobile systems. By reducing the amount of noise needed to achieve rigorous privacy guarantees, the proposed framework can help improve the utility of crivacy-preservin models in real-world deployments. On the other hand, as with any privacy technology. there is a potential risk that stronger privacy accounting tools could be misused to justify under-protective practices or give false sense of security if applied incorrectly. We encourage practitioners to use these methods with clear understanding of their assumptions and limitations and recommend combining them with practical audits and monitoring tools in deployment.
J Limitations
First, the privacy analysis under f-DP assumes access to precise or tightly approximated trade-off functions, which can be computationally intensive to evaluate, especially for large-scale systems or long training horizons. Second, our results rely on assumptions such as fixed communication graphs and Markovian random walks, which may not hold in dynamic adversarial network settings. Third, while we provide both user-level and record-level analyses, we do not account for adaptive adversaries scenarios with heterogeneous trust levels beyond pairwise secret sharing. Fourth, our experiments focus on synthetic graphs and mid-scale real datasets, and results may not fully generalize to highly non-i.i.d. lcrge-scale production environments. Finally, approach does not currently support other privacy mechanisms beyond additive Gaussian noise, which limits its applicability alternative designs such clipping-free free post-processing-bssee schemes.
30

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Contributions are summarized in the introduction section.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Provided in Appendix J
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
31

---

Justification:
Each theorem is accompanied by a complete set of assumptions. Full formal proofs are included in the appendix. All referenced lemmas and external results are properly cited.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proof' can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
Experimental details are in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
32

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
We include our anonymized code as part of the supplementary material in this submission.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips) cc/pu
blic/
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
The paper includes a detailed description of the experimental setup, including dataset information, data splits, and the decentralized communication graph structures. Full implementation details are provided the supplementary material and code.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: The main experimental results are reported with standard deviation error bars across five or four random seeds.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
33

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative eтror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Detailed runtime and computational resource information is provided in Appendix H.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: The research adheres to the NeurlPS Code of Ethics. It promotes privacy- preserving machine learning through rigorous theoretical and empirical analysis without collecting or releasing sensitive data. All datasets used are publicly available and commonly used in the literature, and no human subjects or personally identifiable information are involved. The work contributes positively to the field by improving transparency, repro- ducibility, and safety in decentralized federated learning.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
34

---

Justification:
Provided in Appendix !1
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not involve the release of pretrained models, generative systems, web-scraped datasets. It focuses on theoretical analysis and empirical evaluation of privacy accounting techniques in decentralized federated learning, which poses no foreseeable risk of misuse dual-use.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging. and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
All the code packages or datasets are well cited.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
35

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use package should be provided. For popular datasets, paperswithcode com /ataaatasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's ' creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the datasct/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing research with human subjects.
Guidelines:
36

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does involve LLMs as any important, original, or non-standard components
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to LLM policy for what should or should not be described.
37


Reviews:
[{"review_id": "o18dAIOmpc", "reviewer": "Reviewer_vd4X", "summary": "This paper proposes a decentralized federated learning framework under f-DP constraints. The method quantifies privacy leakage between user pairs in a random-walk-based communication model and supports structured noise injection via shared secrets. By combining f-DP theory with Markov chain concentration, the paper introduces a novel form of privacy amplification that arises from communication sparsity, local updates, and correlated noise. Experimental evaluations are conducted on synthetic graphs with relatively small datasets.", "questions": "Address W1, W2, W3, and W4.", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strength:\n- S1: The proposed mechanisms, PN-f-DP and Sec-f-LDP, are well motivated and thoroughly defined with theoretical rigor.\n- S2: The privacy amplification analysis captures important structural properties such as communication sparsity, local iterations, and Markov hitting times. The resulting guarantees are tight and grounded in a strong theoretical framework.\n- S3: The method demonstrates improved utility–privacy trade-offs compared to Renyi Differential Privacy (RDP) baselines.\n\nWeakness:\n- W1: The paper omits relevant related work, particularly Network Shuffling (SIGMOD 2022) [1], which also considers decentralized privacy amplification through random walks on graphs. Although the privacy models differ, both approaches exploit similar assumptions. A discussion of this work and, if feasible, empirical comparisons in terms of privacy and utility would strengthen the paper.\n- W2: The experimental evaluation is limited to small, synthetic, and idealized graphs. In contrast, Network Shuffling has been validated on real-world graphs. Evaluating the proposed method on such realistic topologies would better demonstrate its practicality.\n- W3: The choice of privacy parameter δ is not appropriate. The paper commonly uses $\\delta=10^{-5}$, but standard DP practice requires $\\delta < 1/n$. This means $\\delta=10^{-5}$ is too large for settings with $n = 16, 32, 2^8, 2^{11}$. A more principled selection of $\\delta$ is needed. \n- W4: The application scope is unclear. For example, typical cross-device federated learning scenarios involve millions of users. It is therefore difficult to assess whether the proposed methods, evaluated only on small-scale graphs, can scale or generalize to real-world use cases.\n\n[1] https://arxiv.org/abs/2204.03919", "was_revised": true, "final_justification": "This paper introduces a theoretical framework for privacy accounting in decentralized federated learning (FL) under f-DP. While my initial concerns centered on the limited experimental evaluation, the lack of clarity around the choice of the $\\delta$ parameter, and the omission of real-graph validation, the authors have made meaningful clarifications and additions during the rebuttal.\n\nIn particular, they have added experiments using a $\\delta$ value appropriate for user-level differential privacy—addressing a key concern (W3) about the validity of the reported privacy guarantees. I also confirm that real-graph experiments are included in the appendix (Appendix H), which addresses W2 to a reasonable extent.\n\nThat said, I believe the paper would benefit from a clearer and consistent statement regarding whether user-level or record-level privacy is assumed throughout, and from ensuring that the final version includes results under the correct δ setting. I expect this revision to be appropriately reflected in the camera-ready version.", "rebuttal": "We sincerely thank the reviewer for their evaluation and feedback. The following are our responses to the questions.\n\n---\n\n**W1: Omission of related work on Network Shuffling (SIGMOD 2022)**\n\nWe thank the reviewer for highlighting the relevant work on **Network Shuffling** (\\[A]), which we will cite and discuss appropriately in the revised version.\n\nWhile \\[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.\n\nWe 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].\n\nOur framework provides **stronger privacy accounting** than \\[A] in two key ways:\n\n* 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.).\n* 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].\n\nIn 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.\nWe will include a discussion highlighting these conceptual and technical differences in the related work section.\n\n---\n\n**W2: Limited experimental evaluation on small/synthetic graphs**\n\nOur 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:\n\n* Validate the **theoretical privacy bounds** under various conditions (graph types, noise levels, user settings),\n* Follow and **align with prior setups**—especially PN-RDP \\[Cyffers et al., ICML 2024] and DecoR \\[Zhu et al., 2023]—to ensure fair comparisons.\n\nWe 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.\n\n---\n\n**W3: Inappropriate choice of $\\delta$ parameter**\n\nWe 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.\n\n---\n\n**W4: Applicability to real-world cross-device FL with millions of users**\n\nWe 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.\n\nMoreover, 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."}, {"review_id": "RZuf8ZjQUI", "reviewer": "Reviewer_PKwX", "summary": "The paper introduces Pairwise Network f-DP (PN-f-DP) and Secret-based f-Local DP (Sec-f-LDP) for decentralized federated learning (DFL) by accommodating communication sparsity, local iteration updates, and markov hitting times. The presentation is clear and well written. The paper has mathematical rigour and the experimental setup is clearly explained.", "questions": "1.\tCan the PN-f-DP and Sec-f-LDP frameworks be extended or adapted to asynchronous, gossip-based, or push-sum decentralized FL algorithms?\n2.\tIn real decentralized FL, users may participate unevenly (due to availability, energy, etc.). How would non-uniform participation affect privacy accounting?\n3.\tAre the Markov hitting-time based privacy amplification results information-theoretically tight, or is there room for further tightening? Could other probabilistic tools such as martingales, stopping times offer sharper bounds?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths \nBy moving from Renyi Differential Privacy (RDP) to f-DP, the authors derive sharper (ϵ, δ)-DP bounds, leading to lower noise requirements and better utility\nThe privacy analysis explicitly models privacy amplification effects due to sparse communication, Markovian random walks, and local iterations.\nThe framework is granular, providing both user-level and record-level privacy analyses, making it adaptable for varying privacy scenarios, The Sec-f-LDP component covers collusion models with shared secrets and correlated noise, which is practically relevant for trusted-user-group scenarios.\nThe authors validate privacy bounds both theoretically and empirically.\n\n## Weakness\n1.\tThe analysis is tightly coupled with random-walk-based communication and DecoR-style correlated noise protocols. Its generalizability to other decentralized FL protocols such as push-sum or asynchronous methods is unclear.\n2.\tThe collusion model in Sec-f-LDP only handles honest-but-curious adversaries. It does not address stronger that form larger collusion sets or rational adversaries who deviate from protocol behavior given enough incentives.\n3.\tThe privacy amplification analysis assumes properties like irreducibility and aperiodicity of the communication graph’s transition matrix. This limits applicability to certain graph topologies and excludes sparse or poorly connected graphs.\n4.\tThere are few a typos and incomplete data. For instance, Algorithm 2 doesn’t contain Output.", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their evaluation and feedback. The following are our responses to the questions.\n\n---\n\n**Q1 & W1. Extension to other decentralized FL algorithms (asynchronous, gossip-based, push-sum):**\n\nYes, 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.\n\nWhile our current analysis focuses on random-walk-based communication, the core reasoning can generalize. For instance:\n\n- 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.\n\n- 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.\n\n- 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.\n\n\nThus, while each new protocol requires re-deriving the mixture weights and update structure, the *f*-DP accounting framework remains applicable and advantageous.\n\n---\n\n**Q2. Impact of non-uniform user participation:**\n\nOur 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.\n\nThat 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.\n\n---\n\n**Q3. On the tightness of Markov hitting-time–based amplification:**\n\nWe 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.\n\nWhile 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**.\n\n---\n\n**W2. Limitations of the collusion model in Sec-f-LDP:**\n\nWe 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.\n\nAddressing 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.\n\n---\n\n**W3. Assumptions on the communication graph (irreducibility and aperiodicity):**\n\nThis 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.\n\nNevertheless, 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."}, {"review_id": "RILJiDcQ9S", "reviewer": "Reviewer_CkH2", "summary": "This work analyzes the differential privacy of two forms of federated forms of DP-SGD where model updates are performed locally by users and shared with other users according to a communication graph.\n\nIn the first considered algorithm, users update the model sequentially according to a random walk on the communication graph and share the updated model with the next user.  \nThe considered privacy notion (PN-DP) requires for all pairs of users $(i,j)$ that the weights released by user $j$ are user- or record-level DP w.r.t. changes of the data of user $i$.  \nThe proof largely proceeds as follows: It can be shown that, with some probability,  user $j$ is selected after user $i$ at most $T'$ times. One can thus derive privacy guarantees for the \"$j$ receives data after $i$\" sub-mechanism and then use privacy accounting to evaluate the $T'$-fold adaptive composition. The sub-mechanism can be decomposed into a random mixture based on hitting times. It's privacy can be upper-bounded via joint concavity of $f$-DP. Each mixture component's privacy can be evaluated by applying known amplification-by-iteration guarantees (which capture the randomness in update steps of users other than $i$ and $j$). The result can be generalized to record-level privacy by considering amplification-by-iteration with subsampling.\n\nIn the second algorithm, all users have their own model weights. They combine their local updates with local updates of adjacent users in parallel.  The considered privacy notion (Sec-LDP) requires that all weights released by the algorithm are DP, assuming some set of secrets shared between different users $i$ $j$ remains hidden. The proof largely revolves around simplifying the trade-off function between two anisotropic Gaussians induced by aggregating parameter noise based on edge weights.\n\nThe privacy guarantees for the first algorithm are evaluated on some set of synthetic communication graphs from prior work. They are shown to be stronger than RDP-based guarantees from prior work. Then, an improved privacy--utility trade-off is demonstrated for federated learning and MNIST housing (again following prior work). Finally, another toy dataset (a9a) is used to demonstrate an improved privacy--utility trade-off for the second algorithm across different synthetic communication structures.", "questions": "Depending on the response to the following question, I will raise my score from \"borderline accept\" to \"accept\":\n\n* Do the baseline's privacy guarantees also only hold with some probability $\\delta'_{T,n}$?\n* If not: How do you account for this slack $\\delta'_{T,n}$ to ensure a fair comparison? Is it just added to $\\delta$ after privacy accounting?\n* If you do not account for it: How large is this $\\delta_{T,n}'$ in your experiments?\n* Could you provide a brief explanation of why the two anisotropic Gaussians in the first equation of Appendix F constitute a valid $f$-DP guarantee under the considered privacy notion? A reference to some other paper is also fine.\n\nThe following is just out of curiosity and will not affect my score. Feel free to ignore it or use a non-rebuttal comment field if a response would exceed your character limit:\n* Ultimately (Appendix G), you derive dominating pairs that attain certain hockey-stick divergences / $(\\epsilon,\\delta)$-DP privacy profile. The experiments are conducted using standard privacy accounting (i.e., not Gaussian DP accounting). So what is the motivation for focusing on $f$-DP instead of $(\\epsilon,\\delta(\\epsilon))$-DP for all definitions and main results? Is it to more easily integrate existing amplification-by-iteration guarantees?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Disclaimers:\n* I made an effort to understand the proof strategy in detail, but did not check every equality for correctness\n* I am familiar with (f-)DP literature, but not with federated learning\n\n## Strengths\n* The proof strategy seems sound, i.e., all results are theoretically well-supported\n* Limitations are openly discussed (albeit in the Appendix)\n* The analyzed algorithms appear like practical methods for federated learning and have already been studied in prior work. Thus, I would assume that improving upon their privacy analysis is likely to have some impact -- at least on this sub-field of graph-based federated learning.\n* As someone not familiar with federated learning, I still found it easy to understand the considered algorithms and privacy notions due to the well-written background section (except for some missing exposition around Definition 3.4, see below)\n* In general, the paper is clearly written and chooses a very good level of abstraction for the discussion of the main results in Section 4\n* The experimental setup is directly based on prior work, which speaks for the fairness of the conducted experiments\n* Experiments are conducted with multiple random seeds and error bars are erported\n\n---\n\n## Weaknesses\n\n### Main Weaknesses\n* Section 3 introduces the desired forms of privacy, which are $f$-DP adaptions of existing concepts. However, the conducted analysis actually only guarantees $f$-DP with some probability $\\delta'_{T,n}$.\n* This probability $\\delta'$ depends on the communication graph's spectral gap. It is not clear how large this $\\delta'$ is in the considered experiments. Especially if $\\delta' \\ll 1$, this slack may give an unfair advantage compared to prior work and could (potentially) be the only reason why an improved privacy--utlity trade-off is attained. I believe that $1 - \\delta'$ could potentially be added to the $\\delta$ of $(\\epsilon,\\delta)$-DP for a fair comparison, but this is not discussed in Appendix G.\n* The proof of Section 4.7. begins with stating that algorithm was $T(P,Q)$ f-DP with some Gaussians $P$ and $Q$. It is not clear why this should hold under the considered collusion setting. (I admit that this statement may be obvious to readers intimately familiar to readers familiar with Sec-f-DP. But since that paper is less than a year old, I would not necessarily treat it as common knowledge.)\n\n### Minor weaknesses\n* The main result is based on bounding mixture trade-off functions via joint concavity. From Theorem G.2, it can be easily inferred that this is equivalent to bounding mixture hockey-stick divergences via joint convexity. Going by experience, such bounds can be incredibly loose compared to tight guarantees. It would have been good to derive optimistic bounds (lower bounds on hockey-stick divergences / upper bounds on trade-off functions) to assess the tightness of the guarantees.\n* There is not sufficient exposition for Definition 3.4 to understand what \"secrets\" and \"conditioning on secrets\" means without consoluting prior work by Allouah et al.\n* Section 4.3 seems to only consider a special case of the privacy notion from Definition 3.4 by constraining it to \"honest-but-curious collusion at level q\". Again, the exposition is not sufficient to follow this subsection without looking into prior work by Allouah et al.\n* MNIST, UCI housing, and a9a are not sufficiently complicated or large-scale datasets to make any meaningful inferences about privacy--utility trade-offs in practical settings. But since this is mostly a theoretical work, I would not consider it a major issue.\n\n---\n\n### Small fixes\nThe following are just miscellaneous comments and do not affect my score.\n\n* Definition 3.4 mentions \"for any neighboring datasets\", but does not specify the neighboring relation (user-level or event-level?)\n* Algorithm 2 does not specify how the local models are aggregated into a final model for evaluation in the experiments\n* Typo in ll. 357-363: \"related noise\" --> \"correlated noise\"\n* It might be nice to also introduce \"standard\" Sec-DP in Section 2.2 before introducing Sec-f-DP in Section 3, as was done with PN-DP. That would further improve the reading follow.\n* In Algorithm $1$ $W_{i,j}$ indicates that $i$ passes messages to $j$. In Algorithm $2$, $W_{i,j}$ indicates that $j$ passes messages to $i, which is slightly confusing but hopefully does not affect the theoretical analysis.\n* The connection between Theorem G.1 and Theorem 4.5 is not immediately clear, because the r.h.s. of Theorem 4.5 is not a trade-off function between mixtures, but a weighted sum of trade-off functions. The connection is somewhat hidden in the Proof of Theorem G.1 and the inequality in ll. 805. Maybe this could be made more explicit.\n* Gradient clipping seems to be missing in Algorithm 1\n* ll. 169 suggests that the noise is \"scaled by the $\\ell_2$-sensitivity $\\Delta$\", but looking at Algorithm 1 and the $\\Delta \\mathbin{/} \\sigma$ terms in Lemma 4.3, this does not appear to be the case\n* It is not clear what \"differ in single record\" and \"differ in all records\" in ll.150-151 means. Substituting with another record? Or adding/removing a record?\n\n---\n\n## Conclusion\nOverall, I think that this is an expertly written paper that appears to make a meaningful theoretical contribution towards better privacy analysis for graph-based federated learning (although I can not really make a fully informed statement about it's relation to the broader federated learning literature).\nMy main reservation is around the fact that the $f$-DP guarantees only hold with some high probability, which is somewhat obfuscated and may result in an unfair comparison with prior work. If the authors can address this concern, I will increase my score to \"accept\".", "was_revised": true, "final_justification": "I had two main concerns:\n* Fairness of comparison with baselines due to bounds only holding with high probability\n* Derivation for one of the main results not being entirely clear\n\nBoth concerns were adequately addressed through the rebuttal.\n\nAfter reading the other reviews, which do not raise any points that I find especially problematic, I have decided to increase my score to \"accept\".", "rebuttal": "We sincerely thank the reviewer for their detailed evaluation and feedback. The following are our responses to the weaknesses and questions.\n\n---\n\n**W1. On the use of the additional \\$\\delta\\_{T,n}'\\$ term in Theorem 4.5:**\n\n1. **Purpose of the term:**\n   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\n$$\n\\delta_{T,n}' = \\exp\\left( -\\frac{1 - \\lambda_2}{1 + \\lambda_2} \\cdot \\frac{2 \\zeta^2 T}{n^2 M} \\right).\n$$\nThis bound enables us to derive a clean expression for the composed trade-off function in Theorem 4.5:\n$$\n\\left( f_{ij}^{\\mathrm{single}} \\right)^{\\bigotimes \\left\\lceil (1 + \\zeta) T / n \\right\\rceil}.\n$$\nIf 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. \n\n2. **Precedent in prior work:**\n   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](https://arxiv.org/pdf/2402.07471)). 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. \n\n    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.\n\n3. **Truncation trick in practice:**\n    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.\n\n4. **Why our improvements are not due to \\$\\delta\\_{T,n}'\\$:**\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:\n\n   * **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).\n\n   * **Lossless composition via *f*-DP:**\n     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.\n\n**In summary:**\nWe 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. \nOur 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**.\n\n---\n\n**W2. Clarifying the Gaussian assumption in Theorem 4.7**\n\nWe 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.\n\nAs 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.\n\nMoreover, 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.\n\nWe 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**\n\n---\n\n**W3. On the tightness of using joint concavity for mixtures**\n\nWe 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.\n\nWhile 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.\n\nAs 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.\n\n---\n\n**W4. Clarification on Definition 3.4 and honest-but-curious collusion**\n\nWe 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.\n\nDue 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.\n\n---\n\n**W5. Why \\$f\\$-DP is used**\n\nWe chose \\$f\\$-DP because it offers two distinct advantages:\n\n* **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.\n* **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.\n\nWe 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)."}, {"review_id": "uMl1ipbqrZ", "reviewer": "Reviewer_RYQa", "summary": "This paper proposes to extend two existing differential privacy approaches for decentralized learning to f-differential privacy, adapting and improving two existing algorithms. The first is Pairwise Network Differential Privacy with random-walk-based DP-SGD, and the second is Secret-based Local Differential Privacy, with the adaptation of a recent gossip-based algorithm with correlated noise. The paper provides clear definitions for PN-f-DP and Sec-f-LDP, and then derives privacy guarantees. The authors then illustrate their methods on several graphs and datasets, showing that their precise accounting leads to a significant improvement in the privacy-utility trade-off.", "questions": "As the paper is already very clear, these are mostly open questions that do not require a full answer for me to support the paper.\n\n* Do you think your accounting methods for the algorithms are tight? If not, where do you think it is possible to improve, and if yes, do you think it is possible to prove lower bounds?\n* Is it costly to compute the privacy guarantees with your method?\n* Is it possible to extend this approach to time-evolving topologies?\n\n**Some very minor typos/comments:**\n\n* In the algorithms block of DecoR, the indices \\${i \\in V}\\$ are missing in the Input line.\n* In the definitions, section 3, you use \"and two datasets.\" I believe it would be less ambiguous to say \"and for all pairs of datasets,\" as the quantification is not obvious otherwise.\n* In line 244, the recap of the definition of \\$w\\_{ij}\\$ is unclear because it does not mention \\$i\\$.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n* The paper demonstrates significantly better privacy-utility trade-offs compared to existing methods, which could make a real difference in implementing these algorithms in practical applications.\n* It successfully combines the power of \\$f\\$-DP with existing approaches for decentralized learning, detects slackness in previous proofs (for instance, concerning the probability of hitting time), and improves upon them.\n* The paper is easy to follow and recaps all the necessary results. It is a very well-written paper.\n* The paper is quite complete in terms of results, covering various adjacency relations and the DecoR algorithm, which is quite recent, so the paper is state of the art.\n* The numerical experiments are convincing. They test on MNIST and Housing, which are the datasets used in previous papers, making the comparison easy to follow, and they test various graphs, allowing the reader to see that the privacy guarantees are coherent with the graph topology. The code is also provided and seems reasonable (I haven't run it, but I browsed it and it seemed to be a reasonable adaptation of the code from the existing papers they build on).\n\n\n**Weaknesses**\n* The paper could be seen a bit incremental as it adapts existing algorithms, but it clearly required significant amount of work.\n* There is maybe improvements to do with respect to f-DP: my impression is that in fact only Gaussian DP was used, but I am not familiar enough with f-DP to judge if it is indeed a limitation.", "was_revised": true, "final_justification": "Good paper that should be accepted", "rebuttal": "We sincerely thank the reviewer for their thoughtful and encouraging comments. Below, we address the open questions and clarify some points raised.\n\n---\n\n **W1. On originality and integration of prior work**\n\nWhile 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.\n\n---\n\n**W2. On generality beyond Gaussian DP**\n\nWe 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.\n\nOur 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).\n\n---\n\n**Q1. On tightness and potential improvements**\n\nOur 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.\n\n---\n\n**Q2. On computational cost**\n\nComputing 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. \n\nThe 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.\n\n---\n\n**Q3. On extension to time-evolving topologies**\n\nYes, 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.\n\n---\n\n**Minor comments**\n\nWe 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)."}, {"review_id": "UMpMgoRh5q", "reviewer": "Reviewer_UhHE", "summary": "This paper tackles privacy accounting for two decentralized federated learning (FL) algorithms using the f-differential privacy (f-DP) framework. The authors introduce two novel f-DP accounting schemes tailored to decentralized environments: Pairwise Network f-DP (PN-f-DP), which quantifies privacy leakage between user pairs under random walk communication patterns, and Secret-based f-Local DP (Sec-f-LDP), which allows for structured noise injection using shared secrets. Leveraging f-DP theory and Markov chain concentration tools, their framework effectively models privacy amplification resulting from sparse communication, local computation, and correlated noise. Experimental results on both synthetic and real-world datasets show that these methods produce consistently tighter $(\\epsilon, \\delta)$ privacy bounds and better utility compared to Rényi DP-based approaches, highlighting the strengths of f-DP for privacy accounting in decentralized learning.", "questions": "- The discussion on related works are relatively compact and limited. The authors generally discussed the DP notions in FL and privacy amplification in  Section 1.1. Local DP can also be applied in FL. What are the difference and pros/cons when compared with this work? Additionally, it would be better to clearly discuss more related works, especially for those with prior knowledge mentioned in Appendix. A comprehensive literature study makes the contribution more clear.\n\n- The experimental comparisons are mostly focusing on decentralized DP-GD, local DP-GD, and our random-walk-based DP-GD. It should be better to consider some more concrete proposed SOTA solutions in FL.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n+ The authors propose a new f-DP notions for decentralized FL.\n+ This paper develops a PN-f-DP analysis that captures privacy amplification from: (i) communication sparsity, (ii) local iteration updates, and (iii) Markov hitting times. \n+ Empirical results show an improved privacy-utility trade-off and a tighter bound.\n\nWeakness\n- The discussion of related  works are very compact. \n- The experiments are not sufficiently compared with prior research.", "was_revised": true, "final_justification": "Thanks for solving my concerns. I have updated the rating.", "rebuttal": "We sincerely thank the reviewer for their comments. Below, we address the two main concerns regarding related work and experimental evaluation.\n\n---\n\n**1. Related Work and Comparison with Local DP**\n\nWe 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.\n\nTo provide additional clarity, we will append the following paragraph to the end of the **\"DP notions in FL\"** paragraph in the related work section:\n\n> *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.*\n---\n\n**2. Experimental Evaluation and Baseline Scope**\n\nThe 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.\n\nTo 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.\n\nWe 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.**"}]

Author rebuttal:

Meta-review: ## Metareview

This paper studies decentralized federated learning (FL) scenario where there is no central server and the communication between the nodes happens at random. While the notion of local differential privacy (LDP) can be used in this setting, it is overly pessimistic (since it assumes e.g. that all except one nodes collude). Thus, two notions that more realistically captures the privacy guarantees in this model have been proposed: Pairwise Network DP (PN-DP) [Cyffers et al., ICML 2024] and Secret-based Local DP (Sec-LDP) [Allouah et al., ICML 2024]. The main contribution of the current work is to give significantly tighter privacy analysis within these frameworks.

More specifically, the aforementioned previous work focuses mostly on analyzing their privacy analysis through Renyi DP (RDP). However, as is known in central DP, privacy analysis through RDP can be quite loose and the notion of $f$-DP, which more tightly characterizes the privacy loss, can significantly improves upon RDP in the centralized setting. The technical contribution of this work is to apply $f$-DP to the decentralized setting under PN-DP and Sec-LDP frameworks. This requires the authors to overcome several technical challenges that arises due to the random nature of the communication. At the end, the authors achieve privacy guarantees that (numerically) significantly improves upon the RDP guarantees.

## Strengths

- Decentralized FL is a natural and important setting. The paper gives a rigorous and more realistic privacy guarantee in this model.

- In the empirical evaluation, the method in this paper achieves significant improvements in terms of privacy budget (more than 2x improvements for $\\epsilon$ in most cases) over RDP-based methods. As expected, these also translate to improvements in model accuracy when trained using a fixed budget.

- From a technical perspective, the analysis requires subtly combining the communication pattern with $f$-DP analysis. The technique might be useful to future work on the topic.

## Weaknesses

- The current analysis is tied to random-walk-based communication and correlated noise protocols. It is unclear how general these techniques  can be applied. In a reply to reviewer PKwX, the authors addressed this by sketching how the core ideas of the analysis can still be applied to other scenarios. 

## Recommendation
This paper makes significant advances toward providing tighter and more realistic differential privacy guarantees in decentralized federated learning. Due to this, we support acceptance of the paper.
Decision: Accept (spotlight)