Muffliato: Peer-to-Peer Privacy Amplification for Decentralized Optimization and Averaging
Authors: Edwige Cyffers
Mathieu Even
Aurélien Bellet
Laurent Massoulié
Venue: NeurIPS 2022 Accept (2022)
Keywords: differential privacy
decentralized optimization
gossip protocols
privacy amplification

Abstract: Decentralized optimization is increasingly popular in machine learning for its scalability and efficiency. Intuitively, it should also provide better privacy guarantees, as nodes only observe the messages sent by their neighbors in the network graph. But formalizing and quantifying this gain is challenging: existing results are typically limited to Local Differential Privacy (LDP) guarantees that overlook the advantages of decentralization. In this work, we introduce pairwise network differential privacy, a relaxation of LDP that captures the fact that the privacy leakage from a node u to a node v may depend on their relative position in the graph. We then analyze the combination of local noise injection with (simple or randomized) gossip averaging protocols on fixed and random communication graphs. We also derive a differentially private decentralized optimization algorithm that alternates between local gradient descent steps and gossip averaging. Our results show that our algorithms amplify privacy guarantees as a function of the distance between nodes in the graph, matching the privacy-utility trade-off of the trusted curator, up to factors that explicitly depend on the graph topology. Remarkably, these factors become constant for expander graphs. Finally, we illustrate our privacy gains with experiments on synthetic and real-world datasets.

Muffliato: Peer-to-Peer Privacy Amplification for Decentralized Optimization and Averaging
Edwige Cyffers 1,* Mathieu Even Aurélien Bellet ', Laurent Massoulie
Equal contribution
Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189 CRIStAL, F-59000 Lille
Inria Paris Département d' d'informatique de I'ENS, PSL Research University, Paris, France
Abstract
Decentralized optimization is increasingly popular in machine learning for its scalability and efficiency. Intuitively, it should also provide better privacy guaran- tees, nodes only observe the messages sent by their neighbors in the network graph. But formalizing and quantifying this gain is challenging: existing results are typically limited to Local Differential Privacy (LDP) guarantees that overlook the advantages of decentralization. In this work, we introduce pairwise network differ- ential privacy, relaxation of LDP that captures the fact that the privacy leakage from a node u to a node may depend on their relative position in the graph. We then analyze the combination of local noise injection with (simple randomized) gossip averaging protocols on fixed and random communication graphs. We also derive differentially private decentralized optimization algorithm that alternates between local gradient descent steps and gossip averaging. Our results show that our algorithms amplify privacy guarantees as function of the distance between nodes in the graph, matching the privacy-utility trade-off of the trusted curator, up factors that explicitly depend on the graph topology. Remarkably, these factors become constant for expander graphs. Finally, we illustrate our privacy gains with experiments on synthetic and real-world datasets.
Introduction
Training machine learning models traditionally requires centralizing data in single server, raising issues of scalability and privacy. An alternative is to use Federated Learning (FL), where each user keeps her data device [44, 36). In fully decentralized FL, the common hypothesis of central server is also removed, letting users, represented as nodes in a graph, train the model via peer-to-peer communications along edges. This approach improves scalability and robustness to central server failures, enabling lower latency, less power consumption and quicker deployment [43, 11, 54, 50, 1, 42, 39].
Another important dimension is privacy, as a wide range applications deal with sensitive and personal data. The gold standard to quantify the privacy leakage of algorithms is Differential Privacy (DP) [20]. DP typically requires to randomly perturb data-dependent computations to prevent the final model from leaking too much information about any individual data point (c.g.. through data memorization). However, decentralized algorithms do not only reveal the final model to the participating nodes, but also the results of some intermediate computations. standard solution is to use Local Differential Privacy (LDP) [37, 19), where random perturbations are performed locally by each user, thus protecting against attacker that would observe everything that users share. From the
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

algorithmic standpoint, local noise addition can be easily performed within decentralized algorithms, as done for instance in [34, 6, 15, 60. 58]. Unfortunately, LDP requires large amounts of noise, and thus provides poor utility.
In this work, we show that LDP guarantees give very pessimistic view of the privacy offered by decentralized algorithms. Indeed, there is no central server receiving all messages, and the participating nodes can only observe the messages sent by their neighbors in the graph. So, a given node should intuitively leak less information about its private data to nodes that are far away. We formally quantify this privacy amplification for the fundamental brick of communication at the core of decentralized optimization: gossip algorithms. Calling Muffiitt the combination of local noise injection with a gossip averaging protocol, we precisely track the resulting privacy leakage between each pair of nodes. Through gossiping, the private values and noise terms of various users add up, obfuscating their contribution well beyond baseline LDP guarantees: as their distance in the graph increases, the privacy loss decreases. We then show that the choice of graph is crucial to enforce a good privacy-utility trade-off while preserving the scalability of gossip algorithms.
Our results are particularly attractive in situations where nodes want stronger guarantees with respect to some (distant) peers. For instance, in social network graphs, users may have lower privacy expectations with respect to close relatives than regarding strangers. In healthcare, a patient might trust her family doctor more than she trusts other doctors, and in turn more than employees of a regional agency and so on, creating hierarchical level of trust that our algorithms naturally match.
1.1 Contributions and outline of the paper
(i) Inspired by the recent definitions of Cyffers and Bellet [17], we introduce pairwise network DP, a relaxation of Local Differential Privacy which is able to quantify the privacy loss of decentralized algorithm for each pair of distinct users in a graph.
(ii) We propose Muffliato', privacy amplification mechanism composed of local Gaussian noise injection at the node level followed by gossiping for averaging the private values. It offers privacy amplification that increases as the distance between two nodes increases. Informally, the locally differentially private value shared by a node u is mixed with other contributions, to the point that the information that leaks to another node can have very small sensitivity to the initial value in comparison to the accumulated noise.
(iii) We analyze both synchronous gossip [18] and randomized gossip [11] under unified privacy analysis with arbitrary varying gossip matrices. We show that the magnitude of the privacy amplification is significant: the average privacy loss over all the pairs in this setting reaches the optimal privacy-utility trade-off of a trusted aggregator, up to a factor d_ where Aw is the weighted "Aw
graph eigengap and d the maximum degree of the graph. Remarkably, this factor can be of order I for stioyy--tiit-y-cclabbe
expanders, yielding a sweet spot in the we study the case where the graph is itself random and private, and derive stronger privacy guarantees.
trade-off of gossip algorithms. Then,
(ir) Finally, we develop and analyze differentially private decentralized Gradient Descent (GD) and Stochastic Gradient Descent (SGD) algorithms to minimize a sum of local objective functions. Building on Muffliato, our algorithms alternate between rounds of differentially private gossip communications and local gradient steps. We prove that they enjoy the same privacy amplification described above for averaging, up to factors that depend on the regularity of the global objective.
(v) We demonstrate the usefulness of our approach and analysis through experiments on synthetic and real-world datasets and network graphs. We illustrate how privacy amplified between nodes in the graph as function of their distance, and show how time-varying random graphs can be used to split the privacy loss more uniformly across nodes in decentralized optimization.
1.2 Related work
Gossip algorithms and decentralized optimization. Gossip algorithms [10. 18] were introduced to compute the global average of local vectors through peer-to-peet -peer communication, and are at the core of many decentralized optimization algorithms. Classical decentralized optimization algorithms alternate
'The name is borrowed from the Harry Potter series: it designates a "spell that filled the cars of anyone nearby with unidentifiable buzzing". thereby concealing messages from unintended listeners through noise injection.
2

---

between gossip communications and local gradient steps [48. 38, 39], or use dual formulations and formulate the consensus constraint using gossip matrices to obtain decentralized dual or primal-dual algorithms [54, 32, 24, 25, 40, 1]. We refer the reader to [49] for broader survey on decentralized optimization. Our algorithms are based on the general analysis of decentralized SGD in [39].
LDP and privacy amplification mechanisms. Limitations of LDP for computing the average of the private values of n users have been studied, showing that for a fixed privacy budget, the expected squared error in LDP is n times larger than in central DP [12]. More generally, LDP is also known to significantly reduce utility for many learning problems [61, 57], which motivates the study of interme- diate trust models. Cryptographic primitives, such as secure aggregation [21, 55, 9. 13, 35, 5, 53] and secure shuffling [16, 23, 3, 31, 30]. as well as additional mechanisms such as amplification by subsam- pling [2] or amplification by iteration [28], can offer better utility for some applications, but cannot be easily applied in a fully decentralized setting, as they require coordination by a central server.
Privacy amplification through decentralization. The idea that decentralized communications can provide differential privacy guarantees was initiated by [7] in the context of rumor spreading. Closer to our work, [17] showed privacy amplification for random walk algorithms on complete graphs, where the model is transmitted from one node another sequentially. While we build on their notion of Network DP, our work differs from [17] in several aspects: (i) our analysis holds for any graph and explicitly quantifies its effect, (ii) instead of worst-case privacy across all pairs of nodes, we prove pairwise guarantees that are stronger for nodes that are far away from each other, and (iii) unlike random walk approaches, gossip algorithms allow parallel computation and thus better scalability.
2 Setting and Pairwise Network Differential Privacy
We study a decentralized model where n nodes (users) hold private datasets and communicate through gossip protocols, that we describe in Section 2.1. In Section 2.2, we recall differential privacy notions and the two natural baselines for our work, central and local DP. Finally, we introduce in Section 2.3 the relaxation of local DP used throughout the paper: the pairwise network DP.
2.1 Gossip Algorithms
We consider a connected graph G = EV, on set of n users. An edge {u, v) E indicates that and can communicate (we say they are neighbors). Each user E V holds local dataset D and we aim at computing averages of private values. This averaging step is a key building block for solving machine learning problems in decentralized manner, as will be discussed in Section 4. From any graph, we can derive a gossip matrix.
Definition 1 (Gossip matrix). A gossip matrix over a graph G is symmetric matrix W E Rnxx with non-negane non-negaeive entries, that satisfies W1 1 i.. W stochastic E RR" is the vector with all entries equal to 1). and such that for any u, v E V, Wa,v > 0 implies that {u, v} E E or V.
The iterates of synchronous gossip [18] are generated through recursion of the form x+1 Wa* ee
and converge to the mean of initial values zd E IR" at a linear rate e -tAw, with Xw defined below. Definition 2 (Spectral gap). The spectral gap Aw associated with a gossip matrix W is min - [A],, where Sp(W) is the spectrum of W.
The inverse of Aw is the relaxation time of the random walk on G with transition probabilities W, and is closely related to the connectivity of the graph: adding edges improve mixing properties (Aw increases), but can reduce scalability by increasing node degrees (and thus the per-iteration communication complexity). The rate of convergence can be accelerated e -tvAw using re-scaled Chebyshev polynomials, leading to iterates of the form x' = P.(W) [8].
Definition 3 (Re-scaled Chebyshev polynomials). The re-scaled Chebyshev polynomials (Pt) with scale parameter 7 E [1, 2] are defined by second-order linear recursion:
Px(X) 1, (X))= = x, P+i(X) = 7X (1-7)
(1)
2.2 Rényi Differential Privacy
Differential Privacy (DP) quantifies how much information the output of an algorithm A leaks about the dataset taken as input [20]. DP requires to define an adjacency relation between datasets. In this
3

---

work, we adopt user-level relation [45] which aims to protect the whole dataset De of a given user represented by node V. Formally, D D and D' U, are adjacent datasets, denoted by DD ~ 'D' if there exists E V such that only DD and D' differ. We use 'D ~vp DD to denote that D and DD' differ only in the data of user v.
We use Rényi Differential Privacy (RDP) [46] to measure the privacy loss, which allows better and simpler composition than the classical (e, 6)-DP. Note that any (a,e)-RDP algorithm is also (s + (m(1)/)))/( Definition (Rényi Differential Privacy). An algorithm A satisfies (a, e)-Rénii Differrntial Privacy (RDP) for a 1 and e > 0 if for all pairs of neighboring datasets D ~ D
1), 6)-DP for any 0 < 5 < 1 [46].
Da (a(((D)))A(D)) E
(2)
where for two random variables X and Da Dx(X (IY) is the Rényi divergence between X and Y:
Dx(X - In () "x(x))z.
with pxx and py the respective densities of X and
Without loss of generality, we consider gossip algorithms with a single real value per node (in that case, D. {ox}} for some 2y E R), and aim at computing a private estimation of the mean I = (1/n) En, Ty. The generalization to vectors is straightforward, as done subsequently for optimization in Section 4. In general, the value of a (scalar) function g of the data can be privately
released using the Gaussian mechanism [20, 46), which adds ~ (N0, a²) to g(D). It satisfies (a, a /22/222)=a0 J-DP for any > where Ag = supD-.D' (l) g(D))l I| the sensitivity of g. We focus on the Gaussian mechanism for its simplicity (similar results could be derived for other DP mechanisms), and thus assume an upper bound on the L2 inputs sensitivity.
Assumption 1. There exists some constant A > 0 such that for all u E V and for any adjacent datasets D ~u D', we have || - x'y |l & A.
In central DP, trusted aggregator can first compute the mean (which has sensitivity A/n) and then reveal a noisy version with the Gaussian mechanism. On the contrary, in local DP where there is no trusted aggregator and everything that given node reveals can be observed, each node must locally perturb its input (which has sensitivity A), deteriorating the privacy-utiityy trade-off. Formally, to achieve (a,e)- eDDD,, one cannot have better utility than:
|
=1|]]
aA2
for local DP, and
E |
=1|]
aA2
for central DP,
2n
2n
where goub is the output of the algorithm. This 1/n gap motivates the study of relaxations of local DP.
2.3 Pairwise Network Differential Privacy
We relax local DP to take into account privacy amplification between nodes that are distant from each other in the graph. We define a decentralized algorithm A as a randomized mapping that takes as input dataset D (D.) and outputs the transcript of all messages exchanged between users in the network. A message between neighboring users {u, e} E E at time is characterized by the tuple (u, m(t), w): user sent a message with content m(() to user v, and A(D) is the set of all these messages. Each node v only has partial knowledge of A(D), captured by its view:
(A(D)) = {(u, m(t), v) E A(D) such that {u, E)
This subset corresponds to direct interactions of with its neighbors, which provide only an indirect information on computations in others parts of the graph. Thus, we seek to express privacy constraints that are personalized for each pair of nodes. This is captured by our notion of Pairwise Network DP.
Definition 5 (Pairwise Network DP). For I VV V IR+,, an algorithm A satisfies (a, f Network DP (PNDP) for all pairs of distinct users u, E V and neighboring datasets ~m D':
(O.(((())) (A(,))) (I,,AAA & f(u, v).
(3)
We note Eu-su [u, u) the privacy leaked to u from u and say that w. is (a, Eu- with respect to if only inequality (3) holds for f(u, v) Eu-we.

---

By taking f constant in Definition 5, we recover the definition of Network DP [17]. Our pairwise variant refines Network DP by allowing the privacy guarantee to depend on u and (typically, on their relative position in the graph). We assume that users are honest but curious: they truthfully follow the protocol, but may try to derive as much information as possible from what they observe. We refer to Appendix G for natural adaptation of our definition and results to the presence of colluding nodes and to the protection of groups users.
In addition to pairwise guarantees, we will use the mean privacy loss o. = 1. Euev f(u, v) to compare with baselines LDP and trusted aggregator by enforcing Σ = max E. E. The value Eg proper
the average of the privacy loss from all the nodes to and thus does not correspond privacy guarantee, but it provides a convenient way to summarize our gains, noting that distant nodes in ways that will be specified will have better privacy guarantee than this average, while worst cases will remain bounded by the baseline LDP guarantee provided by local noise injection.
3 Private Gossip Averaging
In this section, we analyze a generic algorithm with arbitrary time-varying communication matrices for averaging. Then, we instantiate and discuss these results for synchronous communications with fixed gossip matrix, communications using randomized gossip [11], and with Erdös-Rény graphs.
3.1 General Privacy Analysis of Gossip Averaging
We consider gossip over time-varying graphs (Gr)ogreT. defined G. (V,&,,, with correspond-
ing gossip matrices (W))ogrr. The generic Muffliato algorithm AT for averaging x = (xo) corresponds an initial noise addition followed by T gossip steps. Writing Wit = W ... Wo. the iterates of A are thus defined by:
VU E V = x. + Th with Th ~ NN o²), and 2+1 Wir² = 1 (x + +7).
(4)
Note that the update rule node u E V writes as xt Ew (W where Ne(u) are the neighbors of in GG, so for the privacy analysis, the view of node is:
O (A = =(Worl + m))
0 0 OELET-1JUEEN
(5)
Theorem 1. Let T > 1 and denote by Pf P(n.ww) = (s < T [u,w) E EES the set of time-steps with communication along edge {u, w). Under Assumption 1, AT is (a, fNDP with:
aA2 2
Σ
(Woz)a
f(u,
(6)
20
I(
WEVIEP? (o.w)
This theorem, proved in Appendix B. gives tight computation of the privacy loss between every pair of nodes and can easily be computed numerically (see Section 5). Since distant nodes correspond to small entries in Wor, Equation 6 suggests that they reveal less to each other. We will characterize this precisely for the case of fixed communication graph in the next subsection.
Another way to interpret the result of Theorem is to derive the corresponding mean privacy loss:
AA2T.
2ng
where T. is the total number of communications node involved with up to time T. Thus, in comparison with LDP, the mean privacy towards is n/T, times smaller. In other words, a node learns much less than in LDP long it communicates o(n) times.
3.2 Private Synchronous Muffliato
We now consider Muffliato over fixed graph (Algorithm 1). Note that we use gossip acceleration (see Definition 3). We start by analyzing the utility of Muffliato, which decomposes as averaging error term vanishing exponentially fast, and a bias term due to the noise. General convergence rates given in Appendix C, from which we extract the following result.
5

---

Algorithm 1: MUFFLIATO
Algorithm 2: RANDOMIZED MUFFLIATO
Input:
local values (JE)vEY to average, gossip matrix W on graph G, in T iterations, noise variance o²
Input:
local values (Fy)vEV to average.
activation intensities
(P(u,w) (v.w)eE in T itterations,
7 <- 2 11 A
noise variance o²
(2)
for all nodes in parallel do
for all nodes in parallel do
2 6- Tv + 17o where yh ~ (0,
2- 5 Tg + where To ~ (00,
for t == 0 1 do
for 1 0
do for all nodes in parallel do for all neighbors w defined by W do Send v. receive rty
Sample (wz, w. E & with probability P(v..w.))
Vy and wa exchange s't, and s'g Local averaging:
x+1 f-
xtt = x1t11 zir -111-1
(1 - 7)) -- + EWEN, W Wo
2
For v E V V (er, w m = xr
Table 1: Utility of Muffliato for several topologies under the constraint E < for the classic gossip matrix where W.., = min(1/do. 1/dm)) and d, the degree of node v. Ö()) hides constant and
logarithmic factors. Recall that utility is (aa2² / /ns) for LDP and (a 2 /n2e) for central DP.
Graph
Arbitrary
Expander
C-Torus
Complete
Ring
Algorithm
as?d 6
asa n n
CACC n2 17-170 a22 n2 --27777
aA? ng aaa n'e
aa me aa? ne
n'ev/w 04? n'"exw
Algorithm
Theorem 2 (Utility analysis). Let dw be the spectral gap of W. Muffliato (Algorithm 1) verifies, any > :
E
=11]]
30 n
where
Tstop
In
( max (a" n1
1
Σ 1
=1²)
v VWw
For the privacy guarantees, Theorem still holds as accelerated gossip can be seen as a post-processing of the non-accelerated version. Thanks the fixed graph, can derive more explicit formula.
Corollary 1. Algorithm 1 satisfies (a, (a,=T (a)) for node with respect to u. with:
ad max
T
T (o) & 20
W 8,00
= -|x0= u)
(U.w)E
(=1
where (X*), is the random walk on graph G, with transitions W.
This result allows us to directly relate the privacy loss from u to e to the probability that the random walk on G with transition probabilities given by the gossip matrix goes from u to in a certain num- ber of steps. It thus captures a notion of distance between nodes in the graph. We also report the utility under fixed mean privacy loss = max 3n & E in Table for various graphs, where one can see a uuility-privace trade-off improvement of n Aw /d, where is the maximum degree, compared to LDP. Using expanders closes the gap with a trusted aggregator (i.c., central DP) up to constant and logarith- mie terms. Remarkably, graph topologies that make gossip averaging efficient (i.e. with big VAw/en /d), such as exponential graphs or hy hypercubes [59], are also the ones that achieve optimal privacy am- plification (up logarithmic factors). In other words, privacy, utility and scalability are compatible.
3.3 Private Randomized Muffliato
Synchronous protocols require global coordination between nodes, which can be costly or even impos- sible in some settings. On the contrary, asynchronous protocols only require separated activation of edges: they are thus are more resilient to stragglers nodes and faster in practice. In asynchronous gos- sip, at given time-step single edge {u, v} is activated independently from the past with probability

---

P(u,)), as described by Boyd et al. [11]. In our setting, randomized Muffliato (Algorithm 2) corre- sponds to instantiating our general analysis with W = (v,,we) Ln (e., Ew, (ev, Ewe) ) // if {Uz, Wt) J is sampled at time t. The utility analysis is similar to the synchronous case, Theorem 3 (Utility analysis). Let Mp) be the spectral gap of graph G with weights (P(v,w)) (u,w)E Randomized Muffliato (Algorithm 2) verifies, for all t Tstop;
E
+
=|(]
20²
where Tstop
1 X(p)
In
n 02
max (0"
-
1 12 DEV
2m
DEV
To compare with synchronous gossip (Algorithm 1), we note that activation probabilities can be derived from gossip matrix W by taking P(u,r] 2W (W,,,)/nn implying that X(p) 2Aw /n, thus requiring n times more iterations to reach the same utility as the synchronous applications of matrix W. However, for given time-horizon T and node the number of communications can be bounded with high probability by T/nn multiplied by a constant whereas Algorithm requires d.T communications. Consequently, reported in Table I, for fixed privacy mean E., Algorithm has the same utility as Algorithm 1, up to two differences: the degree factor d, is removed, while v V'w degrades to Aw we do not accelerate randomized gossip (see Remark 1 below). Randomized gossip can thus achieve an optimal privacy-utility trade-off with large-degree graphs, as long as the spectral gap is small enough.
Remark 1 (Accelerating Randomized Muffliato). For simplicity, Randomized Muffliato (Algorithm 2) is not accelerated, while Muffliato (Algorithm 1) uses Chebychey acceleration to obtain a dependency on VAw rather than dw. Thus, and as illustrated by Table I, Algorithm 2 does not improve over Algorithm I for all values of d (maximum degree), and Xw. However, Algorithm 2 can be accelerated using a continuized version of Nesterov acceleration [24, 25], thus replacing X()) in the expression of Totp in Theorem 3. by (p)p)/ (ddn) Doing so, using randomized communications improve privacy guarantees over Algorithm for all graphs considered in Table 1.
3.4 Brdös-Rényy Graphs
So far the graph was considered to be public and the amplification only relied on the secrecy of the messages. In practice, the graph may be sampled randomly and the nodes need only to know their direct neighbors. We show that we can leverage this through the weak convexity of Rényi DP to amplify privacy between neighboggggg nodes. We focus on venös-Rényi graphs, which can be built without central coordination by picking each edge independently with the same probability q. For q cln(n)/n n where >>> 1, Erdös-Rényi graphs are good expanders with node degrees d, = Ologni and \n concentrating around [33]. We obtain the following privacy guarantees.
Theorem 4 (Muffiiato on random Erdös-Rényí graph). Let a > 1, T 3 0, o² A'a(a-1)
2
and q .uf()) for c > 1. Let u, v E V be distinct nodes. After running Algorithm I with these with respect to v, with:
parameters, node u is (ar, (a))
a
with probability 4
20
(a) &
2 Td,
with probability 1 q-
d,
This results shows that with probability u and v are neighbors and there is no amplification com- pared LDP. The rest of the time, with probability 1- q. the privacy matches that of a trusted aggre- gator up degree factor d, = Ollog n) and T 0(1 /Aw) Ó(1) [33]. In particular, if several rounds of gossip averaging are needed, as in the next section for SGD, changing the graph mitigates the privacy loss of the rounds where two nodes are neighbors thanks to the rounds where they are not.
4 Private Decentralized Optimization
We now build upon Muffliato to design decentralized optimization algorithms. Each node e E V possesses data-dependent function du RDD + R and we wish to privately minimize the function
(00) Σ (o)),, with s [Dol
1
Σ (0(0 0 RERD
(8)
R.ED.
7

---

Algorithm 3: MUFFLIATO-SGD and MUFFLIATO-GD
Input:
initial points & E RDD, number iterations T, step sizes v > O, noise variance o² gossip matrices (Wi) local functions o.. number of communication rounds K for t 0
do for all nodes parallel do Compute 0r o -VVll (f, at)) where o bu g MUFFLIATO ((O))) (6))) W., K, v²a²)
where D, is the (finite) dataset corresponding to user u for data lying in a space X,, and &, IRD x X. IR a loss function. We assume that is j--trongly convex, and each o is L-smooth, and denote L/p. We note that our results can be extended to the general convex and smooth setting. Denoting by 0 the minimizer of Φ, for some non-negative (C²)vvv, (oE)vey and all V, assume:
(o)(0*) - VO(0"
IV, x.e) - Vo(01)1 & Po
To ~ Lo
where C. the uniform distribution over D.. We write p² = E.ev of and 2 =
We introduce Algorithm 3, private version of the classical decentralized SGD algorithm studied [39]. Inspired by the optimal algorithm MSDA of Scaman et al. [54] that alternates between K Chebychev-accellratee gossip communications and expensive dual gradient computations, our Algorithm alternates between Chebychev-accellrattee gossip communications and cheap local stochastic gradient steps. This alternation reduces the total number of gradients leaked, crucial point for achieving good privacy, Note that Algorithm 3, each communication round uses potentially different gossip matrix W,. In the results stated below, we fix W, = W for all & and defer more general case to Appendix F, where different independent Erdös-Rényi graphs with same parameters are used at each communication round.
Remark 2. Our setting encompasses both GD and SGD. MuffliatoGGD is obtained by removing the stochasticity, i.c., setting (-) = Φo(-). In that case, p² =0. O.
Theorem (Utility analysis of Algorithm 3). For suitable step-size parameters. for a total number Tstop computations and Tstop K communications, with:
Tetop = Ō(),, and k= ==[V>w> In (max (n, Do² + pp )
the iterates )ez) generated by Algorithm 3 verify (0(0mu)) x(0+) Ö Do pnn
where
gout E R is a weighted average of the
Evey Of until Tstop,
For the following privacy analysis, we need a bound on the sensitivity of gradients with respect to the data. To this end, assume that for all and Ie, lo(,,2,) z.) is A Lipschitz'.
Theorem 6 (Privacy analysis of Algorithm 3). Let and v. be two distinct nodes in V. After T iterations of Algorithm with K > 1, node u is (a, ET (a)) with respect to v, with:
TA K-1 4
(W*)2
(a) <
Σ
Σ
20
I(
Thus, for any > O, Algorithm 3 with (K, 0² ,, n) steps and for K as in Theorem 5, there exists f such that the algorithm is f)) -appriiis network DP. with:
aDA
VOEV, E. Ss and E -1(00)))0(00)] <
uunee V/w
nL
where d = maX.ey d...
TTii assumption be replaced by the more general Assumption given in Appendix F.

---

The term á above (which is equal to zero for Mufflaato-GD see Remark 2) is privacy independent. S is typically dominated by the first term, which corresponds to the utility loss due to privacy. Comparing Theorem 6 with the results for Muffliato (Table I in Section 3.2), the only difference lies in the factor DA p. Note that A plays the role of the sensitivity A?, and D appears naturally due to considering D-dimensional parameters. On the other hand, μ is directly related to the complexity of the optimization problem through the condition number the easier the problem, the better the privacy-utility trade-off of our algorithm. Regarding the influence of the graph, the same discussion as after Corollary applies here. In particular, for expander graphs like the exponential graph of [59], the
factor d/ /ww is constant. In this case, converting to standard (c, 6DD gives Ö( DA ), recovering the optimal privacy-utility trade-off of central DP [4, 56] up logarithmie factors. Remarkably, we achieve this optimal rate under near- lear-linear gradient complexity of T 0², n))n ((m)) and linerr total number of messages Totop (K., o²; n) K'n ((K)).
Remark 3 (Time-varying graphs). The analysis of Muffliato-GD/SCC presented in this section (Theorems 5 and 6) assumes constant gossip matrices Wt = W. A more general version of these results is presented in Appendix F to handle time-varying matrices and graphs. This can be used to model randomized communications (as previously described for gossip averaging in Section 3.3) as well as user dropout (see experiments in Appendix H). Time-varying graphs can also be used to split the privacy loss more uniformly across the different nodes by avoiding that nodes have the same neighbors across multiple gossip computations. We illustrate this experimentally for decentralized optimization in Section 5, where we randomize the graph after each gradient step of MuffliatoGGD.
5 Experiments
In this section, we show that pairwise network DP provides significant privacy gains in practice even for moderate size graphs. We use synthetic graphs and real-world graphs for gossip averaging. For decentralized optimization, we solve a logistic regression problem on real-world data with time- varying Erdos-Renyi graphs, showing in each case clear gains in privacy compared to LDP. The code used obtain these results is available at https: htttp:://gitubb www/totiias/etteeeoooooooooaaeet haw.aaa//mffiaatoooo
Averaging on synthetic graphs. We generate synthetic graphs with n = 2048 nodes and define the corresponding gossip matrix according to the Hamilton scheme. Note that the privacy guarantees of Muffliato are deterministic for a fixed W, and defined by Equation 4. For each graph, we run Muffliato for the theoretical number of steps required for convergence, and report in Figure (a) the pairwise privacy guarantees aggregated by shortest path lengths between nodes, along with the LDP baseline for comparison. Exponential graph (generalized hypercube): this has shown be an efficient topology for decentralized learning [59]. Consistently with our theoretical result, privacy is significantly amplified. The shortest path completely defines the privacy loss, so there no variance. Prdos-Reny graph with q = clog n/n (c > 1) [22], averaged over 5 runs: this has nearly the same uuility-privacy trade-off as the exponential graph but with significant variance, which motivates the time-evolving version mentioned in Remark 3. Grid: given its larger mixing time, it is less desirable than the two previous graphs, emphasizing the need for careful design of the communication graph. Geometric random graph: two nodes are connected if and only if their distance is below a given threshold, which models for instance Bluetooth communications (effective only in a certain radius). We sample nodes uniformly at random in the square unit and choose radius ensuring full connectivity. While the shortest path a noisy approximation of the privacy loss, the Euclidean distance is very good estimator as shown in Appendix H.
Averaging on real-world graphs. We consider the graphs of the Facebook ego dataset [41], where nodes are the friends of a given user (this central user is not present is the graph) and edges encode the friendship relation between these nodes. Ego graphs typically induce several clusters corresponding to distinct communities: same high school, same university, same hobbies... For each graph, we extract the giant connected component, choose a user at random and report its privacy loss with respect to other nodes. The privacy loss given by LDP is only relevant within the cluster of direct neighbors: privacy guarantees with respect to users other communities are significantly better, as seen in Figure 1(b). We observe this consistently across other ego graphs (see Appendix H). This is in line with one of our initial motivation: our pairwise guarantees are well suited situations where nodes want stronger privacy with respect to distant nodes.
9

---

10
LDP
PNOP (nm4000)
10
0.88
PNOP (n=2000)
0.2
0.4
0.5
0.8
100
Privacy Loss
10-
Privacy loss
0.9
10-2
-04
0.88
Expanential
10
Erdos
0.7
Random Geomatric
Muffliato Central
10
0
5
20 Shortest Poth Length
10 15
25
0.5
4
8
0.0
Iterations
Figure 1: (a) Left: Privacy loss of Muffliato in pairwise NDP on synthetic graphs (best, worst and average in error bars over nodes at given distance), confirming a significant privacy amplification the distance increases. (b) Middle: Privacy loss of Muffliato from a node chosen at random on a Facebook ego graph, showing that leakage is very limited outside the node's own community. (c) Right: Privacy loss and utility of MufliaatoGGD when using different Erdös-Rényí graphs after each gradient step, compared to a baseline based on a trusted aggregator.
Logistic regression on real-world data. Logistic regression corresponds to minimizing Equation 8 with loss function {(0; x, y) In(1 + exp( yo x)) where x Rd and y E {-1,1]. We use a binarized version of UCI Housing dataset." We standardize the features and normalize each data point x to have unit L22 norm so that the logistic loss 1-Lipschitz for any (x: y). We split the dataset uniformly at random into training set (80%) and test set and further split the training set across users. After each gradient step of Muffliato-Gi same parameter q to perform the gossiping step and run the thcoretical number of steps required for convergence. For each node, we keep track of the privacy loss towards the first node (note that all nodes play the same role). We report the pairwise privacy loss for this node with respect to all others for n = 2000 and n = 4000 in Figure (cc (top). We see that, as discussed in Remark 3, time-varying graphs are effective splitting the privacy loss more uniformly across nodes: the privacy gains over LDP are clear with respect to all nodes. As captured by our theory, these gains increase with the number of nodes in the system, and they also concentrate better around the mean. We compare the utility of Muffliato-GD to a federated learning alternative which uses the same parameters but aggregates noisy model updates using trusted central server rather than by gossiping. As seen in Figure ((c) (bottom), both approaches behave similarly in terms of accuracy across iterations.
we draw at random an Erdös-Rényi Rényi graph of
6 Conclusion
We showed that gossip protocols amplify the LDP guarantees provided by local noise injection as values propagate in the graph. Despite the redundancy of gossip that, at first sight, could be seen as obstacle to privacy, the privacy amplification turns out be significant: it can nearly match the optimal privacy-utility trade-off of the trusted curator. From the fundamental building block
noise injection followed by gossip that we analyzed under the name Muffliato, one can easily extend the analysis to other decentralized algorithms, such as the dual approach proposed in [54]. Our results are motivated by the typical relation between proximity in the communication graph and lower privacy expectations. Other promising directions are to assume that closer people are more similar, which leads to smaller individual privacy accounting [27], to design new notions of similarity between nodes in graphs as done in personalization [26] that match the privacy loss variations, and to study privacy attacks [52].
This work was supported by grants ANR-20- WIRR-2--E23-0000 (Project PRIDE) ANR-20-THIA-001- program "AI PhD@Lille ANR-19-P3JA--0011 (PRAIRIE Institute), and from the MISR-INRLA joint centre. We thank the organizers of NeurIPS @ Paris 2021 for the in-person event that allowed us to meet by chance and to start this piece of work.
Acknowledgments
hhttps://wwe openml. wwppp/lloggdd//....ee org/d/823
10

---

References
[1] Sulaiman A. Alghunaim and Ali H. Sayed. Linear convergence of primal-dual gradient methods and their performance in distributed optimization, 2019. URL https://arxiv org/ abs/ 1904.01196.
[2] Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences. In NeurlPS, 2018.
[3] Borja Balle, James Bell, Adrià Gascón, and Kobbi Nissim. Differentially Private Summation with Multi-Message Shuffling. Technical report, arxiv: 09161,996, 2019.
[4] Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 464-473, Philadelphia, PA, USA, October 2014. IEEE.
[5] James Henry Bell, Kallista A. Bonawitz, Adrià Gascón, Tanerède Lepoint, and Mariana Raykova. Secure single-server aggregation with (poly)logarihmic overheads. In CCS, 2020.
[6] Aurélien Bellet, Rachid Guerraoui, Mahsa Taziki, and Mare Tommasi. Personalized and Private Peer-to-Peer Machine Learning. In AISTATS, 2018.
[7] Aurélien Bellet, Rachid Guerraoui, and Hadrien Hendrikx. Who started this rumor? Quantifying the natural differential privacy guarantees of gossip protocols. In DISC, 2020.
[8] Raphaël Berthier, Francis Bach, and Pierre Gaillard. Accelerated gossip in networks of given di- mension using jacobi polynomial iterations. SIAM Journal on Mathematics of Data Science, 2(1): 44-47, 2020. doi: 10.1 00.1137/1MM244822 URL mattps://doff http:///ooooorr/////// org/ 1 01/0//1912442222
[9] Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H. Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical Secure Aggregation for Privacy-Preserving Machine Learning. In CCS, 2017.
[10] S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Randomized gossip algorithms. IEEE Transactions on Information Theory. 52(6):2508 -530,, 2006. doi: 10.1109/TIT.2006.444555 874516.
[11] Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip algorithms. IEEE transactions on information theory, 52(6):2508-255 2530, 2006.
[12] T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Optimal Lower Bound for Differentially Private Multi-party Aggregation. ESA, 2012.
[13] T.-H. Hubert Chan, Elaine Shi. and Dawn Song. Privacy-preserving stream aggregation with fault tolerance. In Financial Cryptography. 2012.
[14] Konstantinos Chatzikokolakis, Miguel E. Andrés, Nicolás E. Bordenabe, and Catuscia Palamidessi. Broadening the Scope of Differential Privacy Using Metrics. In De Cristo- faro, Emiliano, Wright, and Matthew, editors, The 13th Privacy Enhancing Technologies Symposium, volume 7981 of Lecture Notes Computer Science, pages 82-102, Blooming- ton, Indiana, United States, July 2013. Springer. doi: 10.1007/978--3-4423997777 00767210.
URL
https: inria.
[15] Hsin-Pai Cheng, Patrick Yu, Haojing Hu, Syed Zawad, Feng Yan, Shiyu Li, Hai Helen Li, and Yiran Chen. Towards Decentralized Deep Learning with Differential Privacy, In CLOUD, 2019.
[16] Albert Cheu, Adam D. Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev. Distributed Differential Privacy via Shuffling. In EUROCRYPT, 2019.
[17] Edwige Cyffers and Aurélien Bellet. Privacy amplification by decentralization, 2020. URL https://arxiv. org/ 201/ 05326.
[18] A. G. Dimakis, S. Kar, J. M. Moura, M. G. Rabbat, and A. Scaglione. Gossip algorithms for distributed signal processing. Proceedings of the IEEE, 98(11))1847-164, 2010.
11

---

[19] John C Duchi, Michael Jordan, and Martin J Wainwright. Local privacy and statistical minimax rates. In FOCS. 2013.
[20] Cynthia Dwork and Aaron Roth. The Algorithmic Foundations of Differential Privacy, Founda- tions and Trends@ in Theoretical Computer Science, 9(3-4):211-44) 1--077 2014.
[21] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our Data, Ourselves: Privacy Via Distributed Noise Generation. In EUROCRYPT, 2006.
[22] P. Erdös and A. Rényi. On random graphs i. Publicationes Mathematicae Debrecen, 6:290,
1959.
[23] Ulfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, and Kunal Talwar. Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity. In SODA, 2019.
[24] Mathieu Even, Hadrien Hendrikx, and Laurent Massoulié. Asynchrony and acceleration in gossip algorithms. Technical report, arXiv:201 2020.
[25] Mathieu Even, Raphaël Berthier, Francis Bach, Nicolas Flammarion, Hadrien Hendrikx, Pierre Gaillard, Laurent Massoulié, and Adrien Taylor. Continuized accelerations of deterministic and stochastic gradient descents, and of gossip algorithms. In M. Ran- zato, A. Beygelzimer, Y. Dauphin. P.S. Liang, and J. Wortman Vaughan. editors, Ad- vances in Neural Information Processing Systems, volume 34, pages 28054-28008 Cur- ran Associates, Inc., 2021, URL https: https::/ //pp://dd/ng./s../..ooooo./ neurips ctcplp.....pppppee http:ccccppppeeeee /ttpppp///2////1lle atw.eeeeeebaaacccc770722eee2ee Paper. pdf.
[26] Mathieu Even, Laurent Massoulié, and Kevin Scaman. On sample optimality in personalized collaborative and federated learning. Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL httpp:///penrevies.. met.t/oorrm.dde7EPP0MM....
[27] Vitaly Feldman and Tijana Zrnic. Individual Privacy Accounting via Rényi Filter. In NeurIPS, 2021.
[28] Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta. Privacy Amplification by Iteration. FOCS, 2018
[29] Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta. Privacy amplification by iteration. 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), Oct 2018. doi: 10.1 109 8.00056. URL http: //tx.//xxxx// www.ooorgg....ooo.... 10. 11w9//0CS...../ 2018. 00056.
[30] Vitaly Feldman, Audra McMillan, and Kunal Talwar. Hiding Among the Clones: A Sim- ple and Nearly Optimal Analysis of Privacy Amplification by Shuffling. Technical report, arXiv:2012. 1803,, 2020.
[31] Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, and Ameya Velingker. Pure Differentially Private Summation from Anonymous Messages. Technical report, arXiv:2002.01919, 2020.
[32] Hadrien Hendrikx, Francis Bach, and Laurent Massoulié. An accelerated decentralized stochas- tie proximal algorithm for finite sums. In Advances in Neural Information Processing Systems, 2019.
[33] Christopher Hoffman, Matthew Kahle, and Elliot Paquette. Spectral gaps of random graphs and applications. International Mathematics Research Notices, (1)3((1):33338444 May 2019. ISSN 1687-0247. doi: 10. m//19////////m0777 URL. http: //xx doi otg/10.1093. /000///////////////// rnz077.
[34] Zhenqi Huang, Sayan Mitra, and Nitin Vaidya. Differentially Private Distributed Optimization. In ICDCN, 2015.
12

---

[35] Bargav Jayaraman, Lingxiao Wang, David Evans, and Quanquan Gu. Distributed learning without distress: Privacy- preeeevinn empirical risk minimization. In NeurIPS, 2018.
[36]
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Oliveira, Hubert Eichner, Salim EI Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Har- chaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi. Mikhail Khodak, Jakub Konecný. Alcksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mchryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Hang Qi. Daniel Ramage, Ramesh Raskar, Mariana Raykova, Dawn Song. Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang. Li Xiong, Zheng Xu, Qiang Yang. Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. Foundations and Trends@ in Machine Learning, (411-))1-2110 2021.
[37] Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. What Can We Learn Privately? In FOCS, 2008.
[38] Anastasia Koloskova, Sehastian Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In International Conference on Machine Learning, volume 97, pages 3478-3487. PMLR, 2019.
[39] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized SGD with changing topology and local updates. In Hal Daumé III and Aarti Singh, editors. Proceedings of the 37th International Conference on Machine Learning. volume 119 of Proceedings of Machine Learning Research, pages 5381-5393. PMIR, 13-18 Jul 2020. URL httpps:/pproceeddnnngg wwt.s/s.........e.ee..e.e..eeeee
mlr pgress/viiee http//v111//1llo/ we1.9//olosoovaaa00 html.
[40] Dmitry Kovalev, Elnur Gasanov, Alexander Gasnikov, and Peter Richtarik. Lower bounds and optimal algorithms for smooth and strongly convex decentralized optimization over time-varying networks. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processsig Systems, volume 34, pages 22325-22335. Curran Associates, Inc., 2021. URL
[41] Jure Leskovec and Julian Mcauley. Learning to discover social circles in ego networks. In Pereira, C.J. Burges, L. Bottou, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc., 2012. URL https://proceeddn// neurips. http:////...//.................0
pdf.
[42] Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. In NIPS, 2017.
[43] Cassio G. Lopes and Ali H. Sayed. Incremental adaptive strategies over distributed networks. IEEE Transactions on Signal Processing, (00):406440077 2007. doi: 10.1 109/TSP..07 896034.
[44] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Conmunication-Efiiccii Learning of Deep Networks from Decentralized Data. In Aarti Singh and Jerry Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 1282. PMLR, 20 22 Apr 2017.
[45] H. Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning Differentially Private Recurrent Language Models. In ICLR, 2018.
[46] Ilya Mironov. Renyi differential privacy. CoRR, abs/1702.07476, 2017. URL http://arxiii org/abs/ taabss/1702.00 07477
07476.
[47] Mohar, Y Alavi, Chartrand, and OR Oellermann. The laplacian spectrum of graphs. Graph theory, combinatorics. and applications, 1991.
13

---

[48] Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi- agent opti- mization. IEEE Transactions on Automatic Control, 54(1):48 61, 2009. doi: 10.1 109/TAC. 2008.2009515.
[49] Angelia Nedic, Alex Olshevsky, and Michael G. Rabbat. Network topology and communication- computation tradeoffs in decentralized optimization. Proceedings of the IEEE, 106(5):953-97) May 2018.
[50] Giovanni Neglia, Gianmarco Calbi, Don Towsley, and Gayane Vardoyan. The role of network topology for distributed machine learning. In INFOCOM, 2019.
[51] Helen Nissenbaum. Privacy as contextual integrity. Washington Law Review, 19(1):119-157, February 2004. ISSN 0043-0617.
[52] Dario Pasquini, Mathilde Raynal, and Carmela Troncoso. On the privacy of decentralized machine learning. Technical report, arXiv:2205.08.4 08443, 2022.
[53] César Sabater, Aurélien Bellet, and Jan Ramon. Distributed Differentially Private Averaging with Improved Utility and Robustness to Malicious Parties. Technical report, arXiv:2006.072.18, 2020.
[54] Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, and Laurent Massoulié. Optimal algorithms for smooth and strongly convex distributed optimization in networks. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 3027-3036. PMLR, 06-11 Aug 2017. URL https: https://prrccedinngs mml. wall.press//eeeee /ttsss///////// scasscaaannn 17a html..
[55] Elaine Shi, T.-H. Hubert Chan, Eleanor G. Rieffel, Richard Chow, and Dawn Song. Privacy- Preserving Aggregation of Time-Series Data. In NDSS, 2011.
[56] Di Wang, Minwei Ye, and Jinhui Xu. Differentially private empirical risk minimization revisited: Faster and more general. I. Guyon, U. V. Luxburg, S. Bengio, Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, NeurIPS, volume 30. Curran Associates, Inc., 2017.
[57] Di Wang, Marco Gaboardi, and Jinhui Xu. Empirical Risk Minimization in Non-interactive Local Differential Privacy Revisited. In NeurlPS, 2018
[58] Jie Xu, Wei Zhang, and Fei Wang, Asd:) Asynchronous decentralized paraliel stochastic gradient descent with differential privacy. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
[59] Bicheng Ying, Kun Yuan, Yiming Chen, Hanbin Hu, Pan Pan, and Wotao Yin. Exponential graph is provably efficient for decentralized deep training. In A. Beygelzimer, Y. Dauphin, P. Liang, J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
[60] Xueru Zhang, Mohammad Mahdi Khalili, and Mingyan Liu. Improving the Privacy and Accuracy of ADMM-Basse Distributed Algorithms. In ICML, 2018.
[61] Kai Zheng, Wenlong Mou, and Liwei Wang. Collect at Once, Use Effectively: Making Non-interactive Locally Private Learning Possible. In ICML, 2017.
14


Reviews:
[{"review_id": "nUZSEMxiXpz", "reviewer": "Reviewer_Zauo", "summary": "The paper studies a relaxation of local model of privacy, which they call pairwise network differential privacy. They use gossip protocols to understand the privacy loss under this relaxed notion. They show that the privacy get amplified under this notion of privacy for a range of network topology.", "questions": "Please take a look at above.", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main strength of the paper is the new notion of privacy studied. It seems natural for certain settings, but I am not sure if it is . They also study their new notion of privacy under the setting of colluding nodes in the network. The ring graph and complete graph was studied recently, so that result is not new. The result that is new are for expanded graphs and random graph. The proof seems correct.\n\nThe main weakness of the paper is also the new notion of privacy. For a privacy notion to be of use, it has to satisfy basic properties: group privacy, composition, and robustness to post-processing. I believe the authors can extend their collusion result to get group privacy. I would suggest the authors to do that in order to make this new relaxation more rigorous. It is also unclear what would be a good notion of composition for this new notion of privacy. Do we assume that the network topology (and collusion party) do not change over the period of composition or should we imagine the composition model to be more fitted with their time-varying graph model.\n\nThe other weakness of the paper is the interpretability of the result. Theorem 1 is stated with respect to the norm of the gossip matrix (I am guessing it is the spectral norm). It would be nice if we can have a sense of this theorem with an example. \n\nThe mean privacy loss as the baseline to compare privacy does not make sense. \n\nI would expect Algorithm 2 should have improvement for all values of d and spectral gap. This does not seem to be the case for arbitrary graphs. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ZR-ec3vvHEh", "reviewer": "Reviewer_BroW", "summary": "This paper introduces Pairwise network DP, a relaxation of local DP that allows the privacy constraint to vary as a function of nodes in the decentralized graph (i.e. may allow close nodes to lose more privacy than distant nodes). Given this setting, the work introduces Muffliato which combines local noise injection and gossip protocols and it further derives DP optimization algorithms. The theoretical analysis demonstrates the magnitude of privacy amplification for the protocols.  Intuitively, since nodes only interact directly with their neighbors, the this formulation allows for much tighter privacy guarantees for distant nodes and network topology can have a large impact on privacy utility tradeoffs. Finally, they also demonstrate privacy gain on synthetic and graph datasets.", "questions": "Suggestion: Additional federated learning experiments on a real world dataset (with a real world graph) demonstrating the practical utility of this method would be helpful. ", "limitations": "The paper adequately notes its limitations and discusses its social impacts.", "rating": 7, "confidence": 1, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "To the best of my knowledge, this work offers novel analysis to quantify the privacy amplification of the decentralized protocol for arbitrary graph types and demonstrates a strong improvement in privacy utility tradeoffs over LDP, both theoretically and empirically. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WWpQQm-u2Tb", "reviewer": "Reviewer_sTzh", "summary": "This paper proposes pairwise network differential privacy (PNDP) in decentralized optimization that relates privacy loss between two nodes with their communication weights after running the proposed algorithms for T steps. Several mixing matrices are considered and the paper analyzes both simple gossip averaging and baseline decentralized optimization problems. Utility and privacy analyses are conducted for different mixing matrices and problems. The new notion of differential privacy averages privacy loss for all nodes and thus gives a new perspective of designing privacy-oriented algorithms for decentralized optimization rather than only looking at worst case privacy loss. ", "questions": "I read the proof of Synchronous Muffiato and have the following questions. 1. In line 590, how to get the first bias-variance decomposition? It seems to the cross term has dependent parts and cannot cancel. 2. The first inequality here seems to rely on some properties of $P_t(W)$ while dealing with the 2nd term in the 2nd line. 3. The first term in the 2nd line misses an expectation symbol. in the first line, I guess there should be $\\|x^t - \\mathbb{1} \\bar{x}^\\top\\|$ otherwise the dimension of $\\bar{x}$ is confusing. 4. How to reach the inequality in line 495?", "limitations": "Yes. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The idea of PNDP is a pairwise version of network DP from ref. [16], which highlights and averaged privacy loss for each node instead of the worst case privacy loss. This perspective is original. This paper has quality analyses and experiments to support its claims and is clearly written. For each case considered, the paper shows clear and solid theoretical guarantees. I think this paper is significant in introducing this new idea of pairwise privacy notion, but the main confusion when I read the paper is that how to explicitly compare the utility loss given the same privacy constraints since there is a conversion of DP and Renyi DP which I didn't figure out how these results are compared in detail. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "1XzKVVN3Fe", "reviewer": "Reviewer_MF8v", "summary": "The authors propose a relaxed notion of local differential privacy in a\ndistributed model of local optimization in which users share data across\na network over rounds. The key difference from LDP is that for a particular\nround, a user only sees data from his neighbors, and thus data from many hops\naway is aggregated more and is more private. They propose muffliato, an algorithm\nfor computing noisy averages with an improved accuracy guarantee over LDP for \nseveral important types of network topologies. They show how to use \nmuffliato to perform SGD privately.\n", "questions": "Theorems 2,3 hold for a particular value of T^{stop} which is upper bounded as\nstated and not for all values of T^{stop} up to that bound, right? The second \ncase seems incorrect as early iterates would not be accurate. Please make this\nmore clear in the theorem statements.\n\nIn real life, the communication networks often change between rounds of\ninteraction, and users drop out and come back online. This seems to be  \ncaptured well by the general analysis of\nMuffliato, which allows W to change over time. However, for random muffliato,\nhow realistic is it to assume that some mechanism exists to sample edges randomly\nand query the users? Does this require a central authority to do the sampling,\nand what happens if the users are offline?\n\nThis extends to the Muffliatio-GD, where it appears one must assume a fixed\ncommunication matrix, or use randomized muffliato, many times.\n", "limitations": "The communication/coordination limitation could be addressed by running experiments\nwith different communication graphs each round.\n\n(Edit) I thank the authors for addressing this concern.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+ muffliato offers a big improvement over LDP in terms of accuracy and realistic\nassumptions about the network in which the compuatations are done.\n\n+ The authors provide a tight privacy analysis of Muffliato when the Gaussian\n  mechanism is used.\n\n+ the experiments are good quality and indicate the improvements of Muffliato\n\n- Muffliato, and especially Muffliato-SGD, still require many rounds of\n  coordination between users which is often hard to achieve in the decentralized\n  setting.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept