A general differentially private learning framework for decentralized data
Authors: Mei Li
Bo Pan
Yafei Wang
Lingchen Kong
Linglong Kong
Bei Jiang
Venue: Submitted to ICLR 2023 (2023)

Abstract: Decentralized consensus learning has been hugely successful, which minimizes a finite sum of expected objective functions over a network of nodes. However, the local communication across neighboring nodes in the network may lead to the leakage of private information. To address this challenge, we propose a general differentially private (DP) learning framework for decentralized data that applies to many non-smooth learning problems. We show that the proposed algorithm retains the performance guarantee in terms of stability, generalization, and finite sample performance. We investigate the impact of local privacy-preserving computation on the global DP guarantee. Further, we extend the discussion by adopting a new class of noise-adding DP mechanisms based on generalized Gaussian distributions to improve the utility-privacy trade-offs. Our numerical results demonstrate the effectiveness of our algorithm and its better performance over the state-of-the-art baseline methods in various decentralized settings.

Under review as a conference paper at ICLR 2023
A GENERAL DIFFERENTIALLY PRIVATE LEARNING FRAMEWORK FOR DECENTRALIZED DATA
Anonymous authors Paper under double-blind review
ABSTRACT
Decentralized consensus learning has been hugely successful that minimizing a finite sum of expected objectives over a network of agents. However, the local communication across neighbouring agents in the network may lead to the leak- age of private information. To address this challenge, we propose a general differ- entially private (DP) learning framework that is applicable to direct and indirect communication networks without a central coordinator. We show that the pro- posed algorithm retains the performance guarantee in terms of generalization and finite sample performance. We investigate the impact of local crivacy-rreeevvng computation on the global DP guarantee. Further, extend the discussion by adopting a new class of noise-adding DP mechanisms based on generalized Gaus- sian distributions to improve the utility-privace trade-offs. Our numerical results demonstrate the effectiveness of our algorithm and its better performance over the sfate-of-the-ad baseline methods in various decentralized settings.
INTRODUCTION
Decentralized learning is a process of learning consensus model using the datasets that dis- tributed across different agents, such as machines, hospitals, and mobile devices (Shi et al.) 2014
Han et al. 2017; Gong et al., 2016 Beyan et al.) (020). During the process, each local agent (I) keeps its own private data locally; (2) requires no exchange of raw data; and (3) communicates only with its connected agents to train its local model and updates the global parameters directly without a central coordinator. In particular, as medical data are inherently decentralized, i.e., owned or distributed across different institutions, direct sharing or central aggregation of such distributed medical data is increasingly restricted due to either ownership or other regulatory constraints. As consequence, the advancement of decentralized learning will offer innovative solutions to transform healthcare sectors Herresthl et al., 2021).
Although decentralized learning only requires parallel computation at each local agent and shar- ing of the estimates perhaps other intermediate parameters (auxiliary variables) with connected neighbouring agents, past experience has demonstrated the possibility of privacy leakage in the pro- cess: the attacker can still recover sensitive information from local communications (e.g..,.Feeriksoo, let al. 2015 Shokri et al. 2017). One defence procedure is to adopt private variant of the learning algorithm using Differential Privacy (DP) to secure the training process. Very few DP algorithms focus on decentralized learning systems, with the exception of recent works in Xu et al. (2022); Yu et al. (2021a); Huang & Gong (2020). However, when introducing perturbation into the itera- live learning process, these carlier methods only focus on achieving (s, d)-DP guarantee for each agent. Due the communications with neighbouring agents during the iterative process, the overall privacy guarantee of the algorithm is no longer (c, (DP.). Importantly, it is unclear how one can split the privacy budgets among all the agents in order to achieve a global (c, DDP guarantee for the algorithm when using these earlier methods. Finally, these existing methods consider stan- dard Gaussian noise-adding mechanism. The added unbounded noise could lead to unstable results, which severely affect the learning efficiency and degrade the performance of the trained global model (Farokhil 2022). This paper aims to provide a unified solution to address these issues and discuss the theoretical guarantees of the proposed algorithm.

---

Under review as a conference paper at ICLR 2023
1.1 RELATED WORKS
In the setting of centralized learning for distributed data, a handful number of papers have studied how to integrate privacy-preserving techniques. such as DP, into the training process (Jayaraman et al.
Li et al., 2022a; Guo et al., 20200 Cai et al., 2018; Li et al. 2022b; Huang et al.) Cao et al. 2021 For example, Jayaraman al. (2018) proposed DP algorithms for convex problems where ensuring the information obtained from each local model satisfies DP guarantees before being aggregated in central coordinator; [Li et al. (2022b) proposed unified centralized learning framework to ensure DP guarantees for each local agent for a general class of non-convex problems. However, these algorithms cannot be directly adapted to solve our problem; they focus on the setting where there exists central coordinator that is responsible for aggregating information obtained from each local agent.
2018
2020
There have been very few recent developments in decentralized learning algorithms with DP guar- antees. We are aware of only three recent works in the literature. Among them, Huang & Gong (2220) is the first one; they proposed DP Alternating Direction Method of Multipliers (ADMM) algorithm for a wide range convex learning problems, where they perturb the objective function before solving the minimization associated with the local dataset each local agent. More recently, Yu et al. (2021a) proposed a DP decentralized stochastic gradient descent (SGD)-based algorithm by perturbing the intermediate parameter updates each local agent before communicating the perturbed parameter updates with its connected neighbouring agents: Xu et al. (2022) proposed a blockchain -enableed-e decentralized DP learning algorithm through gradient perturbation. However, these gradient-basee based methods impose restrictions on the objectives, such as smoothness, and there- fore have limited application gradient descent to find the minimums of the target objective functions. Instead, by using operator theory, we solve the optimization problem by defining a suitable operator or mapping such that the fixed points the solutions the original problem; in other words, consider a broader generic problem of finding a fixed point of averaged iteration of a nonexpansive mapping. Under such an operator theoretical framework, the SGD and ADMM algorithms previously considered in [Huang & Gong (020)); Yu et al. (2021a): Xu et al. 2022 generic algorithm.
broader settings.
contrast, we don't 't restrict ourselves to using
can be considered special cases of our proposed
1.2 OUR CONTRIBUTIONS
In this paper, propose general framework of a decentralized learning algorithm with DP guaran- tee, referring to Differentially Private decentralized Krasnosel'skil-Maan skii-Mann iteration (DP-dKM). Our contributions are summarized as follows.
1. Built on the Krasnosel skii Mann(KM) iteration (Krasnosel skii 1955 Mann 1953 we propose a unified decentralized learning framework with an overall DP guarantee, which is applicable to all communication network diagrams and covers many existing optimization algorithms, including the previously considered ones in Xu et al. (2022): Huang & Gong 2020). as special cases.
Yu et al. a021a):
2. We obtain an upper bound of the global sensitivity of the intermediate updates until the fixed iteration step; by injecting enough noises calibrated according to this upper bound, we can achieve a global (c. 6)-DP guarantee without worrying about splitting the total privacy costs among different agents.
3. To the best of our knowledge, provide the first decentralized learning algorithm that can achieve any desired overall DP guarantee while existing works rely on local DP mecha- nisms and therefore have no control over the overall privacy cost beforehand. And this is the first work that provides theoretical guarantees on the generalization and finite sample performance of the proposed algorithm.
4. To further optimize the privacy and utility trade-offs, we propose class of truncated gen- eralized Gaussian noise-adding DP mechanisms, which allows one to achieve significantly higher utility under the same level of DP guarantee.
5. Empirically, conduct comprehensive experiments to demonstrate that our approach out- performs prior works in various decentralized settings characterized by different commu- nication network diagrams.
2

---

Under review as a conference paper at ICLR 2023
2 PROBLEM STATEMENT AND PRELIMINARIES
In this section, we first start with the problem set. We then present preliminaries about decentralized learning schemes as well as differential privacy. Throughout this paper, we denote the f1. l2, foo norm of E IR" as || ||]]| and | For function ((x,
R" x E + R, |/ == sup,,5 [[x E)I- For a matrix, A denotes A ||Allops ||A|| F as its transpose, spectral norm, and Frobenius norm respectively. Given another matrix B, A > B means that A B is positively defined, and B means B is positive semidefinite.
Problem formulation: Consider network with M agents, each of which holds dataset E.m = (5((m))ss for m 1,..., M, where N; is the number of training samples in the dataset Em. Si(m) E RP is the i-th sample stored in the m-thh agent. We assume that data are evenly collected and each agent has equal sample size of N for ease of presentation. Our primary focus is solving a stochastic decentralized optimization approximated by its corresponding empirical loss,
M
N
M
N
Ż(x) = min Σ Σ Im (ar, (i(m))))) E := arg min #ER MN
Σ
Σ
lm (a,, (i(m))
ZERP
MN
where is the target parameter, and (m)s)s are the objectives that measure the performance of the local models. Throughout, we assume the objectives are convex, closed, and proper (c.c.p) but not necessarily differentiable. The goal is to learn a globally optimal solution, referring to consensus parameter (Cao et al. 2021 Shi et al. 2014) ā= M Em= x(m). on M agents across a network diagram, where x [im) is the solution of the local parameter on the m-th agent. Among the agents, the estimates per iterate are peer-to-peer without the existence of a central coordinator, and its connection is typically modeled as graph, e.g. Figure 4 in the Appendix. We stress that each agent operates independently and the average is only taken in the last iteration.
Communication graph: We now formally define the mathematical concept of graphs character- ize the communication among the agents. We define the connected network by, 9 = (V, E) with vertex set V {1, (1....,,M and edge set 3 - V. We denote ((m) the neighbour set of agents m. Edge (m, I) E E represents the interconnection between agent m and its neighbors E A (m). The decentralized optimization is associated with a given network topology that can be formulated mathematically by a mixing matrix (Alghunaim et al. 2019 Ying et al. 2021) and its properties can be summarized as follows.
Definition (Mixing Matrix) For any given graph g = (V,E), the mixing matrix W [wm.i] RMMxM defined on the edge set V that satisfies: (1) if m * and (m, 1) & E, then wint 0; otherwise, Wml > 0; (2) W WT; (3) null(T-
W) span 1); (4) Iz W > -I.
We remark that W is double gossip matrix that characterizes the communication among the agents Sun et al.] 2021). Let :=
and the matrix is non-unique for a given graph (Ying et al. 2021
max A22 [AMl], where \; denotes the ith largest eigenvalue of W
M
The spectral gap as
1-X X measures the connectivity of gossip communications among these agents (Zhu et al. 2022).
Definition [ implies that 0 X 1. A larger value of À indicates less exchange communication among local agents.
The KM iteration, as a simple implementation and fast convergence method in practice, has a long history and has been the most useful method in modern computing including operator-splittigg and alternating-direet dirrectio methods (Wotao) 2019 Wang et al. 2022). is the basic and one of the most popular iterative schemes for finding one fixed point of nonexpansive operator. Specifically, the
KM algorithm offers several advantages over traditional optimization methods (e.g., Newton-type algorithms and interior-point methods) (Davis & Yin 2016); Ryu & Yin 2022 Liang 2016): the former can easily handle nonsmooth terms and abstract linear operators, requires only simple arith- metic operations and scales well with the dimension of the problem. The KM additionally applies decomposition procedure in which the original problem is broken into subproblems that can easily be solved (Ryu & Boyd| (0166) The KM iteration is widely applied centralized learning (Chaiii & Taka8 2019] /Saber Malekmohammadi 2021 Malinovsky et al.) (020).H However, it is still an open question perform the KM iteration in decentralized learning setting. We next fill this gap by proposing the decentralized KM iteration and presenting detailed schemes for the local agents.
3

---

Under review as a conference paper at ICLR 2023
Definition 2 (Stochastic Decentralized Krasnosel'skii-Mann (dKM)) Suppose the training sam- ple set = U Em is distrübuted-stored in M agents with total sample size NM, where E.n is a training dataset located in the m-th agent for m = L,,-. M. We assume that Ei(m) ~ P with Sa(m) E Emmfor any m,i. i. For each agent, given a nonexpansive operator T, the iterative formula of the stochastic dKM algorithm, A, is defined as,
x (m) = Ax (m)) - Σ
(mma"(1) + ou (T (m))) -x (m)), (I) (EN(m)
where Wmi is the element of a given matrix W satisfying Definition 1 an E (0, in is an i..dd
variable drawn from the uniform distribution over {1,-.. .N} at the k-th iteration. Further, let
X [x(1). xx (M)] E MxP that stores all local parameters across the network, T(X;
[T (=(1; 3 , EM)) E IR 1gMxx stacking all local updating w.e.. the first argument. Iteration has the matrix form, xk+1 = WX + Ock (T (x) x²).
As we consider the general framework of decentralized learning problem with mild conditions (c.c.p.) for the loss, general computational procedures with wide coverage and flexibility that can be used to handle numerically inconvenient loss come more naturally. Specifically, the form of T in Definition] 2 depends on the specific algorithm we adopt. For example, dKM implies gradient descent, proximal gradient descent, and ADMM algorithms in a decentralized setting when choosing T as forward operator, Table D in the appendix for some forms of T. Additionally, the stochastic dKM algorithm provides a guideline to design a new decentralized learning algorithm by specifying the form of T.
operator, and Douglas-Ruchford Rachford operator. Please refer to
Despite each agent communicating with its neighbours by sending parameters instead of directly exchanging raw data, the risk of leaking information still exists: the attacker can recover the sensitive information of data from shared parameters as discussed in Shokri et al. (217)) Fredrikson et al. (2015). This motivates us to consider privacy preserving iteration procedure with efficient communication while it retains a performance guarantee. Differential Privacy (DP), introduced by Dwork et al. (2006), is a widely adopted definition due to its important advantages over other privacy techniques. It quantifies to what extent individual privacy in a dataset is preserved while releasing aggregated information.
Privacy Concern:
Definition 3 ((E, ((e,))-Diffeee Diffferential Privacy Dwork et al. (0066) A stochastic algorithm A is called (e. diiffffffrettt privacy for any subset Eo
C I2 and any neighbouring sample set pair E and E'
[ F (
which differs by only one sample, we have log
The common interpretation of (s, -)ddffferre privacy is that it e-differential privacy except with probability 5 (Mironov| /Mi7) The parameters& and 5 are privacy budgets indicating the strength of privacy protection from the algorithm. The classic differential privacy is called e-differential privacy with 8 = O. which imposes upper bound e the multiplicative distance of probability distributions of randomized query outputs for any two neighbouring data sets (Dong et al. 2019).
3 SENSITIVITY OF THE STOCHASTIC DKM ITERATION
In this section, we estimate the l norm sensitivity of the stochastic dKM, laying the foundation for noise addition in the truncated generalized Gaussian mechanisms in Section Before formalizing the result, we present the assumptions throughout and introduce the definition of the sensitivity of algorithms in a decentralized learning setting.
Assumption (1) The loss function is c.c.p. and sub-differentiable with respect to x. and the fixed- point iteration bounded by a finite constant B, i.e., max,,g [[ E) x1 < B: (2) The loss function 1(. E) is nonnegative and ||||| I R for some constant R 0.
[[T E) || in Assumption (1) is defined as a fixed point residual in the literature which typically relates to the gradient of an objective function (Davis & Yin 2016). We note that Assumption (1) is (0220)|Sun)) [Sun et al. (202T): Zhu et al.
weaker than Yu et al. (202 a); Xu et al. (2022): Huang & Gong (2020);
2022) as well as common Assumption (2) in Sun et al. (2021) Zhu et al. (2022
4

---

Under review as a conference paper at ICLR 2023
The sensitivity based on two datasets that differ at only one point is commonly used in Yu et al. a0 Xu et al. (2022) ; Huang & Gong 2020). Although the only different point stored at any lo- cal agent, the local communication among agents without a coordinator, affecting the full networks, promotes us to quantify its impact on a learning algorithm globally as introduced in Definition
Definition 4 (Sensitivity) For a specific algorithm A acting on training samples, E'E"" which are two adjacent datasets that differ by data point. Until iteration K, define the -e-seiiitvvtty of algorithm A as AK == supE (E') (E")II
We are now establishing the A - of the dKM algorithm. That is, we, through Theorem provide the boundedness on Ax due to the only one different point for any two adjacent datasets.
Theorem (Ak -Sensiiviity Given rK as the corresponding outputs of the dKM algorithm applied to two sets E. =" of size NM which differ only one point. Assume the initial value X = O. With Assumption (1) satisfied, given relaxed parameter, {ox 1K E (0, 11, the A Ax-sensitivity of the dKM algorithm has the upper bound.
M - - M
(m)) (m) y Em 1 (m) denote x² and y M
EAK S
2B
2
K-1 K=
aK
+4B
E1 2ax) R=0
K-1
R-1
aajaa-1-s
NM
1=0
Note that the derivation of sensitivity of our proposed dKM algorithm does not require the assump- tion of smoothness and strong convexity of objective functions. Theorem | lated deviation bound between two trajectories of iterates based on two datasets that differ at only one point, where it allows to exist at any local agent. Compared with Huang & Gong (2020) studying the local sensitivity, Theorem | establishes the global sensitivity as the local communication of the network makes this different point, e.g. storing in agent 1, affects the final output. The expectation in Theorem | comes from the randomness of picking the different point to update the iterate in Defi- pick the only different point for two adjacent datasets with probability 1/N to update the iterate and have 1 1- 1/N chance using the same points. We, from Theorem D have that with fixed iteration number K, the data size, M, N increases and decreases, Ax k gets smaller for both diminishing and constant learning rates. However, it fails to control the sensitivity when K increases, which also suggests the risk of privacy that, with the higher iterative step, will be easier to identify the specific sample. Moreover, the sensitivity decreases as À decreases indicating the effect of different topologies on Áx. Table 2 in the appendix summarizes for clarity. This theorem also provides rule to establish the adding mechanisms to guarantee DP in Section 5
quantifies the accumu-
nition 2 Specifically,
4 PERFORMANCE AND GENERALIZATION OF DECENTRALIZED LEARNING ALGORITTM WITH DIFFERENTIAL PRIVACY
Existing DP schemes in decentralized learning typically rely the perturbation of objective func- tions, and gradients, but are limited to iterates (Yu et al. 20 Xu et al. 2022: Huang & Gongl 2020). Such methods usually introduce extra noise that has privacy preservation. is still hard to examine the privacy and performance trade-off in the generalization of DP algorithms (He et al.) 2021]. In this section, we establish a generalization error bound and finite sample guarantee of decentralized learning algorithms when these algorithms satisfy differential privacy. These results illustrate the effectiveness of using dKM with any differentially private mechanism (Definition 3 in applications. We next proceed by quantifying the bound considering iterate independent noise addition mechanisms and computing the end-to-end differential privacy guarantee across M agents over network system.
Let L(x) = [Eg==[(<, {)] and xt be its optimal solution. Note that, for a specific stochastic al- gorithm B : (A.,... , AAs) on E with sample size NM with output B(E), where A AM performing on local agent allows being different, the excess generalization error of B defined as, Ez,8 (B)) L (x*) )] can be decomposed into three terms (Bottou & Bousquet 2007).
Es,8 L(B())) L(B(E))
+ B F(B()))- - [())
+ +E, [(()) (x*)
(2)
gemeralization emor
optimization errur
test error
5

---

Under review as a conference paper at ICLR 2023
We establish the boundedness of generalization error in Theorem 2 that reflects joint effects caused by the data and the algorithm.
Theorem (Generalization Bound) Assume that the decentralized learning algorithm B E + RP x (1, .M is (effe-iiffreentially private. Under Assumption (2), we have that,
E [B((E)) [(((EE) (1-
E-PMY (E))
Theorem (Finite Sample Guarantee) Under the Assumption of Theorem we have,
F(L(B(E)) & L(B(E) + (1- =MM
for any >
6 + R
These two theorems represent the gap between the empirical loss based on finite samples and its expectation. It demonstrates the impact of differential privacy on out-of-sample performance by establishing the bound of (B()))) in probability and expectation. Although ensuring data privacy sacrifices the generalization, these results show that good privacy-preservee
mechanism still re- tains a certain level of generalization as well as a finite sample guarantee. In the existing work for DP decentralized learning, Xu al. 2022) provided convergence and regret analysis based on gra- dient aggregation and Gaussian mechanism explored the convergence rate of SPD algorithm with Gaussian mechanism; HHung & Gong (2200) theoretically analyzed the utility of DP-ADMM algorithm, which can be measured by the expected empirical risk with feasibility violation. Note that our theoretical results in Theorem 2 and 3 aare suitable for all DP mechanisms. As far as we know, we are the first to establish a generalization bound and finite sample guarantee in DP decentralized setting.
the presence of Byzantine nodes; Yu et al. (2021a)
We address that Theorem and 3 require the algorithm B globally being (s, d)-D.. Additionally, considering that each agent acts independently practice, where there is less likely to reach an agreement on consistent (s, 8)-P across all agents (Bellet et al. 2018), we then proceed by investigating how the local computation would affect global differential privacy as a composition
theorem which also provides the reasonableness of DP assumption in Theorem and B In detail,
Theorem shows the level of overall privacy cost, given the privacy cost levels of the local agents. Similar results are discussed in Huang & Gong (2000); Yu et al. (2021a).
Theorem 4 (Composition Theorem) Define iterates, which is similar to the output in Definition 2 generated by the specific stochastic algorithum with K steps as {x* K For the m-th agent, denote Am : :E + (m)) where a² (m) is the iterates corrupted by noise. For any fixed m, if Am is (Em, 5m) diifferreet private, then X = (1), (1),...,.$MMM) (M)) is ('d.8))-iffeerenta private, where,
M II
8m
}
M
8 m + c
e' = min (2,,,, 81
(1 am
II
1 + 1 @5
m=1
with, Eι = MM Cmr E2 = MM
(05m-1)em
EMM 262 log ce V ca
E3
efm+1
IM CKL(m) + /2log( d )
M m=1 2nh) with (k)(m) min {min {2, c=m 1} Ems Em for
some am S Em, MM am s', and real constant 8.
For completeness, Algorithm D shows the detailed iterative step of dKM with noise addition to preserve DP, and we further examine the optimization error bound in formula (2) that is caused by adding noise to the query output. Specifically, we consider iterate independent noise addition mechanisms (Definition 5) to preserve DP for dKM in practice: a random noise is added to the iterate to reduce leakage information.
Definition (Noise-adding Mechanisms for dKM) Given a data set E, a query-output indepen- dent noise-ade adding mechanism A will release the query output zt = A(x*;E) corrupted by an additive random noise d, - x + d.

---

Under review as a conference paper at ICLR 2023
Algorithm Differentially Private Decentralized Maasnosel'skii-MMin Iteration (DP-dKM)
1: Initialize: X", .mixing matrix W, on E (0, 1J. number of iterations K
2: while & I K do
3: for m E V (m E MJ) do
4: (mm) = wX (m) + 1
- -z (m)) (Local computation)
5: end for
6: for m E do
7: Generate random noise en. x (m) x (m) + t (Differential Privacy)
8: Broadcast (m) to all neighbours j E (m(m
9: end for
10: end while
Output: X (x (1), xx(M) (M)) and æ
M Σm xx (m)
Let X [ , E RMx be the true parameter and X = [ā(1, T be the released iterates corrupted by an additive random noise for each agent, the DP-dKM can be written
as X WX* + az (T (x*; x*). According to Assumption (1) and (2), the error bound controlled by
|| an (T (x :) x+) x - W Xx* -
where the first term the same in the non- con-privacy setting, which depends on the convergence properties of a given algorithm (Wotao 2019). The second term indicates the deviation by using the privacy mechanisms. The following theorem gives the upper bound of the second term.
Theorem (Boundedness of local iterates based on Gaussian additive noise) Given a data set E. assume iterative independently noise-adding mechanism A releases the output ; x² + corrupted by an additive random noise d, where d follows a Gaussian distribution with mean y and variance o². The error bound caused by the additive noise
)1 sp + n²) 1)2- +1]
E
W x
DIFFERENTIAL PRIVACY VIA TRUNCATED GENERALIZED GAUSSIAN MECHANISMS
While commonly adopted Gaussian aaisen mechanisms for a single iterate can guarantee DP (Croft et al., 2022, Cormode et al., 2019) Yu al., 2021a| Xu et al., 2022, Huang & Gong 2020), such mechanisms do not take into consideration the valid range of the iterates being posed and the utility of learning algorithm Geng et al. (2018); Bun et al. (2018): the extremely large noise will severely affect learning process and degrade the performance of the trained model under differential privacy guarantee. For example, Yu et al. 202 b) gave the lower bound of variance of Gaussian noise guarantee DP. Ganesh & Zhao 2020) considered (e, diifferenttt privacy with generalized Gaussian mechanisms to answer & counting queries about a database. Different from Ganesh & Zhao (2020), our proposed generalized Gaussian mechanisms novel due to the boundedness of noise. Specifically, we truncate the probability density function used for the generation of noise with careful determination of an appropriate bounding parameter and propose truncated Generalized Gaussian (GG) distribution Pa == GG(O, a, b) with location parameter 0, scale parameter 0, shape parameter > Its probability density function is.
p(= b,), Cag exp {
)
[21
6
where E A-,,,A,
(3)
where Cyg is a constant to guanrantee / p(2 0, b)dz = 1. In the experiment, we use truncated GG noise with b = 2, which represents the truncated Laplace distribution (Definition 6 and truncated normal distribution (Theorem to preserve DP.

---

We compare the proposed DP-dKM algorithm with baseline algorithms under various decentralized settings (ring, star, and full-connected graphs): (a) non-private decentralized approach; (b) private decentralized approach with Laplace noise; (c) private decentralized approach with Gaussian noise Yu et al. 2021a: Huang & Gong 2020). The average root means squared error (RMSE) is used to quantity their performance. To start with, we do a sensitivity analysis caused by privacy parameters fully connected graph. The results are Under review as a conference paper at ICLR 2023
Definition 6 (Truncated Laplacian Distribution Geng et al. (2018)) Given the privacy parame-
ters. < 8 < 2' E > O, and iterates sensitivity > O. the truncated Laplacian distri-
bution with = 1 in formula (3) preserves (e, (e.8)-differential privacy when taking À == A
CLap = (2x (2x e (1--x) )) A À log (1+ e--1)
26
Theorem 6 (Truncated Gaussian Distribution) The truncated Gaussian distribution Pnor(z) with P in formula (3) preserves (e, (e.)))difeeeee -differrrntt privacy, where o² 2 E A?? , the constants Cror and A are determined by J-A Pnor (z)r(2)dz satisfying the equation,
Cnor Σ(-1
A
1 2' Cnor
((-)) 1=0
22 (A 2)
=
22 +
1=0
Note that the truncated Gaussian mechanism is also considered in Cesar & Rogers (0221) which focused on exploring privacy loss composition bounds for special classes of differentially private algorithms, while we aim to reduce the amount of added noise with the same level of privacy, An important property of the truncated GG mechanism is that the range of addition noises is bounded to A- A] while the DP still holds. More importantly, the truncated GG mechanism simultancously improves the utility and guarantees privacy. good performance compared with the state-of-the-an methods is illustrated in the numerical experiments.
5 0.01
5 0.1
0.01
f.1
-Lppox
Logier
25
Gemmin
35
GGanca 2
-Galliy
Grases
traceed Laplen
Sevated Laglns
Iiaacadd Chcuuia e 63
Insaand Gutrile d Le-
25
Figure 1: The sensitivity analysis of parameter (E, for SGD with a full connected graph.
NUMERICAL EXPERIMENT
(c, by solving least squares using the SGD algorithm
shown in Figure [
In Figure 1 the first and second columns compare the performance of Laplace and truncated Laplace mechanisms with different and Similarly, the comparisons between Gaussian and truncated Gaussian mechanisms are shown in the third and fourth columns. Figure indicates that the pro- posed mechanism has the smallest RMSE compared with Laplace and Gaussian mechanisms and enjoys better convergence properties. In addition, the results demonstrate the privacy-utility trade- offs of the proposed approach: the RMSE increases E increases with fixed 8. When privacy leakage increases, the truncated Laplace and truncated Gaussian approach achieves better utility.
We next consider 4 regularized least square regression and & regularized logistic regression by employing the differentially private SPGD and ADMM algorithms with truncated generalized GG noise with b = 1.2 2 to evaluate the performance of Algorithm
N
M
N
Σ
(Amiz - bmi))² 2 + A||
Σ VIL
flog(1 + +mAaa)) - Ama + A||2|12-
MN
MN
The element Amis I are drawn independently from the normal distribution. > 0 is a regularized parameter controlling the impact of the regularizer and is chosen by the grid search method. We fix
8

---

Under review as a conference paper at ICLR 2023
Ring
Ring
Ring
Ring
100
withon
EC
Lapaer
Eaplic
Guariia
Ludit
-33
Iraw and Cuasias
10
15
150 Itee GD)
102
190
220
100
200
230
55
100
200
230
Iter ADMM)
Iser (SPG))
Iter (ADM))
Star
Stat
Star
Star
Taplica
Laglen
Eaplice
Laphox
mnamiie Gocati
Inaarsid Chearii
Irem and Loc
M
163
120
500
100
100
700
100
750
Hee (PPG))
Itert (DMM)
ISPG))
[eM(ADDMM)
Full connected
Full connected
connected
comnocted
1s
Sapkir
Lophes
Lappion
Laghan
Saplin
Cacadl
Iten (SPGD)
(DMM)
(SPC))
[DK(AMMM)
Figure 2: Estimation error on Ring, Star, and Full connected graphs. The first and two columns are & penalized least squares; The third and fourth columns are & penalized logistic regression.
the privacy budget e = 0.5 and 5 = 10-3 to evaluate the performance of the truncated approaches under the settings with different numbers of distributed data sources and different typologies. The We consider M 5, N 100 in Figure 2 Figure B
results are summarized in Figure 3 explores the estimation eтror as the number of agents changes, showing that RMSE increases as agents increases. It also demonstrates that the truncated GG mechanism has the smallest RMSE than Laplace and Gaussian mechanisms, and keeps the same level of privacy. These results also show the the algorithm converges faster
effect of the topology graph on the convergence of the Algorithm [ with the star and full-connected graphs than the ring graph.
< penalized leaet squaces
F penalizod lesel aquirree
penalized logistic regression
F. pennlised logistic regr esstion
Higgermmmte Luplons
---ptppttaannet Luphor
-i-gga eecoceet Luphor comastie Enplece
Laylao
meceate pnreeni Lapiaco
mennte) cnsembial laphar
400
100
convimeeant Gattethe
Star irsooned Comertis
Strittmponee Commtoo
XX
200
15
100
10
10
agente/SPPD)
agents (ADMt)
SSPnt
agents(ADMbl]
Figure 3: The estimation error as the number of agents changes.
7 CONCLUSION
In this paper, we have proposed a general framework of the that is applicable to all communication network diagrams and covers many existing decentralized learning and optimization problems and show that the proposed algorithm retains the performance guarantee generalization, and finite sample performance. We also established the effect of local privacy-preserving computation on global differential privacy. To avoid extremely large additional noise added to the shared information that will severely affect and degrade the performance of the learning process, we have introduced truncated generalized Gaussian mechanism, in which we demonstrate privacy and utility trade-offfs under a differential privacy guarantee. Experiments have demonstrated that our algorithm is effective in decentralized settings and performs better than the state-of-the-ane baseline algorithms.
algorithm, DP-dKM,
9

---

Under review as a conference paper at ICLR 2023
REFERENCES
Sulaiman Alghunaim, Kun Yuan, and Ali H Sayed. A linearly convergent proximal gradient algo- rithm for decentralized optimization. Advances Neural Information Processing Systems, 32,
2019.
Aurélien Bellet, Rachid Guerraoui, Mahsa Taziki, and Mare Tommasi. Personalized and private peer-to-peer machine learning. In International Conference on Artificial Intelligence and Statis- tics, pp. 473 481. PMLR, 2018.
Oya Beyan, Ananya Choudhury, Johan van Soest, Oliver Kohlbacher, Lukas Zimmermann, Hol- ger Stenzhorn, Md. Rezaul Karim, Michel Dumontier, Stefan Decker, Luiz Olavo Bonino da Silva Santos, and Andre Dekker. Distributed analytics on sensitive medical data: The per- sonal health train. Data Intelligence, 2(1-2):96 107, 2020.
Léon Bottou and Olivier Bousquet. The tradcoffs of large scale learning. Advances in Neural Information Processing Systems, 20, 2007.
Mark Bun, Cynthia Dwork, Guy N Rothblum, and Thomas Steinke. Composable and versatile privacy via truncated cdp. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 74-86, 2018.
Zhipeng Cai, Zaobo He, Xin Guan, and Yingshu Li. Collective data-sanitization for preventing sensitive information inference attacks in social networks. IEEE Transactions on Dependable and Secure Computing, 1574)5577-590, 2018.
Xuanyu Cao, Junshan Zhang, H. Vincent Poor, and Zhi Tian. Differentially private admm for reg- ularized consensus optimization. IEEE Transactions Automatic Control, 66(8):3718-3722 2021.
Mark Cesar and Ryan M. Rogers. Bounding, concentrating, and truncating: Unifying privacy loss composition for data analytics. Proceedings of Machine Learning Research, 132:1-37, 2021.
Khaled A. Kovalev D. Richtárik P. Salim A. Chraibi, S. and M. Takáč. Distributed fixed point methods with compressed iterates. ArXiv:1912.09995. 2019.
Graham Cormode, Tejas Kulkarni, and Divesh Srivastava. Constrained private mechanisms for count
data. IEEE Transactions on Knowledge and Data Engineering. 33(2):415 430, 2019.
William Croft, Jörg-Rüdiger Sack, and Wei Shi. Differential privacy via a truncated and normalized laplace mechanism. Journal of Computer Science and Technology, 37(2)3669-388, 2022.
Damek Davis and Wotao Yin. Convergence rate analysis of several splitting schemes. In Splitting Methods in Communication, Imaging, Science, and Engineering, pp. 115-163. Springer, 2016.
Jinshuo Dong, Aaron Roth, and Weijie Su. arXiv:1905.0238: 2019,
Gaussian differential privacy. arXiv preprint
John Duchi and Ryan Rogers. Lower bounds for locally private estimation via communication complexity. In Conference Learning Theory, pp. 1161-1191. PMLR, 2019.
Cynthia Dwork and Guy N Rothblum. Concentrated differential privacy. arXiv preprint 160iv 2016.
Cynthia Dwork. Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference, pp. 265-284. Springer, 2006.
Farhad Farokhi. Distributionalll--rouust machine learning using locally differentially-prive data. Optimization Letters, 16(4): 166-11199 2022.
Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit confi- dence information and basic countermeasures. Proceedings of the 22nd ACM SIGSAC Confer- on Computer and Communications Security, pp. 1322-1333 1333, 2015.
10

---

Under review as a conference paper at ICLR 2023
Arun Ganesh and Jiazheng Zhao. Privately answering counting queries with generalized gaussian mechanisms. arXiv:2010.01457, 2020.
Quan Geng, Wei Ding, Ruiqi Guo, and Sanjiv Kumar. Privacy and utility tradeoff in approximate differential privacy. arXiv preprint arXiv:1810.00 000777 2018.
Yanmin Gong, Yuguang Fang, and Yuanxiong Guo. Private data analytics on biomedical sensing data via distributed computation. IEEE/ACM Transactions Computational Biology and Bioin- formatics, 13:1-1, 01 2016.
Shaoyong Guo, Yuanyuan Qi, Peng Yu, Siya Xu, and Feng Qi. When network operation meets blockchain: An iaaiiiica-iitelligenee-tttiiii customization service for trusted virtual resources of iot. IEEE Network, 34(5):46-55 53, 2020.
Shuo Han, Ufuk Topcu, and George J. Pappas. Differentially private distributed constrained opti- mization. IEEE Transactions on Automatic Control, 62(1):50-64 2017.
Fengxiang He, Bohan Wang, and Dacheng Tao. Tighter generalization bounds for iterative differen- tially private learning algorithms. In Uncertainty Artificial Intelligence, pp. 802-812. PMLR, 2021.
Zonghao Huang and Yanmin Gong. Differentially private ADMM for convex distributed learning: Improved accuracy via multi-step approximation. 2020. doi: arXiv:2005.07899.
Zonghao Huang, Rui Hu, Yuanxiong Guo, Eric Chan-Time Tin, and Yanmin Gong, Dp-admm: Admm- based distributed learning with differential privacy. IEEE Transactions on Information Forensics and Security, 15:1002-1012, 2020.
Bargav Jayaraman, Lingxiao Wang, David Evans, and Quanquan Gu. Distributed learning with- out distress: Privacy- preseevii empirical risk minimization. Advances in Neural Information Processing Systems, 31, 2018.
M.A. Krasmosel'skin skii. Two remarks on the method of successive approximations. Uspekhi Matem- aticheskikh Nauk, 10: 10:122-127, 1955.
Yiwei Li, Shuai Wang, Tsung-Hui Chang, and Chong-Yung Chi. Federated stochastic primal-dual learning with differential privacy. arXiv preprint arXiv:2204.12284 2022a.
Zhize Li, Haoyu Zhao, Boyue Li, and Yuejic Chi. SoteriaFL: A unified framework for private federated learning with communication compression. arXiv preprint arXiv:2206. 09988, 2022b.
Jingwei Liang. Convergence rates of first-order operator splitting methods. Optimization and Con- trol [math. OC], 2016.
Grigory Malinovsky, Dmitry Kovalev, Elnur Gasanov, Laurent Condat, and Peter Richtárik. From local sgd to local fixed-point methods for federated learning. Proceedings of the 37th Interna- tional Conference on Machine Learning, 621:6692-6701, 2020.
W. Robert Mann. Mean value methods in iteration. American Mathematical Society (AMS), 4(3): 506-510, 1953.
Ilya Mironov. Rényi differential privacy. In IEEE 30th Computer Security Foundations Symposium (CSF), pp. 263-275. IEEE, 2017.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018
Ernest K Ryu and Stephen Boyd. Primer on monotone operator methods. Appl. comput. math, 15 (1):3-43, 2016.
Ernest Ryu and Wotao Yin. Large-Scale Convex Optimization. Cambridge University Press, 2022.
Zeou Hu Yaoliang Yu Saber Malekmohanmadi, Kiarash Shaloudegi. An operator splitting view of federated learning. 10Xiv:2/08.05977 2021.

---

Under review as a conference paper at ICLR 2023
Wei Shi, Qing Ling, Kun Yuan, Gang Wu, and Wotao Yin. On the linear convergence of the admm in decentralized consensus optimization. IEEE Transactions on Signal Processing. 62(7):1750- 1761, 2014. doi: 10.1109TTSP20442334422.
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference tacks against machine learning models. In IEEE Symposium on Security and Privacy (SP), pp. 3-18. IEEE, 2017.
Tao Sun, Dongsheng Li, and Bao Wang. Stability and generalization of decentralized stochastic gradient descent. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 9756-9764, 2021.
Yafei Wang. Bo Pan, Wei Tu, Peng Liu, Bei Jiang, Chao Gao, Wei Lu, Shangling Jui, and Lin- glong Kong. Sample average approximation for stochastic optimization with dependent data: Performance guarantees and tractability, In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 3859-3867, 2022.
Stefanie Varnat-Herrestall. Hartmut Schultze, Krishnaprasad Lingadahalli Shastry, Sathya- narayanan Manamohan, Saikat Mukherjee, Vishesh Garg, Ravi Sarveswara, Kristian Händler, Peter Pickkers, N Ahmad Aziz, et al. Swarm learning for decentralized and confidential clinical machine learning, Nature, 594(7862) 2021.
Yin Wotao. Operator splitting methods for decentralized optimization. Mathematica Numerica Sinica, 21(3):225,00))
Minghui Xu, Zongrui Zou, Ye Cheng, Qin Hu, Dongxiao Yu, and Xiuzhen Cheng. SPDL: A Blockchain-enabled secure and privacy-preserving decentralized learning system. IEEE Transac- fions on Computers, 14(8):1-1, 2022.
Bicheng Ying, Kun Yuan, Hanbin Hu, Yiming Chen, and Wotao Yin. Bluefog: Make decentralized algorithms practical for optimization and deep learning. arXiv preprint arXiv:2111.0428 2021.
Dongxiao Yu, Zongrui Zou, Shuzhen Chen, Youming Tao, Bing Tian, Weifeng Lv, and Xiuzhen Cheng. Decentralized parallel SGD with privacy preservation in vehicular networks. IEEE Trans- actions on Vehicular Technology, 7066):51115522) 2021a. doi: 10. 2.11099TTT..22213366644
Dongxiao Yu, Zongrui Zou, Shuzhen Chen, Youming Tao. Bing Tian, Weifeng Lv, and Xiuzhen Cheng. Decentralized parallel sgd with privacy preservation in vehicular networks. IEEE Trans- actions Vehicular Technology, 70(6):521155277 2021b.
Tongtian Zhu, Fengxiang He, Lan Zhang, Zhengyang Niu, Mingli Song, and Dacheng Tao. Topology-awe aware generalization of decentralized SGD. In International Conference on Machine Learning, pp.
PMLR, 2022.
12


Reviews:
[{"review_id": "sw9PCGLUtr", "reviewer": "Reviewer_boyW", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper claims to give a general DP framework for decentralized data. The authors claim that the algorithm retains all the desirable properties that we have in non-private setting: generalization or stability and finite sample performance. ", "summary_of_the_review": "I was unable to read the proofs of the main claim, so I cannot make a judgement of their correctness. For now, I would rely that the authors have done their paper in writing the correct proof. \n\nI have one central question. Ganesh and Zhao proved that generalized Gaussian is DP for all b \\leq \\log(k), where k is the number of queries (in their paper). The current submission makes similar statement but only for b=2. How is the proof different or anyhow technically novel considering the paper by Ganesh and Zhao (2020) and adapting their proof for truncated Gaussian just like Geng et al. did for truncated Laplacian? Am I missing something here? The authors have not cited Ganesh and Zhao, so I am wondering if the authors are aware of the paper. \n\nSecond, the authors claim that they present their result for equal sample size for the ease of presentation. Is it just for the ease of presentation or is it the case that the analysis only goes through when sample sizes are equal. I would imagine that if the sample size comes from a very skewed distribution, then we should not be able to say anything meaningful about the generalization error. \n\nWhy do we call the mean parameter vector a consensus vector? Is it common in this literature?\n\nWhat is $\\lambda$? I am guessing it is the rate of the convergence to the stationary distribution.\n\nWhat is the notation $\\| \\ell \\|_\\infty$?\n\nTheorem 5: What is $C_{KL}$ and is other $\\widetilde X(i)$ defined similarly to $\\widetilde X(1)$? Theorem statement should be precise and complete on their own. \n\nThe notation $\\mathbb P$ is overloaded. \n\nDisclaimer: I am trying to read the proof. I hope to be able to engage with the authors much more during the discussion phase. My current scores are for placeholder. \n\n\n\n\n[1] Ganesh and Zhao. https://arxiv.org/abs/2010.01457", "strength_and_weaknesses": "The main idea in this paper seems to be to use the private version of stochastic D-KM algorithm. The paper analyzes its sensitivity and from there uses truncated generalized Gaussian mechanism for privacy. The paper claims privacy proof for truncated generalized Gaussian mechanism as well. I believe this can be casted as one of the novel contribution of the paper, too. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "MMpgFkfbEz7", "reviewer": "Reviewer_Xztu", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper develops a new differentially private (DP) framework to tackle the problem of decentralised consensus learning. This framework is based on the stochastic Decentralised Krasnosel'skii-Mann (D-KM) iteration (its privatised version referred to as \"DP-KM\" in this paper). It provides both theoretical and empirical results for their approach.", "summary_of_the_review": "I don't think I got enough information from this paper to be able to provide a convincing argument in favour of accepting it. I hope my suggestions/comments on the writing help the authors.\n\nUpdate: I appreciate and respect the authors' willingness to make all the suggested edits to improve the readability. However, I see that a *very significant* portion of the paper had to be rewritten in order to introduce more clarity, so I am hesitant to change my score. The readability has improved a lot, but I think the authors might benefit from spending some more time on the presentation of the paper, and providing a more convincing argument about the problem and the technical challenges and novelty.", "strength_and_weaknesses": "Strength:\n1. A new private framework is provided to deal with this problem that utilises generalised versions of distributions, like Laplace and Gaussian. There is mathematical rigour in this paper, which I appreciate.\n\nWeaknesses:\n1. One major complaint I have is about the writing quality of this paper. It pretty much makes it impossible for me to evaluate its significance and quality. I'll describe more in the next section.\n2. I don't completely understand the objective or the motivation of this paper, to be honest. What assumptions are being made/removed about the loss functions, and why is this framework stronger and more general-purpose than in the prior work we have seen so far? What is it trying to improve on -- what is the prior work here? What are the baseline (trivial or non-trivial) approaches I could compare this work with? This point does tie in with the previous point I made here.\n3. Theoretical comparisons with some prior work could have given more context.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "EGj1tSMyyEn", "reviewer": "Reviewer_HapE", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper provides a differential private learning framework for consensus learning over networks. Some theoretical results are established for the proposed algorithms. Several numerical studies are demonstrated.", "summary_of_the_review": "This paper provides a differential private learning framework for decentralized learning. However, the contribution seems to be incremental. ", "strength_and_weaknesses": "Strength:\nThe targeted problem is interesting. This paper is easy to follow.\n\nWeakness:\n1. Differential private decentralized learning has been widely studied. The work aims to provide a general framework by simply combining SGD and SPGD algorithms. The contribution seems to be incremental.\n2. In terms of the theoretical study, can the authors provide a detailed analysis of optimization error with differential private mechanisms? What are the convergence rates of the algorithms with SGD, and SPGD, respectively? \n3. We would expect a more comprehensive experimental study. For example, the current experiments only focus on least square regressions with/without l1 regularized term. Can the proposed algorithm apply to classification problems such as logistic regression? What is the effect of the proposed algorithms under different privacy levels (epsilon, delta)? \n4. Also, the proposed algorithm involves some parameters. The authors should provide a sensitive study on these parameters.\n5. The text in the figures is too small.\n6. How about the support recovery of the regularized least square regression with an l1 penalty with a noise-adding mechanism? It seems that the noise-adding ruins the spare structure easily. Can the authors provide an analysis of the noise-adding mechanism on structure recovery in addition to generalization error?\n7. In Theorem 5, what is the sequence {a_m}? It makes delta^{\\prime} different.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "1Ezs661vdR", "reviewer": "Reviewer_9m8T", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper proposes a general DP decentralized learning framework based on stochastic Decentralized Kras\u0002nosel’skiˇı–Mann (D-KM) iteration, which can represent the common first-order algorithms, like SGD, SPGD, and ADMM. Also, based on previous truncated Laplace mechanism, they proposed a truncated generalized Gaussian mechanism. ", "summary_of_the_review": "Based on the weaknesses in previous part, the paper needs more concrete comparisons with previous works from theoretical and experiments and insights. ", "strength_and_weaknesses": "Strength:\n1. Achieving privacy in decentralized learning is interesting and important.\n2. The paper gives general framework based on D-KM iteration. \n3. Proposed a truncated generalized Gaussian mechanism with higher utility. \n\nWeakness:\n1. Lots of decentralized learning with DP works are not considered.  Please check the corresponding works in \nLi, Zhize, Haoyu Zhao, Boyue Li, and Yuejie Chi. \"SoteriaFL: A unified framework for private federated learning with communication compression.\" arXiv preprint arXiv:2206.09888 (2022).\n2. Please provide the experiments comparisons with previous works. For example, In Figure 4, please compare the proposed methods with previous DP-ADMM algorithms to show the effectiveness.  The same things for Figure 2 and 3. \n3. The motivation for proposing truncated generalized Gaussian mechanism is not clear. Instead of the advantage of $l_2$ sensitivity, what is the advantage of truncated generalized Gaussian when compared with Laplace noise? Also, here is a work also proposed truncated Gaussian mechanism. [1] Cesar, Mark, and Ryan Rogers. \"Bounding, concentrating, and truncating: Unifying privacy loss composition for data analytics.\" In Algorithmic Learning Theory, pp. 421-457. PMLR, 2021.\n4. Please also provide the generalization and optimization error bound with previous DP-SGD, DP-SPGD and DP-ADMM. \n5. Please provide more experiments over large datasets and neural networks models. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject