Communication efficient privacy-preserving distributed optimization using adaptive differential quantization

The main contribution of this paper that we propose a new privacy-preserving distributed optimization approach to mitigate the aforementioned trade-off between privacy and communication bandwidth. To do so, we first give an information-theoretical analysis on this trade-off in noise insertion approaches. After that we propose to address this trade-off by exploiting an adaptive differential quantization scheme. To the best of our knowledge, this is the first approach which provides information theoretical privacy guarantees for distributed optimization with quantization. The proposed approach has a number of attractive properties:

• •

  It addresses the privacy and communication bandwidth trade-off by significantly reducing the overall communication cost compared to existing approaches including secret sharing, subspace perturbation and differential privacy based approaches.

• •

  The accuracy of the optimization result is not compromised by considering both privacy and quantization.

• •

  It is generally applicable to various distibuted optimizers such as ADMM, PDMM and related algorithms.

• •

  It provides privacy guarantees under two widely-considered adversary models: eavesdropping and passive adversary models.

The rest of the paper is organized as follows. Section II reviews fundamentals of distributed optimization. Section III introduces important concepts about privacy and then formulate the problem to be solved. Section IV explains the reason why there is always a trade-off between privacy and communication bandwidth and Section V introduces the proposed approach to address it. Numerical results and comparisons with existing approaches are demonstrated in Section VI. Finally, the conclusion is given in Section VII.

We use the following notation throughout this paper. Lowercase letters $x$ denote scalars, lowercase boldface letters $\bm{x}$ denote vectors, uppercase boldface letters $\bm{X}$ denote matrices. $\bm{x}_{i}$ and $\bm{X}_{ij}$ denote the $i$-th and $(i,j)$-th entry of the vector $\bm{x}$ and the matrix $\bm{X}$, respectively. Denote calligraphic letters $\mathcal{X}$ as sets and uppercase letters $X$ denote random variables having realizations $x$. $H(X)$ and $h(X)$ denote the Shannon entropy and differential entropy of a random variable $X$, respectively.

We model a distributed network as a graph $\mathcal{G}=(\mathcal{N},\mathcal{E})$ where $\mathcal{N}={\{1,2,...,n}\}$ is the set of nodes and $\mathcal{E}\subseteq\mathcal{N}\times\mathcal{N}$ is the set of edges. Moreover, let $\mathcal{N}_{i}=\{j\,|\,{(i,j)\in\mathcal{E}\}}$ denote the set of neighboring nodes and $d_{i}=|\mathcal{N}_{i}|$ denote the degree (number of neighboring nodes) of node $i$. A standard distributed convex optimization problem with constraints over the network can be formulated as

where $\bm{x}_{i}\in\mathbb{R}^{u}$ denotes the optimization variable of node $i$, $f_{i}:\mathbb{R}^{u}\mapsto\mathbb{R}\cup\{\infty\}$ denotes the local objective function which is assumed to be convex, $\bm{B}_{i|j}$ and $\bm{B}_{j|i}$ are edge-related matrices (weights) and $\bm{b}_{i,j}\in\mathbb{R}^{u}$ denotes the constraint imposed at edge $(i,j)\in\mathcal{E}$. For simplicity, we assume $u=1$ and $\bm{b}_{i,j}=\bm{0}$, but the results can easily be generalized to arbitrary dimension and cases where $\bm{b}_{i,j}\neq\bm{0}$. With this, $\bm{B}_{i|j}$ and $\bm{B}_{j|i}$ are related to entries of the incidence matrix $\bm{B}\in\mathbb{R}^{m\times n},m=|\mathcal{E}|,$ of the graph: $\bm{B}_{li}=\bm{B}_{i|j}=1$, $\bm{B}_{lj}=\bm{B}_{j|i}=-1$ if and only if $e_{l}=(i,j)\in\mathcal{E}$ and $i<j$,

To solve the problem in (1) in a decentralized manner, i.e., where each node is only allowed to exchange information with its neighboring nodes, a number of distributed, iterative optimizers have been proposed, including ADMM [17] and PDMM [18, 19, 20]. It has been shown using monotone operator theory and operator splitting techniques that ADMM and PDMM are closely related [20] (see [21] for details on monotone operator theory). The updating equations at iteration $t=0,1,\ldots$ can be generally represented as

where $c$ is a constant for controlling the convergence rate. Each edge $e_{l}=(i,j)\in\mathcal{E}$ is associated to two auxiliary variables $\bm{z}=\bm{z}_{i|j}$ and $\bm{z}_{l+m}=\bm{z}_{j|i}$. Stacking all auxiliary variables together we have $\bm{z}\in\mathbb{R}^{2m}$. $\theta\in[0,1)$ is a constant for controlling the averaging of the nonexpansive operators. For example, $\theta=0$ results in Peaceman-Rachford splitting (PDMM) and $\theta=1/2$ results in Douglas-Rachford splitting (ADMM). For simplicity, we will use $\theta=0$, i.e., PDMM, as an example to explain the main idea but the conclusions hold for all $\theta\in[0,1)$.

In distributed optimization, sensitive personal information is often embedded in each node’s local objective function $f_{i}(\bm{x}_{i})$. The main reason is that the local objective function contains node-specific data as input and such data are often private in nature. As an example, consider a smart grid application. Assume each household/node in the network has its own power consumption data $\bm{s}_{i}$ and the goal is to compute the global average of these power consumption data, i.e., $n^{-1}\sum_{i\in\mathcal{N}}\bm{s}_{i}$. In this context the local objective function is given by $f_{i}(\bm{x}_{i})=\frac{1}{2}\|\bm{x}_{i}-\bm{s}_{i}\|^{2}_{2}$ and the overall problem setup can be formulated as follows:

Note that the power consumption data $\bm{s}_{i}$, contained in the local objective function $f_{i}(\bm{x}_{i})$, of each household should be protected from being revealed to others, because it can reveal information regarding the householders such as their activities and even their health conditions like whether they are disabled or not [22]. Hence, information regarding the local objective function $f_{i}(\bm{x}_{i})$ is considered to be sensitive and should be protected from being revealed in the process of solving the optimization problem.

To analyze the privacy, we must specify an adversary model. The purpose of such a model is to quantify the system robustness in dealing with different security attacks. In this paper, we consider two types of adversary models: the passive and the eavesdropping model. The passive (also called semi-honest or honest-but-curious) adversary model is a classical model considered in distributed networks [23]. It works by colluding a number of nodes, referred to as corrupted nodes. The corrupted nodes are assumed to follow the algorithm instructions (called the protocol) but will share information together. We call an edge in the graph corrupted as long as there is one corrupted node at its ends. All messages transmitted along such an edge will be known to the corrupted nodes, thus also to the passive adversary. See Fig.1 for a toy example. Hence, the passive adversary will collect all information from the corrupted nodes to infer private data of the other non-colluding nodes (referred to as honest nodes).

The eavesdropping adversary is assumed to attack the system by listening to the messages transmitted along the communication channels, i.e., edges. This model receives little attention as it can be addressed by assuming all communication channels are securely encrypted such that the transmitted messages cannot be eavesdropped, e.g., secret sharing based approaches [24, 11, 10]. However, this assumption is particularly expensive to realize in distributed optimization applications, as a large number of iterations is often required.

We assume that the considered two adversaries can cooperate, i.e., they share information together with the aim of inferring the private data of the honest nodes.

Putting things together, we now state the main requirements that communication efficient privacy-preserving distributed optimization should satisfy and introduce the related metrics.

1. 1.

   Output correctness: Each node $i$ should obtain the optimal solution to (1), denoted by $\bm{x}_{i}^{*}$, at the end of the algorithm. A typical way to quantify the output correctness is to adopt certain distance metrics to calculate the difference between the estimated output $\bm{x}^{(t)}$ and the optimum output $\bm{x}^{*}$. In this paper we use the overall mean square error (MSE) to quantify it, i.e., $\left\|\bm{x}^{(t)}-\bm{x}^{*}\right\|^{2}$.

2. 2.

   Communication cost: After the algorithm execution, the cost of all communications should be as low as possible. The communication cost is given by $T(2m)l$, where $T$ is the total number of iterations, $2m$ is the total amount of messages transmitted at each iteration ($d_{i}$ per node) and $l$ is the number of bits needed to represent each message.

3. 3.

   Individual privacy: Each node’s private information, embedded in $f_{i}(\bm{x}_{i})$, should be protected under both eavesdropping and passive adversaries throughout the algorithm. As we are focusing on noise insertion approaches, we will focus on information-theoretical metrics to describe the privacy. In the context of distributed processing, two commonly used metrics are the so-called $\epsilon$-differential privacy and mutual information [25]. In this paper we choose mutual information as the individual privacy metric. The main reasons are as follows. (1) Mutual information has been proven effective in the context of privacy-preserving distributed processing [26], and has been applied in various applications [27, 28, 29, 30, 31, 32]. (2) It is closely related to $\epsilon$-differential privacy (see [33] for more details), and is easier to realize in practice [34, 35, 36]. (3) $\epsilon$-differential privacy does not work if the private data is correlated [37].

Assume a scenario that a number of people, each having his/her own private data, would like to participate in a project which takes the private data of all these participants as input. Let $s$ denote the private data held by you and you are reluctant to share your private data to others due to privacy concerns. The idea of noise insertion is to insert certain noise, denoted by $r$, to obfuscate the private data and then share the obfuscated data, denoted by $s_{r}$, to others. One of the most simple yet widely-used way of noise insertion is to directly add the noise to the private data for protecting it from being revealed to others, referred to as additive noise insertion, and defined as

Intuitively, a higher privacy level will be achieved if the obfuscated data $s_{r}$ is less correlated with the private data $s$. We have the following result.

Hence, the more noise is inserted, the higher privacy level can be obtained. However, we remark that more noise will inevitably increase the noise entropy and thus requires a higher bit-rate (i.e., communication bandwidth). In what follows we will explain this in more detail.

The main idea of quantization is to establish a mapping of the input data to a countable set of reproduction values, which is referred to as a codebook. More specifically, a quantizer divides the input domain into so-called quantization cells (Voronoi regions) where all elements within a cell are represented by a unique reproduction or code value. Let $l$ denote the number of bits to represent the reproduction values, $2^{l}$ in total. Although there exists many different quantization schemes, we will introduce a simple yet effective one, namely uniform quantization. In this quantizer, all quantization cells have the same size, except for the cells at the boundary of the domain in the case of fixed bit-rate quantization. For example, a one-dimensional 2-bit uniform mid-rise quantizer with cell-width $\Delta$ will divide the input range into four regions, each represented by a unique code value. That is, the quantization cells are given by $(-\infty,-\Delta],(-\Delta,0],(0,\Delta],(\Delta,\infty)$ and respresented by $-\frac{3\Delta}{2},-\frac{\Delta}{2},\frac{\Delta}{2}$, and $\frac{3\Delta}{2}$, respectively.

Using a finite number of bits to quantize a continuous random variable will always produce an error, or distortion. Intuitively, the fewer bits are used, the more distortion will occur. To have an idea on how many bits are required for transmitting a message, we can determine its entropy since this gives a lower bound on the number of bits needed to represent the data. With a uniform quantizer, the entropy of a quantized continuous random variable $X$ at sufficiently high rate can be approximated as [38]:

where $\hat{X}$ is the discrete random variable after quantizing $X$, $\Delta_{x}$ denotes the quantization cell width and $D_{\Delta_{x}}=\frac{\Delta_{x}^{2}}{12}$ is the quantization noise variance. Here, $H(\hat{X})$ is the Shannon entropy of $\hat{X}$, and $h(X)$ is the differential entropy of $X$, assuming it exists. Since the differential entropy of a random variable with fixed variance $\sigma^{2}$ is upper bounded by

we have

Assume the inserted noise $R$ is Gaussian distributed and the desired privacy level $\delta$ is given. The entropy of the obfuscated data $S_{r}$ is then given by

where (a) holds as $S$ and $R$ are independent and (b) follows by setting $\sigma^{2}_{R}$ equal to $\beta$ given by (5). By inspection of (9), we can see that the smaller the information leakage $\delta$ is, i.e., the higher the privacy level is, the higher the amount of bits for representing the quantized obfuscated data $\hat{S_{r}}$ will be. Clearly there is a trade-off between them. In Fig. 2 we give an example based on (9) to demonstrate this trade-off, where we set $\sigma^{2}_{S}=1$ and $\Delta_{s_{r}}=10^{-5}$.

By inspection of (20), for $t\geq 1$ the updates $\bm{x}_{i}^{(t)}$ satisfy

We can see that the private data is only contained in the subgradient $\partial f_{i}(\bm{x}_{i}^{(t+1)})$. As a consequence, the goal of the privacy analysis is to see what information regarding $\partial f_{i}(\bm{x}_{i}^{(t+1)})$ is revealed during the iterations. Note that for $t=0$ we have $\partial f_{i}(\bm{x}_{i}^{(1)})+\sum_{j\in\mathcal{N}_{i}}\bm{B}_{i|j}\bm{z}_{i|j}^{(0)}+cd_{i}\bm{x}_{i}^{(1)}=0$.

For simplicity, assume $\bm{B}_{i|j}=1$ for all $j\in\mathcal{N}_{i}$, and thus $\bm{B}_{j|i}=-1$. Denote $\mathcal{N}_{c}$ and $\mathcal{N}_{h}$ as the set of corrupted nodes and honest nodes, respectively. Let $\mathcal{N}_{i,c}=\mathcal{N}_{i}\cap\mathcal{N}_{c}$ and $\mathcal{N}_{i,h}=\mathcal{N}_{i}\cap\mathcal{N}_{h}$ denote the set of the corrupted and honest neighbors of the node $i$, respectively. In addition, we assume a worse case that each honest node has at least one corrupted neighboring node, i.e., $\mathcal{N}_{i,c}\neq\emptyset$. Combining (14) and (15) we conclude that $\hat{\bm{v}}^{(t)}-\bm{n}_{q,v^{(t)}}=\bm{z}^{(t)}-\hat{\bm{z}}^{(t-1)}$, so that (18) can be expressed as

For node $k\in\mathcal{N}_{i,c}$, using (21) and (23), we can express the left-hand side of (22) as

To quantify the amount of information about the private data $\partial f_{i}(\bm{x}_{i}^{(t+1)})$ learned by the adversaries, we must first inspect what information is available to them. We first consider the passive adversary. As it can collect all the information available to the corrupted nodes, it has the following knowledge:

where $\mathcal{E}_{c}=\{(i,j)\in\mathcal{E},(i,j)\notin\mathcal{N}_{h}\times\mathcal{N}_{h}\}$ denotes the set of corrupted edges. With the above knowledge, the passive adversary is able to compute both $\sum_{j\in\mathcal{N}_{i,c}}\hat{\bm{z}}^{(t)}_{i|j}$ using (19) and $\frac{1}{2}d_{i}(\hat{\bm{z}}_{k|i}^{(t+1)}-\hat{\bm{z}}_{i|k}^{(t)})$ in (24). After computing these known terms, the unknown terms in (24) are given by

Next, we consider the eavesdropping adversary. To minimize the expense of requiring securely encrypted communication channels, we propose to use secure channel encryption only once. More specifically, no channel encryption is involved except for transmitting $\bm{z}^{(0)}$ during the initialization step. As a consequence, the eavesdropping adversary can listen to all transmitted messages after initialization, i.e.,

note that it does not have knowledge about ${\bm{z}}_{i|j}^{(0)}$. Based on (19), we can, therefore, deduce $\sum_{\tau=1}^{t}\hat{\bm{v}}_{i|j}^{(\tau)}$ from $\hat{\bm{z}}^{(t)}_{i|j}$ in (25) as it is known to the eavesdropping adversary. Consequently, we conclude that all what the passive and eavesdropping adversaries observe about the honest node $i$ is given by

where the last term $\{\bm{n}_{q,v_{k|i}^{(t+1)}}\}_{j\in\mathcal{N}_{i,c}}$ will converge to the all-zero vector as the iterations proceed. If node $i$ has at least one honest neighbor, i.e., $\mathcal{N}_{i,h}\neq\emptyset$, the term $\sum_{j\in\mathcal{N}_{i,h}}\bm{z}_{i|j}^{(0)}$ can be considered as noise. Hence, we can, by Proposition 1, protect the private data $\partial f_{i}(\bm{x}_{i}^{(t+1)})$ from being revealed by making the variance of $\bm{z}^{(0)}$ arbitrarily large at the initialization step. Therefore, arbitrarily small information leakage regarding $\partial f_{i}(\bm{x}_{i}^{(t+1)})$ can be achieved at every iteration.

We remark that the proposed quantized approach can be seen as a privacy-enhanced version of the existing subspace perturbation based approach [16] since it introduces an additional noise component $\bm{n}_{q,v_{k|i}^{(t+1)}}$ in (26) which helps to further protect the private data. Hence, we conclude that the conditions to guarantee the privacy of the data of honest node $i\in\mathcal{N}_{h}$ for both passive and eavesdropping adversaries are given by:

• •

  It has at least one honest neighbor. That is, $\mathcal{N}_{i,h}\neq\emptyset$.

• •

  The communication channels are securely encrypted in the initialization phase when transmitting $\bm{z}^{(0)}$.

In [40] it has been shown that if the sequence $\{{\bm{n}_{q,v^{(t)}}}\}_{t>0}$ is finitely summable, then Douglas-Rachford splitting will convergence to a fixed point $\bm{x}^{*}$ which is the solution to (1). Hence, the output correctness requirement is satisfied. As for the communication cost, we can see that with the help of quantization, the communication cost of the proposed approach is substantially reduced. In fact, as we will demonstrate in the next section, we can quantize the data with a one-bit quanitzer ($l=1$) and still obtain perfect output correctness and individual privacy.

The details of the proposed algorithm are summarized in Algorithm 1.

We use two applications to test the performance of the proposed approach: distributed average consensus and distributed least squares. The main reason for choosing these two applications is that they are intensively investigated in the literature [43, 44, 45, 24, 11, 46, 47, 48, 49, 14, 15]. The detailed problem formulation of distributed average consensus is already introduced in (2). As for distributed least squares, assume each node has partial knowledge of a linear system (assuming overdetermined) including an input observation, denoted as $\bm{Q}_{i}\in\mathbb{R}^{p_{i}\times u},\,p_{i}>u$ and a decision vector, denoted as $\bm{y}_{i}\in\mathbb{R}^{p_{i}}$. Stacking the partial knowledge together we denote $\bm{Q}=[\bm{Q}^{\top}_{1},\dots,\bm{Q}^{\top}_{n}]^{\top}\in\mathbb{R}^{P_{n}\times u}$ and $\bm{y}=[\bm{y}^{\top}_{1},\dots,\bm{y}^{\top}_{n}]^{\top}\in\mathbb{R}^{P_{n}}$, where $P_{n}=\sum_{i\in\mathcal{N}}p_{i}$. The goal of privacy-preserving distributed least squares is to allow each node to achieve the global optimum solution $\forall i\in\mathcal{N},\,\bm{x}_{i}^{*}=(\bm{Q}^{\top}\bm{Q})^{-1}\bm{Q}^{\top}\bm{y}\in\mathbb{R}^{u}$, without revealing its private data, i.e., $\bm{Q}_{i},\bm{y}_{i}$. With distributed optimization this problem can be formulated as

In all experiments, we randomly draw the private data, i.e., $\bm{s}_{i}$ in the case of distributed average consensus and $\bm{Q}_{i},\bm{y}_{i}$ in the case of distributed least squares, from a zero-mean Gaussian distribution with unit variance. In addition, we set $c=\gamma=0.9$ and the auxiliary variable $\bm{z}^{(0)}$ is initialized with zero-mean Gaussian distributed noise having a variance $\sigma^{2}_{z^{(0)}}\!={\Delta^{(0)}}^{2}$, where $\Delta^{(0)}$ is the initial quantization cell-width. Moreover, for the proposed quantized approach, a one-bit (mid-rise) quantizer is used with cell-width $\Delta^{(t)}$, which means that we only transmit the signs of the $\bm{z}_{i|j}$s which will be reconstructed at the receiver by $\pm\Delta^{(t)}/2$.

The performance of the proposed approach is demonstrated in terms of the three requirements mentioned in Section III-C.

1. 1.

   Output correctness: From Fig.3 we can see that applying the proposed adaptive differential quantization scheme to both PDMM (QPDMM) and ADMM (QADMM), the quantization noise $\bm{n}_{q,v^{(t)}}$ converges to zero and the optimization variable $\bm{x}^{(t)}$ converges to the optimal $\bm{x}^{*}$. These results validate the claim stated in Section V-B: if the sequence $\{{\bm{n}_{q,v^{(t)}}}\}_{t>0}$ is finite summable, the output correctness will be guaranteed. Hence, we conclude that the proposed approach satisfies the output correctness requirement, i.e., accuracy is not compromised by considering both quantization and privacy. Additionally, it is generally applicable to both ADMM and PDMM.

2. 2.

   Communication cost: Fig. 4 demonstrates the total communication cost (the amount of bits) of the proposed QADMM and QPDMM under three different privacy levels: $\sigma^{2}_{z^{(0)}}=10^{0},\sigma^{2}_{z^{(0)}}=10^{2},\sigma^{2}_{z^{(0)}}=10^{4}$. Note that for the proposed approach we have $l=1$ since a one-bit quantizer is used. We can see that the convergence rate of the proposed approach is invariant to the privacy level.

3. 3.

   Individual privacy: Fig.5 shows the individual privacy of an arbitrary honest node over iterations using the proposed approach under the condition that there is only one honest neighboring node when applied to the distributed average consensus problem. That is, the normalized mutual information measured based on (26) when $\mathcal{N}_{i,c}=d_{i}-1$. We can see that the larger $\sigma^{2}_{z^{(0)}}$ is, the less individual privacy is revealed, i.e., the higher the privacy level is. Hence, the proposed approach is able to guarantee individual privacy by controlling the variance of the initialized $\bm{z}^{(0)}$, i.e., $\sigma^{2}_{z^{(0)}}$.

We now compare the performance of the proposed QADMM with existing approaches including subspace perturbation (SP) based approach [16], secret sharing (SS) based approach [44] and differential privacy (DP) based approach [46]. To ensure a fair comparison, we insert the same amount of noise in all these algorithms. More specifically, all inserted noise are Gaussian distributed with zero mean and variance $10^{2}$. Additionally, all algorithms are based on the ADMM optimizer. Note that since none of the existing algorithms use a quantization scheme, the number of bits to represent each massage is set to $l=64$ (MATLAB double precision floating-point format). From Fig.6, we can see that

• •

  among these approaches, differential privacy based approach does not output an accurate result, i.e., it suffers from a privacy-accuracy trade-off;

• •

  as expected, compared to all existing approaches the proposed algorithm significantly reduces the communication cost.

One remark is placed here. Among all existing approaches: subspace perturbation, secret sharing and differential privacy based approaches, the proposed approach is obtained by applying adaptive differential quantization to the subspace perturbation based approaches such that the communication cost is reduced without sacrificing the individual privacy and output correctness. For the other two types of approaches it would also be interesting to investigate how quantization affects their performances in terms of privacy and accuracy.