Distributed Least-Squares Optimization Solvers with Differential Privacy

Distributed optimization, in which networked agents seek to minimize a global cost function in a distributed and cooperative fashion, has gained significant attention in diverse fields such as machine learning [1], unmanned aerial vehicles (UAV) [2], and sensor networks [3]. For such a problem, since the seminal work of the distributed gradient-descend algorithm [4], numerical algorithms have been developed, that differ from linear or sub-linear convergence rate [5, 6, 7, 8], deterministic or stochastic communication graph [9, 10], and equality or inequality constraints [11, 12], etc. Particularly, the gradient-tracking algorithm [13, 5] has gained increasing attention due to its fast convergence rate, yielding several variants such as [14, 15, 16, 17, 18]. As a special case, distribution least-squares optimization considers the computation problems where cost functions are squared, with wide applications across many fields (e.g., versatile LiDAR SLAM [19]). See [20, 21] for a thorough review of recent advances of distributed optimization.

In distributed optimization, each network agent holds a local dataset (that defines a local cost function), that may contain private sensitive information for the agent. For example, in the digital contact tracing based computational epidemiology, users’ privacy-sensitive data such as localization is encoded in the corresponding optimization problem [22]. In existing distributed optimization algorithms, during computing processes each agent needs to communicate with neighboring agents its local states or some intermediate variables that may directly contain the local sensitive data, or can be used to infer the local data. In view of this, new risks of privacy breach arise when there are eavesdroppers having access to network communication messages.

For privacy concern in distributed optimization, a natural idea is to apply homomorphic encryption on transmitted messages [10, 23]. However, this method may lead to heavy computation and communication burden. Besides, other approaches have also been proposed by injecting uncertainties into exchanged states [24, 25], or into asynchronous heterogeneous stepsize [26]. To further describe a rigorous privacy preserving notion, the differential privacy is proposed in [27], and has been widely applied in various fields such as signal processing [28], and distributed computation [25, 29, 30, 31, 32, 33, 34, 35], due to its resilience to side information and post-processing [36]. For a distributed optimization problem with a trusted cloud, a differentially private computation framework is proposed in [35] where the cloud sends perturbed global gradient to agents. Further, for the scenario without a trusted cloud, [31] studies distributed optimization problems with bounded gradients and sensitive constraints by injecting noises to communication messages, for which the desired privacy is guaranteed by splitting the privacy budget to each iteration round. In [33], to preserve the differential privacy under arbitrary iteration rounds, the idea of perturbing objective functions is introduced for a class of distributed convex optimization problem with square-integrable cost functions. Note that as shown in [33], in these results the introduction of randomness for privacy concern inevitably leads to a certain computation error, i.e., there is an accuracy-privacy trade-off. When an exact optimal solution is sought, [25, 32] turn to make a bit modification on the adjacency notion for the differential privacy, and develop novel algorithms by perturbing communication messages with noises having increasing variants and employing a vanishing stepsize that is appropriately designed.

In this paper, we focus on the problem of distributed least-squares optimization with differential privacy requirements of local cost functions under a common data adjacency notion. For such a problem, a common approach is to perturb communication messages, but as in [31] the change of iteration number may lead to a different privacy budget, i.e., yielding an iteration-number-dependent differential privacy. Besides, we also note that the idea of functional perturbation [33] is not applicable as the cost functions are not square-integrable, though it may remove the dependence on the iteration number.

In view of this analysis, inspired by the truncated Laplace mechanism [37] and the Gaussian mechanism [38], we first propose a Differentially Private Gradient Tracking-based (DP-GT-based) solver by perturbing the gradient tracking algorithm in such a way of appropriately adding Gaussian and truncated Laplacian noises to the initial values and parameters that contain the sensitive data, respectively. Moreover, a trade-off between the achievable $(\epsilon,\delta)$-differential privacy and the computation accuracy is rigorously proved, and the iteration round is allowed to be arbitrary with no influence on the privacy guarantee. For such a method, it is noted that the intrinsic property of truncated Laplacian differential privacy mechanism [37] limits the achievable differential-privacy level and the computation accuracy linearly relies on the network size, which makes it inapplicable to a large-scaled distributed least-squares problem. In view of this, we further propose a Differentially Private Dishuf Average Consensus-Based (DP-DiShuf-AC-based) solver, where agents run the Distributed Shuffling (DiShuf)-based differentially private average consensus algorithm [39] to obtain a noisy estimate of the global gradient function, enabling each agent to solve for the optimal solution independently with differential privacy guarantees. Benefiting from the use of distributed shuffling mechanism, the least-squares optimization problem can be eventually solved to fulfill any desired differential privacy levels, and with the accuracy independent of the network size, which makes it more suitable for large-scale least-squares optimization problems. In the paper, our contribution mainly lies in proposing two differentially private least-squares optimization solvers: the DP-GT-based solver and DP-DiShuf-AC-based Solver. Particularly, the latter is able to achieve a privacy-accuracy trade-off which is independent of the network size as shown by numerical simulations.

The remainder of this paper is organized as follows. In Section II the differentially private distributed least squares problem is formulated, for which two solvers are explicitly presented in Sections III and IV. Simulations are then conducted in Section V to verify the effectiveness of the proposed solvers. Finally, Section VI concludes the paper.

Notation. Denote by $\mathbb{R}$ the real number, $\mathbb{R}^{n}$ the real space of $n$ dimension for any positive integer $n$. Denote by $\mathbf{1}_{n}\in\mathbb{R}^{n}$ as a vector with each entry being $1$ and $\mathbf{0}_{n}\in\mathbb{R}^{n}$ as a vector with each entry being $0$. For a vector $x\in\mathbb{R}^{n}$, denote ${\|x\|}_{0}$, ${\|x\|}_{1}$, ${\|x\|}$ as the 0, 1, and 2-norm of vector $x$. For a matrix $A$, denote $(A)_{ij}$ as its $i$-th row $j$-th column element, $\|A\|$ as 2-norm, $\|A\|_{F}$ as Frobenius norm, and $\lambda_{i}(A)$ as $i$-th eigenvalue. Denote by $\eta\sim\mathcal{N}(\mu,\sigma^{2})^{r}$ if each entry of $\eta\in\mathbb{R}^{r}$ is i.i.d. and drawn from Gaussian distribution with mean $\mu$ and variance $\sigma^{2}$ for positive integer $r$. Define $\Phi(s)=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{s}e^{-\tau^{2}/2}d\tau$ and $\kappa_{\epsilon}(s)=\Phi(\frac{s}{2}-\frac{\epsilon}{s})-e^{\epsilon}\Phi(-\frac{s}{2}-\frac{\epsilon}{s})$ for any $\epsilon>0$. Denote by $\bar{\kappa}_{\epsilon}(\delta)$ the inverse function of $\kappa_{\epsilon}(s)$ for $s>0$. It can be verified that both $\kappa_{\epsilon}(s)$ and $\bar{\kappa}_{\epsilon}(\delta)$ are strictly increasing functions.

Consider a multi-agent system with an undirected and connected communication network $\mathrm{G}=(\mathrm{V},\mathrm{E})$, where the agent set $\mathrm{V}=\{1,2,...,n\}$, the edge set $\mathrm{E}\subseteq\mathrm{V}\times\mathrm{V}$, and each agent $i\in\mathrm{V}$ holds a local and privacy-sensitive cost function of the form

where $A_{i}\in\mathbb{R}^{m\times m}$ is symmetric, $B_{i}\in\mathbb{R}^{m}$ and $C_{i}$ is a scalar. The networked system aims to solve the following least-squares optimization problem

in a distributed and privacy-preserved manner. It is well-known that the value of $C_{i}$ does not affect the solution of the optimization problem and is generally not used. Thus, in the sequel we only consider the privacy concern of the matrix pair $(A_{i},B_{i})$ while developing algorithms to solve the problem (2), though the privacy of $f_{i}$ is encoded in the triplet $(A_{i},B_{i},C_{i})$. Denote by $\mathcal{F}$ as the mapping that rearranges all elements of matrix $A_{i}$ to a vector $\theta_{i}^{A}\in\mathbb{R}^{\frac{m(m+1)}{2}}$, i.e. $\theta_{i}^{A}=\mathcal{F}(A_{i})$. Specifically, $\theta_{i}^{A}$ is obtained by setting the element in the $p$-th row and the $q$-th column with $q\geq p$ of $A_{i}$ as the $[\frac{(2m-p+2)(p-1)}{2}+q-(p-1)]$-th element. Note that since $A_{i}$ is symmetric, we only put the upper-triangle elements of $A_{i}$ in the mapping $\mathcal{F}$. On the other hand, it is clear that $\mathcal{F}$ is invertible. For convenience, we denote by $\mathcal{F}^{-1}$ as its inverse, i.e., $A_{i}=\mathcal{F}^{-1}(\theta_{i}^{A})$, and define the sensitive-data vector $\theta_{i}:=[{\theta_{i}^{A}};B_{i}]\in\mathbb{R}^{\frac{m(m+3)}{2}}$.

To ensure the solvability of the problem (2), we make the following assumption throughout the paper.

The above assumption guarantees strict convexity of global cost function $f(x)$, admitting the unique least-squares solution

where we define $B:=\sum_{i=1}^{n}B_{i}$.

In solving the distributed least-squares optimization problem (2) over the network $\mathrm{G}$, necessarily agents communicate with neighboring agents about local information, which may contain the sensitive data $(A_{i},B_{i})$ (i.e., vector $\theta_{i}$) directly or indirectly. If there exists adversaries having access to the communication messages, then the sensitive data $(A_{i},B_{i})$ may be inferred, leading to privacy leakage risks. This motivates to develop distributed algorithms that solve the problem (2) with privacy guarantees of the sensitive data $(A_{i},B_{i})$ against the adversaries eavesdropping all communication messages.

For privacy concern, this paper focuses on the notion of differential privacy, originated from [27] and is widely used in the field of distributed computation. Differential privacy describes rigorous privacy preserving in that eavesdroppers could not infer sensitive data by the way of “differentiating”. Any pair of data $\theta_{i},\theta_{i}^{\prime}\in\mathbb{R}^{\frac{m(m+3)}{2}}$ is said to be $\mu$-adjacent with $\mu>0$, denoted by $(\theta_{i},\theta_{i}^{\prime})\in Adj(\mu)$, if ${\|\theta_{i}-\theta_{i}^{\prime}\|}_{0}=1$ and ${\|\theta_{i}-\theta_{i}^{\prime}\|}_{1}\leq\mu$. We denote $\mathcal{M}$ as a mapping (or mechanism) from the sensitive data $\theta_{i}$ to the eavesdropped communication messages, and give the following definition of $(\epsilon,\delta)$-differential privacy [27].

Before the close of this section, we make the following claims on the communication network. Denote by $\mathrm{N_{i}}=\{j|(i,j)\in\mathrm{E}\}$ as neighbor set of agent $i$, and $w_{ij}$ the weight of edge $(i,j)$, satisfying $w_{ij}=w_{ji}\in(0,1)$ for $j\in\mathrm{N_{i}}$ and $w_{ji}=0$ for $j\notin\mathrm{N_{i}}$. Moreover, denote by $L$ the Laplacian matrix of the graph $\mathrm{G}$, satisfying $(L)_{ij}=-w_{ij},\enspace i\neq j$, and $(L)_{ii}=\sum_{k=1}^{n}w_{ik}\in(0,1),\enspace i\in\mathrm{V}$. Since the graph $\mathrm{G}$ is assumed to be connected, by [40, Theorem 2.8] and Gershgorin Circle Theorem [41] there holds $0=\lambda_{1}(L)<\lambda_{2}(L)\leq\ldots\leq\lambda_{n}(L)<2$.

In this section, we modify the distributed gradient tracking algorithm [5] by injecting random noises to the sensitive data for the purpose of solving the distributed least-squares problem (2) while preserving differential privacy of $\theta_{i}$, $i\in\mathrm{V}$.

Let $\bar{\gamma}=\frac{d}{\sqrt{n}m}\underline{\lambda}_{A}$ for $d\in(0,1)$. For any $\epsilon>0$, we let

for $c\in(0,1)$, and choose $\sigma_{\eta}\geq{\mu}/{\bar{\kappa}_{\epsilon}(\delta)}$. With these parameters, we propose the Differentially Private Gradient Tracking-based (DP-GT-based) solver in Algorithm 1.

In Algorithm 1, two types of random noises (i.e., truncated Laplacian noises $\gamma_{i}$ and Gaussian noises $\eta_{i}$) are, respectively, added to the gradient tracking algorithm in the manner of directly perturbing the parameters $A_{i}$ (or $\theta_{i}^{A}$) and $B_{i}$, for the purpose of preserving $(\epsilon,\delta)$-differential privacy of these parameters. Particularly, the use of truncated Laplacian distribution (6) is motivated by [37]. It can be easily verified that the noise generated according to the truncated Laplacian distribution (6) has the mean zero and variance $\sigma_{\gamma}^{2}$ satisfying

Denote $\Omega_{A}=\mathcal{F}^{-1}(\sum_{i=1}^{n}\gamma_{i})$ and $\Omega_{B}=\sum_{i=1}^{n}\eta_{i}$. The following result demonstrates the differential privacy and computation accuracy that can be achieved by the above algorithm.

In this section, a new distributed solver with differential privacy is proposed to overcome the issues addressed in Remark 1.

We first observe that, the least-squares solution $x^{\ast}=-(\sum_{i=1}^{n}A_{i})^{-1}(\sum_{i=1}^{n}B_{i})$ implies that the least-squares problem (2) is solved if each agent obtains the global information $A=\sum_{i=1}^{n}A_{i}$ and $B=\sum_{i=1}^{n}B_{i}$. This intuition immediately motivates us to employ differentially private average consensus algorithms (e.g., [29, 42, 39]) to compute these global information in a distributed manner, while preserving the desired differential privacy. Further, we note that the differentially private average consensus algorithm proposed in [42, 39] yields a computation accuracy that can almost recover the centralized averaging algorithm where the accuracy of computing the sum is independent of the network size.

In view of the previous analysis, we propose a new solver by employing the differentially private average consensus algorithm proposed in [42, 39], whose implementation relies on the following distributed shuffling (DiShuf) mechanism where Paillier cryptosystem [43] is adopted with $\mathrm{E}_{i}(\cdot)$ and $\mathrm{D}_{i}(\cdot)$ as encryption and decryption operation, respectively, and $(k_{pi}$, $k_{si}$) as public and private key pair.

With some lengthy but straightforward computations, it can be seen that the output of the DiShuf mechanism (see Algorithm 2) satisfies

which implies $\sum_{i\in\mathrm{V}}\Delta_{i}=\textbf{0}_{m}$. Then we introduce the differentially private DiShuf-based average consensus algorithm below.

As $\sum_{i=1}^{n}\Delta_{i}=\textbf{0}_{m}$, it can be easily verified that

implying that the noises $\eta_{i}$ do not affect the average of $y_{i}(0)$, $i\in\mathrm{V}$. Thus, there are two design freedoms of noise variances (i.e., $\sigma_{\eta}^{2}$ and $\sigma_{\gamma}^{2}$), with the former affecting only achievable differential privacy, but having no influence on the average. As a result, by appropriately designing $\sigma_{\eta}$ and $\sigma_{\gamma}$, a better trade-off between the privacy and the accuracy can be achieved. The following result from [39] demonstrates the corresponding privacy and computation properties.

Towards this end, by employing Algorithm 3 to compute the average of $\theta_{i}:=[{\theta_{i}^{A}};B_{i}]$, $i\in\mathrm{V}$ in a distributed and differentially private manner, each agent $i\in\mathrm{V}$ can eventually obtain $\hat{\theta}:=ny(\infty):=\sum_{i=1}^{n}\theta_{i}+\sum_{i=1}^{n}\gamma_{i}$ and thus an estimate of the global information $(A,B)$ as $\hat{A}=A+\Omega_{A}$ and $\hat{B}=B+\Omega_{B}$, with $\Omega_{A}=\mathcal{F}^{-1}(\omega_{A})$ where $\omega_{A}$ denotes the vector formed by the first $m(m+1)/2$ entries of $\sum_{i=1}^{n}\gamma_{i}$, and $\Omega_{B}$ the vector formed by the last $m$ entries of $\sum_{i=1}^{n}\gamma_{i}$. Therefore, each agent $i$ can compute for the solution $x^{\ast}$ of the least-squares problem (2) by computing $\hat{x}^{\ast}$ from

It is noted that with $A$ invertible, its noisy version $\hat{A}=A+\Omega_{A}$ is actually invertible in a generic sense. Besides, if the resulting $\hat{A}$ is singular, one can implement Algorithm 3 again. It is also noted that $\mathbb{E}\|\hat{\theta}-\sum_{i=1}^{n}\theta_{i}\|^{2}=\frac{(1+g)^{2}\mu^{2}}{(\bar{\kappa}_{\epsilon}(\delta))^{2}}$, which is independent of the network size $n$. A natural conjecture comes out that the mean-square error between the computed $\hat{x}^{\ast}$ and the actual solution $x^{\ast}$ is also independent of $n$, though it is still open to derive an explicit expression of $\mathbb{E}\|\hat{x}^{\ast}-x^{\ast}\|^{2}$ due to the inverse operation on the random matrix, i.e., $\hat{A}^{-1}$.

In this section, we implement numerical simulations to show the effectiveness of our proposed Algorithms 1 and 3 (i.e., DP-GT-based solver and DP-DiShuf-AC-based solver, respectively), and compare their computation performance. We consider a cycle communication graph with each edge having the same weight $w_{ij}=0.3$ for $(i,j)\in\mathrm{E}$. In this section, $A_{i}\in\mathbb{R}^{3\times 3}$ and $B_{i}\in\mathbb{R}^{3}$ are randomly generated and $A=\sum_{i=1}^{n}A_{i}>0$.

Let the network size $n=10$ and choose $\bar{\gamma}=3.1$. Given the privacy budget $\mu=3$, $\epsilon=10$ and $\delta=0.2$, we let $\sigma_{\eta}=\frac{\mu}{\bar{\kappa}_{\epsilon}(\delta)}$ and $\beta=0.005$. It is shown in Figure 1 that the mean-square error $\mathbb{E}[\frac{1}{n}\sum_{i=1}^{n}\|x_{i}(t)-x^{\ast}\|^{2}]$ decreases and exponentially converges as $t$ increases, demonstrating the effectiveness of Algorithm 1.

Then we show the effectiveness of DP-DiShuf-AC-based solver. Taking the same $m$, $n$, $\mu$, $\delta$, choose $g=0.01$, we change $\epsilon$ and corresponding computed $\sigma_{\gamma}$ and $\sigma_{\eta}$. Figure 2 shows the distribution of computation error $\frac{1}{n}\sum_{i=1}^{n}\|\hat{x}^{\ast}-x^{\ast}\|^{2}$ under different $\epsilon$ with 100 samples. It is observed our Algorithm 3 holds a resilience to a higher privacy preservation level, i.e., a smaller $\epsilon$, in the sense of computation accuracy.

Further, we study the computation error $\frac{1}{n}\sum_{i=1}^{n}\|\hat{x}^{\ast}-x^{\ast}\|^{2}$ of our DP-Dishuf-AC-based solver (Algorithm 3) and DP-GT-based solver (Algorithm 1) under varying network size $n=10,50,250$. To make a comparison, we consider a differentially private average consensus based solver (DP-AC-based solver), obtained by removing the DiShuf mechanism in Algorithm 3, where Gaussian noises are directly added to privacy-sensitive data to preserve differential privacy [38]. It can be observed in Figure 3 that our Algorithm 3 (i.e., the DP-Dishuf-AC-based solver) shows the best computation accuracy in different scale networks.

In this paper, two solvers were proposed to solve the distributed least squares optimization problem with requirements of preserving differential privacy of local cost functions. The first solver was established on the distributed gradient-tracking algorithm, by perturbing the parameters encoding the sensitive data with truncated Laplacian noises and Gaussian noises. It was shown that this method leads to a limited differential-privacy-protection ability and the resulting computation accuracy linearly relies on the network size. To overcome these issues, the second solver was developed where the differentially private DiShuf-based average consensus algorithm was employed such that each agent obtains an noisy estimate of the global gradient function and thus compute the solution directly. As a result, one could achieve arbitrary differential privacy requirements and a computation accuracy independent of the network size. By simulations, it was shown that the computation accuracy of the former solver strictly increases as the network size increases, while such trend was not observed by the latter.