Recently, with rapid advances in sensing technologies, we are witnessing a deluge of data [20,21]. Statistical analysis of this data has paved the way for the development of machine learning that brings valuable benefits to society, such as more intelligent autopilot technology and higher medical quality, among others. The enormous data generated from such various applications is scattered around different places, and it increasingly becomes difficult for a single machine to process such giant data. Hence, the centralized model can no longer efficiently process this data [2,3]. Apart from the limitations on processing, this data draws detailed pictures of people's lives and involves highly sensitive information. So the data owners might be reluctant to share their data for analysis. Therefore, with the rise in the volume of data being generated, there is a critical need of privacypreserving machine learning algorithms that can both cater the processing and privacy needs.
To address the above issues, we develop a privacy-preserving machine learning algorithm that processes data in a distributed manner while providing privacy guarantee for each training sample. One of the promise applications is the health domain. For example, in health monitoring applications multiple hospitals collaborate to provide constructive diagnosis to the patients. Hospitals have a large number of cases, and the data analysis of these cases helps doctors to make an accurate diagnosis and offer early treatment plans. Thus, multiple hospitals could collaboratively train a classifier through a central server that can help in prognosis and diagnosing diseases early. However, such medical cases may contains sensitive information about the patients and each hospital cannot share its patients' cases with other hospitals. Hence, the key challenge is to effectively conduct medical research while preserving the privacy of the patients in the analysis. Concisely, this problem is a distributed machine learning problem where data is collected from multiple data providers and each data sample's privacy needs to be guaranteed during the optimization.
One of the promising solutions for such distributed machine learning problems is alternating direction method of multipliers (ADMM) [4,14,15]. ADMM enables distributed learning by decomposing a large-scale optimization into smaller subproblems and each subproblem is easy to solve in a distributed and parallel way. Each data provider uses its own private data to train a local classifier and the central server averages all of the local classifiers and broadcasts the result to the data providers. These steps iterate several times until the server and users have a high-performance model. Through this decomposition and coordination procedure of ADMM, the distributed learning problem achieves effective results. However, when both the number of features and the size of dataset are large, the computational burden of using ADMM is heavy [17]. Recently Zhang et al. propose a novel ADMM algorithm called SCAS-ADMM, which achieves lower computational burden by employing stochastic variance reduced gradient (SVRG) [13] as an inexact solver for subproblems. Zhang et al. considered the SCAS-ADMM in the centralized scenario [23]. We investigate on the SCAS-ADMM in distributed machine learning scenario to obtain a low computational cost per iteration, without compromising the privacy of data samples.
Beyond effectively solving the distributed machine learning problem, the data privacy is the critical concern in such analyses since the private information pertaining to the datasets should not to be shared and kept private. But the privacy concerns are still inherent during the communication between the data providers and the central server. As each data provider needs to share the local model trained over the sensitive raw data at each iteration, an adversary could infer the sensitive information from the shared model as described in [8]. Therefore, we use differential privacy [6,7], a de facto notion for privacy that offers strong privacy guarantees, to tackle the privacy concerns and protect disclosed privacy from the model parameters during the iterative procedure. Differential privacy guarantees privacy by measuring the change in the outcome of the algorithm as the presence or absence of a single data entry in the original dataset does not explicitly change the outcome. In this work we investigate on collectively considering differential privacy and distributed machine learning to get effective results in the analysis, with low computation burden and without compromising the privacy of the data owners. In the existing literature, there are some research efforts integrating ADMM into private distributed learning. Zhang et al. developed a dual perturbation based on ADMM [22], in which they add noise to the dual variables of decentralized ADMM and only provide privacy guarantee of a single data provider per iteration, but their decentralized algorithm needs robust network topology and does not guarantee utility and privacy when considering all nodes during the whole training procedure. Guo et al. proposed another approach for preserving privacy in ADMM in [10], which incorporate secure computation and distributed noise generation in the asynchronous ADMM algorithm. Though privacy during communication can be preserved, their scheme suffers from poor communication and computation costs because of the encryption and decryption over huge datasets.
To address these challenges, we propose a novel stochastic ADMM based privacy-preserving distributed machine learning (PS-ADMM) algorithm in this paper, which jointly considers the distributed learning setting and differential privacy. In PS-ADMM, we employ differential privacy to stochastic ADMM algorithm with the objective of protecting the privacy of data samples and achieving distributed learning over multiple data providers. Different from the approach proposed in [22], we propose to extend the stochastic ADMM in a distributed setting to deal with the computational burden of local computation at each data provider, and add differential privacy based noise to the updating gradients during local computation procedure. We utilize the moments accountant method [1] to analyze the privacy guarantee of PS-ADMM, and we also provide the convergence rate and utility bound of PS-ADMM. The major contributions of this paper are listed as follows.
-We design a novel stochastic ADMM based privacy-preserving distributed machine learning algorithm called PS-ADMM, where we investigate the SCAS-ADMM algorithm in a distributed setting and perturb the gradient updates with Gaussian noise to further improve the computational efficiency and provide differential privacy guarantee.
-Compared to the existing research in [22] that only considers privacy guarantee at each iteration, we consider the entire iterative procedure and adopt moments accountant method to provide a tighter differential privacy guarantee for PS-ADMM. -We theoretically analyze and prove the convergence and utility bound of the proposed algorithm PS-ADMM. -We show that the proposed PS-ADMM outperforms other differentially private ADMM algorithms under the same differential privacy guarantee by conducting PS-ADMM over real-world data.
The remainder of this paper is organized as follows. Section 2 presents the problem statement, preliminaries and associated privacy concerns. We propose our differentially private algorithm PS-ADMM in Sect. 3. This is followed by our theoretical analysis of convergence and utility bound in Sect. 4. Detailed simulations and comparisons are presented in Sect. 5. Section 6 concludes the whole paper.
In this section, we describe the problem statement in Sect. 2.1, introduce the preliminaries of ADMM and differential privacy in Sect. 2.2. The overview of the distributed SCAS-ADMM algorithm is presented in Sect. 2.3 and the privacy concerns of the distributed ADMM based solution are presented in Sect. 2.4. As shown in Fig. 1, we consider a star network topology consisting of a set of data providers N = {1, • • • , N} and a central server, where multiple data providers have the ability to communicate with the server and the server is responsible for aggregation and message passing. Here, each data provider possesses a private dataset D i = {(a im , y im )} M m=1 consisting of feature vector a im from a data universe X , and y im ∈ Y that is a label we aim to predict from a im . The objective of our problem is to build a classifier over the aggregated sensitive dataset ∪ i∈N {D i } from data providers through a distributed manner, where the classifier can be obtained by minimizing a regularized empirical risk minimization problem (ERM) [9]. The regularized empirical risk minimization problem is to learn a classifier x over a convex set C ⊆ R p , which can be formulated as
where l im (•) : X ×Y ×C → R is a loss function of provider i for each data sample (a im , y im ) and g(x) is a convex regularizer to prevent overfitting. In this paper, we assume the loss function l im (•) is convex, G-Lipschitz and has L m -Lipschitz continuous gradient. Note that our algorithm is not limited to the classification problem since the convergence and privacy analysis are still valid.
The above ERM problem (1) can be minimized by ADMM, which is a practical distributed scheme that can be applied to large-scale machine learning algorithms. Since the goal is to build a classifier with sensitive data, privacy concerns inherent in the training procedure need to be addressed while solving the ERM problem.
Distributed Machine Learning with ADMM. In order to solve the problem in (1) with ADMM method [4], the ERM problem in (1) can be reformulated as consensus formulation [18] by introducing a global variable z ∈ R p as
In ( 2),
is the i-th data provider's loss function due to dataset D i , and x i is the local classifier of the i-th data provider. Since the objective function in ( 2) is already decoupled, each data provider only needs to optimize a subproblem, i.e., empirical risk minimization problem over its local dataset. The constraints (3) enforce that all the local classifiers reach consensus finally. Apparently, the problem above is equivalent to the problem in (1).
Let λ ∈ R p denote the Lagrange dual variable, and ρ > 0 be a pre-defined penalty parameter. The standard ADMM consists of the following iterations
where • denotes l 2 norm. The entire procedure illustrates the exchange of information between data providers and the central server. It is obvious that the classifier x k+1 i can be locally updated for each party. This is because the whole problem has been divided into N subproblems which can be solved in parallel. Each party broadcasts x k+1 i it owns to the central server. Then, the central server solves subproblems ( 5) and ( 6) and gets z k+1 and then dual variable λ k+1 i . Finally, the optimal parameter can be obtained after several iterations. Differential Privacy. Differential privacy [7] is a widely-adopted privacy notion, which can be used to quantify the privacy risk of each individual record in a dataset. Mathematically, differential privacy is defined as follows Definition 1. A randomized algorithm A is ( , δ)-differentially private if for all datasets D, D ∈ D that differ in a single element and for all s ∈ Ω, where Ω is the output space of A, we have
Differential privacy concentrates on the output distribution of a mechanism when there exists the participation of an individual. Smaller values of mean stronger privacy guarantees of A. The most common mechanism for achieving differential privacy is Gaussian Mechanism [6].
. Then, the Gaussian mechanism preserves ( , δ)-differential privacy.
Traditional ADMM [4,22] is quite computationally expensive when we have large size of the dataset, since solving subproblem (4) needs to visit all the M data points at each iteration. In this paper, we extend the stochastic ADMM (SCAS-ADMM [23]) into a distributed setting to highly reduce the computation cost.
1: Algorithm of the i-th data provider:
Randomly pick a data point (aims , yims ) ∈ Di; 7:
end for 11:
Send x k+1 i to the central server; 13: end for 14: Algorithm of the central server: 15: Initialize z 0 , λ 0 i and broadcast them to the providers; 16:
Since distributed SCAS-ADMM just needs to utilize several data points at each iteration to achieve distributed learning, it is quite computation efficientfoot_0 . Before stating the details of distributed stochastic ADMM, we first define the following functions
The following Lemma shows the convexity of above functions.
The details of distributed stochastic ADMM are summarized in Algorithm 1. To be specific, after receiving updated variable z k and λ k i from the server, each data provider updates its local variable x k+1 i at iteration k by optimizing subproblem (4) through the SVRG method [13]. At the beginning of each iteration k, the gradient ûi = ∇f i (
For each inner iteration s, the approximate gradient
) is used to iteratively update v s+1 i with a step size η. And then, we adopt the convex combination to improve the convergence rate. Hence, the subproblem (4) reduces to
. Then, all the data providers broadcast their x k+1 i to the central server which computes z k+1 and λ k+1 i . The whole procedure ends when the number of iterations exceeds a maximum value K. However, while there is no direct exchange of data among data providers, the sequence of iterations broadcasted by a provider may reveal sensitive information through the output of the local learning.
In our problem setting, there is no need to send the dataset stored at each data provider to the central server directly, while the risk of information leakage still exists. We assume that an adversary can eavesdrop all communications between data providers and the server. In some cases, the adversary using model inversion attack [8] may be able to obtain sensitive information about the private data points of the training dataset by observing the local learning parameter from the provider at iteration k and the final output model parameters of the distributed algorithm. To mitigate this risk, we develop a differentially private algorithm that provides differential privacy for all of the intermediate parameters. If the adversary collects all the intermediate computational results of a provider during communications with the server and the final output of the algorithm, the privacy of local data points at each data provider is still protected.
In this section, we propose our novel algorithm PS-ADMM, which integrates differential privacy into distributed stochastic ADMM. In order to provide differential privacy in distributed stochastic ADMM algorithm, we use the noisy gradient that adds Gaussian noise to the gradient updates of subproblem (4). To analyze the privacy guarantee of PS-ADMM, we consider the moments accountant method [1] of computing privacy loss during a iterative process, which is shown in Theorem 1.
Theorem 1. There exist constants c 1 and c 2 such that given the sampling probability q = l/M and the number of steps K, for any < c 1 q 2 K and for the G-Lipschitz loss function, a differentially private stochastic gradient algorithm with batch size l that injects Gaussian Noise with standard deviation Gσ to the Algorithm 2. Differentially Private Stochastic ADMM (PS-ADMM)
1: Algorithm of the i-th data provider: 2:
Generate Gaussian noise:
Randomly pick a data point (aims , yims ) ∈ Di; 8:
gradients, is ( , δ)-differentially private for any δ > 0, if we choose
The differentially private stochastic ADMM (PS-ADMM) is shown in Algorithm 2. Details of PS-ADMM are summarized as follows: At iteration k, each data provider utilizes the SVRG method to solve subproblem (4) in order to obtain the local classifier x k+1 i . For the inner iteration s at this iteration, the ith data provider generates a zero mean Gaussian noise θ s k with variance (σ 2 ) s k to perturb the approximate gradient g s i , and by averaging vs+1 i of all S inner iterations, the i-th data provider gets a differential private local classifier x k+1 i . During the iteration of SVRG method, we adopt the convex combination to increase the convergence rate. In addition, we employ the iteration average to improve the convergence of ADMM. And then data providers send all differentially private {x k+1 i } N i=1 to the server. The server will update z k+1 and {λ k+1 i } N i=1 by solving subproblems ( 5) and ( 6) after receiving all of the local parameters{x k+1 i } N i=1 . Next, each data provider updates its private local parameter by using updated variable z k+1 and {λ k+1 i } N i=1 from the central server. The iterative process will continue until reaching K rounds of communication between server and data provider.
During this iterative process, the shared local classifiers {x k+1 i } N i=1 may reveal sensitive information about local dataset D i of data provider i. Thus, we need to show that PS-ADMM guarantees differential privacy with local classifiers {x k+1 i } N i=1 . Since we use Gaussian mechanism to add noise, we should give the l 2 sensitivity estimation of the approximate gradient g s i at first. According to [19], the sensitivity of g s i is Δ 2 ≤ 3G, where G is the lipschitz constant of loss function l im (•). The following theorem shows that our algorithm provides ( , δ)differential privacyfoot_1 . Theorem 2. For ≤ c 1 KS M 2 and δ ∈ (0, 1), and the noise θ s k is sampled from zero mean Gaussian distribution with variance
then, PS-ADMM algorithm satisfies ( , δ)-differential privacy, where c 1 and c are some constants.
In a distributed and iterative algorithm, the output of the algorithm includes all of exchanged intermediate results and the end result. Since the adversary may perform inference by using all intermediate results, the privacy leakage accumulates over time through the iterative process. Different from the prior study in [22], where the privacy leakage is only bounded at a single iteration, our proposed differentially private algorithm PS-ADMM provides ( , δ)-differential privacy guarantee for all of the intermediate results exchanged during the iterative procedure and the end result.
In this section, we discuss the convergence and the utility bound of the proposed PS-ADMM algorithm. To define the convergence and utility bound, we will use the following criterion
which is the same as the variational inequality used in [16] and [12]. In criterion (9), u = {x 1 ; x 2 ; ...; x N ; z} and P (u) = N i=1 f i (x i )+g(z), and u * is the optimal solution of problem 2.
Similar to most iterative distributed optimization algorithms [11], distributed stochastic ADMM only converges in a probabilistic sense when the number of iterations K → ∞. Therefore, we can now prove the following expected suboptimality of the proposed algorithm according to the criterion (9).
2 , the expected suboptimality of PS-ADMM is bounded after K iterations
where
Proof. See Appendix A.3.
As K increases, the first term in (10) decreases, though the second term in (10) increases. Then, the minimized suboptimality of the proposed algorithm exists as we choose an optimal K. Hence, the following theorem gives the utility bound when choosing an optimal K.
Theorem 4 (Utility Bound).
Proof. See Appendix A.4.
We conduct simulations on the same dataset as [22], i.e, the Adult dataset from UCI Machine Learning Repository [5], which contains 48,842 samples with 14 features like age, sex, education, etc. The goal is to predict whether the annual income is more than 50k or not. Before the simulation, we preprocess the data by normalizing all numerical attributes such that l 2 -norm is at most 1 and transform the label {>50k, ≤50k} to {+1, -1}. We separate the whole dataset for training and testing (the ratio is around 70%:30%). And for training samples, we separate them into five parts representing five data providers (N = 5). Consistent with [22], we use the logistic loss l(z) = log(1 + exp(z)). And N data providers collaboratively solve the following regularized logistic regression
We inspect the convergence and accuracy of our approach by comparing with the dual variable perturbation (DVP-ADMM) method adopted in [22]. The convergence is measured by expected loss defined by 1
The accuracy is defined by classification error rate over testing dataset. For the DVP-ADMM algorithm, the parameters are the same as in settings of [22].
For each parameter setting, we conduct 20 independent runs of the algorithm. For each time, both the mean and standard deviation of the expected loss and the accuracy are recorded. The smaller the standard deviation is, the greater is the stability of the algorithm. In all experiments, we set the regularization coefficient R = 0.0001, and δ = 0.001.
Figures 2 and3 compare our approach with DVP-ADMM method and the non-private algorithm for expected loss and testing accuracy under different privacy budgets. The non-private algorithm here is a stochastic ADMM without adding noise. As the number of iterations increases, we see that our approach (red) has achieved much less expected loss and higher testing accuracy than DVP-ADMM (blue) for all three cases of privacy budget . Hence, our method can outperform DVP-ADMM (blue) significantly. However, the excepted loss does not always monotonically decrease as too much noise introduced in PS-ADMM affects the convergence, especially when is small. While privacy budget is large enough (e.g., = 0.5), it follows the same trend as non-private ADMM and still outperforms DVP-ADMM.
In this paper, we proposed a novel algorithm called PS-ADMM by extending SCAS-ADMM into a distributed setting and adding differentially private Gaussian noise to the gradient updates. Thus, the sensitive information stored in the training dataset at each data provider can be protected against an adversary who can eavesdrop the communications between the data provider and the server. The convergence and utility bound of PS-ADMM have been analyzed theoretically. We empirically demonstrate that PS-ADMM outperforms other differentially private ADMM algorithms under the same privacy guarantee.
Proof. Since each l im (x) is convex, G-Lipschitz and has L m -Lipschitz continuous gradient, for any x 1 and x 2 , there exists L m > 0 such that
We can see that
, where v f = max m L m . Then, we can have
where we let v L ≥ v f + ρ. Thus, L i (x) and Lm (x) are v L -smooth. Moreover, it is obvious to see that L i (x) is μ L -strongly convex with μ L ≤ μ f + ρ.
Lemma 2. The variance of
Hence, the variance of g s i can be bounded as
where the first inequality uses a+b 2 ≤ 2 a 2 +2 b 2 and the second inequality uses
Lemma 3. For 0 < η < 1 2vL , we have
Proof.
Taking expectation on both sides, we obtain
)
Then, we have
By choosing η < 1/(2v L ), we get
Proof. We have E(b s i ) = ∇f i (v s i ) and this leads to
Then, we have
According to Lemma 3, we obtain
where
Proof. By deriving the optimal conditions of the minimization problem in (5), we have
Then, by using the notation
where
Lemma 7. Assume f i (•) be μ f -strongly convex, and let x k+1 i , z k and λ k i be generated by the proposed algorithm. For η satisfies 0
Proof. Using Lemma 4 and the strong convexity of L i (v i ), we have
where we apply Lemma 2 and
By using the Jensen's inequality, we have
where qs+1 i = λ k i + ρ(v s+1 i -z k ). Summing from s = 0, 1, 2, ..., S -1 and using
where α k+1 i = λ k i + ρ(x k+1 i -z k ). Thus, we have
where we assume 1 -ρξ 2 -
Proof. Combining Lemmas 7, 5 and 6 together and using the convergence criterion (9), we let w k+1
where
Summing the inequality over k = 0, 1, 2, ..., K -1 and using the Jensen's inequality, we get E P ( ûk+1 ) -P (u) +
The specific results of computation cost and memory cost refer to[23].
The proof of Theorem 2 is very similar to the B.2 in[19]. Due to the space limitation, we omit the detail of it.