Differentially Private Distributed Mismatch Tracking Algorithm for Constraint-Coupled Resource Allocation Problems

Distributed resource allocation problem (DRAP) has received much attention due to its wide applications in various domains, including smart grids [1], wireless networks[2] and robot networks [3]. The goal of DRAP is to achieve the cost-optimal distribution of limited resources among users to meet their demands, local constraints, and possibly certain coupled global constraints, see [4] for example. Conventional centralized approaches are subject to performance limitations of the central entity, such as a single point of failure, limited scalability. Moreover, it may raise privacy concerns when the central agent is not reliable enough. Alternatively, distributed approaches which operate with only local information have better robustness and scalability, especially for large-scale systems [5, 6, 7].

To implement algorithms in a distributed manner, the information exchange between agents in the network is unavoidable which can raise concerns about privacy disclosure. For example, in the supply–demand optimization of the power grid, attackers can infer users’ life patterns from certain published information that is computed based on the demand from users[8]. While the aforementioned works consider an ambitious suite of topics under various constraints imposed by real-world applications, privacy is an aspect generally absent in their treatments.

Recently, privacy preservation becomes an increasingly critical issue for distributed systems. Encryption-based algorithms are proposed for distributed optimization problems [9], [10] and proved to be effective. However, the encryption technique leads to a high computational complexity which seems undesirable in large-scale networks. To preserve the privacy of the agents’ costs, an asynchronous heterogeneous-stepsize algorithm is proposed in [11], but the method assumes that the infomation of communication topology is unavailable to attackers.

Another thread to address distributed optimization problems is to adopt differential privacy technique which is robust to arbitrary auxiliary information exposed to attackers, including communication topology information, thus well suited for multi-agents scenarios. Motivated by the privacy concerns in EV charging networks, the work in [8] presents a differentially private distributed algorithm to solve distributed optimization problem, but an extra central agent is needed. In [12], the authors design a completely distributed algorithm that guarantees differential privacy by perturbing the states with Laplace noise. It requires the stepsize to be decaying to guarantee the convergence, resulting in a low convergence rate. Adopting the gradient-tracking scheme, a differentially private distributed algorithm is proposed in [13] which has a linear convergence rate with constant stepsizes. However, the proposed algorithm in [13] is only applicable to unconstrained problems. For solving the economic dispatch problem where both global and local constraints are considered, a privacy-preserving distributed optimization algorithm is proposed in [14] for quadratic cost functions and its effctiveness in preserving privacy is guaranteed through qualitative analysis. The extension to general DRAPs is performed in [15] for strongly convex and Lipschitz smooth cost functions. Additionally, quantitative analysis of privacy is provided. However, the work only considers scalar cost functions and the coupling within constraints is ignored.

In this paper, a differentially private distributed mismatch tracking algorithm (diff-DMAC) is proposed to solve constraint-coupled DRAPs with individual constraints and a global linear coupling constraint while preserving the privacy of the local cost functions. To meet the global coupled-constraint, a mismatch tracking step is introduced to obtain the supply-demand mismatch in the network. And the tracked global mismatch is then implemented for error compensation. With a constant stepsize, diff-DMAC has a provable linear convergence rate for strongly convex and Lipschitz smooth cost functions. We further present a rigorous analysis of the algorithm’s differential privacy and thus provide a stronger privacy guarantee. Finally, its convergence properties and effectiveness in privacy-preserving are numerically validated.

The rest of the paper is organized as follows. Section II formulates the constraint-coupled DRAP. The proposed algorithm is developed in Section III. And the theoretical analyses about its convergence and privacy are given in Section IV and V, respectively. Then the algorithm is numerically tested in Section VI. Finally, Section VII concludes the paper.

Notation: Vectors default to columns if not otherwise specified. Bold letter $\mathbf{x}\in\mathbb{R}^{n\times p}$ is defined as $\mathbf{x}=[x_{1}^{\intercal},\cdots,x_{n}^{\intercal}]^{\intercal}$. The Kronecker product is denoted by $\otimes$. Let $\mathbf{1}_{n}$ be the $n$-dimension vector with all one entries. For vectors, we use $\|\cdot\|$ to denote the 2-norm. And for matrices, $\|\cdot\|$ denotes the spectral norm. $\underline{\lambda}(X)$ denotes the minimum eigenvalue of matrix $X$. We use $blkdiag(X_{1},\cdots,X_{n})$ to refer to the block-diagonal matrix with $X_{1},\cdots,X_{n}$ as blocks. For a random variable $x\in\mathbb{R}$, $Lap(\theta)$ denotes the Laplace distribution with pdf $f=(x|\theta)=\frac{1}{2\theta}e^{-\frac{|x|}{\theta}}$, where $\theta>0$. If $x\sim Lap(\theta)$, we have $\mathbb{E}[|x|]=\theta$, $\mathbb{E}[x^{2}]=2\theta^{2}$. $\mathbb{P}(\cdot)$ is used to denote the probability. $\mathbb{B}(S)$ denotes the set of Borel subsets of topological space $S$.

We consider the following general constraint-coupled distributed resource allocation problem

where $f_{i}:\mathbb{R}^{p}\rightarrow\mathbb{R}$ is the agent $i$’s private cost function, $x_{i}\in\mathbb{R}^{p}$ is the decision vector of agent $i$ and $d_{i}$ denotes the local resource demand. $\mathcal{X}_{i}$ is a local convex and closed set which encodes local constraints of agent $i$. $A_{i}\in\mathbb{R}^{m\times p}\ (p\geq m)$ is the coupling matrix with full row rank and $A_{i}^{\intercal}A_{i}$ is invertible, i.e., $\lambda$$(A_{i}^{\intercal}A_{i})>0$.

Many practical problems take the form of problem (1), e.g.,[1, 16]. One typical example is the economic dispatch of multi-microgrid (multi-MG) systems as shown in Fig. 1, where both microturbines and non-dispatchable distributed generators are involved to provide energy to meet the loads, and the outputs of non-dispatchable distributed generators can fluctuate significantly [16]. When the supply-demand balance in the MG cannot be maintained, the coordination among MGs is needed and both within-MG, between-MG optimization problems should be considered to improve systems’ reliability [17].

Assumption 1: Each cost function $f_{i}:\mathbb{R}^{p}\rightarrow\mathbb{R}$ is strongly convex and Lipschitz smooth, i.e.,

and

$\forall x,x^{\prime}\in\mathbb{R}^{p}$, where $\varphi_{i}>0$ and $L_{i}<\infty$ are the strong convexity and Lipschitz constants, respectively. Define $\underline{\varphi}=\min_{i}\{\varphi_{i}\}$ and $\overline{L}=\max_{i}\{L_{i}\}$.

The communication network over which agents exchange information can be represented by an undirected graph $\mathcal{G}=\left(\mathcal{N},\mathcal{E}\right)$ where $\mathcal{N}=\{1,\cdots,n\}$ is the set of agents and $\mathcal{E}\subseteq\mathcal{N}\times\mathcal{N}$ denotes the set of edges, accompanied with a nonnegative weighted matrix $\mathcal{W}$. For any $i,j\in\mathcal{N}$ in the network, $w_{ij}>0$ denotes agent $j$ can exchange information with agent $i$. The collection of all individual agents that agent $i$ can communicate with is defined as its neighbors set $\mathcal{N}_{i}$.

Assumption 2: The graph $\mathcal{G}$ is undirected and connected and the weight matrix $\mathcal{W}\in\mathbb{R}^{n\times n}$ is doubly stochastic, i.e., $\mathcal{W}\mathbf{1}_{n}=\mathbf{1}_{n}$ and $\mathbf{1}_{n}^{\intercal}\mathcal{W}=\mathbf{1}_{n}^{\intercal}$.

Assumptions 1-2 are standard when solving related problems.

In this problem, agents want to achieve the optimum while preserving the privacy of local cost functions which can be commercially sensitive in practice. To preserve privacy of functions, we add noise $\boldsymbol{\zeta}$ to mask the exchanged information $\mathbf{x}(k)$ at each time instant as $\mathbf{z}(k)=\mathbf{x}(k)+\boldsymbol{\zeta}(k)$. Let $\mathcal{F}$ be the function set $\{f_{i}\}_{i=1}^{n}$, the update of $\mathbf{x}$ can be expressed in impact form

where $g(\cdot)$ denotes the update rule. Therefore, exchanged information $\mathbf{z}=\{\mathbf{z}(k)\}_{k=0}^{\infty}$ can be determined if the initialization $\mathbf{x}(0)$, the added noises $\boldsymbol{\zeta}=\{\boldsymbol{\zeta}(k)\}_{k=0}^{\infty}$, the communication topology $\mathcal{W}$ and the function set $\mathcal{F}$ are known. To provide theoretical guarantees on the privacy for their cost functions, the concept of differential privacy is introduced, see [15].

Definition 1: Given $\delta>0$ and two function sets $\mathcal{F}^{(1)}=\{f_{i}^{(1)}\}_{i=1}^{n}$ and $\mathcal{F}^{(2)}=\{f_{i}^{(2)}\}_{i=1}^{n}$, the two subsets are $\delta$-adjacent if there exists $\delta^{\prime}\in(-\delta,\delta)$ and some $i_{0}$ such that

where $\mathcal{X}_{i_{0}}^{(l)}$ is the domain of $f^{(l)}_{i_{0}},l=1,2$ and they satisfy that $\mathcal{X}_{i_{0}}^{(2)}=\{x+\delta^{\prime}|x\in\mathcal{X}_{i_{0}}^{(1)}\}$.

Definition 2: Given $\delta,\epsilon>0$, for any two $\delta$-adjacent function sets $\mathcal{F}^{(1)},\mathcal{F}^{(2)}$ and any observation $\mathcal{O}\subset\mathbb{B}((\mathbb{R}^{nm})^{\mathbb{N}})$, the process keeps $\epsilon$-differentially private if

where we define $T^{(l)}=\{x(0),\mathcal{W},\mathcal{F}^{(l)}\}$, $Z_{T^{(1)}}(\boldsymbol{\zeta})=\mathbf{z}$ and the observation $\mathcal{O}$ encodes all the information collected by the potential attacker.

The attacker is assumed to know all auxiliary information, including the exchanged information between agents, communication topology, etc., except the parameter $\delta^{\prime}$. Intuitively, differential privacy guarantees that the two function sets can not be distinguished through the released information and thus avoids the leakage of the optimal operating point.

In this section, a distributed algorithm is designed to solve constraint-coupled DRAPs with privacy concerns. The following Proposition is presented to give the optimal conditions for constraint-coupled DRAP.

Proposition 1: $x^{\star}=[{x_{1}^{\star}}^{\intercal},\cdots,{x_{n}^{\star}}^{\intercal}]\in\mathbb{R}^{n\times p}$ is the optimal solution of (1) if it satisfies
i) $\ \sum_{i=1}^{n}A_{i}x_{i}^{\star}=\sum_{i=1}^{n}d_{i}$,
ii) there exists $\mu^{\star}\in\mathbb{R}^{m}$ such that

where $\mathcal{X}$ is defined as the Cartesian product $\mathcal{X}=\mathcal{X}_{1}\times\cdots\times\mathcal{X}_{n}$ and the matrix $\mathbf{A}=blkdiag(A_{1},\cdots,A_{n})$.

Proof: i) is one of the feasible conditions of (1) which must be satisfied. Problem (4) can be decomposed into $n$ subproblems $x_{i}^{\star}=\arg\min_{z\in\mathcal{X}_{i}}\{f_{i}(z)-{\mu^{\star}}^{\intercal}A_{i}z\},\forall i=1,\cdots,n$. It follows that

Summing the above inequality from $i=1$ to $n$ yields

If $\mathbf{x}^{\star}$ satisfies condition i), $\sum_{i=1}^{n}A_{i}x_{i}-\sum_{i=1}^{n}A_{i}x_{i}^{\star}=0$ holds for any feasible solution $\mathbf{x}$ of (1). Thus, we have $f(\mathbf{x}^{\star})\leq f(\mathbf{x})$ which completes the proof. $\hfill\blacksquare$

In the following, we will use Proposition 1 to develop a distributed algorithm for solving the DRAP (1). Based on the condition ii) of Proposition 1, the $\mathbf{x}$-update is designed and the consensus protocol [18] is adopted to drive $\mu_{i}$ in each agent to same value

where we define $\mathbf{W}=\mathcal{W}\otimes I_{m}$.

Inspired by the gradient-tracking scheme [19] , a tracking step is introduced here to track the global supply-demand mismatch as follows

Under Assumption 2, if the initialization condition $(\mathbf{1}_{n}\otimes I_{m})^{\intercal}(\mathbf{A}\mathbf{x}(0)-\mathbf{d})=(\mathbf{1}_{n}\otimes I_{m})^{\intercal}\mathbf{y}(0)$ holds, iteration (7) can infer that

To guarantee the condition i) of Proposition 1 holds, the tracked mismatch is used as a compensation term for $\boldsymbol{\mu}$-update (5). Thus, the proposed algorithm is obtained

The following Lemma shows the fixed point of the proposed algorithm is consistent with the optimal solution of the problem when Assumption 2 holds.

Lemma 1: Under Assumption 2, any fixed point of the proposed algorithm satisfies the optimal conditions of constraint-coupled DRAP.

Proof: It is not difficult to check that any fixed point $(\boldsymbol{\mu}_{F},\mathbf{x}_{F},\mathbf{y}_{F})$ of the proposed algorithm satisfies

Under Assumption 2, from (12) and (14), we have

Thus, $\mathbf{y}_{F}=0$ holds and combining it with (12) yields

Moreover, with proper initialization, from (8) we have

where (13), (16) and (17) correspond to the optimal conditions in Proposition 1 which completes the proof. $\hfill\blacksquare$

With privacy concerns, agents exchange noise-masked information against potential attackers to prevent information disclosure. In [20], Laplace noise is shown to satisfy the necessary and sufficient condition of differential privacy. Furthermore, due to the noise accumulation in the tracking process as $\sum_{i=1}^{n}y_{i}=\sum_{i=1}^{n}A_{i}x_{i}-\sum_{i=1}^{n}d_{i}+\sum_{i=1}^{n}\sum_{t=0}^{n-1}\zeta_{i}(t)$, the added noise $\zeta_{i}$ needs to decay to ensure the convergence of $y_{i}$. Likewise, $\eta_{i}$ also needs to decay for the convergence of $\mu_{i}$ and $y_{i}$. Thus, the added noises are set to $\eta_{i}(k)\sim Lap(\theta_{ik}^{\eta})$, $\zeta_{i}(k)\sim Lap(\theta_{ik}^{\zeta})$ where $\theta_{ik}^{\eta}=d_{\eta_{i}}{q_{i}}^{k},\theta_{ik}^{\zeta}=d_{\zeta_{i}}{q_{i}}^{k},q_{i}\in(0,1)$. That is, two diminishing Laplace noises are added to the communication process of $\mu_{i}$, $y_{i}$, respectively. Both of them are shown to be necessary in Section V.

Based on the mismatch tracking scheme and the information-masked protocol, a differentially private distributed mismatch tracking algorithm (diff-DMAC) is proposed which is shown in Algorithm 1 in details.

In this section, we will establish the linear convergence rate of the proposed algorithm in mean square. And the upper and lower bounds of the convergence accuracy is also provided. We set $d_{i}=0$, $\forall i$ in the following analysis for simplicity while nonzero scenarios can be analyzed similarly.

Let $\nabla f(x)=[{\nabla f_{1}(x_{1})}^{\intercal},\cdots,{\nabla f_{n}(x_{n})}^{\intercal}]^{\intercal}$ and $\mathbf{\bar{W}}=\frac{\mathbf{1}_{n}^{\intercal}\mathbf{1}_{n}}{n}\otimes I_{m}$, $\mathbf{\check{W}}=I_{nm}-\mathbf{\bar{W}}$, $\mathbf{\tilde{W}}=\mathbf{W}\mathbf{\check{W}}$. From (7), (9), we have that

where $\bar{\boldsymbol{\mu}}=\mathbf{\bar{W}}{\boldsymbol{\mu}}$, $\check{\boldsymbol{\mu}}=\mathbf{\check{W}}{\boldsymbol{\mu}}$ and the doubly stochasticity of the weight matrix is used here. Under Assumption 2, as a consequence of the Perron–Frobenius theorem, we have that $\|\mathcal{W}-\frac{\mathbf{1}^{\intercal}\mathbf{1}}{n}\|<1$, and thus

Lemma 2: For positive $a_{1}$, $a_{2}$, $a_{3}>0$, if $a_{1}a_{2}a_{3}>1$ holds, there exist $\gamma_{1}$, $\gamma_{2}$, $\gamma_{3}>0$ such that

The proof is omitted. Note that for any $\beta>0$, $\gamma_{i}^{\prime}=\beta\gamma_{i}$, $i=1,2,3$, also satisfy the condition (23). Define $C=\{1+(\frac{\|\mathbf{A}\|^{2}\alpha^{2}}{\underline{\varphi}^{2}}-\frac{2\alpha}{\overline{L}})\cdot\underline{\lambda}(A^{\intercal}A)\}^{\frac{1}{2}}$. Based on the above results, the following Theorem is proved by induction argument.

Theorem 1: Given a constant $r\in(r_{LB},\infty)$, where $r_{LB}$ is defined as $r_{LB}=\max\{q_{\zeta_{i}},q_{\eta_{i}},C,\bar{\lambda}\}$. Suppose Assumptions 1,2 hold, $\alpha$ satisfies

then the sequences generated by diff-DMAC satisfy

for some constant $\gamma_{1},\gamma_{2},\gamma_{3},\gamma_{4}>0$, where $\mathbf{x}^{\infty}$ and $\boldsymbol{\mu}^{\infty}$ satisfy

Proof: Combining (18) and (29), we have that

Under Assumption 1, the function

is differentiable and $f_{i}^{*}$ satisfies $\frac{1}{L_{i}}-$strongly convex and $\frac{1}{\varphi_{i}}-$Lipschitz smooth [21]. Furthermore, it follows (10) and the Proposition B.25 in [22] that

From (30) and (32), we can obtain that

where $C<1$ under (24) and the last inequality follows from the strongly convexity and Lipschitz smoothness of $f^{*}$.

We will prove (25)-(28) by induction. When $\kappa=0$, it is not difficult to find $\gamma_{1},\gamma_{2},\gamma_{3},\gamma_{4}>0$ such that (25)-(28) hold. We assume that for all $\kappa\leq k$, (25)-(28) hold. Considering $\kappa=k+1$, we obtain from (31) and (33) that

Combining (20)-(22) gives

Under Assumption 1, (32) implies that

where the last inequality is due to the Lipschitz smoothness of $f^{*}$.

Note that constant $\bar{\lambda},C\in(0,1)$, due to Lemma 2, there exist $\gamma_{1},\gamma_{2},\gamma_{3},\gamma_{4}>0$ such that

Basd on equations (38)-(41), taking suffciently large $\gamma_{1},\gamma_{2},\gamma_{3},\gamma_{4}>0$ yields

where we use the definition of $r_{LB}$ and substituting these equations into (34)-(37) completes the proof. $\hfill\blacksquare$

Based on Theorem 1, we prove the linear convergence property of diff-DMAC and quantify its convergence accuracy.

Theorem 2: Suppose the conditions in Theorem 1 are satisfied. If $\alpha$ further satisfies

the sequence $\{\mathbf{x(k)}\}_{k\geq 0}$ generated by diff-DMAC will converge linearly to the neighbor of the optimum $\mathbf{x}^{\star}$ in mean square and we have

where $N_{\zeta}$ is defined as $N_{\zeta}=\sum_{i=1}^{n}\frac{2md_{\zeta i}^{2}}{1-q_{\zeta i}^{2}}$ .

Proof: Note that $\bar{\lambda},C\in(0,1)$, it is not difficult to see that with $\alpha$ chosen to satisfy (42), we can always find a constant $r\in(r_{LB},1)$ such that equations (25)-(28) hold. Thus, the convergence of diff-DMAC is proved by Theorem 1.

Due to (29) and $\bar{\mathbf{W}}\mathbf{A}{\mathbf{x}}^{\star}=0$, we have

Since $\mathbf{\bar{W}}=\frac{\mathbf{1}^{\intercal}\mathbf{1}}{n}\otimes I_{m}$, it is easy to obtain that

The optimality condition of the $\mathbf{x}-$update (10) implies that

Based on (46) and (47), we obtain

The facts that $\bar{\mathbf{W}}{\boldsymbol{\mu}}^{\infty}={\boldsymbol{\mu}}^{\infty}$ and $\bar{\mathbf{W}}{\boldsymbol{\mu}}^{\star}={\boldsymbol{\mu}}^{\star}$ imply