KEYWORDS: Communication compression; Distributed optimization; Exponential convergence; Spatio-temporal compressors

1 Introduction↩︎

Distributed intelligent systems, such as drone swarms, smart grids, and cyber-physical systems, have been extensively researched across disciplines such as control, signal processing, and machine learning [2]-[3]. The mathematical representation of a distributed system involves a network connecting multiple agents, where each node symbolizes an individual agent, and the edges depict communication lines between these nodes. When distributed systems are required to implement tasks such as cluster optimization and collaborative control, it is required to compute distributively. In this process, each node stores localized information, communicates messages with connected nodes through the network, and collaboratively solves a mathematical problem [2]. This paper focuses on addressing distributed optimization problems, where each node possesses a function, aiming to identify solutions that collectively minimize the sum of all functions through communication across the network.

An extensive effort has been devoted to developing distributed optimization algorithms based on the consensus algorithm. The goal of the consensus algorithm is to reach a consensus of the states across nodes. A combination of the consensus algorithm with the classical gradient descent method in optimization problems, coupled with stability tactics, results in the distributed (sub)gradient algorithm (DSG), achieving sublinear convergence under a strongly convex global objective function [4]-[5]. More algorithms have been introduced to address distributed optimization problems with faster rate requirements, e.g., linear convergence. For example, the distributed gradient tracking algorithm (DGT) incorporates an additional state to track the gradient of the objective function [6], akin to integral action [7]. Besides, for different formulations of distributed optimization, various Lagrangian functions have been proposed, giving rise to multiple algorithms based on the saddle point dynamic method. Examples include the Wang–Eila algorithm in [8] and the primal-dual algorithm in [9], distinct in communication states.

In practical implementation, the network bandwidth for communication in distributed systems is limited and numerous strategies have been developed to address this issue. In [10], an event-triggered communication strategy is proposed to reduce communication frequency, thereby alleviating the communication burden. In addition, compressors that reduce the communication burden in each round have been extensively studied. Specifically, several compressors capable of reducing communication bits are proposed by synthesizing concepts from quantization [11]-[12], sparsity [13], scalarization [14] and randomization [15], [16]. Instead of specific ones, there are also some results that propose a general class of compressors [17]-[18], which contains some existing specific compressors and also allows to explore new compressors. However, the compressor classes proposed in the literature mainly focus on the spatial dimension, utilizing the information contained within transmitted messages. This prevents new compressors that utilize temporal information (e.g., [14]) from being included, which motivates our study of new compressor classes that capture both temporal and spatial information.

In addition, how to combine the compressors with distributed optimization algorithms has become a noteworthy area of study. This is because the compression method can facilitate the successful integration of more general compressors and enhance the effectiveness of the algorithm. Direct compression often leads to biased convergence [19], [20]. To handle this, more complex compression methods with extra states are proposed. For instance, [11], [16] incorporate a weighted sum of the updated value and the original value into the original value, while [21], [22] compress the difference between iterations rather than the original value. In [23], [24], the difference is scaled and then compressed, with the results communicated after a reverse reduction to ensure convergence. In [12], [25]–[27] a difference compression method based on filters is adopted, where only compressed values are exchanged through some additional equivalent transformations. Despite these impressive results, it is still open how to achieve unbiased linear convergence when directly incorporating the compressors into distributed optimization algorithms. This then acts as part of our research motivations.

In view of the previous analysis, this paper aims to propose a new and general compressor class characterized by properties of simultaneously capturing both temporal and spatial dimensions, i.e., the spatial-temporal (ST) compressor. Given this compressor class and considering the fact that the majority of existing distributed optimization algorithms are established on the consensus, we first investigate the condition under which direct compression in the consensus flow can lead to unbiased exponential convergence. To incorporate more ST compressors into algorithms, we further propose a novel observer-based compression method. With these compressed consensus flows, we then propose two distributed ST-compressed primal-dual flows with direct and observer-based compression, respectively, for which exponential convergence can be guaranteed. Moreover, for implementation, discrete-time algorithms are established by Euler discretization with linear convergence guarantees. The main contribution lies in the following aspects.

• A general class of ST compressors and its strong version are proposed for communication compression in distributed optimization, from a novel perspective of nonlinear system theory, specifically, in terms of exponential stability of nonlinear non-autonomous systems. This ST compressor class not only encompasses various existing communication compressors, but also inspires new compressors.

• An affirmative answer is established that directly incorporating the strong ST compressors can lead to unbiased exponential/linear convergence, if a sufficient condition is satisfied. It is also shown that such a condition is satisfied if the compressor is linear, e.g., the scalarization compressor.

• An observer-based compression method is developed so that more general ST compressors can be incorporated into distributed algorithms with exponential/linear convergence guaranteed, while removing the restrictive sufficient condition for the direct compression method.

We begin with and focus on continuous-time systems in this paper, even though distributed optimization algorithms in real applications are mostly in discrete-time. This is because, first, the properties of our ST compressors are described by the induced systems, and the converse Lyapunov theorem is used, with the continuous-time form being more intuitive for our analysis. Second, we would like to build our work as a natural extension of the results on continuous-time distributed optimization algorithms in the control system community, e.g., [28]-[29]. In addition, we offer a discrete version of the proposed continuous algorithm by Euler approximation, enabling our results to be applied in real situations.

The paper is structured as follows. Section 2 formulates the distributed optimization problem and proposes the notion of (strong) spatio-temporal compressor for message communication. In Section 3, we start from the distributed consensus to illustrate the conditions required by the direct compression method, and then introduce the observer-based compression method. In Section 4, we respectively discuss the applicability of these two compression methods to the primal-dual flow. In Section 5, we propose the ST compressors in discrete time and discretize the continuous-time flows by the Euler method. Numerical simulations are presented to show the effectiveness of the proposed algorithms in Section 6. Finally, a conclusion is made in Section 7. All proofs are collected in Appendices. Compared to our preliminary conference version [1], this paper has made several new significant results, by introducing the concept of strong ST compressors and proposing distributed compressed consensus/optimization flows with direct and observer-based compression methods (see Theorems 1-4). Furthermore, we introduce the ST compressors in discrete time and propose two distributed compressed optimization algorithms via Euler discretization.

Notations. \(\left\|\cdot \right\|\) denotes the Euclidean norm. The notation \(\mathbf{1}_n\left(\mathbf{0}_n\right)\), \(\mathbf{I}_n\) and \(\left\{{\boldsymbol{e}}_1,\dots,{\boldsymbol{e}}_n\right\}\) denote column one (zero vector, identity matrix and base vectors in \(\mathbb{R}^n\), respectively. Denote \(\mathrm{diag}\left(x_1,\dots,x_n\right)\) as a diagonal matrix with the \(i\)-th diagonal element being \(x_i\). The symbol \(\otimes\) denotes the Kronecker product. We use \(\nabla\left(\cdot\right)\) to denote the gradient of a function and use \(*\) to denote the Hadamard product.

2 Problem Formulation↩︎

2.1 Distributed Optimization↩︎

Consider a network of agents indexed by \(\mathrm{V}=\left\{1,2,\dots,n\right\}\), where each agent \(i\in\mathrm{V}\) holds an objective function \(f_i:\mathbb{R}^d\rightarrow \mathbb{R}\). The agents aim to solve the following system-level optimization problem \[\label{eq:DO} \begin{align} \mathrm{min}&\; \sum_{i=1}^n f_i\left(\mathbf{x}_i\right),\\ \mathrm{s.t.}&\;\mathbf{x}_i=\mathbf{x}_j, \quad\forall i,j\in \mathrm{V}. \end{align}\tag{1}\] In particular, each local objective function \(f_i\) is assumed to satisfy the following requirements.

If Assumption 1 holds, then the considered optimization problem 1 turns out a strongly convex optimization problem, allowing a unique solution \(s^\ast{\in}\mathbb{R}^d\) such that \(\nabla f\left(s^\ast\right)=0\) and \(f\left(s^\ast\right)=f^\ast\), where \(f^\ast\) is the optimal value.

As each agent only has information about its own objective function, to solve such a distributed optimization problem 1 , a communication network is usually required to transmit messages. Denote the communication graph \(\mathrm{G=\left(V,E\right)}\), where \(\mathrm E\) denotes the set of edges. Let \([a_{ij}]\in \mathrm{R}^{n\times n}\) denote the weight matrix, i.e., \(a_{ij}>0\) if \(\left\{j,i\right\}\in\mathrm{E}\) and \(a_{ij}=0\) if \(\left\{j,i\right\}\notin\mathrm{E}\). Then denote the Laplacian matrix of graph \(\mathrm G\) by \(\mathbf{L}\), satisfying \([\mathbf{L}]_{ij}=-a_{ij}\) for all \(i\neq j\), and \([\mathbf{L}]_{ii}=\sum_{j=1}^n a_{ij}\) for all \(i\in\mathrm{V}\). Denote the neighbor set of agent \(i\) as \(\mathrm{N}_i\), satisfying \(j\in\mathrm{N}_i\) if and only if \([\mathbf{L}]_{ij}\neq0\) for all \(i,j\in\mathrm{V}\). For simplicity, we make the following assumption on the communication graph.

Assumption 2 indicates that the Laplacian matrix \(\mathbf{L}\) is symmetric and positive semi-definite, with \([\mathbf{L}]_{ij}=[\mathbf{L}]_{ji}\), \(\mathbf{L}\mathbf{1}_n=\mathbf{0}_{n}\) and its eigenvalues \(\lambda_i\), \(i\in\mathrm{V}\) in ascending order satisfying \(0=\lambda_1<\lambda_2\leq\dots\leq \lambda_n\) by [2]. We let \(\mathbf{S}\in\mathbb{R}^{n\times\left(n-1\right)}\) be a matrix whose rows are eigenvectors corresponding to non-zero eigenvalues of \(\mathbf{L}\), satisfying \[\begin{align} \mathbf{S}^T\mathbf{1}_n =\mathbf{0}_{n-1}\,,\quad \mathbf{I}_n = \mathbf{S}\mathbf{S}^T +\mathbf{1}_n\mathbf{1}_n^T/n . \end{align}\] In the literature, various distributed optimization algorithms have been developed to compute the solution \(s^\ast\) for 1-[9]. In this paper, we focus on the distributed primal-dual algorithm, which enables exponential convergence and further generalizations to the case with constraints [30], [31]⁸. A common distributed primal-dual flow for 1 takes the form [8], [9], [32] \[\begin{align}\label{eq:Primal95Dual} \dot{\mathbf{x}}_i=-\sum^{n}_{j=1}\mathbf{L}_{ij} {\mathbf{x}}_{j}-\beta \mathbf{v}_i-\eta \nabla f_i\left(\mathbf{x}_i\right), \; \dot{\mathbf{v}}_i={\beta\sum^{n}_{j=1}\mathbf{L}_{ij}\mathbf{x}_{j}}, \end{align}\tag{2}\] where \(\beta,\eta>0\) are parameters to be fixed and the initial condition \(\sum_{i=1}^n \mathbf{v}_i\left(0\right)=\mathbf{0}_d\).

2.2 Spatio-Temporal Compressors↩︎

We propose the following notions of (strong) spatio-temporal compressors for compressing node-to-node communications in distributed algorithms.

For a ST compressor \(\mathbf{C}\), it needs to vanish at the origin, i.e., \(\mathbf{C}\left(0,t\right)\equiv0\) uniformly in \(t\), to satisfy the UGES property. This immediately implies that P2) turns out the uniformly linearly bounded property, i.e., \(\left\|\mathbf{C}\left(\mathbf{x}_e,t\right)\right\| \leq L_c\left\|\mathbf{x}_e\right\|\). In addition, it is clear that \(k\mathbf{C}\) is also a ST compressor if so is the mapping \(\mathbf{C}\) by definition. Thus, we can simply incorporate such \(k\) when designing compressors. In view of this, without loss of generality, we assume UGES of \(\dot{\mathbf{x}}_e=-\mathbf{C}\left(\mathbf{x}_e,t\right)\) by letting \(k=1\) for simplicity, when referring to a ST compressor \(\mathbf{C}\) in the sequel. By the converse Lyapunov Theorem for UGES [33], this enables to construct a Lyapunov function \(V_e\left(\mathbf{x}_e,t\right):\mathbb{R}^{d}\times\mathbb{R}_+\rightarrow\mathbb{R}\) such that \[\begin{align}\label{eq:AC46b46Ve} c_1\|\mathbf{x}_e\|^2 \leq V_{e}\left(\mathbf{x}_e,t\right)&\leq c_2\|\mathbf{x}_e\|^2,\\ \frac{\partial V_{e}}{\partial t} - \frac{\partial V_{e}}{\partial \mathbf{x}_e} \mathbf{C}\left(\mathbf{x}_e,t\right) &\leq -c_3\|\mathbf{x}_e\|^2,\\ \left\|\frac{\partial V_{e}}{\partial \mathbf{x}_e}\right\| &\leq c_4 \|\mathbf{x}_e\|, \end{align}\tag{3}\] for some explicit parameters \(c_1,c_2,c_3,c_4>0\).

In the following, we show that various existing compressors can be categorized into ST or SST compressors.

Inspired by [23], [24] and the definition of ST compressor, we also propose a new compressor below.

Problem of Interest. In view of the above notion of ST compressors, the following two intuitive questions can be naturally raised, which will be addressed in this paper.

• How to incorporate ST compressors into distributed primal-dual algorithms to solve problem 1 with compressed communication?

• For the resulting distributed compressed primal-dual algorithms, can the convergence be maintained in such a way to reduce the communication burden?

3 ST-Compressed Consensus Flows↩︎

Distributed consensus is a fundamental algorithm that acts as a subroutine in numerous distributed optimization problems. In this section, we investigate how to combine the ST compressors with the consensus algorithm, which motivates the subsequent developments of distributed optimization algorithms with ST compressors. Moreover, due to its convenience of analysis, we focus on the continuous-time distributed consensus, taking the form \[\begin{align}\label{eq:AC} \dot{{\mathbf{x}}}_i &= -\sum_{j\in\mathrm{N}_i} \mathbf{L}_{ij} {\mathbf{x}}_{j}. \end{align}\;\tag{4}\] It is clear that under Assumption 2, each node state exponentially reaches consensus at \({\mathbf{x}}^\ast:=\frac{1}{n}\sum_{j=0}^n \mathbf{x}_j\left(0\right)\) [35].

3.1 Consensus with Direct Compression↩︎

An intuitive design of the compressed consensus algorithm is to directly replace the information \(\mathbf{x}_i\) with the compressed one for transmission, leading to the following distributed consensus flow with direct compression (DC-DC flow) as \[\begin{align}\label{eq:AC46a} \dot{{\mathbf{x}}}_i &= -\sum_{j\in\mathrm{N}_i} \mathbf{L}_{ij} \mathbf{C}\left({\mathbf{x}}_j,t\right). \end{align}\;\tag{5}\]

In the following, we will investigate when the DC-DC flow 5 maintains exponential convergence to the average. Before answering this question, we make the following observation on the SST compressor. Given a SST compressor \(\mathbf{C}\), it is clear that the system \[\begin{align} \dot{\mathbf{y}}_e=-\Lambda \overline{\mathcal{C}}\left(\mathbf{y}_e,t\right), \end{align}\] where \({\mathbf{y}}_e\in\mathbb{R}^{\left(n-1\right)d}\), \(\Lambda:= \mathrm{diag} \left(\lambda_2,\dots,\lambda_n\right)\otimes \mathbf{I}_d\) and \(\overline{\mathcal{C}}\left(\mathbf{y},t\right):=[\mathbf{C}^T\left(\mathbf{y}_{1},t\right),\dots,\mathbf{C}^T\left(\mathbf{y}_{n-1},t\right)]^T\), is UGES at the zero equilibrium. By the converse Lyapunov Theorem for UGES [33], this enables to construct a Lyapunov function \(V_e:\mathbb{R}^{\left(n-1\right)d}\times\mathbb{R}_+\rightarrow\mathbb{R}_+\) such that

\[\begin{align} \label{eq:Ve} \overline{c}_1\|\mathbf{y}_e\|^2 \leq \overline{V}_{e}\left(\mathbf{y}_e,t\right)&\leq \overline{c}_2\|\mathbf{y}_e\|^2,\\ \frac{\partial \overline{V}_{e}}{\partial t} - \frac{\partial \overline{V}_{e}}{\partial \mathbf{y}_e} \Lambda \overline{\mathcal{C}}\left(\mathbf{y}_e,t\right)& \leq \overline{c}_3\|\mathbf{y}_e\|^2,\\ \left\|\frac{\partial V_{e}}{\partial \mathbf{y}_e}\right\| &\leq \overline{c}_4 \|\mathbf{y}_e\|, \end{align}\tag{6}\] for some explicit constants \(\overline{c}_1,\overline{c}_2,\overline{c}_3,\overline{c}_4>0\). With this in mind, by defining \(\mathbf{S}_\otimes:=\mathbf{S}\otimes\mathbf{I}_d\) and \(\mathcal{C}\left(\mathbf{x},t\right):=[\mathbf{C}^T\left(\mathbf{x}_{1},t\right),\dots,\mathbf{C}^T\left(\mathbf{x}_{n},t\right)]^T\), we are ready to propose the following theorem for Flow 5 , answering the question by showing that a condition on the communication network \(\mathrm{G}\) and the SST compressor \(\mathbf{C}\) is still required in order to maintain exponential convergence to the average.

From the extra condition ?? , it can be seen that the SST compressor \(\mathbf{C}\) needs to satisfy some conditions relying on the network topology (see \(\mathbf{S}_\otimes\)) to ensure the exponential convergence property of the DC-DC Flow 5 in general. Notably, by taking a linear form of SST compressor \(\mathbf{C}\left(\mathbf{x}_e,t\right)=M(t)\mathbf{x}_e\), e.g. the scalarization compressor \(\mathbf{C}_1\), we note that the extra condition ?? reduces to \[\|[\left(\mathbf{I}_{n-1}\otimes M(t)\right)\mathbf{S}_\otimes^T-\mathbf{S}_\otimes^T \left(\mathbf{I}_{n-1}\otimes M(t)\right)]\mathbf{x}\|\leq \delta \|\mathbf{S}_\otimes^T\mathbf{x}\|\,,\] which holds for all \(\left(\mathbf{x},t\right)\in\mathbb{R}^{nd}\times\mathbb{R}_+\), since \(\left(\mathbf{I}_{n-1}\otimes M(t)\right)\mathbf{S}_\otimes^T-\mathbf{S}_\otimes^T \left(\mathbf{I}_{n-1}\otimes M(t)\right) = 0\). This immediately implies that the linear SST compressor, e.g., the scalarization compressor \(\mathbf{C}_1\), is applicable to the DC-DC Flow 5 with no need of any extra condition, as shown in [14]. On the other hand, due to the involvement of the network topology and dependence on \((\mathbf{x},t)\), the verification of ?? is generally difficult for nonlinear compressors. This thus motivates the subsequent development of new compression methods that allow more general ST compressors applicable.

3.2 Consensus with Observer-based Compression↩︎

In the previous section, it has been shown that the SST compressor can be directly incorporated, subject to an extra condition ?? . This poses limitations on the range of feasible compressors. In this section, to allow more general ST compressors to be incorporated, we propose another compression method based on distributed observer. The corresponding distributed compressed consensus takes the form \[\begin{align}\label{eq:AC46b} \dot{{\mathbf{x}}}_i &= -\alpha\sum_{j\in\mathrm{N}_i} \mathbf{L}_{ij} {\hat{\mathbf{x}}}^i_j, \\ \dot{\hat{\mathbf{x}}}^i_j&={\mathbf{x}}_{j,c} ,\quad j\in\mathrm{N}_i,\\ {\mathbf{x}}_{i,c}&=\mathbf{C}\left({\mathbf{x}}_i-{\hat{\mathbf{x}}}^i_i,t\right), \end{align}\;\tag{7}\] where \(\alpha>0\) is a gain parameter, and \({\hat{\mathbf{x}}}^j_i\left(0\right)={\hat{\mathbf{x}}}^{j'}_i\left(0\right),\forall j,j'\in \mathrm{N}_i\), \(i\in\mathrm{V}\).

The proposed compressed consensus Flow 7 is comprised of two sets of states for each agent \(i\). The state \(\mathbf{x}_i\) denotes the estimate of the consensus solution as in 4 , while the states \({\hat{\mathbf{x}}}^i_j\) are introduced to each agent \(i\) to estimate its neighboring solution state \(\mathbf{x}_j\), \(j\in\mathrm{N}_i\). To have a better view of this, let us first ignore the compressor and have \({\mathbf{x}}_{i,c}={\mathbf{x}}_i-{\hat{\mathbf{x}}}^i_i\) in 7 . Then it is clear that the \({\hat{\mathbf{x}}}^i_j\) acts as an observer to estimate \(\mathbf{x}_j\). The observer-based compression method is thus established in order to realize compression and communication of the error state \({\mathbf{x}}_i-{\hat{\mathbf{x}}}^i_i\). Since the compression errors for the error state \({\mathbf{x}}_i-{\hat{\mathbf{x}}}^i_i\) are smaller compared to directly compressing the state \({\mathbf{x}}_i\), the observer-based compression method allows the use of more general compressors than direct compression.

A rigorous proof of Theorem 2 is presented in Appendix C. Intuitively, from the perspective of control systems, we stress that the corresponding system 7 can be regarded as an interconnection of two subsystems: \(\mathbf{x}_i\)-subsystem and \({\hat{\mathbf{x}}}^i_j\)-subsystem, with \(\alpha\) a low gain that is tuned such that the supply functions of the two interconnected subsystems satisfy some small-gain conditions for closed-loop exponential stability [33]. On the other hand, we note that such \(\alpha\) is not necessarily to be small, as the \(\mathbf{C}\) is designable and can be chosen so as to have a large margin for \(\alpha\).

4 ST-Compressed Primal-Dual Flows↩︎

In the previous section, two compressor incorporation methods have been introduced to the consensus flow with exponential convergence guarantees. In the following, we will show that the resulting two ST-compressed consensus flows can be further explored, respectively, to establish distributed ST-compressed primal-dual flows based on Flow 2 for problem 1 with linear convergence guarantees.

4.1 Direct Compression↩︎

In this subsection, we aim to propose a distributed compressed primal-dual flow for problem 1 based on the directly compressed consensus Flow 5 . The proposed distributed primal-dual flow with direct compression takes the form \[\begin{align}\label{eq:CPD46a} \dot{\mathbf{x}}_i&=-\sum^{n}_{j=1}\mathbf{L}_{ij} \mathbf{C}\left(\mathbf{x}_j,t\right)-\beta \mathbf{v}_i-\eta \nabla f_i\left(\mathbf{x}_i\right), \\ \dot{\mathbf{v}}_i&={\beta\sum^{n}_{j=1}\mathbf{L}_{ij}\mathbf{C}\left(\mathbf{x}_j,t\right)}, \end{align}\tag{8}\] where the initial condition \(\sum_{i=1}^n \mathbf{v}_i\left(0\right)=\mathbf{0}_d\).

We propose the following theorem for Flow 8 .

This theorem demonstrates the effectiveness of direct compression. When the conditions in Theorem 3 are satisfied, direct compression of the compressor can ensure exponential convergence, without introducing extra states required by other compression methods. The convergence rates presented in Theorem 3 and the subsequent theorems are in fact explicitly derived. However, because of the involvement of numerous intermediate variables, we provide the detailed expressions in Appendices for readers of interest.

4.2 Observer-based Compression↩︎

In this section, we propose distributed compressed primal-dual flow based on distributed observer-based compressed consensus 7 in Section 3.2.

The proposed distributed primal-dual flow in continuous-time form with observer-based compression takes the form \[\begin{align}\label{eq:CPD46b} \dot{\mathbf{x}}_i&=-\alpha\sum^{n}_{j=1}\mathbf{L}_{ij} {\hat{\mathbf{x}}}^i_j-\beta \mathbf{v}_i-\eta \nabla f_i\left(\mathbf{x}_i\right), \\ \dot{\mathbf{v}}_i&={\beta\sum^{n}_{j=1}\mathbf{L}_{ij}{\hat{\mathbf{x}}}^i_j},\\ \dot{\hat{\mathbf{x}}}^i_j&= {\mathbf{x}}_{j,c} ,\quad j\in\mathrm{N}_i,\\ {\mathbf{x}}_{i,c}&=\mathbf{C}\left({\mathbf{x}}_i-{\hat{\mathbf{x}}}^i_i,t\right), \end{align}\tag{9}\] where the initial condition is \(\sum_{i=1}^n \mathbf{v}_i\left(0\right)=\mathbf{0}_d\) and for each \(i\in\mathrm{V}\), \({\hat{\mathbf{x}}}^j_i\left(0\right)={\hat{\mathbf{x}}}^{j'}_i\left(0\right),\forall j,j'\in \mathrm{V}\).

We propose the following theorem for Flow 9 .

5 Discrete Implementations↩︎

5.1 ST Compressors in Discrete Time↩︎

Based on the ST compressors in Definition 1, we propose the following (strong) ST compressors in discrete time.

In discrete-time cases, it should be noticed that the condition ?? of the scalarization compressor becomes \(\alpha_2 \mathbf{I}_d \geq \sum_{s=t}^{t+T_1-1} \boldsymbol{\psi}\left(s\right)\boldsymbol{\psi}^T \left(s\right) \geq \alpha_1 \mathbf{I}_d\,,\;\forall t\geq 0\,.\) A specific example of discrete-time cases of \(\mathbf{C}_1\), denoted by \(\mathbf{C}_{1a}\), can be derived by letting \(\boldsymbol{\psi}(t)= \mathbf{e}_i\) with \(i=1+\left(t\; \mathrm{mod}\;d\right)\) for \(t\in\mathbb{N}\).

5.2 Discretization of Compressed Primal-Dual Flows↩︎

In practice, algorithms are always implemented in a discrete-time form. In the following, we discretize the Flow 8 based on the Euler method, resulting in Algorithm 1.

Next, we discretize Flow 9 based on the Euler approximation method, yielding Algorithm 2.

5.3 Comparison with Filter-based Compression↩︎

The distributed primal-dual flow with filter-based compression (DPD-FC) takes the form 10 . Similar ideas can be seen in [12], [25]–[27].

\[\label{eq:fc} \begin{align} {\boldsymbol{\sigma}}_{i}\left(t+1\right)&=\boldsymbol{\sigma}_i(t)+\kappa_0\mathbf{q}_i(t), \\ {\mathbf{z}}_{i}\left(t+1\right)&=\mathbf{z}_i(t)+\kappa_0\big(\mathbf{q}_i(t)-\sum^{n}_{j=1}\mathbf{L}_{ij}\mathbf{q}_j(t)\big),\\ {\mathbf{x}}_{i}\left(t+1\right)&=\mathbf{x}_i(t)-\kappa\big(\boldsymbol{\sigma}_i(t)-\mathbf{z}_i(t)+\sum^{n}_{j=1}\mathbf{L}_{ij}{\mathbf{q}}_j(t)\\ &\quad +\beta \mathbf{v}_{i}(t)+\eta \nabla f_i(\mathbf{x}_i(t))\big), \\ {\mathbf{v}}_{i}\left(t+1\right)&=\mathbf{v}_i(t)+\kappa{\beta\big(\boldsymbol{\sigma}_i(t)-\mathbf{z}_i(t)+\sum^{n}_{j=1}\mathbf{L}_{ij}{\mathbf{q}}_j(t)\big)},\\ \mathbf{q}_i(t) &= \mathbf{C}\left(\mathbf{x}_i(t)-\boldsymbol{\sigma}_i(t),t\right). \end{align}\tag{10}\]

The DPD-FC 10 introduces a distributed filter and a distributed integrator. The filter \(\boldsymbol{\sigma}_i\) is used to track the state \(\mathbf{x}_i\), while the integrator \(\mathbf{z}_i\) tracks the term \(\boldsymbol{\sigma}_i - \sum_{j=1}^{n}\mathbf{L}_{ij} \boldsymbol{\sigma}_j.\) In contrast, the DPD-OC in Algorithm 2 introduces distributed observers to track the states of neighboring nodes. As a result, both algorithms share a similar compression idea in the sense of compressing and transmitting error states.

For DPD-FC 10 , the ST compressors can be incorporated, leading to unbiased linear convergence. The corresponding analysis is referred to in the conference version [1], but is omitted here due to space limitations.

5.4 Stochastic ST Compressors and Algorithms↩︎

It should be noticed that many literature on compressor assumption take into account the presence of randomness. Therefore, we extend the ST compressor to randomness and study its effectiveness in applications. In this section, we study the randomization of the ST compressor and the application of DPD-OC as a example.

Introduce randomness to ST compressors, we obtain the definition of Stochastic Spatio-Temporal (StST) Compressor, with focus on discrete time.

The ST compressor is a special case of the StST compressor. Moreover, some compressor assumptions in literature belongs to the StST compressor.

The proof of Proposition 2 is similar to that of Proposition b). and is omitted for simplicity.

We apply the StST compressor to DPD-OC and propose the following theorem for DPD-OC.

6 Numerical Simulations↩︎

6.1 Verification of ST Compressors↩︎

In this section, we verify that the compressors mentioned in this paper \(\mathbf{C}_{1a}\), \(\mathbf{C}_{2a}\) (\(k=2\)), \(\mathbf{C}_{2b}\), \(\mathbf{C}_{2c}\) (\(\Delta=1\)), \(\mathbf{C}_{3a}\) (\(\gamma_e=0.9\)), satisfy that the induced system \(\dot{\mathbf{x}}_e=-\mathbf{C}\left(\mathbf{x}_e,t\right)\) is UGES at the zero equilibrium, thus belong to the ST compressors.

The plots in figures respectively demonstrate the exponential convergence system \(\dot{\mathbf{x}}_e=-\mathbf{C}\left(\mathbf{x}_e,t\right)\) with different compressors, validating our conclusions in Proposition 1.

6.2 Simulations under Different Compression Methods↩︎

In this section, we consider a network of \(n=10\) nodes over a circle communication graph and the dimension of the local state is \(d=5\), where each edge is assigned with the same unit weight and each node holds a local function \(f_i\left(\mathbf{x}_i\right)=\frac{1}{2}\|\mathbf{H}^T_i \mathbf{x}_i-b_i\|^2\) with randomly generated \(\mathbf{H}_i\in\mathbb{R}^d\) and \(b_i\in\mathbb{R}\). Moreover, the functions \(f_i\left(\mathbf{x}_i\right)\) satisfy Assumption 1 with \(\mu>0\) and a unique optimal solution \(s^\ast\). Next, we will incorporate different compression methods into algorithms and compare their effects.

We use the scalarization compressor \(\mathbf{C}_{1a}\) and the greedy sparsifier compressor \(\mathbf{C}_{2a}\) as examples. In this application, we integrate DPD-DC, DPD-OC, DPD-FC, DPD-Choco with \(\mathbf{C}_{1a}\), and integrate DPD-OC, DPD-FC, DPD-Choco with \(\mathbf{C}_{2a}\), where DPD-Choco is an algorithm incorporating the compression method from [13] into 2 . The plots in figures illustrate the evolution of the sum of squared distances from the current \(\mathbf{x}_i(t)\) to \(s^\ast\), denoted as \(\sum_{i=1}^n\|\mathbf{x}_i(t)-s^\ast\|^2\) with respect to iterations and transmitted bytes in each node, respectively. It can be seen that the algorithms exhibit linear convergence to the optimal solution, verifying Theorem 5 and Theorem 6. In addition, as we set the stepsize parameters large enough, the figures show that DPD-OC converges faster than DPD-DC, thereby requiring fewer transmitted bytes to achieve the same accuracy, which verifies Remark 5.

6.3 Simulations with Different Compressors↩︎

Next, we investigate the performance of different specific compressors. For the above-mentioned problem, we incorporate compressors \(\mathbf{C}_{1a}\), \(\mathbf{C}_{2a}\), \(\mathbf{C}_{2b}\), \(\mathbf{C}_{3a}\) into the DPD-OC proposed in this paper, while keeping all other parameters unchanged. The plots in figures illustrate the evolution of \(\sum_{i=1}^n\|\mathbf{x}_i(t)-s^\ast\|^2\) with respect to iterations, which show the linear convergence of DPD-OC with any ST compressor, verifying Theorem 6. Moreover, the number of bytes required for each iteration, the number of iterations required to achieve an accuracy of \(10^{-4}\) and the total number of transmitted bytes are shown in Table 1, from which we can observe that all compressors significantly reduce the total transmitted bytes.

6.4 Simulations with Convex Objective Functions↩︎

Next, we discuss the case where the objective function is convex but not strongly convex, while other settings are the same as that in the previous subsection. We take the objective function from [36] as \[\begin{align} \min\sum_{i=1}^nf_i\left(\mathbf{x}\right) = \sum_{j=1}^{d-1} \left[ 100\left([\mathbf{x}]_{j+1} - [\mathbf{x}]_j^2\right)^2 + \left([\mathbf{x}]_j - a_i\mathbf{1}_d\right)^2 \right], \end{align}\] whose optimal solution is \(s^\ast=\mathbf{1}_d\). The simulation results of DPD-DC, DPD-OC, DPD-FC, DPD-Choco with \(\mathbf{C}_{1a}\), as examples, are shown in figures. From the figure, we can see that the above algorithm can achieve asymptotic convergence to the optimal solution for convex but not strongly convex functions. Moreover, in this case, there is no significant difference in the convergence rates of the different compression methods. This contrasts with the results in figures and is worth studying in our future work.

7 Conclusion↩︎

In this paper, we have introduced a type of spatio-temporal compressor that integrates both spatial and temporal characteristics, and effectively compresses information by leveraging information from both the time and space domains. This type of compressor has covered several compressors in the literature and inspired the proposal of new compressors. Our proposed compressor has been implemented in the primal-dual algorithm by the direct compression method and the observer-based compression method for exponential/linear convergence. Future work includes the application of the ST compressor to other classical distributed optimization algorithms, such as those based on stochastic gradient methods [37], to further explore and verify its general applicability. In addition, methods beyond compressors, such as stochastic communication [38] and event-triggered communication [10], can be integrated with our ST compressors to reduce the communication burden. Furthermore, extending the proposed algorithms to nonconvex optimization problems, particularly those with objective functions satisfying the P-Ł condition [39], presents another promising avenue for future research.

8 Proof of Proposition 1↩︎

Proof of a). First, we prove \(\mathbf{C}_1\) belong to ST compressors. The proof of P1) is obvious that the system \(\dot{\mathbf{x}}_e=-k\boldsymbol{\psi}(t)\boldsymbol{\psi}(t)^T\mathbf{x}_e\) is UGES at the zero equilibrium for any \(k>0\) by recalling [40], and the proof of P2) can be shown by noting that \(\boldsymbol{\psi}(t)\) is uniformly bounded.

Proof of b). Next, for \(\mathbf{C}_2\), we note that the property ?? is equivalent to \[\begin{align} \label{ass95c239} \|{\mathbf{C}_2\left(\mathbf{x}_e\right)}/{p}\|^2-2{\mathbf{x}_e^T\mathbf{C}_2\left(\mathbf{x}_e\right)}/{p}\leq -\varphi\|\mathbf{x}_e\|^2\,. \end{align}\tag{11}\] First, we prove that the system \(\dot{\mathbf{x}}_e=-\mathbf{C}_2\left(\mathbf{x}_e,t\right)\) is UGES at the zero equilibrium. By choosing the Lyapunov function \(V_e\left(\mathbf{x}_e\right)={\|\mathbf{x}_e\|^2}/{p}\) and using 11 , we have \(\dot{V}_e=-2\frac{\mathbf{x}_e^T\mathbf{C}_2\left(\mathbf{x}_e\right)}{p}\leq -\varphi\|\mathbf{x}_e\|^2.\) With \(\varphi>0\), we conclude that \(\mathbf{x}_e\)-system is UGES at the zero equilibrium and then P1) is proved. In addition, by 11 and the Young’s inequality, we have \[\label{eq:c2L} \begin{align} \|{\mathbf{C}_2\left(\mathbf{x}_e\right)}/{p}\|^2&\leq \frac{1}{2}\|{\mathbf{C}_2\left(\mathbf{x}_e\right)}/{p}\|^2-\left(\varphi-2\right)\|\mathbf{x}_e\|^2\\ \Rightarrow \|{\mathbf{C}_2\left(\mathbf{x}_e\right)}\|&\leq p\sqrt{{2\left(2-\varphi\right)}}\|\mathbf{x}_e\|\leq 2p\|\mathbf{x}_e\|, \end{align}\tag{12}\] where the last inequality is obtained by \(\varphi\in(0,1]\). Thus P2) is proved with \(L_c=2p>0\).

Proof of c). Finally, for \(\mathbf{C}_3\), to prove the system \(\dot{\mathbf{x}}_e=-\mathbf{C}_3(\mathbf{x}_e,t)=-\gamma_e^t\left\lfloor\frac{\mathbf{x}_e}{\gamma_e^t}\right\rfloor\) is UGES, we let \(\mathbf{z}_e(t):=\frac{\mathbf{x}_e(t)}{\gamma_e^t}\), and then have \[\begin{align} \dot{\mathbf{z}}_e=-\left\lfloor\mathbf{z}_e\right\rfloor-\ln(\gamma_e)\mathbf{z}_e. \end{align}\] By choosing \(V_e\left(\mathbf{z}_e\right)={\|\mathbf{z}_e\|^2}/{2}\), we have \[\begin{align} \dot{V}_e&=-\mathbf{z}_e^T\left\lfloor\mathbf{z}_e\right\rfloor-\ln(\gamma_e)\mathbf{z}_e^T\mathbf{z}_e\\&\leq -(1+\ln(\gamma_e))\|\mathbf{z}_e\|^2+\sqrt{d}\|\mathbf{z}_e\|\\ &\leq-(1+\ln(\gamma_e))V_e+\frac{d}{2(1+\ln(\gamma_e))}. \end{align}\] As \(\gamma_e\in(e^{-1},1)\), we can obtain \(1+\ln(\gamma_e)>0\). Thus \(V_e(t)\) and \(\mathbf{z}_e(t)\) are bounded uniformly. With \(\mathbf{x}_e(t)=\mathbf{z}_e(t)\gamma_e^t\) and \(\gamma_e< 1\), we complete the proof of P1) with \(k=1\). In addition, it is easy to obtain that \(\|\mathbf{C}_3(\mathbf{x}_e,t)\|\leq \|\mathbf{x}_e\|\) for all \(t\geq0\), and thus P2) is proved with \(L_c=1\). The proof of Proposition 1 is completed.

9 Proof of Theorem 1↩︎

Flow 5 can be written in a compact form as \[\label{eq:AC46a461} \begin{align} \dot{\mathbf{x}}&=-\mathbf{L}_\otimes\mathbf{x}_c,\\ \mathbf{x}_c&= \mathcal{C}\left(\mathbf{x},t\right), \end{align}\tag{13}\] where \(\mathbf{x}:=[\mathbf{x}_1^T,\dots,\mathbf{x}_n^T]^T\), \(\mathbf{x}_c:=[\mathbf{x}_{1,c}^T,\dots,\mathbf{x}_{n,c}^T]^T\) and \(\mathbf{L}_\otimes:=\mathbf{L}\otimes\mathbf{I}_d\). We decompose \(\mathbf{x}\) by defining \(\mathbf{x}_\perp:=\mathbf{S}_\otimes^T\mathbf{x}=[\mathbf{x}^T_{\perp,1},\dots,\mathbf{x}^T_{\perp,n-1}]^T\) and \(\mathbf{x}_\parallel:=\mathbf{1}_\otimes^T\mathbf{x}\), where \(\mathbf{1}_\otimes:=\frac{1}{\sqrt{n}}\mathbf{1}_n\otimes \mathbf{I}_d\). This immediately implies \(\dot{\mathbf{x}}_\parallel=\mathbf{0}_{d}\) using the fact \[\begin{align}\label{eq:HL} \mathbf{1}_\otimes^T \mathbf{L}_\otimes=\mathbf{0}\quad \mathbf{L}_\otimes\mathbf{1}_\otimes=\mathbf{0}. \end{align}\tag{14}\] Moreover, with \[\begin{align} \label{eq:HK}\mathbf{S}_\otimes\mathbf{S}_\otimes^T+\mathbf{1}_\otimes\mathbf{1}_\otimes^T=\mathbf{I}_{nd}, \end{align}\tag{15}\] it is clear that \(\mathbf{x}_i(t)\) converges to the average consensus exponentially if \(\mathbf{x}_\perp(t)\) is shown to be convergent to zero exponentially.

With the above in mind, we compute the time derivative of \(\mathbf{x}_\perp\) as \[\label{eq:AC46a462} \begin{align} \dot{\mathbf{x}}_\perp= -\mathbf{S}_\otimes^T\mathbf{L}_\otimes\mathbf{\mathcal{C}}\left(\mathbf{x},t\right), \end{align}\tag{16}\] for which we choose a Lyapunov function as \(V\left(\mathbf{x}_\perp,t\right):=\overline{V}_e\left(\mathbf{x}_\perp,t\right)\), which is defined in 6 , and obtain \[\begin{align} \label{eq:AC46a46V} \dot{V}&=\frac{\partial V}{\partial t} - \frac{\partial V}{\partial \mathbf{x}_\perp} \Lambda \overline{\mathcal{C}}\left({\mathbf{x}}_\perp,t\right)+\frac{\partial V}{\partial \mathbf{x}_\perp}[\Lambda \overline{\mathcal{C}}\left({\mathbf{x}}_\perp,t\right)-\mathbf{S}_\otimes^T\mathbf{L}_\otimes\mathbf{\mathcal{C}}\left(\mathbf{x},t\right)] \\ &\leq -\left(\overline{c}_3-\overline{c}_4\delta\lambda_n\right)\|\mathbf{x}_\perp\|^2, \end{align}\tag{17}\] where the inequality is obtained by using \[\begin{align} \|\Lambda \overline{\mathcal{C}}\left(\mathbf{y}_e,t\right)-\mathbf{S}_\otimes^T\mathbf{L}_\otimes\mathbf{\mathcal{C}}\left(\mathbf{x},t\right)\| &\leq \lambda_n\|\overline{\mathcal{C}}\left({\mathbf{x}}_\perp,t\right)-\mathbf{S}_\otimes^T\mathcal{C}\left(\mathbf{x},t\right)\|\\ &\leq\delta\lambda_n\|\mathbf{x}_\perp\|. \end{align}\] For \(\delta<\frac{\overline{c}_3}{\overline{c}_4\lambda_n}\), \(\dot{V}\) is negative definite. With 6 , we further have \(\dot{V}\leq -\frac{\overline{c}_3-\overline{c}_4\delta\lambda_n}{\overline{c}_1}V,\) yielding \(\|\mathbf{x}_\perp(t)\|^2=\mathcal{O}\left(e^{-\gamma t}\right)\) with \(\gamma=\frac{\overline{c}_3-\overline{c}_4\delta\lambda_n}{\overline{c}_1}\). The theorem is thus proved.

10 Proof of Theorem 2↩︎

From Flow 7 and its initial condition, we can obtain that for each \(i\in \mathrm{V}\), \({\hat{\mathbf{x}}}^i_j\left(0\right)={\hat{\mathbf{x}}}^{j'}_i\left(0\right),\forall j,j'\in \mathrm{V}\), i.e., the stored value of \(\mathbf{x}_i\) is same in each node. Thus the stored value of each node can be written as \(\mathbf{x}_c:=[\mathbf{x}_{1,c}^T,\dots,\mathbf{x}_{n,c}^T]^T\). Then Flow 7 can be written in a compact form as \[\label{eq:AC46b461} \begin{align} \dot{\mathbf{x}}&=-\alpha\mathbf{L}_\otimes \mathbf{x}_c, \\\dot{\mathbf{x}}_c&=\mathcal{C}\left(\mathbf{x}-\mathbf{x}_c, t\right), \end{align}\tag{18}\] where \(\mathcal{C}\left(\mathbf{x}-\mathbf{x}_c,t\right)=[\mathbf{C}^T\left(\mathbf{x}_{1}-\mathbf{x}_{1,c}, t\right),\dots,\mathbf{C}^T\left(\mathbf{x}_{n}-\mathbf{x}_{n,c}, t\right)]^T.\) Similarly, we decompose \(\mathbf{x}\) by defining \(\mathbf{x}_\perp:=\mathbf{S}_\otimes^T\mathbf{x}\) and \(\mathbf{x}_\parallel:=\mathbf{1}_\otimes^T\mathbf{x}\). Then there holds \(\dot{\mathbf{x}}_\parallel=\mathbf{0}_d\), and the proof is done if we show that \(\mathbf{x}_\perp(t)\) exponentially converges to zero.

By 18 , we have \[\label{eq:AC46b462} \begin{align} \dot{\mathbf{x}}_\perp&=-\alpha\mathbf{S}_\otimes^T\mathbf{L}_\otimes \mathbf{x}_c, \\\dot{\mathbf{x}}_c&=\mathcal{C}\left(\mathbf{x}-\mathbf{x}_c, t\right). \end{align}\tag{19}\]

Next, we will introduce Lyapunov functions for system 19 . By choosing \(V_1\left(\mathbf{x}_\perp\right):=\frac{1}{2}\|\mathbf{x}_\perp\|^2\), there holds \[\label{eq:AC46b46V1} \begin{align} \dot{V}_1\leq \frac{\alpha}{2}\left(-\lambda_2\|\mathbf{x}_\perp\|^2+\lambda_n\|\mathbf{x}-\mathbf{x}_c\|^2\right). \end{align}\tag{20}\]

Letting \(V_2\left(\mathbf{x}-\mathbf{x}_c,t\right):=\sum_{i=1}^n V_e\left(\mathbf{x}_i-\mathbf{x}_{i,c}, t\right)\), which is defined in 3 , then we have \[\label{eq:AC46b46V2} \begin{align} \dot{V}_2&\leq -c_3\|\mathbf{x}-\mathbf{x}_c\|^2+\frac{\alpha}{2}\lambda_nc_4\sqrt{n} \|\mathbf{x}-\mathbf{x}_c\|^2 + \frac{\alpha}{2} c_4\sqrt{n} \mathbf{x}_c^T\mathbf{L}_\otimes\mathbf{x}_c \\ &\leq -\left(c_3-\frac{3\alpha}{2}\lambda_nc_4\sqrt{n}\right)\|\mathbf{x}-\mathbf{x}_c\|^2+\alpha \lambda_n c_4\sqrt{n}\|\mathbf{x}_\perp\|^2, \end{align}\tag{21}\] where the first inequality is obtained by 3 and the second inequality is obtained by the fact \[\begin{align} \mathbf{x}_c^T\mathbf{L}_\otimes\mathbf{x}_c\leq2\lambda_n\|\mathbf{x}-\mathbf{x}_c\|^2 + 2\lambda_n\|\mathbf{x}_\perp\|^2. \end{align}\] Define the Lyapunov function for system 19 as \(V:=\chi_0V_1+V_2\) with \(\chi_0=\frac{4\lambda_nc_4\sqrt{n}}{\lambda_2}\). Then for any given \(\alpha\leq\alpha^\ast:=\mathrm{min}\left\{\frac{2c_3}{9\lambda_nc_4\sqrt{n}},\frac{\lambda_2c_3}{6\lambda^2_nc_4\sqrt{n}}\right\}\), and with 20 and 21 , we have \[\label{eq:AC46b46V} \begin{align} \dot{V}\leq -\frac{\alpha}{4}\chi_0\lambda_2\|\mathbf{x}_\perp\|^2-\frac{c_3}{3}\|\mathbf{x}-\mathbf{x}_c\|^2. \end{align}\tag{22}\] With 3 , we have \(V\geq \frac{\chi_0}{2}\|\mathbf{x}_\perp\|^2+c_1\|\mathbf{x}-\mathbf{x}_c\|^2,\) then \(\|\mathbf{x}_\perp(t)\|^2=\mathcal{O}\left(e^{-\gamma t}\right)\) with \(\gamma=\mathrm{min}\left\{\frac{ \alpha\lambda_2}{2},\frac{ c_3}{3c_1}\right\}\). The theorem is thus proved.

11 Proof of Theorem 3↩︎

Flow 8 can be written in a compact form as \[\begin{align}\label{eq:CPD46a461} \dot{\mathbf{x}}&= -\mathbf{L}_\otimes{\mathbf{x}_c}-\beta \mathbf{v}-\eta \mathbf{F}\left(\mathbf{x}\right), \\ \dot{\mathbf{v}}&={\beta \mathbf{L}_\otimes\mathbf{x}_c},\\ \mathbf{x}_c&= \mathcal{C}\left(\mathbf{x},t\right), \end{align}\tag{23}\] where \(\mathbf{v}:=[\mathbf{v}_{1}^T,\dots,\mathbf{v}_{n}^T]^T\) and \(\mathbf{F}\left(\mathbf{x}\right):=[\nabla f_1^T\left(\mathbf{x}_{1}\right),\dots,\nabla f_n^T\left(\mathbf{x}_{n}\right)]^T\).

As \(f\left(x\right)\) is strongly convex, there exists a unique \(s^\ast\in\mathbb{R}^d\) such that \(\nabla f\left(s^\ast\right)=\mathbf{0}_d\), i.e., \(\mathbf{1}_\otimes^T \mathbf{F}\left(\mathbf{s}\right)=\mathbf{0}_d\) with \(\mathbf{s}:=\sqrt{n}\mathbf{1}_\otimes s^\ast\). Then it can be easily verified that \((\mathbf{x},\mathbf{v})=(\mathbf{s},-\frac{\eta \mathbf{F}\left(\mathbf{s}\right)}{\beta})\) is the equilibrium point of system 23 . Define state errors \(\overline{\mathbf{x}}:=\mathbf{x}-\mathbf{s}\) and \(\overline{\mathbf{v}}:=\mathbf{v}+\frac{\eta \mathbf{F}\left(\mathbf{s}\right)}{\beta}\), whose time derivatives along 23 are given by \[\begin{align}\label{eq:CPD46a462} \dot{\overline{\mathbf{x}}}&=-\mathbf{L}_\otimes\mathbf{x}_c-\beta \overline{\mathbf{v}}-\eta \tilde{\mathbf{F}}\left(\overline{\mathbf{x}}\right), \\ \dot{\overline{\mathbf{v}}}&=\beta \mathbf{L}_\otimes\mathbf{x}_c,\\ \mathbf{x}_c&=\mathcal{C}\left(\mathbf{x},t\right), \end{align}\tag{24}\] where \(\tilde{\mathbf{F}}\left(\overline{\mathbf{x}}\right):=\mathbf{F}\left(\overline{\mathbf{x}}+\mathbf{s}\right)-\mathbf{F}\left(\mathbf{s}\right)\).

We decompose \(\overline{\mathbf{x}}\) and \(\overline{\mathbf{v}}\) by defining \(\mathbf{\overline{x}}_{\perp}:=\mathbf{S}_\otimes^T\overline{\mathbf{x}}\), \(\mathbf{\overline{x}}_{\parallel}:=\mathbf{1}_\otimes^T\overline{\mathbf{x}}\), \(\mathbf{\overline{v}}_{\perp}:=\mathbf{S}_\otimes^T\overline{\mathbf{v}}\) and \(\mathbf{\overline{v}}_{\parallel}:=\mathbf{1}_\otimes^T\overline{\mathbf{v}}\). From 15 , it can be concluded that the exponential convergence of \(\overline{\mathbf{x}}(t)\) and \(\overline{\mathbf{v}}(t)\) is proved if \(\mathbf{\overline{x}}_{\parallel}(t)\), \(\mathbf{\overline{x}}_{\perp}(t)\), \(\mathbf{\overline{v}}_{\parallel}(t)\) and \(\mathbf{\overline{v}}_{\perp}(t)\) are shown to exponentially converge to zero.

Now we proceed to investigate exponential convergence of \(\mathbf{\overline{x}}_{\parallel}(t)\), \(\mathbf{\overline{x}}_{\perp}(t)\), \(\mathbf{\overline{v}}_{\parallel}(t)\) and \(\mathbf{\overline{v}}_{\perp}(t)\). From 23 and 14 , it is clear that \(\mathbf{1}_\otimes^T\dot{\mathbf{v}}(t)=\mathbf{0}_{d}\). With the initial condition \(\mathbf{1}_\otimes^T\mathbf{v}\left(0\right)=\mathbf{0}_{d}\), we have \[\label{eq:Hv} \begin{align} \mathbf{\overline{v}}_{\parallel}(t)=\mathbf{1}_\otimes^T\overline{\mathbf{v}}(t)=\mathbf{1}_\otimes^T(\mathbf{v}(t)-\frac{\eta\mathbf{F}\left(\mathbf{s}\right)}{\beta})=\mathbf{0}_{d}. \end{align}\tag{25}\] Then, taking the time derivatives of \(\mathbf{\overline{x}}_{\parallel}(t)\), \(\mathbf{\overline{x}}_{\perp}(t)\) and \(\mathbf{\overline{v}}_{\perp}(t)\), yields \[\begin{align}\label{eq:CPD46a463} \mathbf{\dot{\overline{x}}}_{\perp}&=-\mathbf{S}_\otimes^T \mathbf{L}_\otimes \mathbf{x}_c-\beta \mathbf{\overline{v}}_{\perp}-\eta\mathbf{S}_\otimes^T \tilde{\mathbf{F}}\left(\overline{\mathbf{x}}\right),\\ \mathbf{\dot{\overline{x}}}_{\parallel}&=-\eta\mathbf{1}_\otimes^T\tilde{\mathbf{F}}\left(\overline{\mathbf{x}}\right),\\ \mathbf{\dot{\tilde{v}}}_{\perp}&=\beta\mathbf{S}_\otimes^T \mathbf{L}_\otimes \mathbf{x}_c,\\ \mathbf{x}_c&=\mathcal{C}\left(\mathbf{x},t\right)-\mathcal{C}\left(\mathbf{1}_\otimes\mathbf{\overline{x}}_{\parallel}+\mathbf{s},t\right), \end{align}\tag{26}\] where 14 , 25 , and \(\mathbf{L}_\otimes\mathcal{C}\left(\mathbf{1}_\otimes\overline{\mathbf{x}}+\mathbf{s},t\right)=\mathbf{0}_{nd}\) are used.

Consider the change of coordinate \(\mathbf{z}:=\frac{1}{\beta}\mathbf{\overline{v}}_{\perp}+\mathbf{\overline{x}}_{\perp}\). System 26 thus can be equivalently transformed into the one under coordinates \(({\overline{\mathbf{x}}}_{\perp}, {\overline{\mathbf{x}}}_{\parallel}, {\mathbf{z}})\), as \[\label{eq:CPD46a464} \begin{align} \mathbf{\dot{\overline{x}}}_{\perp}&=-\mathbf{S}_\otimes^T \mathbf{L}_\otimes \mathbf{x}_c+\beta^2\mathbf{\overline{x}}_{\perp}-\beta^2 \mathbf{z}-\eta\mathbf{S}_\otimes^T \tilde{\mathbf{F}}\left(\overline{\mathbf{x}}\right),\\ \mathbf{\dot{\overline{x}}}_{\parallel}&=-\eta\mathbf{1}_\otimes^T\tilde{\mathbf{F}}\left(\overline{\mathbf{x}}\right),\\ \dot{\mathbf{z}}&=-\beta^2 \mathbf{z}+\beta^2\mathbf{\overline{x}}_{\perp}- \eta\mathbf{S}_\otimes^T \tilde{\mathbf{F}}\left(\overline{\mathbf{x}}\right),\\ \mathbf{x}_c&=\mathcal{C}\left(\mathbf{x},t\right)-\mathcal{C}\left(\mathbf{1}_\otimes\mathbf{\overline{x}}_{\parallel}+\mathbf{s},t\right) . \end{align}\tag{27}\] In the following, the stability of system 27 will be investigated. Let \(V_{1}\left(\mathbf{\overline{x}}_{\perp},\mathbf{z}\right)=\frac{1}{2}\left(\|\mathbf{\overline{x}}_{\perp}\|^2+\|\mathbf{z}\|^2\right)\), whose time derivative is given by \[\label{eq:CPD46a46V1} \begin{align} \dot{V}_{1} &\leq -\mathbf{\overline{x}}_{\perp}^T\mathbf{S}_\otimes\mathbf{L}_\otimes\mathbf{x}_c -\beta^2 \|\mathbf{z}\|^2 +\beta^2 \|\mathbf{\overline{x}}_{\perp}\|^2 \\ &\quad -\eta \mathbf{z}^T\mathbf{S}_\otimes^T \tilde{\mathbf{F}}\left(\overline{\mathbf{x}}\right)-\eta\mathbf{\overline{x}}_{\perp}^T\mathbf{S}_\otimes^T\tilde{\mathbf{F}}\left(\overline{\mathbf{x}}\right)]\\ &\leq L_c\lambda_n\|\mathbf{\overline{x}}_{\perp}\|^2-\left(\beta^2-\frac{\eta}{2}\right) \|\mathbf{z}\|^2 \\ &\quad +\left(\beta^2+\frac{\eta}{2}+{\eta}L_f^2\right) \|\mathbf{\overline{x}}_{\perp}\|^2 +\eta L_f^2\|\mathbf{\overline{x}}_{\parallel}\|^2, \end{align}\tag{28}\] where the second inequality is obtained by using \[\label{eq:Fl} \begin{align} \|\tilde{\mathbf{F}}\left(\overline{\mathbf{x}}\right)\|^2\leq L^2_f\left(\|\mathbf{\overline{x}}_{\perp}\|^2+\|\mathbf{\overline{x}}_{\parallel}\|^2\right)\,, \end{align}\tag{29}\] and the fact \[\label{eq:xc} \begin{align} \|\mathbf{x}_c\|&=\|\mathcal{C}\left(\mathbf{x},t\right)-\mathcal{C}\left(\mathbf{1}_\otimes\mathbf{\overline{x}}_{\parallel}+\mathbf{s},t\right)\|\\ &\leq L_c\|\mathbf{x}-\mathbf{1}_\otimes\mathbf{\overline{x}}_{\parallel}-\mathbf{s}\| \leq L_c\|\mathbf{\overline{x}}_{\perp}\|, \end{align}\tag{30}\] which is derived from P2) of the ST compressor \(\mathbf{C}\).

Let \(V_2\left(\mathbf{\overline{x}}_{\perp},t\right)=\overline{V}_e\left(\mathbf{\overline{x}}_{\perp},t\right)\) with \(V_e\) defined in 6 , whose time derivative is given by \[\label{eq:CPD46a46V2} \begin{align} \dot{V}_2&=\frac{\partial V_2}{\partial t} - \frac{\partial V_2}{\partial \mathbf{\overline{x}}_{\perp}} \Lambda \overline{\mathcal{C}}\left(\mathbf{\overline{x}}_{\perp},t\right)+\frac{\partial V_2}{\partial \mathbf{\overline{x}}_{\perp}}(\Lambda \overline{\mathcal{C}}\left(\mathbf{\overline{x}}_{\perp},t\right)\\ &\quad -\mathbf{S}_\otimes^T\mathbf{L}_\otimes\mathbf{\mathcal{C}}\left(\mathbf{x},t\right))+\frac{\partial V_2}{\partial \mathbf{x}_\perp}\left(\beta^2\mathbf{\overline{x}}_{\perp}-\beta^2 \mathbf{z}-\eta\mathbf{S}_\otimes^T \tilde{\mathbf{F}}\left(\overline{\mathbf{x}}\right)\right)\\ &\leq -\left(c'_3-\overline{c}_4\beta^2-\overline{c}_4\beta^2/r-\overline{c}_4\eta/r-\overline{c}_4\eta L_f^2r\right)\|\mathbf{\overline{x}}_{\perp}\|^2\\ &\quad +\overline{c}_4\beta^2r\|\mathbf{z}\|^2+\overline{c}_{4}\eta rL_f^2\|\mathbf{\overline{x}}_{\parallel}\|^2, \end{align}\tag{31}\] with \(c'_3:=\overline{c}_3-{\overline{c}_4\delta\lambda_n}>0\) by choosing \(\delta<\frac{c_3\lambda_2}{c_4\lambda_n}\), and \(r>0\) to be determined later, where the inequality is obtained by 17 , the fact \(\mathbf{S}_\otimes^T\mathbf{x}=\mathbf{S}_\otimes^T\overline{\mathbf{x}}=\mathbf{\overline{x}}_{\perp}\), 29 and the Young’s Inequality.

Let \(V_{3}\left(\mathbf{\overline{x}}_{\parallel}\right)=\frac{1}{2}\|\mathbf{\overline{x}}_{\parallel}\|^2\). As \(f\left(x\right)\) is \(\mu\)-strongly convex, we have \[\label{eq:CPD46a46V3} \begin{align} \dot{V}_{3} &= -\eta \mathbf{\overline{x}}_{\parallel}^T\mathbf{1}_\otimes^T \tilde{\mathbf{F}}\left(\overline{\mathbf{x}}\right)\\ &=-\eta\mathbf{\overline{x}}_{\parallel}^T\mathbf{1}_\otimes^T[\mathbf{F}\left(\overline{\mathbf{x}}+\mathbf{s}\right)-\mathbf{F}\left(\mathbf{S}_\otimes\mathbf{\overline{x}}_{\perp}+\mathbf{s}\right)\\ &\quad +\mathbf{F}\left(\mathbf{S}_\otimes\mathbf{\overline{x}}_{\perp}+\mathbf{s}\right)-\mathbf{F}\left(\mathbf{s}\right)]\\&\leq -\frac{\eta\mu_n}{2} \|\mathbf{\overline{x}}_{\parallel}\|^2+\frac{\eta}{2\mu_n}L_f^2 \|\mathbf{\overline{x}}_{\perp}\|^2, \end{align}\tag{32}\] where the inequality is obtained by Properties i) and ii) of \(f\left(x\right)\) in Assumption 1 with \(\mu_n:=\frac{\mu}{n}\).

For convenience of subsequent analysis, we introduce some parameters, which are independent of \(\beta\), \(r\) and \(\eta\), as \[\begin{align} &\chi_0=2L_c\lambda_n/c'_3,\quad \chi_1=\frac{4L_f^2}{\mu_n}+\frac{4\chi_0\overline{c}_4L_f^2}{\mu_n},\\ &\xi_1=\frac{3}{2}+L_f^2+\chi_0\left(\overline{c}_4+\overline{c}_4L_f^2\right)+\chi_1\frac{L_f^2}{2\mu_n},\\ &\xi_2=2\chi_0\overline{c}_4,\quad \xi_3=\chi_0\overline{c}_4,\quad \xi_4=\frac{1}{2}. \end{align}\]

In view of the previous analysis and definitions, we choose the Lyapunov function of system 27 as \(V = V_{1}+\chi_0V_{2}+\chi_1V_{3}\), which satisfies \[\begin{align}\label{eq:CPD46a46Vp} V\geq \left(\frac{1}{2}+\chi_0c_1\right)\|\mathbf{\overline{x}}_{\perp}\|^2+\frac{1}{2}\|\mathbf{z}\|^2+ \frac{\chi_1}{2}\|\mathbf{\overline{x}}_{\parallel}\|^2. \end{align}\tag{33}\] Combining 28 , 31 , 32 , and letting \(r\leq1,\eta\leq\beta^2\), we can further derive \[\begin{align} \dot{V}&\leq -\left(\frac{1}{2}\chi_0c'_{3}-\xi_1\beta^2-\xi_2\beta^2/r\right)\|\mathbf{\overline{x}}_{\perp}\|^2 \\ &\quad -\left(\beta^2-\xi_3\beta^2r-\xi_4\eta\right)\|\mathbf{z}\|^2 -\left(\eta \frac{\mu_n}{4}\chi_1\right) \|\mathbf{\overline{x}}_{\parallel}\|^2. \end{align}\] Thus by fixing \(r=\mathrm{min}\left\{\frac{1}{4\xi_3},1\right\}\), \(\beta^2\leq \mathrm{min}\left\{\frac{\chi_0c'_{3}\lambda_2}{8\xi_1}, \frac{\chi_0c'_{3}r}{8\xi_2}\right\}\), \(\eta\leq \mathrm{min}\left\{\beta^2,\frac{\beta^2}{4\xi_4}\right\}\), it can be verified that \(\dot{V}\) is negative definite. With 33 , we have \[\dot{V}\leq -\gamma V,\quad \gamma = \mathrm{min}\left\{\frac{L_c\lambda_n\lambda_2c_3'}{\lambda_2c_3'+4L_c\lambda_n\overline{c}_1},\beta^2,\eta\frac{\mu}{2n}\right\}.\] Therefore, we have \(\|\overline{\mathbf{x}}(t)\|^2=\mathcal{O}\left(e^{-\gamma t}\right)\) by recalling the definition of \(V(t)\). This immediately implies by \(\overline{\mathbf{x}}(t):=\mathbf{x}(t)-\mathbf{s}\) that \(\mathbf{x}_i(t)\) in Flow 8 converges exponentially to the optimal solution \(s^\ast\) with the SST compressor. The proof is completed.

12 Proof of Theorem 4↩︎

As analyzed in Appendix 10, Flow 9 satisfies that for each \(i\in \mathrm{V}\), there holds \({\hat{\mathbf{x}}}^j_i\left(0\right)={\hat{\mathbf{x}}}^{j'}_i\left(0\right),\forall j,j'\in \mathrm{V}\). Then Flow 9 can be written as \[\label{eq:CPD46b461} \begin{align} \dot{\mathbf{x}}&= -\alpha\mathbf{L}_\otimes{\mathbf{x}_c}-\beta \mathbf{v}-\eta \mathbf{F}\left(\mathbf{x}\right), \\ \dot{\mathbf{v}}&={\beta \mathbf{L}_\otimes\mathbf{x}_c},\\\dot{\mathbf{x}}_c&=\mathcal{C}\left(\mathbf{x}-\mathbf{x}_c,t\right). \end{align}\tag{34}\] We carry out a similar proof process by defining \(\mathbf{\overline{x}}_{\parallel}(t)\), \(\mathbf{\overline{x}}_{\perp}(t)\), \(\mathbf{\overline{v}}_{\parallel}(t)\) and \(\mathbf{\overline{v}}_{\perp}(t)\) described in Appendix 11. Consider the change of coordinate \(\mathbf{z}:=\frac{\alpha}{\beta}\mathbf{\overline{v}}_{\perp}+\mathbf{\overline{x}}_{\perp}\), and we yield the following system for \(({\overline{\mathbf{x}}}_{\perp}, {\overline{\mathbf{x}}}_{\parallel}, {\mathbf{z}})\), as \[\label{eq:CPD46b462} \begin{align} \mathbf{\dot{\tilde{x}}}_{\perp}&=-\alpha\mathbf{S}_\otimes^T \mathbf{L}_\otimes \overline{\mathbf{x}}_c+\beta^2_\alpha\mathbf{\overline{x}}_{\perp}-\beta^2_\alpha \mathbf{z}-\eta\mathbf{S}_\otimes^T \tilde{\mathbf{F}}\left(\overline{\mathbf{x}}\right),\\ \mathbf{\dot{\tilde{x}}}_{\parallel}&=-\eta\mathbf{1}_\otimes^T\tilde{\mathbf{F}}\left(\overline{\mathbf{x}}\right),\\ \dot{\mathbf{z}}&=-\beta^2_\alpha \mathbf{z}+\beta^2_\alpha\mathbf{\overline{x}}_{\perp}- \eta\mathbf{S}_\otimes^T \tilde{\mathbf{F}}\left(\overline{\mathbf{x}}\right),\\ \dot{\tilde{\mathbf{x}}}_c&=\mathcal{C}\left(\overline{\mathbf{x}}-\overline{\mathbf{x}}_c,t\right), \end{align}\tag{35}\] where \(\overline{\mathbf{x}}_c:=\mathbf{x}_c-\mathbf{s}\) and \(\beta^2_\alpha:=\beta^2/\alpha\).

In the following, the stability of system 35 will be investigated. Let \(V_{1}\left(\mathbf{\overline{x}}_{\perp},\mathbf{z}\right)=\frac{1}{2}\left(\|\mathbf{\overline{x}}_{\perp}\|^2+\|\mathbf{z}\|^2\right)\), whose time derivative is given by \[\label{eq:CPD46b46V1} \begin{align} \dot{V}_{1} &\leq -\alpha\mathbf{\overline{x}}_{\perp}^T\mathbf{S}_\otimes\mathbf{L}_\otimes\overline{\mathbf{x}}_c -\beta^2_\alpha \|\mathbf{z}\|^2 +\beta^2_\alpha \|\mathbf{\overline{x}}_{\perp}\|^2 \\ &\quad -\eta \mathbf{z}^T\mathbf{S}_\otimes^T \tilde{\mathbf{F}}\left(\overline{\mathbf{x}}\right)-\eta\mathbf{\overline{x}}_{\perp}^T\mathbf{S}_\otimes^T\tilde{\mathbf{F}}\left(\overline{\mathbf{x}}\right)]\\ &\leq -\frac{\alpha\lambda_2}{2}\|\mathbf{\overline{x}}_{\perp}\|^2-\left(\beta^2_\alpha-\frac{\eta}{2}\right) \|\mathbf{z}\|^2 \\ &\quad +\left(\beta^2_\alpha+\frac{\eta}{2}+{\eta}L_f^2\right) \|\mathbf{\overline{x}}_{\perp}\|^2 +\eta L_f^2\|\mathbf{\overline{x}}_{\parallel}\|^2\\ &\quad +\frac{\alpha\lambda_n}{2}\|\overline{\mathbf{x}}-\overline{\mathbf{x}}_c\|^2, \end{align}\tag{36}\] where the second inequality is obtained by the fact \[\label{eq:xSLx} \begin{align} -\mathbf{\overline{x}}_{\perp}^T\mathbf{S}_\otimes^T\mathbf{L}_\otimes \overline{\mathbf{x}}_c&\leq -\frac{1}{2}\lambda_2\left(\|\mathbf{\overline{x}}_{\perp}\|^2\right)+\frac{1}{2}\lambda_n\left(\|\overline{\mathbf{x}}-\overline{\mathbf{x}}_c\|^2\right). \end{align}\tag{37}\] For \(V_2\left(\overline{\mathbf{x}}-\overline{\mathbf{x}}_c,t\right)=V_2\left(\mathbf{x}-\mathbf{x}_c,t\right):=\sum_{i=1}^n V_e\left(\mathbf{x}_i-\mathbf{x}_{i,c}, t\right)\), which is defined in 3 , we have \[\label{eq:CPD46b46V2} \begin{align} \dot{V}_{2} &\leq-c_3\|\overline{\mathbf{x}}-\overline{\mathbf{x}}_c\|^2 + c_4\sqrt{n}\|\overline{\mathbf{x}}-\overline{\mathbf{x}}_c\|\|\alpha \mathbf{L}_\otimes\overline{\mathbf{x}}_c\\ &\quad +\beta^2_\alpha \mathbf{S}_\otimes\mathbf{z}_{k}-\beta_\alpha^2\mathbf{S}_\otimes\mathbf{\overline{x}}_{\perp}+\eta \tilde{\mathbf{F}}\left(\overline{\mathbf{x}}\right)\| \\ &\leq-\left[ c_3- c_4\sqrt{n}\left( \frac{ \alpha}{r}+\frac{2 \beta_\alpha^2}{r}+\frac{\eta}{r}+2 \alpha r\lambda_n^2 \right)\right]\|\overline{\mathbf{x}}-\overline{\mathbf{x}}_c\|^2 \\ &\quad +c_4\sqrt{n} \beta^2_\alpha r\|\mathbf{z}\|^2+\left(2c_4\sqrt{n} \alpha r\lambda_n^2+c_4\beta^2_\alpha r\right)\|\mathbf{\overline{x}}_{\perp}\|^2\\ &\quad +c_4\sqrt{n} \eta rL_f^2\|\mathbf{\overline{x}}_{\perp}\|^2+c_4\sqrt{n} \eta rL_f^2\|\mathbf{\overline{x}}_{\parallel}\|^2, \end{align}\tag{38}\] where \(r>0\) is a parameter to be determined later, the first inequality is obtained by \(\overline{\mathbf{v}}=\mathbf{S}_\otimes\mathbf{\overline{v}}_{\perp}\) and 3 , and the last inequality is obtained by 29 , the fact \[\label{eq:CPD46b46fact} \begin{align} \mathbf{x}_c^T{\mathbf{L}^2_\otimes}\mathbf{x}_c&\leq2\lambda_n^2\|\overline{\mathbf{x}}-\overline{\mathbf{x}}_c\|^2 + 2\lambda_n^2\|\mathbf{\overline{x}}_{\perp}\|^2, \end{align}\tag{39}\] and the Young’s Inequality.

For convenience of subsequent analysis, let us introduce some positive parameters, independent of \(\alpha\), \(\beta\), \(r\) and \(\eta\), as \[\begin{align} &\quad \chi_1=\frac{4L_f^2}{\mu_n}+\frac{4c_4\sqrt{n}L_f^2}{\mu_n},\quad\xi_1=\frac{\lambda_2}{2},\\ &\quad \xi_2=\frac{3}{2}+L_f^2+c_4\sqrt{n}+c_4\sqrt{n}L_f^2+\chi_1\frac{L_f^2}{2\mu_n},\\ &\quad \xi_3=2c_4\sqrt{n} \lambda_n^2,\quad \xi_4=\frac{1}{2},\quad \xi_5=c_4\sqrt{n},\\&\quad \xi_6=4c_4\sqrt{n},\quad \xi_7=\frac{\lambda_n}{2}+2c_4\sqrt{n}\lambda_n^2. \end{align}\]

In view of the previous analysis and definitions, we choose the Lyapunov functions of system 35 as \(V: = V_{1}+V_{2}+\chi_1V_{3}\) with \(V_3\) defined in Appendix 11 and satisfying 32 . Then we have \[\begin{align}\label{eq:CPD46b46Vp} V\geq \frac{1}{2}\|\mathbf{\overline{x}}_{\perp}\|^2+\frac{1}{2}\|\mathbf{z}\|^2+ \frac{\chi_1}{2}\|\mathbf{\overline{x}}_{\parallel}\|^2+c_1\|\overline{\mathbf{x}}-\overline{\mathbf{x}}_c\|. \end{align}\tag{40}\] Combining 36 , 38 , 32 , and letting \(r\leq1,\beta\leq\alpha,\eta\leq\beta^2_\alpha\), we can derive \[\begin{align} \dot{V}&\leq -(\xi_{1} \alpha -\xi_{2} \beta_\alpha^2 - \xi_3 \alpha r)\|\mathbf{\overline{x}}_{\perp}\|^2 -(\beta^2_\alpha-\xi_4 \eta-\xi_5 \beta^2_\alpha r)\|\mathbf{z}\|^2\\ &\quad-(\eta \frac{\mu_n}{4}\chi_1) \|\mathbf{\overline{x}}_{\parallel}\|^2-(c_3-\xi_6 \alpha/r - \xi_7 \alpha)\|\overline{\mathbf{x}}-\overline{\mathbf{x}}_c\|^2. \end{align}\] It can be noticed that \(\dot{V}\) is negative definite when we choose \(r=\mathrm{min}\left\{\frac{\xi_1}{4\xi_3},\frac{1}{4\xi_5},1\right\}\), \(\alpha\leq \mathrm{min}\left\{\frac{c_3r}{4\xi_6}, \frac{c_3}{4\xi_7}\right\}\), \(\beta^2\leq \mathrm{min}\left\{{\alpha^2},\frac{\xi_1\alpha^2}{4\xi_2}\right\}\), \(\eta\leq \mathrm{min}\left\{\beta_\alpha^2,\frac{1}{4\xi_4}\right\}\). With 40 , we have \[\dot{V}\leq -\gamma V,\quad \gamma = \mathrm{min}\left\{\frac{\lambda_2\alpha}{2},\frac{\beta^2}{\alpha},\eta\frac{\mu}{2n},\frac{c_3}{2c_1}\right\}.\] This yields \(\|\overline{\mathbf{x}}(t)\|^2=\mathcal{O}\left(e^{-\gamma t}\right)\) by the definition of \(V(t)\). With the definition \(\overline{\mathbf{x}}(t)=\mathbf{x}(t)-\mathbf{s}\) before, we know that \(\mathbf{x}_i(t)\) in Flow 9 converges exponentially to the optimal solution \(s^\ast\) with the ST compressor. The proof is completed.

13 Proof of Proposition 2↩︎

Proof of a). By recalling [40], it can be proved that \({\mathbf{x}}_e\left(t+1\right)=\mathbf{x}_e(t)-\kappa_0\boldsymbol{\psi}(t)\boldsymbol{\psi}(t)^T\mathbf{x}_e(t)\) is UGLS at the zero equilibrium for any \(\kappa_0\leq \kappa_0^\ast\) with some \(\kappa_0^\ast>0\) under the condition in discrete-time cases. The remaining proof is similar to that in Proposition 1.a) and is omitted here.

Proof of b). Next, we prove that \(\mathbf{C}_2\) is the ST compressor in discrete time by proving the system \(\mathbf{x}_e\left(t+1\right)=\mathbf{x}_e(t)-\kappa_0\mathbf{C}_2\left(\mathbf{x}_e(t)\right)\) is UGLS at the zero equilibrium with \(\kappa_0=\frac{1}{p}\). By 11 , there holds \[\begin{align} &\quad\|\mathbf{x}_e\left(t+1\right)\|^2-\|\mathbf{x}_e(t)\|^2\\&=-\frac{2\mathbf{C}_2\left(\mathbf{x}_e(t)\right)^T\mathbf{x}_e(t)}{p}+\left\|\frac{\mathbf{C}_2\left(\mathbf{x}_e(t)\right)}{p}\right\|^2\leq -\varphi\|\mathbf{x}_e(t)\|^2. \end{align}\] Thus \(\mathbf{x}_e\)-system is UGLS at the zero equilibrium with \(\varphi\in(0,1]\). With 12 , the proof is complete.

Proof of c). Finally, we prove that \(\mathbf{C}_3\) is the ST compressor in discrete time by proving the system \(\mathbf{x}_e\left(t+1\right)=\mathbf{x}_e(t)-\kappa_0\gamma_e^t\left\lfloor\frac{\mathbf{x}_e}{\gamma_e^t}\right\rfloor\) is UGLS at the zero equilibrium with \(\kappa_0=1\). We let \(\mathbf{z}_e(t):=\frac{\mathbf{x}_e(t)}{\gamma^t_e}\), then we have \[\begin{align} \mathbf{z}_e\left(t+1\right)-\mathbf{z}_e(t)&=-\frac{\left\lfloor\mathbf{z}_e(t)\right\rfloor}{\gamma_e}+\frac{1-\gamma_e}{\gamma_e}\mathbf{z}_e(t) \\ \Rightarrow \mathbf{z}_e\left(t+1\right)&= \frac{1-\gamma_e}{\gamma_e}(\mathbf{z}_e(t)-\left\lfloor\mathbf{z}_e(t)\right\rfloor), \end{align}\] which leads to \(\|\mathbf{z}_e(t)\|\leq \frac{1-\gamma_e}{\gamma_e}\sqrt{d}\) for any \(t\geq0\). The remaining proof is the same as that in Proposition 1.c) and we complete the proof.

14 Proof for Theorem 5↩︎

Referring to the continuous-time flow in Appendix 11, DPD-DC can be written in a compact form with the same equilibrium point as system 23 . Then we introduce the state error by defining \(\overline{\mathbf{x}}:=\mathbf{x}-\mathbf{s}\), \(\overline{\mathbf{v}}:=\mathbf{v}+\frac{\eta \mathbf{F}\left(\mathbf{s}\right)}{\beta}\), and decompose \(\overline{\mathbf{x}}\) and \(\overline{\mathbf{v}}\) by defining \(\mathbf{\overline{x}}_{\perp}:=\mathbf{S}_\otimes^T\overline{\mathbf{x}}\), \(\mathbf{\overline{x}}_{\parallel}:=\mathbf{1}_\otimes^T\overline{\mathbf{x}}\), \(\mathbf{\overline{v}}_{\perp}:=\mathbf{S}_\otimes^T\overline{\mathbf{v}}\) and \(\mathbf{\overline{v}}_{\parallel}:=\mathbf{1}_\otimes^T\overline{\mathbf{v}}\). The convergence of \(\overline{\mathbf{x}}(t)\) and \(\overline{\mathbf{v}}(t)\) follows by proving \(\mathbf{\overline{x}}_{\parallel}(t)\), \(\mathbf{\overline{x}}_{\perp}(t)\), \(\mathbf{\overline{v}}_{\parallel}(t)\) and \(\mathbf{\overline{v}}_{\perp}(t)\) converge to the zero equilibrium. In addition, we can conclude that 25 holds.

Consider \(\mathbf{z}:=\frac{1}{\beta}\mathbf{\overline{v}}_{\perp}+\mathbf{\overline{x}}_{\perp}\), then DPD-DC is equal to the following system for \(({\overline{\mathbf{x}}}_{\perp}, {\overline{\mathbf{x}}}_{\parallel}, {\mathbf{z}})\), as \[\label{eq:DPD46a463} \begin{align} \mathbf{{\overline{x}}}_{\perp}\left(t+1\right)&=\mathbf{{\overline{x}}}_{\perp}(t)-\kappa_0\mathbf{S}_\otimes^T \mathbf{L}_\otimes \mathbf{x}_c(t)\\ &\quad +\kappa[\beta^2\mathbf{\overline{x}}_{\perp}(t)-\beta^2 \mathbf{z}(t) -\eta\mathbf{S}_\otimes^T \tilde{\mathbf{F}}\left(\overline{\mathbf{x}}(t)\right)],\\ \mathbf{{\overline{x}}}_{\parallel}\left(t+1\right)&=\mathbf{{\overline{x}}}_{\parallel}(t)-\kappa\eta\mathbf{1}_\otimes^T\tilde{\mathbf{F}}\left(\overline{\mathbf{x}}(t)\right),\\ {\mathbf{z}\left(t+1\right)}&=\mathbf{z}(t)+\kappa[-\beta^2 \mathbf{z}(t) +\beta^2\mathbf{\overline{x}}_{\perp}(t)- \eta\mathbf{S}_\otimes^T \tilde{\mathbf{F}}\left(\overline{\mathbf{x}}(t)\right)],\\ \mathbf{x}_c(t)&=\mathcal{C}\left(\mathbf{x}(t),t\right)-\mathcal{C}\left(\mathbf{1}_\otimes\mathbf{\overline{x}}_{\parallel}(t)+\mathbf{s},t\right) . \end{align}.\tag{41}\]

In the following, we investigate the stability of system 41 . Let \(V_{1,t}\left(\mathbf{\overline{x}}_{\perp},\mathbf{z}\right)=\frac{1}{2}\left(\|\mathbf{\overline{x}}_{\perp}\|^2+\|\mathbf{z}\|^2\right)\), whose difference is given by \[\label{eq:DPD46a46V1} \begin{align} \Delta{V}_{1,t} &\leq \left(L_c\lambda_n\kappa_0+2L_c^2\lambda^2_n\kappa_0^2\right)\|\mathbf{\overline{x}}_{\perp}\|^2\\ &\quad +\kappa[-\left(\beta^2-\frac{\eta}{2}\right) \|\mathbf{z}\|^2 +\left(\beta^2+\frac{\eta}{2}+{\eta}L_f^2\right) \|\mathbf{\overline{x}}_{\perp}\|^2 \\&\quad +\eta L_f^2\|\mathbf{\overline{x}}_{\parallel}\|^2]+\frac{1}{2}\kappa^2[\left(7\eta^2L_f^2+7\beta^4\right)\|\mathbf{\overline{x}}_{\perp}\|^2\\&\quad +7\beta^4\|\mathbf{z}\|^2+7\eta^2L_f^2\|\mathbf{\overline{x}}_{\parallel}\|^2], \end{align}\tag{42}\] where the inequality is obtained by 29 and 30 .

Before we introduce the second Lyapunov function, we will show that the following system, \[\label{eq:DPD46aux} \begin{align} {\mathbf{y}}_{e}\left(t+1\right)=\mathbf{y}_{e}(t)-\kappa_0\mathbf{S}_\otimes^T\mathbf{L}_\otimes\mathbf{\mathcal{C}}\left(\mathbf{x}_{e}(t),t\right), \end{align}\tag{43}\] where \(\mathbf{y}_e\in\mathbb{R}^{\left(n-1\right)d}\), \(\mathbf{x}_e\in\mathbb{R}^{nd}\) and \({\mathbf{y}}_{e}=\mathbf{S}_\otimes^T{\mathbf{x}}_{e}\), achieves UGLS at the zero equilibrium for some \(\kappa_0,\delta\).

By P1’) of \(\mathbf{C}\left(\mathbf{x}_e,t\right)\), it is easy to find the following system achieves UGLS at the zero equilibrium if \(\kappa_0\leq\kappa_0^\ast/\min\{\lambda_n,1\}\), \[\begin{align} {\mathbf{y}}_{e}\left(t+1\right)=\mathbf{y}_{e}(t)-\kappa_0\Lambda \overline{\mathcal{C}}\left(\mathbf{y}_{e}(t),t\right). \end{align}\] Then there exist positive constants \(C\), \(\gamma_D<1\) such that for any \(t\) and \(N\in\mathbb{N}_+\), the solution satisfies \[\left(\|\mathbf{y}_{e}\left(t+N\right)\|^2\right)\leq C\left(\|\mathbf{y}_{e}(t)\|^2\right)\gamma_D^N.\] We assume \(\phi_t^{t+T}\left(\mathbf{y}_{e}(t)\right)\) is the state of the system \(\mathbf{y}_{e}\left(t+1\right)=\mathbf{y}_{e}(t)-\kappa_0\Lambda \overline{\mathcal{C}}\left(\mathbf{y}_{e}(t),t\right)\) in \(t+T\) moment for any \(0\leq T\leq N\) with the state in \(t\) moment is \(\mathbf{y}_{e}(t)\). It is easy to verify that there exists some \(L_\phi>0\) that \(\|\phi_t^{t+T}\left(\mathbf{y}\right)\|^2\leq L_\phi \|\mathbf{y}\|^2\) holds for any \(\mathbf{y}\in\mathbb{R}^{\left(n-1\right)d}\) and \(0\leq T\leq N\) by P2’) of the compressor \(\mathbf{C}\).

We define a Lyapunov function \(V_{e,t}\left(\mathbf{y}_e,t\right):=\sum_{j=0}^{N-1}\|\phi_t^{t+j}\left(\mathbf{y}_e\right)\|^2\) satisfying \[\label{eq:DPD46a46Ve} \begin{align}&\quad c_{1}\|\mathbf{y}_{e}\|^2\leq V_{e,t}\leq c_{2}\|\mathbf{y}_e\|^2 \end{align}\tag{44}\] for \(c_{1}=1,c_{2}=NL_\phi\).

In addition, we have \[\label{eq:V95e1} \begin{align} \Delta V_{e,t}&=\sum_{j=1}^{N}\|\phi_{t+1}^{t+j}\left(\mathbf{y}_{e}\left(t+1\right)\right)\|^2-\sum_{j=0}^{N-1}\|\phi_t^{t+j}\left(\mathbf{y}_e(t)\right)\|^2\\ &=\|\mathbf{y}_{e}\left(t+N\right)\|^2-\|\mathbf{y}_e(t)\|^2\\ &\leq -\left(1-C\gamma_D^{N}\right)\|\mathbf{y}_e(t)\|^2 \leq -c_3\lambda_2\hat{\kappa}\|\mathbf{y}_e(t)\|^2 \end{align}\tag{45}\] for \(\hat{\kappa}:=\frac{\kappa_0}{\kappa_0^\ast}\leq\min\{\frac{1}{\lambda_n},1\}\). Notably, for convenience in the subsequent analysis and to highlight the effect of \(\Lambda\), we use \(c_3\lambda_2\), instead of a single parameter, in the middle inequality of 45 .

We choose a \(N\in\mathbb{N}_+\) large enough and then \(c_{3}:=\frac{1-C\gamma_D^{N}}{\lambda_2\hat{\kappa}}>0\), i.e., \[\begin{align} \label{eq:DPD46a46Vec3} &\quad \sum_{j=1}^{N}\|\phi_{t+1}^{t+j}\left(\mathbf{y}_e-\hat{\kappa}\Lambda \overline{\mathcal{C}}\left(\mathbf{y}_e,t\right)\right)\|^2-\sum_{j=0}^{N-1}\|\phi_t^{t+j}\left(\mathbf{y}_e\right)\|^2\\&\leq -c_{3}\lambda_2\hat{\kappa}\|\mathbf{y}_e\|^2. \end{align}\tag{46}\] In addition, we have \[\begin{align}\label{eq:DPD46a46fact1} \|\mathbf{y}_e-\kappa_0\Lambda \overline{\mathcal{C}}\left(\mathbf{y}_e,t\right)\|^2\leq \theta\|\mathbf{y}_e\|^2, \end{align}\tag{47}\] for \(\theta:=2+2 L_c^2\kappa_0^2\lambda_n^2>0\) by P2’) of \(\mathbf{C}\).

For system 43 , we use the Lyapunov function \(V_{e,t}\left(\mathbf{y}_e,t\right)\) and obtain the difference of it, as \[\begin{align}\label{eq:DPD46a46Ve39} &\quad \sum_{j=1}^{N}\|\phi_{t+1}^{t+j}\left(\mathbf{y}_e-\kappa_0\mathbf{S}_\otimes^T\mathbf{L}_\otimes\mathbf{\mathcal{C}}\left(\mathbf{x}_e(t),t\right)\right)\|^2 -\sum_{j=0}^{N-1}\|\phi_t^{t+j}\left(\mathbf{y}_e\right)\|^2\\&\leq -c_{3}\lambda_2\hat{\kappa}\|\mathbf{y}_e\|^2+c_4\kappa_0^2\lambda_n^2\|\overline{\mathcal{C}}\left(\mathbf{S}_\otimes^T\mathbf{x}_e(t),t\right)-\mathbf{S}_\otimes^T\mathcal{C}\left(\mathbf{x}_e(t),t\right)\|^2\\&\quad +2c_4\kappa_0\lambda_n\|\mathbf{y}_e\|\|\overline{\mathcal{C}}\left(\mathbf{S}_\otimes^T\mathbf{x}_e(t),t\right)-\mathbf{S}_\otimes^T\mathcal{C}\left(\mathbf{x}_e(t),t\right)\|\\&\leq-\left(c_3\lambda_2\hat{\kappa}-2c_4\kappa_0\lambda_n\delta-c_4\kappa_0^2\lambda_n^2\delta^2\right)\|\mathbf{y}_e\|^2 \end{align}\tag{48}\] for \(c_{4}:=NL_\phi\theta\), where the first inequality is obtained by 46 and the second inequality is obtained by ?? . It is obvious that for \(0<\delta<\frac{c_4+\sqrt{c_4^2+c_3\lambda_2c_4\hat{\kappa}}}{c_4\kappa_0\lambda_n}\), the difference of \(V_e\left(\mathbf{y}_e,t\right)\) is negative definite with \(c_3':=c_3-\frac{2c_4\kappa_0\lambda_n\delta-c_4\kappa_0^2\lambda_n^2\delta^2}{\lambda_2\hat{\kappa}}>0\). Thus system 43 achieves UGLS at the zero equilibrium.

Next we continue to choose the Lyapunov function for system 41 by letting \(V_{2,t}(\mathbf{\overline{x}}_{\perp},t)=V_e\left(\mathbf{\overline{x}}_{\perp},t\right)\), then we have \[\begin{align}\label{eq:DPD46a46V2} \Delta V_{2,t} &= \sum_{j=1}^{N}\|\phi_{t+1}^{t+j} \left(\mathbf{\overline{x}}_{\perp}\left(t+1\right)\right) \|^2-\sum_{j=0}^{N-1}\|\phi_t^{t+j}\left(\mathbf{\overline{x}}_{\perp}(t)\right)\|^2\\ &\leq -\left(\hat{\kappa}\lambda_2c'_{3}-\kappa c_4 \left(\beta^2- \frac{\beta^2}{r}- \frac{\eta}{r}-\eta rL_f^2\right)\right)\|\mathbf{\overline{x}}_{\perp}\|^2\\&\quad+ \kappa\big(c_{4}\beta^2 r\|\mathbf{z}\|^2+c_{4}\eta rL_f^2\|\mathbf{\overline{x}}_{\parallel}\|^2\big) \\ &\quad +\kappa^2NL_\phi\big(\left(3\beta^4+3\eta^2L_f^2\right)\|\mathbf{\overline{x}}_{\perp}\|^2\\ &\quad +3\beta^4\|\mathbf{z}\|^2+3\eta^2L_f^2\|\mathbf{\overline{x}}_{\parallel}\|^2\big), \end{align}\tag{49}\] where \(r>0\) is a parameter to be determined later, and the inequality is obtained by 47 , 48 , 29 and the Young’s Inequality.

Let \(V_{3,t}\left(\mathbf{\overline{x}}_{\parallel}\right)=\frac{1}{2}\|\mathbf{\overline{x}}_{\parallel}\|^2\). With 32 in mind, we have \[\label{eq:DPD46a46V3} \begin{align} \Delta V_{3,t}&=\frac{1}{2}\left(\mathbf{\overline{x}}_{\parallel}-\kappa\eta\mathbf{1}_\otimes^T \tilde{\mathbf{F}}\left(\overline{\mathbf{x}}\right)\right)^T\left(\mathbf{\overline{x}}_{\parallel}-\kappa\eta\mathbf{1}_\otimes^T \tilde{\mathbf{F}}\left(\overline{\mathbf{x}}\right)\right)-\frac{1}{2}\mathbf{\overline{x}}_{\parallel}^T\mathbf{\overline{x}}_{\parallel}\\ &\leq \kappa \left(-\eta\frac{\mu_n}{2} \|\mathbf{\overline{x}}_{\parallel}\|^2+\eta\frac{1}{2\mu_n}L_f^2 \|\mathbf{\overline{x}}_{\perp}\|^2 \right)\\ &\quad +\frac{1}{2}\kappa^2\eta^2L_f^2\left(\|\mathbf{\overline{x}}_{\perp}\|^2+\|\mathbf{\overline{x}}_{\parallel}\|^2\right), \end{align}\tag{50}\] where the equality is obtained by 29 and 32 .

For convenience of subsequent analysis, let us introduce some parameters \(\chi_0\), \(\chi_1\), \(\xi_1\), \(\xi_2,\dots>0\), which are independent of \(\beta\), \(r\) and \(\eta\), and some parameters \(\zeta_1\), \(\zeta_2,\dots>0\), as \[\begin{align} &\quad \chi_0=\left(2L_c\lambda_n\kappa_0+4L_c^2\lambda_n^2\kappa_0^2\right)/\lambda_2c'_3\hat{\kappa},\\&\quad \chi_1=\frac{4L_f^2}{\mu_n}+\frac{4\chi_0c_4L_f^2}{\mu_n},\\ &\quad \xi_1=\frac{3}{2}+L_f^2+\chi_0\left(c_4+c_4L_f^2\right)+\chi_1\frac{L_f^2}{2\mu_n},\\ &\quad \xi_2=2\chi_0c_4,\quad \xi_3=\chi_0c_4,\quad \xi_4=\frac{1}{2},\\ &\quad \zeta_1=\frac{7}{2}\eta^2L_f^2+\frac{7}{2}\beta^4+\chi_0NL_\phi\left(3\beta^4+3\eta^2L_f^2\right)+\frac{1}{2}\chi_1\eta^2L_f^2,\\ &\quad \zeta_2=\frac{7}{2}\beta^4+3\chi_0NL_\phi\beta^4,\\ &\quad \zeta_3=\frac{7}{2}\eta^2L_f^2+3\eta^2\chi_0NL_\phi L_f^2+\frac{1}{2}\eta^2\chi_1L_f^2. \end{align}\]

In view of the previous analysis and definitions, we choose the Lyapunov functions of system 41 as \(V_t: = V_{1,t}+\chi_0V_{2,t}+\chi_1V_{3,t}\), which satisfies \[\begin{align}\label{eq:DPD46a46Vp} V_t\geq \left(\frac{1}{2}+\chi_0c_1\right)\|\mathbf{\overline{x}}_{\perp}\|^2+\frac{1}{2}\|\mathbf{z}\|^2+\frac{\chi_1}{2} \|\mathbf{\overline{x}}_{\parallel}\|^2. \end{align}\tag{51}\] Combining 42 , 49 , 50 , and letting \(r\leq1\), \(\eta\leq\beta^2\), \(\kappa\leq1\), we have \[\begin{align} \Delta V_t&\leq -(\frac{1}{2}\chi_0c'_{3}-\kappa(\xi_1\beta^2+\xi_2\beta^2/r)-\kappa^2\zeta_1)\|\mathbf{\overline{x}}_{\perp}\|^2 \\ &\quad-(\kappa(\beta^2-\xi_3\beta^2r-\xi_4\eta)-\kappa^2\zeta_2)\|\mathbf{z}\|_P^2\\ &\quad-(\kappa\eta \frac{\mu_n}{4}\chi_1-\kappa^2\zeta_3) \|\mathbf{\overline{x}}_{\parallel}\|^2. \end{align}\] It can be noted that \(\Delta V_t\) is negative definite when we choose \(r=\mathrm{min}\left\{\frac{1}{4\xi_3},1\right\}\), \(\beta^2\leq \mathrm{min}\left\{\frac{\chi_0c'_{3}\lambda_2\hat{\kappa}}{8\xi_1}, \frac{\chi_0c'_{3}r}{8\xi_2}\right\}\), \(\eta\leq \mathrm{min}\left\{\beta^2,\frac{\beta^2}{4\xi_4}\right\}\) and \(\kappa\leq \kappa_1:=\frac{1}{2}\mathrm{min}\left\{\frac{\chi_0c'_{3}\lambda_2\hat{\kappa}}{4\zeta_1},\frac{\beta^2}{2\zeta_2},\eta\frac{\mu_n\chi_1}{4\zeta_3},1\right\}\). With 51 in mind, we have \[\label{eq:rate95dc} \begin{align} \Delta V_t \leq -\gamma V_t,\;\gamma =\frac{1}{2} \kappa\mathrm{min}\left\{\frac{L_c\lambda_nc_3'\lambda_2\kappa_0}{\lambda_2c_3'+4L_c\lambda_nc_1\kappa^\ast_0},\beta^2,\eta\frac{\mu}{2n}\right\}. \end{align}\tag{52}\] Let \(\kappa_2:=2/\mathrm{min}\left\{\frac{\chi_0\lambda_2c'_3\hat{\kappa}}{2\left(1+2\chi_0c_1\right)},\beta^2,\eta\frac{\mu_n}{2}\right\}\). When \(\kappa\leq\mathrm{min}\left\{\kappa_1,\kappa_2\right\}\), we can derive for some \(\gamma\in\left(0,1\right)\) , \(V_t=\mathcal{O}\left(\left(1-\gamma\right)^t\right)\). It can be derived that \(\|\overline{\mathbf{x}}(t)\|^2=\mathcal{O}\left(\left(1-\gamma\right)^t\right)\) by the definition of \(V_t\). This implies by the definition \(\overline{\mathbf{x}}(t)=\mathbf{x}(t)-\mathbf{s}\) that \(\mathbf{x}_i(t)\) in DPD-OC converges linearly to the optimal solution \(s^\ast\) with the SST compressor. The proof is completed.

15 Proof of Theorem 6↩︎

Using the same definitions of \(\mathbf{\overline{x}}_{\parallel}(t)\), \(\mathbf{\overline{x}}_{\perp}(t)\), \(\mathbf{\overline{v}}_{\parallel}(t)\) and \(\mathbf{\overline{v}}_{\perp}(t)\) in Appendix 14, with system 35 in mind, we know DPD-OC is equal to the following system, as \[\label{eq:DPD46b461} \begin{align} \mathbf{{\overline{x}}}_{\perp}\left(t+1\right)&=\mathbf{{\overline{x}}}_{\perp}(t)-\kappa\mathbf{S}_\otimes^T\mathbf{L}_\otimes\overline{\mathbf{x}}_c(t)\\ &\quad +\kappa[\beta^2\mathbf{\overline{x}}_{\perp}(t)-\beta^2 \mathbf{z}(t) -\eta\mathbf{S}_\otimes^T \tilde{\mathbf{F}}\left(\overline{\mathbf{x}}(t)\right)],\\ \mathbf{{\overline{x}}}_{\parallel}\left(t+1\right)&=\mathbf{{\overline{x}}}_{\parallel}(t)-\kappa\eta\mathbf{1}_\otimes^T\tilde{\mathbf{F}}\left(\overline{\mathbf{x}}(t)\right),\\ {\mathbf{z}\left(t+1\right)}&=\mathbf{z}(t)+\kappa[-\beta^2 \mathbf{z}(t)+\beta^2\mathbf{\overline{x}}_{\perp}(t)- \eta\mathbf{S}_\otimes^T \tilde{\mathbf{F}}\left(\overline{\mathbf{x}}(t)\right)],\\\overline{\mathbf{x}}_c\left(t+1\right)&=\overline{\mathbf{x}}_c(t)+\kappa_0\mathcal{C}\left(\overline{\mathbf{x}}(t)-\overline{\mathbf{x}}_c(t),t\right). \end{align}\tag{53}\]

Next, we will introduce some Lyapunov functions for system 53 . Let \(V_{1,t}\left(\mathbf{\overline{x}}_{\perp},\mathbf{z}\right)=\frac{1}{2}\left(\|\mathbf{\overline{x}}_{\perp}\|^2+\|\mathbf{z}\|^2\right)\), then we have \[\label{eq:DPD46b46V1} \begin{align} \Delta{V}_{1,t} &\leq \kappa\frac{1}{2}\lambda_n\|\overline{\mathbf{x}}-\overline{\mathbf{x}}_c\|^2+2\kappa^2\lambda_n^2\|\overline{\mathbf{x}}_c\|^2 +\kappa[-\left(\beta^2-\frac{\eta}{2}\right) \|\mathbf{z}\|^2 \\ &\quad +\left(-\frac{1}{2}\lambda_2+\beta^2+\frac{\eta}{2}+{\eta}L_f^2\right) \|\mathbf{\overline{x}}_{\perp}\|^2 +\eta L_f^2\|\mathbf{\overline{x}}_{\parallel}\|^2]\\ &\quad +\frac{7}{2}\kappa^2[\left(\eta^2L_f^2+\beta^4\right)\|\mathbf{\overline{x}}_{\perp}\|^2+\beta^4\|\mathbf{z}\|^2+\eta^2L_f^2\|\mathbf{\overline{x}}_{\parallel}\|^2], \end{align}\tag{54}\] where the inequality is obtained by 29 and 37 .

We conduct the following analysis to obtain the second Lyapunov function. Now that \(\mathbf{x}_e\left(t+1\right)-\mathbf{x}_e(t)=-\kappa_0\mathbf{C}\left(\mathbf{x}_e(t),t\right)\), where \(\mathbf{x}_e\in\mathbb{R}^{d}\), achieves UGLS at the zero equilibrium by P1’) of the compressor \(\mathbf{C}_1\), then we know \(\mathbf{y}_e\left(t+1\right)-\mathbf{y}_e(t)=-\kappa_0\mathcal{C}\left(\mathbf{y}_e(t),t\right)\), where \(\mathbf{y}_e\in\mathbb{R}^{nd}\), also achieves UGLS at the zero equilibrium. A function \(V_{e,t}\left(\mathbf{y}_e,t\right)=\sum_{j=0}^{N-1}\|\phi_t^{t+j}\left(\mathbf{y}_e\right)\|^2\) with same definition process as that in Appendix 14 can be obtained, which satisfies \[\label{eq:DPD46b46Ve} \begin{align} &\quad c_{1}\|\mathbf{y}_e\|^2\leq V_{e,t}\leq c_{2}\|\mathbf{y}_e\|^2,\\ &\quad \sum_{j=1}^{N}\|\phi_{t+1}^{t+j}\left(\mathbf{y}_e-\kappa_0\mathcal{C}\left(\mathbf{y}_e,t\right)\right)\|^2-\sum_{j=0}^{N-1}\|\phi_t^{t+j}\left(\mathbf{y}_e\right)\|^2\\&\leq -c_{3}\|\mathbf{y}_e\|^2\\ \end{align}\tag{55}\] for \(c_{1}=1,c_{2}=NL_\phi,c_{3}>0\). As \(V_{e,t}\geq0\), we have \[\label{eq:c3c1} c_3\leq c_1\tag{56}\] In addition, \[\begin{align}\label{eq:DPD46b46fact1} \|\overline{\mathbf{x}}-\overline{\mathbf{x}}_c+\kappa_0\mathcal{C}\left(\overline{\mathbf{x}}-\overline{\mathbf{x}}_c,t\right)\|^2\leq \theta\|\overline{\mathbf{x}}-\overline{\mathbf{x}}_c\|^2 \end{align}\tag{57}\] for \(\theta=2+2 L_c^2\kappa_0^2>0\) by P2’) of \(\mathbf{C}\). Moreover, we can conclude that 39 holds.

Next we continue to choose the Lyapunov function by letting \(V_{2,t}\left(\overline{\mathbf{x}}-\overline{\mathbf{x}}_c,t\right)= V_{e,t}\left(\overline{\mathbf{x}}-\overline{\mathbf{x}}_c,t\right)\), and we can derive \[\label{eq:DPD46b46V2} \begin{align} \Delta V_{2,t} &= \sum_{j=1}^{N}\|\phi_{t+1}^{t+j}\left(\overline{\mathbf{x}}\left(t+1\right)-\overline{\mathbf{x}}_c\left(t+1\right)\right)\|^2\\ &\quad -\sum_{j=0}^{N-1}\|\phi_t^{t+j}\left(\overline{\mathbf{x}}(t)-\overline{\mathbf{x}}_c(t)\right)\|^2\\ &\leq-\big(c_3-\kappa ( c_{4} r+2 c_{4} \beta^2/r+c_{4} \eta/r\\ &\quad+ 2c_{4} r\lambda_n^2)\big) \|\overline{\mathbf{x}}-\overline{\mathbf{x}}_c\|^2+\kappa ( c_{4} \beta^2 r\|\mathbf{z}\|^2\\ &\quad +(2c_{4} r\lambda_n^2+c_4\beta^2 r+c_{4} \eta rL_f^2)\|\mathbf{\overline{x}}_{\perp}\|^2+c_{4} \eta rL_f^2\|\mathbf{\overline{x}}_{\parallel}\|^2)\\ &\quad +\kappa^2NL_\phi \big(4\lambda_n^2\|\overline{\mathbf{x}}_c\|^2+4\beta^4 \|\overline{\mathbf{v}}\|^2+(4\beta^4\\ &\quad +4\eta^2 L_f^2) \|\mathbf{\overline{x}}_{\perp}\|^2+4\eta^2 L_f^2 \|\mathbf{\overline{x}}_{\parallel}\|^2 \big) \end{align}\tag{58}\] for \(c_{4}:=NL_\phi\theta\), where \(r>0\) is a parameter to be determined later, the inequality is obtained by \(\overline{\mathbf{v}}=\mathbf{S}_\otimes\mathbf{\overline{v}}_{\perp}\), 55 , 57 , 29 , 39 and the Young’s Inequality.

For convenience of subsequent analysis, let us introduce some parameters \(\chi_1\), \(\xi_1,\dots>0\), which are independent of \(\alpha\), \(\beta\), \(r\) and \(\eta\), and some parameters \(\zeta_1\), \(\zeta_2,\dots>0\), as \[\begin{align} &\quad \chi_1=\frac{4L_f^2}{\mu_n}+\frac{4c_4L_f^2}{\mu_n},\quad \xi_1=\frac{\lambda_2}{2},\\ &\quad \xi_2=\frac{3}{2}+L_f^2+c_4+c_4L_f^2+\chi_1\frac{L_f^2}{2\mu_n},\quad\xi_3=2c_4 \lambda_n^2,\\ &\quad \xi_4=\frac{1}{2},\quad \xi_5=c_4,\quad \xi_6=4c_4,\quad\xi_7=\frac{\lambda_n}{2}+2c_4\lambda_n^2,\\ &\quad \zeta_1=\frac{7}{2}\eta^2L_f^2+\frac{7}{2}\beta^4+4\lambda_n^2\\ &\qquad \quad+NL_\phi\left(8\lambda_n^2+4\beta^4+4\eta^2L_f^2\right)+\frac{1}{2}\chi_1\eta^2L_f^2,\\ &\quad \zeta_2=\frac{7}{2}\beta^4+4NL_\phi\beta^4,\;\zeta_3=\frac{7}{2}\eta^2L_f^2+4NL_\phi\eta^2L_f^2+\frac{1}{2}\eta^2\chi_1L_f^2,\\ &\quad \zeta_4=4\lambda_n+8NL_\phi\lambda_n^2. \end{align}\]

In view of the previous analysis and definitions, we define the Lyapunov functions of system 35 as \(V_t: = V_{1,t}+V_{2,t}+\chi_1V_{3,t}\) with \(V_{3,t}\) defined in Appendix 14 and satisfying 50 . Then we have \[\begin{align}\label{eq:DPD46b46Vp} V\geq \frac{1}{2}\|\mathbf{\overline{x}}_{\perp}\|^2+\frac{1}{2}\|\mathbf{z}\|^2+ \frac{\chi_1}{2}\|\mathbf{\overline{x}}_{\parallel}\|^2+c_1\|\overline{\mathbf{x}}-\overline{\mathbf{x}}_c\|. \end{align}\tag{59}\]

Combining 54 , 58 , 50 , and letting \(r\leq1\), \(\beta^2\leq1\), \(\eta\leq\beta^2\), we have \[\begin{align} \Delta V_t&\leq \kappa\big(-(\xi_{1} -\xi_{2} \beta^2 - \xi_3 r)\|\mathbf{\overline{x}}_{\perp}\|^2\\ &\quad-(\beta^2-\xi_4 \eta-\xi_5 \beta^2 r)\|\mathbf{z}\|^2-\eta \frac{\mu_n}{4}\chi_1 \|\mathbf{\overline{x}}_{\parallel}\|^2\\ &\quad-(c_3/\kappa-\xi_6 /r - \xi_7 )\big)\|\overline{\mathbf{x}}-\overline{\mathbf{x}}_c\|^2\\ &\quad+\kappa^2\big(\zeta_1 \|\mathbf{\overline{x}}_{\perp}\|^2 + \zeta_2 \|\overline{\mathbf{v}}\|^2_P+ \zeta_3 \|\overline{\mathbf{x}}-\overline{\mathbf{x}}_c\|^2 + \zeta_4 \|\mathbf{\overline{x}}_{\parallel}\|^2 \big). \end{align}\] It can be noted that \(\Delta{V_t}\) is negative definite when we choose \(r=\mathrm{min}\left\{\frac{\xi_1}{4\xi_3},\frac{1}{4\xi_5},1\right\}\), \(\kappa\leq \kappa_1= \frac{c_3}{2\xi_6r+2\xi_7}\), \(\beta^2\leq \mathrm{min}\left\{{1},\frac{\xi_1}{4\xi_2}\right\}\), \(\eta\leq \mathrm{min}\left\{\beta^2,\frac{1}{4\xi_4}\right\}\) and \(\kappa\leq\kappa_2:=\frac{1}{2}\mathrm{min}\left\{\frac{\xi_{1} }{2\zeta_1}, \frac{\beta^2}{2\zeta_2}, \eta \frac{\chi_{1}\mu_n}{4\zeta_3},\frac{c_{3}}{2\zeta_4}\right\}\). With 59 in mind, we have \[\label{eq:rate95oc} \begin{align} \Delta V_t \leq -\gamma V_t,\;\gamma = \frac{1}{2}\kappa\mathrm{min}\left\{\frac{\lambda_2}{2}, {\beta^2}, \eta \frac{\mu}{2n},\frac{c_3}{2c_1}\right\}. \end{align}\tag{60}\] Let \(\kappa_3:=2/\mathrm{min}\left\{{\xi_{1}}, {\beta^2}, \eta \frac{\mu_n}{2},\frac{c_3}{2c_1}\right\}\). When \(\kappa\leq\mathrm{min}\left\{\kappa_1,\kappa_2,\kappa_3\right\}\), we can derive for some \(\gamma\in\left(0,1\right)\) , \(V_t=\mathcal{O}\left(\left(1-\gamma\right)^t\right)\) and thus \(\|\overline{\mathbf{x}}(t)\|^2=\mathcal{O}\left(\left(1-\gamma\right)^t\right)\). With the previous definition \(\overline{\mathbf{x}}(t)=\mathbf{x}(t)-\mathbf{s}\), we conclude that \(\mathbf{x}_i(t)\) in DPD-OC converges linearly to the optimal solution \(s^\ast\) with the ST compressor. The proof is completed.

16 The expression of \(\gamma_{OC}\) and \(\gamma_{DC}\) for compressor \(\mathbf{C}_{1a}\).↩︎

In this section, we prove that the expressions of \(\gamma_{DC}\) and \(\gamma_{OC}\) are given by \(\gamma_{DC}=\frac{1}{2} \kappa\mathrm{min}\left\{\frac{c_3\lambda_2}{4c_1\lambda_n},\frac{c_3\lambda_2}{4c_1},\beta^2,\eta\frac{\mu}{2n}\right\}\) and \(\gamma_{OC}= \frac{1}{2}\kappa\mathrm{min}\left\{\frac{\lambda_2}{2}, {\beta^2}, \eta \frac{\mu}{2n},\frac{c_3}{2c_1}\right\}\). As \(\delta=0\) when \(\mathbf{C}_{1a}\) is used, the expressions can be easily obtained by 52 and 60 as long as we can prove the parameters \(c_3,c_1\) in 52 and 60 are the same.

To distinguish, we will refer to \(c_3,c_1\) in \(\gamma_{OC}\) as \(c_{3,OC},c_{1,OC}\) and \(c_3\) in \(\gamma_{DC}\) as \(c_{3,DC},c_{1,DC}\). Next, we will prove that for compressor \(\mathbf{C}_{1a}\), there holds \(c_{3,OC}=c_{3,DC},c_{1,OC}=c_{1,DC}\).

For the following system in Appendix 14, \[\begin{align} {\mathbf{y}}_{e}\left(t+1\right)=\mathbf{y}_{e}(t)-\kappa_0\Lambda \mathcal{C}\left(\mathbf{y}_{e}(t),t\right), \end{align}\] noting that \(\mathbf{C}_{1a}=\boldsymbol{\psi}(t)\boldsymbol{\psi}^T(t)\mathbf{x}\), where \(\boldsymbol{\psi}(t)= \mathbf{e}_i\) with \(i=1+\left(t\; \mathrm{mod}\;d\right)\) for \(t\in\mathbb{N}\), we define \(V_{e,t}:=\sum_{i=1}^{d}\|\phi_t^{t+j}\left(\mathbf{x}_e\right)\|^2\), where \(\phi_t^{t+j}\) is defined in Appendix 14, then we have \(\|\mathbf{y}_{e}\|^2\leq V_{e,t}\leq d\|\mathbf{y}_{e}\|^2\) and \(\Delta V_{e,t} \leq -\lambda_2\kappa_0\alpha_1\|\mathbf{y}_e(t)\|^2.\) Comparing the results with 46 , we have \(c_{3,DC}=\kappa_0\alpha_1\) and \(c_{1,DC}=1\).

For the following system in Appendix 15, \[\begin{align} {\mathbf{y}}_{e}\left(t+1\right)=\mathbf{y}_{e}(t)-\kappa_0^\ast \mathcal{C}\left(\mathbf{y}_{e}(t),t\right), \end{align}\] we define \(V_{e,t}=\sum_{i=1}^n\|\phi_t^{t+j}\left(\mathbf{x}_e\right)\|^2\), where \(\phi_t^{t+j}\) is defined in Appendix 15, then we have \(\|\mathbf{y}_{e}\|^2\leq V_{e,t}\leq d\|\mathbf{y}_{e}\|^2\) and \(\Delta V_{e,t} \leq -\kappa_0\alpha_1\|\mathbf{y}_e(t)\|^2\) by \(\kappa_0\leq\kappa_0^\ast\). Comparing the results with 55 , we have \(c_{3,OC}=\kappa_0\alpha_1\) and \(c_{1,OC}=1\). Then we complete the proof.

17 Proof of Theorem 7↩︎

The idea of proof is quite similar to that in Appendix 15. We just recalculate \(\Delta V_{2,t}\) with stochastic impact while the other proof process is the same.

Now that \(\mathbf{x}_e(t+1)-\mathbf{x}_e(t)=-\kappa_0\mathbf{C}(\mathbf{x}_e(t),t)\), where \(\mathbf{x}_e(t)\in\mathbb{R}^{d}\), achieves mean square exponential convergence at the zero equilibrium, then clearly \(\mathbf{y}_e(t+1)-\mathbf{y}_e=-\kappa_0\mathcal{C}(\mathbf{y}_e,t)\), where \(\mathbf{y}_e\in\mathbb{R}^{nd}\), achieves also. Then there exists positive constants \(C\), \(\gamma<1\), for any \(t\) and \(T\in\mathbb{N}_+\), the solution satisfies \[\mathbb{E}\|\mathbf{y}_{e}(t+T)\|^2\leq C(\|\mathbf{y}_e(t)\|^2)\gamma^T.\]

Assume \(\phi_t^{t+N}(\mathbf{y}_e)\) is the state of system \(\mathbf{y}_e(t+1)-\mathbf{y}_e(t)=-\kappa_0\mathcal{C}(\mathbf{y}_e(t),t)\) in \(t+N\) moment with the state in \(t\) moment is \(\mathbf{y}_e(t)\). It is easy to verified that \[\begin{align} \mathbb{E}\|\phi_t^{t+N}(\mathbf{y})\|^2&\leq& L_\phi \|\mathbf{y}\|^2 \end{align}\] for any \(\mathbf{y}\in\mathbb{R}^{(n-1)d}\) and some \(L_\phi>0\) by property of compressor \(\mathbf{C}\).

With 46 in mind, we can proof Lyapunov function \(V_0(\mathbf{y}_e,t)=\sum_{j=0}^{N-1}\|\phi_t^{t+j}(\mathbf{y}_e)\|^2\) with some \(N>0\) satisfies \[\label{eq:DPD46d46Ve} \begin{align} &c_{1}\|\mathbf{y}_e\|^2\leq\mathbb{E}(V_{e,t})\leq c_{2}\|\mathbf{y}_e\|^2\\ &\mathbb{E}\sum_{j=1}^{N}\|\phi_{t+1}^{t+j}(\mathbf{y}_e-\kappa_0C(\mathbf{y}_e,t))\|^2-\mathbb{E}\sum_{j=0}^{N-1}\|\phi_t^{t+j}(\mathbf{y}_e)\|^2\\ &\leq -c_{3}\|\mathbf{y}_e\|^2\\ \end{align}\tag{61}\] for \(c_{1}=1,c_{2}=NL_\phi,c_{3}>0\).

Besides, \[\begin{align}\label{eq:DPD46d46fact1} \mathbb{E}\|\overline{\mathbf{x}}-\overline{\mathbf{x}}_c+\kappa_0\mathcal{C}(\overline{\mathbf{x}}-\overline{\mathbf{x}}_c,t)\|^2\leq \theta\|\overline{\mathbf{x}}-\overline{\mathbf{x}}_c\|^2, \end{align}\tag{62}\] for \(\theta=2+2 L^2_c\kappa_0^2>0\) by property of \(\mathbf{C}\).

Define \(V_2(\overline{\mathbf{x}}-\overline{\mathbf{x}}_c,t):= V_e(\overline{\mathbf{x}}-\overline{\mathbf{x}}_c,t)\), with 58 in mind, we can derive \[\label{eq:DPDS46b46V2} \begin{align} \mathbb{E}\Delta V_{2,t}&= \mathbb{E}\sum_{j=1}^{N}\|\phi_{t+1}^{t+j}(\overline{\mathbf{x}}(t+1)-\overline{\mathbf{x}}_c(t+1))\|^2\\ &-\mathbb{E}\sum_{j=0}^{N-1}\|\phi_t^{t+j}(\overline{\mathbf{x}}(t)-\overline{\mathbf{x}}_c(t))\|^2)\\ &\leq-[c_3-\kappa\big( c_{4} /r+2 c_{4} \beta^2/r+c_{4} \eta/r) \|\overline{\mathbf{x}}-\overline{\mathbf{x}}_c\|^2] \\ &+\kappa\big( c_{4} r\lambda_n^2\|\overline{\mathbf{x}}_c\|^2+c_{4} \beta^2 r\|\mathbf{z}\|^2+c_4\beta^2 r\|\mathbf{\overline{x}}_{\perp}\|^2+\\ &c_{4} \eta rL_f^2\|\mathbf{\overline{x}}_{\perp}\|^2+c_{4} \eta rL_f^2\|\mathbf{\overline{x}}_{\parallel}\|^2\big)\\ &+\kappa^2NL_\phi\big(4\lambda_n^2\|\overline{\mathbf{x}}_c\|^2+4\beta^4 \|\overline{\mathbf{v}}\|^2+(4\beta^4\\ &+4\eta^2 L_f^2) \|\mathbf{\overline{x}}_{\perp}\|^2+4\eta^2 L_f^2 \|\mathbf{\overline{x}}_{\parallel}\|^2\big), \end{align}\tag{63}\] for \(c_{4}:=NL_\phi\theta\), where the first inequality is obtained 61 and 62 , and \(r>0\) is a parameter which will be determined later.

We define the same \(V_t\) as that in Appendix 15, then 59 holds and we have \[\begin{align} \mathbb{E}\Delta V_t \leq -\gamma V_t,\;\gamma = \frac{1}{2}\kappa\mathrm{min}\{\frac{\lambda_{2}}{2}, {\beta^2}, \eta \frac{\mu_n}{2},\frac{c_3}{2c_1}\}. \end{align}\] with the same parameters. Then we can derive \(\mathbb{E}\|\overline{\mathbf{x}}(t)\|^2=\mathcal{O}((1-\gamma)^t)\). With the definition \(\overline{\mathbf{x}}=\mathbf{x}-\mathbf{s}\) before, we know that the mean square of \(\mathbf{x}_i(t)\) in DPD-OC converge exponentially to the optimal solution \(s^\ast\) with the StST compressor.

References↩︎

---

1. A preliminary version of the paper was presented at the 63rd IEEE Conference on Decision and Control, December 16-19, 2024, Allianz MiCo, Milan Convention Centre, Italy [1]. (Corresponding author: Lei Wang)↩︎

2. Z. Ren, L. Wang and Z. Wu are with State Key Laboratory of Industrial Control Technology, Institute of Cyber-Systems and Control, Zhejiang University, Hangzhou 310027, China. (E-mail: {zhren2000; lei.wangzju; nashwzhg}zju.edu.cn?)↩︎

3. X. Yi is with the College of Electronics and Information Engineering, Tongji University, China. (E-mail:xinleiyi@tongji.edu.cn)↩︎

4. X. Wang is with the School of Electrical Engineering Telecommunications, University of New South Wales, Sydney, Australia. (E-mail: xi.wang14@unsw.edu.au)↩︎

5. D. Yuan is with the School of Automation, Nanjing University of Science and Technology, China. (E-mail: dmyuan1012@gmail.com)↩︎

6. T. Yang is with the State Key Laboratory of Synthetical Automation for Process Industries, Northeastern University, China. (E-mail: yangtao@mail.neu.edu.cn)↩︎

7. G. Shi is with the Australian Centre for Robotics, School of Aerospace, Mechanical and Mechatronic Engineering, The University of Sydney, Sydney, NSW 2006, Australia. (E-mail:guodong.shi@sydney.edu.au)↩︎

8. Though only distributed primal-dual algorithm is considered, we stress that the proposed compressors and compression methods in this paper can be incorporated into other common consensus-based algorithms, e.g. DGT in [6] or the Wang-Eila algorithm in [8].↩︎

9. Readers of interest can refer to the Section V.4 for the stochastic version of \(\mathbf{C}_2\).↩︎