Towards Plausible Differentially Private ADMM Based Distributed Machine Learning

Nowadays, the development of machine learning creates many emerging applications that can improve the quality of our life, such as medical diagnosis, autonomous driving, face recognition, etc. With the proliferation of mobile phones and Internet-of-things devices, a vast amount of data have been generated at an ever-increasing rate, which leads to significant computational complexity for data collection and processes via a centralized machine learning approach. Therefore, distributed machine learning plays an increasingly important role in dealing with large scale machine learning tasks. There are many research efforts on distributed training a large scale optimization problem, which mainly consist of two types: (sub)gradient based methods, and Alternating Direction Method of Multipliers (ADMM) based methods. As shown in (Chang et al., 2014), the convergence of (sub)gradient based methods are usually slow, which is $\mathcal{O}(1/{\sqrt{T}})$ under general convex objectives, while ADMM based algorithms can achieve $\mathcal{O}(1/{T})$ convergence rate, where $T$ is the number of iterations. Therefore, ADMM has been widely used in distributed machine learning (Zhang and Kwok, 2014; Mota et al., 2013), and in this paper, we focus on the distributed ADMM.

In the framework of distributed ADMM, data providers (agents) collaboratively solve a learning problem, which can be decomposed into several subproblems, via an interactive procedure of local computation and message passing. However, the information exchanges during this process raise serious privacy concerns, and the adversary can extract private information from the shared learning models via various inference attacks (Shokri et al., 2017; Melis et al., 2019). To prevent such privacy leakage, differential privacy (DP) (Dwork et al., 2006) provides a de facto standard of privacy definition for protecting data privacy, which guarantees that the adversary with arbitrary background knowledge cannot extract any sensitive information about the training dataset.

Many pioneering works have studied how to effectively integrate ADMM with DP, e.g., (Zhang and Zhu, 2016; Zhang et al., 2018a, b; Huang et al., 2019; Ding et al., 2019a, b, c), which can be classified into two categories in general. The first type of works is to add a noisy term to perturb the objective function in each ADMM iteration using an objective perturbation approach (Chaudhuri et al., 2011). The second type of works is to perturb the updates of original distributed ADMM algorithm via an output perturbation approach (Chaudhuri et al., 2011). Specifically, as an objective perturbation method, (Zhang and Zhu, 2016) proposed to inject noise to the update of the dual variable to provide DP guarantee, while the total privacy loss over the whole iterative process is not quantified. Further, (Zhang et al., 2018a, b) proposed to perturb the penalty parameter of ADMM and re-utilize the previous iteration’s results to save the privacy loss. These methods also quantify the total privacy loss over the entire process. Moreover, (Huang et al., 2019) perturbed the augmented Lagrangian with time-varying Gaussian noise and considered a centralized network structure to perform ADMM updates. As output perturbation methods, (Ding et al., 2019b, c) proposed to perturb the primal variables by Gaussian noise with linearly decaying Gaussian noise to preserve DP and maintain the utility.

However, the guarantee of DP in the above works relies on the premise that the optimality of each local problem can be perfectly attained in each iteration during the whole training procedure, which is seldom seen in practice. Further, the trained models from the above works exhibit severe degradation in terms of the convergence performance and model accuracy, compared to their non-private versions.

In this paper, we propose (Improved) Plausible differentially Private ADMM based distributed machine learning algorithm called PP-ADMM and IPP-ADMM, respectively. Instead of requiring each local problem to reach the optimality, PP-ADMM is able to release a noisy approximate solution of the local optimization with Gaussian noise related to the optimization accuracy, while preserving DP.

To further improve the utility, we propose an improved version of PP-ADMM, i.e., IPP-ADMM, by exploiting the sparse vector technique (SVT) to check whether the current approximate solution has enough difference from that of the previous iteration. Moreover, the privacy analysis of our algorithms based on the zero-concentrated DP (zCDP) yields a tight privacy loss bound. We analyze the generalization performance of PP-ADMM. Our salient contributions are summarized as follows.

• •

  To release the shackles of “exact local optimal results” and make ADMM based distributed machine learning achieve DP and plausible, we propose a novel PP-ADMM method by exploiting the inexact solution of the perturbed local optimization over local agent’s private data during each ADMM iteration, while preserving the data privacy.

• •

  We further propose an improved version of PP-ADMM (IPP-ADMM) by employing SVT to evaluate whether the current approximate solution has a big enough difference from that of the previous iteration. If the difference surpasses a predefined threshold, the approximate solution with Gaussian noise will be shared with neighbors; otherwise, the current approximate solution will be discarded. By this way, the redundant privacy loss accumulation and the transmissions of “low quality” can be avoided during the ADMM iterative process.

• •

  To best track the privacy loss accumulation, we leverage the serial and parallel composition theorems of the zCDP to theoretically quantify and analyze the overall privacy guarantees of the PP-ADMM and IPP-ADMM algorithms. Moreover, we provide a generalization performance analysis of PP-ADMM by measuring the number of data samples required to achieve a certain criteria.

• •

  Through extensive experiments on the real-world datasets, we show the superior performance of the proposed algorithms over the state-of-the-art differentially private ADMM algorithms.

The rest of the paper is organized as follows. Section 2 formulates the optimization problem, and describes preliminaries of ADMM and differential privacy. Then, the plausible private robust ADMM algorithm and its corresponding privacy and sample complexity analysis are presented in Section 3. In Section 4, we provide the IPP-ADMM, an improved version of PP-ADMM, and the corresponding privacy analysis. The experimental results on real-world datasets are shown in Section 5. Finally, we draw conclusive remarks in Section 6.

In this paper, we consider a connected network contains $N$ agents with node set $\mathscr{N}=\{1,\cdots,N\}$, and each agent $i$ has a dataset $D_{i}$ with $D_{i}=\{(x_{i}^{n},y_{i}^{n})\}_{n=1}^{|D_{i}|}$, where $x_{i}^{n}\in\mathcal{X}$ is a feature vector and $y_{i}^{n}\in\mathcal{Y}$ is a label. The communication among agents can be represented by an undirected graph $G=\{\mathscr{N},\mathscr{E}\}$, where $\mathscr{E}$ denotes the set of communication links between agents. Note that two agents $i$ and $j$ can communicate with each other only when they are neighbors, i.e., $(i,j)\in\mathscr{E}$. We also denote the set of neighbors of agent $i$ as $\mathscr{B}_{i}$. The goal is to cooperatively train a classifier $\theta\in\mathbb{R}^{d}$ over the union of all local datasets in a decentralized fashion (i.e., no centralized controller) while keeping the privacy for each data sample, which can be formulated as an Empirical Risk Minimization (ERM) problem.

where $\mathscr{L}(\cdot):\mathcal{X}\times\mathcal{Y}\times\mathbb{R}^{d}\to\mathbb{R}$ stands for a convex loss function with $|\mathscr{L}^{\prime}(\cdot)|\leq 1$ and $0<\mathscr{L}^{\prime\prime}(\cdot)\leq c_{1}$, $\mathscr{R}(\theta):\mathbb{R}^{d}\to\mathbb{R}$ is a differentiable and 1-strongly convex regularizer to prevent overfitting, and $\hat{\lambda}\geq 0$ refers to a regularizer parameter that controls the impact of regularizer. We assume that each feature vector $x_{i}^{n}$ is normalized to $\|x_{i}^{n}\|_{2}\leq 1$. Note that the formulations of classification in machine learning like logistic regression, or support vector machines, can also be fallen into the framework of ERM. In order to solve the ERM problem (1) in a decentralized manner, we adopt the simple but efficient optimization method, ADMM. We then in the following subsection review some preliminaries about ADMM algorithm for solving Problem (1).

In this section, we will present our plausible differentially private (PP-ADMM) by adding Gaussian noise related to the maximum tolerable gradient norm of perturbed objective in each ADMM iteration, which relaxes the requirement of exact optimal solution as shown in (Zhang and Zhu, 2016; Zhang et al., 2018a, b), to provide differential privacy guarantee of each training data sample during the iterative procedure. We also adopt the privacy framework of zCDP to compute much tighter privacy loss estimation of PP-ADMM. In addition, the generalization performance guarantees of PP-ADMM is provided by measuring the number of data samples at each agent to achieve a specific criteria.

Specifically, in each iteration, we perturb the subproblem (3) with the objective perturbation method the same as used in previous studies (Zhang and Zhu, 2016; Zhang et al., 2018a, b), where a random linear vector $(b_{i1})^{T}\theta_{i}$ is injected to the objective function, and $b_{i1}$ is a random vector drawn from a zero mean Gaussian distribution $\mathcal{N}(0,{\sigma}_{i1}^{2}I_{d})$. Consequently the objective function (3) used to update the primal variable $\theta_{i}^{t+1}$ becomes the following modified function:

where $f_{i}(\theta_{i})=\frac{1}{|D_{i}|}\sum_{n=1}^{|D_{i}|}\mathscr{L}(y_{i}^{n}\theta_{i}^{T}x_{i}^{n})+\frac{\hat{\lambda}}{N}\mathscr{R}(\theta_{i})$. In order to ensure DP guarantee, as pointed out in (Zhang and Zhu, 2016; Zhang et al., 2018a, b), each agent $i\in\mathscr{N}$ needs to find the optimal solution $\tilde{\theta}_{i}^{t+1}$ of the perturbed objective function $\mathcal{L}_{per}(\theta_{i},D_{i})$, i.e.,

However, the subproblem (6) may not be easy to solve and obtain an optimal solution in a finite time. For instance, if we choose logistic regression as loss function, the subproblem (6) cannot yield an analytical solution due to the complicated form of logistic regression. Especially when the problem dimension or the number of training samples is large, obtaining optimal solution might not be feasible in every iteration.

Thus, we consider obtaining the approximate solution of perturbed objective function $\mathcal{L}_{per}(\theta_{i},D_{i})$ to provide privacy guarantees when the optimal solution is not attainable.

Specifically, we approximately solve the perturbed problem until the norm of gradient of $\mathcal{L}_{per}$ is within a pre-defined threshold $\beta$. However, due to the limitations of objective perturbation method (Chaudhuri et al., 2011), releasing this inexact solution leads to the failure of providing DP guarantee. We thus perturb the approximated solution $\hat{\theta}_{i}^{t+1}$ with another random noise $b_{i2}$ from Gaussian distribution $\mathcal{N}(0,{\sigma}_{i2}^{2}I_{d})$, to ”fuzz” the difference between $\hat{\theta}_{i}^{t+1}$ and the optimal solution $\tilde{\theta}_{i}^{t+1}$. Note that the noise variance ${\sigma}_{i2}^{2}$ has the parameter $\beta$ about the maximum tolerable gradient norm, which leads to a trade-off between the gradient norm bound and the difficulty of obtaining an approximate solution within the norm bound.

The key steps of PP-ADMM algorithm are summarized in Algorithm 1. The privacy parameters $(\epsilon_{i1},\delta_{i1})$ are used to perturb the objective function while the parameter $\rho_{i2}$ being used to perturb the approximate solution. Moreover, the parameter $\epsilon_{i3}$, a portion of $\epsilon_{i1}$, is used to scale the noise injected to the objective function, and the remaining privacy budget $(\epsilon_{i1}-\epsilon_{i3})$ is allocated to setting the regularizer parameter. Notice that we also define an Optimizer $\mathscr{O}(\cdot,\cdot):\mathscr{F}\times{\bm{\beta}}\to\mathbb{R}^{d}$, where $\mathscr{F}$ is the class of objectives, and $\bm{\beta}$ is the optimization accuracy, i.e., the gradient norm of objectives. Each agent $i$ then constructs the perturbed function $\mathcal{L}_{per}(\theta_{i},D_{i})$ with a Gaussian random vector $b_{i1}$ and finds an inexact solution $\hat{\theta}_{i}^{t+1}$ where the norm of gradient is lower than $\beta$, i.e., $\hat{\theta}_{i}^{t+1}=\mathscr{O}(\mathcal{L}_{per}(\theta_{i},D_{i}),\beta)$. After that each agent $i$ generates a random Gaussian noise $b_{i2}$ and transmits $\theta_{i}^{t+1}=\hat{\theta}_{i}+b_{i2}$ to its neighbors $j\in\mathscr{B}_{i}$. Finally, each agent updates the local dual variables $\lambda_{i}^{t+1}$ via $\lambda_{i}^{t+1}=\lambda_{i}^{t}+\dfrac{\eta}{2}\sum\limits_{j\in\mathscr{B}_{i}}(\theta_{i}^{t+1}-\theta_{j}^{t+1})$.

In this section, we present an improved version of PP-ADMM algorithm called Improved Plausible Private ADMM (IPP-ADMM) by leveraging sparse vector technique (SVT) to improve the performance and reduce the communication cost of PP-ADMM. Compared with current differentially private ADMM algorithms (Zhang and Zhu, 2016; Zhang et al., 2018a, b), although the proposed PP-ADMM algorithm can ensure DP guarantee without requiring the optimal solution during each ADMM iteration, the primal variable is updated using the local data in every iteration and frequently broadcasted to neighboring agents, which leads to the privacy loss unavoidably accumulating over the iterations, and compromise the accuracy during the whole training procedure.

Hence, we adopt SVT that can output some local computational results without paying any privacy budget, to check whether current approximate solution has a big enough difference from that of previous iteration,

where the difference is quantified by a quality function, $f_{i}(\theta_{i}^{t})-f_{i}(\hat{\theta}_{i}^{t+1})$, based on the change of the values of local function over the primal variable from previous iteration and current approximate solution. If a sufficient level of difference $\alpha$ is achieved, each agent transmits the current approximate solution with Gaussian noise to its neighbors. Intuitively, if the difference between the current approximate solution $\hat{\theta}_{i}^{t+1}$ and the previously transmitted $\theta_{i}^{t}$ is small, then using either one does not help the convergence of the iterative process, which leads to reducing the communication cost.

However, one difficulty in using SVT is that there is no known priori bound on query (i.e., the quality function) $f_{i}(\theta_{i}^{t})-f_{i}(\hat{\theta}_{i})$. To bound the sensitivity of $f_{i}(\theta_{i}^{t})-f_{i}(\hat{\theta}_{i})$, we apply the clipping method to clipping the loss function $\mathscr{L}(\cdot)$. Given a fixed clipping threshold $C_{loss}$, we compute the value of loss function $\mathscr{L}(\cdot)$ on each local data sample, clip the values at most $C_{loss}$, and compute the value of $f_{i}(\theta_{i}^{t})-f_{i}(\hat{\theta}_{i})$ based on the clipped values. Note that we denote this loss function clipping procedure as Clip.

The complete procedure of IPP-ADMM algorithm for a single agent is shown in Algorithm 2. The privacy parameters $\epsilon_{1}$ and $\epsilon_{2}$ are allocated to perturb the quality function and threshold $\alpha$, respectively. In each iteration, each agent $i$ first constructs the perturbed function $\mathcal{L}_{per}(\theta_{i},D_{i})$ with a Gaussian random vector $b_{i1}$ and finds an inexact solution $\hat{\theta}_{i}^{t+1}$, where the norm of gradient is lower than $\beta$, i.e., $\hat{\theta}_{i}^{t+1}=\mathscr{O}(\mathcal{L}_{per}(\theta_{i},D_{i}),\beta)$. Then each agent apply the clipping method Clip to clip the quality function $f_{i}(\theta_{i}^{t})-f_{i}(\hat{\theta}_{i}^{t+1})$ with a clipping threshold $C_{loss}$ to limit the sensitivity of quality function. Further, each agent uses SVT to check whether the difference between the approximate solution $\hat{\theta}_{i}^{t+1}$ and $\theta_{i}^{t}$ is below a noisy threshold $\hat{\alpha}=\alpha+{\rm Lap}(\frac{2{\rm\mathbf{c}}{C}_{loss}}{\epsilon_{1}})$ via a noisy quality function, $\texttt{Clip}\left[f_{i}(\theta_{i}^{t})-f_{i}(\hat{\theta}_{i}^{t+1})\right]+{\rm Lap}(\frac{4{\mathbf{c}}{C}_{loss}}{\epsilon_{2}})$. If yes, then agent $i$ does not transmit any computational results and let $\theta_{i}^{t+1}=\theta_{i}^{t}$; otherwise, each agent $i$ generates a random noise $b_{i2}\sim\mathcal{N}(0,{\sigma}_{i2}^{2}I_{d})$ with ${\sigma}_{i2}={\beta}/{\sqrt{2\rho_{i2}}(\frac{\hat{\lambda}}{N}+2\eta|\mathscr{B}_{i}|)}$, and transmits $\theta_{i}^{t+1}=\hat{\theta}_{i}^{t+1}+b_{i2}$ to its neighbors. Moreover, each agent maintains a counter ${count}_{i}$ to bound the total number of broadcasts of primal variables during the whole interactive process. If a predefined transmission number ${\rm\mathbf{c}}({\rm\mathbf{c}}\leq T)$ is exceeded, agent $i$ stops transmitting anything even when the condition in Line 7 is satisfied. Hence, if agent $i$ does not receive $\theta_{j}^{t+1}$ from any neighbor $j\in\mathscr{B}_{i}$, then lets $\theta_{j}^{t+1}=\theta_{j}^{t}$. Finally, each agent updates the local dual variables $\lambda_{i}^{t+1}$ via $\lambda_{i}^{t+1}=\lambda_{i}^{t}+\dfrac{\eta}{2}\sum\limits_{j\in\mathscr{B}_{i}}(\theta_{i}^{t+1}-\theta_{j}^{t+1})$.