A Flexible Framework for Decentralized Composite Optimization with Compressed Communication

The recent increase in the number of mobile devices with enhanced computing and communication capabilities has led to significant development of multiagent systems [1,2]. Within these systems, many applications, including smart grid management [3,4], wireless communications [5], multi-robot coordination [6,7], large-scale machine learning [8], etc., can be cast to decentralized optimization problems, in which a network of nodes cooperatively solve a finite-sum optimization problem using local information.

A vast of decentralized optimization algorithms have been proposed, since the pioneer work DGD [9], in which each node performs gradient descent and simultaneously communicates decision vector with its neighbors for consensus. As DGD requires diminishing stepsize, which might slower the convergence rate, gradient tracking (GT) based algorithms using constant stepsizes are then developed [10,11] and have been extensively investigated under various scenarios [12,13,14,15], to name a few. However, GT-based methods require to transmit both the decision vector and an additional gradient estimation vector, which increase the communication cost. In parallel, another type of decentralized algorithms based on alternating direction method of multipliers (ADMM) are proposed and analyzed [16,17]. Compared with GT-based algorithms, ADMM-type algorithms can achieve the same convergence rate but require the transmission of only decision vector, which can be more communication-efficient. Following this line, some decentralized optimization algorithms are proposed for accelerating the convergence rate by introducing second-order information [18,19,20,21]. More recently, Ref. [22] proposed a family of decentralized curvature aided primal dual algorithms, which can include gradient, Newton, and BFGS type of updates.

In the decentralized algorithms, it is of great significance to improve communication-efficiency. The methods can be classified into two types. One method is to adopt compressed communication scheme, using quantization [23] or sparsification [24,25] techniques to reduce communication overhead per transmission. Recently, the compressed communication scheme has been combined with DGD [26,27], GT-based algorithms [28,29], and ADMM-type algorithms [30,31]. Another method is to employ intermittent communication scheme which aims to reduce the communication frequency. Such type of methods includes event-triggered communication [32,33,34], lazy aggregation scheme (LAG) [35], etc. Besides, there are also some works combining the both methods [36,37,38]. In particular, ref. [39] combined event-triggered and compressed communication scheme with an ADMM-type algorithm and proposed a communication-efficient decentralized second-order optimization algorithm, which improve both computation and communication efficiency. It is worthy noting that the information distortion arisen by compressed communication scheme may have a negative effect on the convergence performance of the decentralized optimization algorithms. To overcome this shortage, Ref. [40] developed an error-feedback communication scheme (EF21) to avoid the negative effect of information distortion. Recently, a more general efficient communication scheme termed as three point compressor (3PC) is proposed in [41], which provides a unified method including EF21 and LAG as special cases. However, 3PC scheme is only investigated in distributed gradient descent algorithms under the parameter-server framework.

Despite of the progress, the development of communication-efficient decentralized optimization algorithms over the general networks is still lack an in-deep analysis, especially for the objective with non-differentiable part, i.e., decentralized composite optimization problems. Note that such problems have widely applications in the field of machine learning due to the existence of the non-differentiable regularization terms. Currently, some decentralized composite optimization algorithms have been proposed [22,42,43,44], but without employing efficient-communication schemes. Moreover, to the best of our knowledge, no work has been reported on communication-efficient decentralized composite optimization using second-order information. To fill this gap, in this paper, we incorporate the general efficient communication scheme 3PC [41] into the ADMM-based decentralized optimization framework [22], which result in a family of communication-efficient decentralized composite optimization algorithms with theoretical guarantees. It is worthy noting that such incorporation is not trivial as we need to overcome the negative effect arisen by the propagation of communication error over networks. The main contribution of this work can be summarized in the following two aspects:

Notation. If not specified, $\Vert \mathbf{x}\Vert$ and $\Vert \mathbf{A}\Vert$ represent the Euclidean norm and the spectral norm, respectively. For a positive definite matrix $\mathbf{P}\succ 0$, let ${\Vert \mathbf{x}\Vert }_{\mathbf{P}}:=\sqrt{{\mathbf{x}}^{\top }\mathbf{P}\mathbf{x}}$. Use $\left[n\right]$ to denote the set $\{1,\cdots ,n\}$. The proximal mapping for a function $g(·):{\mathbb{R}}^d\to \mathbb{R}$ is defined by ${\mathbf{prox}}_{g/\mathsf{\mu }}\left(\mathbf{v}\right)={arg\; min}_{\mathit{\theta }\in {\mathbb{R}}^d}\{g\left(\mathit{\theta }\right)+{\displaystyle \frac{\mathsf{\mu }}{2}}{\Vert \mathit{\theta }-\mathbf{v}\Vert }^2\}$. Let ${\mathbf{I}}_d$ represent the d-dimensional identity matrix, and $\mathbf{A}\otimes \mathbf{B}$ represent the Kronecker product of matrices $\mathbf{A}$ and $\mathbf{B}$.

In this paper, we study the decentralized composite optimization problem on an undirected connected network with n agents (or, nodes), which takes the form where $\mathbf{x}$ refers to the decision vector and $f_i(·):{\mathbb{R}}^d\to \mathbb{R}$ is a convex and smooth function accessible only by node i and $g(·):{\mathbb{R}}^d\to \mathbb{R}$ is a convex (possibly non-smooth) regularizer.

Next, we equivalently reformulate problem (1) into a compact form in terms of the whole network following the same idea in [22]. Denote the communication graph as $\mathcal{G}=\left\{\mathcal{V},\mathcal{E}\right\}$, where $\mathcal{V}:=\left[n\right]$ is the set of agents and $\mathcal{E}\subseteq \mathcal{V}\times \mathcal{V}$ is the set of edges containing the pair $(i,j)$ if and only if agent i can communicate with agent j. There is no self-loops in $\mathcal{G}$, i.e., $(i,i)\notin \mathcal{E}$ for any $i\in \left[n\right]$. Note that the edges in $\mathcal{E}$ are enumerated in arbitrary order, with $e_k:=(i,j)\in \mathcal{E}$ denoting the k-th edge, where $k\in \left[m\right]$ and $m:=\left|\mathcal{E}\right|$ is the number of edges. The neighbor set of agent i is ${\mathcal{N}}_i:=\{j\in \mathcal{V}:(i,j)\in \mathcal{E}\}$. Let ${\mathbf{x}}_i\in {\mathbb{R}}^d$ and ${\mathbf{z}}_k\in {\mathbb{R}}^d$ be the local decision vectors corresponding the ith-node kth-edge, respectively. We assume that $\mathcal{G}$ is connected. Then, problem (1) is equivalent to the following constrained form: where $\mathit{\theta }\in {\mathbb{R}}^d$ is an auxiliary variable for decoupling the smooth and non-smooth functions. Denote the optimal solution of problem (1) and (2) as ${\mathbf{x}}^{★}$ and $\{{\mathbf{x}}_i^{★},{\mathbf{z}}_k^{★},{\mathit{\theta }}^{★}\}$, respectively. It is straightforward to verify that ${\mathbf{x}}^{★}={\mathbf{x}}_i^{★}={\mathbf{z}}_k^{★}={\mathit{\theta }}^{★}$ for all $i\in \left[n\right]$ and $k\in \left[m\right]$.

In what follows, define $\tilde{\mathbf{x}}:=[{\mathbf{x}}_1;{\mathbf{x}}_2;\cdots ;{\mathbf{x}}_n]\in {\mathbb{R}}^{nd}$ and $\tilde{\mathbf{z}}:=[{\mathbf{z}}_1;{\mathbf{z}}_2;\cdots ;{\mathbf{z}}_m]\in {\mathbb{R}}^{md}$. In addition, define two matrices ${\widehat{\mathbf{A}}}_s$ and ${\widehat{\mathbf{A}}}_d\in {\mathbb{R}}^{m\times n}$ as follows: the k-th row of both ${\widehat{\mathbf{A}}}_s$ and ${\widehat{\mathbf{A}}}_d$ represents the k-th edge $e_k$. Specifically, the entries ${\left[\widehat{\mathbf{A}}s\right]}_{ki}$ and ${\left[\widehat{\mathbf{A}}d\right]}_{kj}$ are both equal to 1 if and only if the edge $e_k=(i,j)$; otherwise, they are 0. We also define $\mathbf{S}:=({\mathbf{s}}_l\otimes {\mathbf{I}}_d)\in {\mathbb{R}}^{nd\times d}$, where ${\mathbf{s}}_l\in {\mathbb{R}}^n$ is a vector with a 1 at its l-th position and 0 elsewhere. Clearly, the matrix ${\mathbf{S}}^{\top }$ extracts the component of $\tilde{\mathbf{x}}$ that corresponds to agent l, meaning that ${\mathbf{S}}^{\top }\tilde{\mathbf{x}}={\mathbf{x}}_l$. Let $F\left(\tilde{\mathbf{x}}\right):={\sum }_{i=1}^n{f}_i\left({\mathbf{x}}_i\right)$. Then, problem (2) can be written as

Note that problem (3) is written from the network level, which will be the basis for designing our algorithm.

In this section, we first introduce the basic iterations of our algorithm based on ADMM method. Then, by combining compressed communication techniques with the ADMM-based algorithm, we will devise our algorithm and discuss its relationship with existing algorithms.

In this section, we propose a unified framework to analyze the proposed algorithms that incorporate gradient, Newton, and BFGS updates, along with a communication-efficient mechanism. First, we make the following assumptions throughout of the paper.

It is worthy noting that Assumption 3 is only required for the quasi-Newton update case. Next, we introduce the optimal condition of problem (3), which is independent of the algorithm and has been proved in [22]. The result is given below.

Now, we are ready to analyze our algorithm CE-DADMM. First, we write (11) into a compact form:

According to the discussion in Section 3.1, we have ${\mathbf{E}}_u{\tilde{\mathbf{x}}}_t=2{\tilde{\mathbf{z}}}_t$ and ${\mathit{\varphi }}_t={\mathbf{E}}_s^{\top }{\mathit{\alpha }}_t$ hold in (17). Then, it follows from Lemma 1 that the convergence of CE-DADMM can be obtained by showing $({\tilde{\mathbf{x}}}^t,{\tilde{\mathbf{z}}}^t,{\mathit{\alpha }}^t,{\mathit{\theta }}^t,{\mathit{\lambda }}^t)$ converges to $({\tilde{\mathbf{x}}}^{★},{\tilde{\mathbf{z}}}^{★},{\mathit{\alpha }}^{★},{\mathit{\theta }}^{★},{\mathit{\lambda }}^{★})$.

Due to the existence of the efficient communication scheme, we need to analyze the impact of communication error on the convergence of CE-DADMM. Define $\tilde{\mathbf{e}}:=[{\mathbf{e}}_1;{\mathbf{e}}_2;\cdots ;{\mathbf{e}}_n]$, where ${\mathbf{e}}_i:={\mathbf{y}}_i-{\mathbf{x}}_i$ for all agent i. Clearly, $\tilde{\mathbf{e}}$ describes the error caused by efficient communication scheme. Regarding $\tilde{\mathbf{e}}$, the following result holds.

Clearly, if 3PC is set as EF21 (9), it follows from Lemma 2 that

If 3PC is set as CLAG (10), we have

Then, to characterize the suboptimality of the iterates when (5a) is replaced by (17a), we introduce the following error term:

The bound of the error term (18) is give below, which is important for our main result.

Lemma 3 extends the results in [17,18] by providing an upper bound on the error introduced when replacing the exact sub-optimization step (5a) with a one-step update using the compressed variable (17a). Under Newton updates, as the error $\Vert {\tilde{\mathbf{e}}}_t\Vert$ approaches zero, the term ${\displaystyle \frac{L_f}{2}}\Vert {\tilde{\mathbf{x}}}_{t+1}-{\tilde{\mathbf{x}}}_t\Vert +L_f\Vert {\tilde{\mathbf{e}}}_t\Vert$ becomes smaller than $2M_f$ in (20). In the case of Quasi-Newton updates, the error $\Vert {\mathbf{r}}_t\Vert$ remains bounded by a constant, ensuring it do not grow indefinitely.

Let ${\sigma }_{max}^{{\mathbf{L}}_u}$ and ${\sigma }_{min}^{{\mathbf{L}}_u}$ denote the maximum and minimum eigenvalues of ${\mathbf{L}}_u$, respectively. Let ${\sigma }_{max}^{{\mathbf{L}}_s}$ denote the maximum eigenvalue of ${\mathbf{L}}_s$. Denote by ${\sigma }_{min}^{+}$ the smallest positive eigenvalue of $\mathbf{C}{\mathbf{C}}^{\top }$, where $\mathbf{C}$ is given in Lemma 1. Define ${\tilde{\mathbf{v}}}_t:={[{\tilde{\mathbf{x}}}_t,{\tilde{\mathbf{z}}}_t,{\mathit{\alpha }}_t,{\mathit{\theta }}_t,{\mathit{\lambda }}_t]}^{\top }$, ${\tilde{\mathbf{v}}}^{★}:={[{\mathbf{x}}_{★},{\mathbf{z}}_{★},{\mathit{\alpha }}_{★},{\mathit{\theta }}_{★},{\mathit{\lambda }}_{★}]}^{\top }$, and ${\mathcal{H}}_1=diag[ϵ,2{\mathsf{\mu }}_z,{\displaystyle \frac{2}{{\mathsf{\mu }}_z}},{\mathsf{\mu }}_{\theta },{\displaystyle \frac{1}{{\mathsf{\mu }}_{\theta }}}]$. Consider the following Lyapunov function: Clearly, $V_t$ converges to zero implies that ${\tilde{\mathbf{v}}}_t$ converges to the optimal solution. We will use $V_t$ to establish the convergence result of our algorithm, which is given below.

Clearly, Theorem 1 implies that CE-DADMM can achieve exact linear convergence at a rate of $\mathcal{O}\left({\mathit{\rho }}^t\right)$ with $\mathit{\rho }={\displaystyle \frac{1}{1+{\eta }_t}}$. The larger ${\eta }_t$ is, the faster CE-DADMM converges. To ensure positive ${\eta }_t$ in (23), it can be obtain that the step size ${\mathsf{\mu }}_{\theta }$ should not be too large. Besides, excessive compression of ${\mathbf{x}}_k$ should be avoided. This is because, when the compression ratio A is very small, B approaches infinity. According to (23), as $B\to \infty$, the first term in (23) becomes negative. It is worth noting that when ${\eta }_t,{\gamma }_t=0$, the compression ratio A can be arbitrarily small, making the approach highly applicable in scenarios with extremely limited bandwidth. Also, at this situation, we can get the fastest convergence rate and the smallest communication cost. However, setting ${\eta }_t,{\gamma }_t=0$ implies solving the subproblem (5a) exactly, which may result in high computational cost. This shows a trade-off between communication cost and computation cost in decentralized optimization.

In this section, CE-DADMM is compared with existing state-of-the-art algorithms, including DRUID [22], PG-EXTRA [42], P2D2 [43], and CC-DQM [39], in distributed logistic/ridge/lasso regression problems. Noting that CC-DQM do not support non-smooth terms.

Datasets. We use real-world datasets from the LIBSVM library (Available Online: https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/binary.html, accessed on 3 December 2024): a9a (32,561 samples, 123 dimensions) and ijcnn1 (49,990 samples, 22 dimensions). The samples are evenly distributed across n agents. The distribution of samples across agents for the a9a dataset (left) and ijcnn1 (right) is shown in Figure 1. Our experiments are implemented in Python 3.10.13.

Experimental setting. The communication graph is randomly generated, with connections based on a Bernoulli distribution ($p=0.5$) among $n=10$ agents, as shown in Figure 2. We evaluate performance based on the total communication bits and the number of iterations. CE-DADMM employs compression mechanisms EF21 and CLAG, using a Top-K compressor to reduce dimensions to 30 dimensions for the a9a dataset and 6 dimensions for the ijcnn1 dataset. In the experiment, we examine the algorithms from two perspectives: the number of iterations and total communication bits. The number of iterations refers to the number of times the algorithm runs, while total communication bits is calculated based on the cumulative number of bits of variable $\mathbf{y}$ transmitted between agents. Additionally, we define $er{r}_t:={\displaystyle \frac{\Vert {\mathbf{x}}_t-{\mathbf{x}}^{★}\Vert }{\Vert {\mathbf{x}}_0-{\mathbf{x}}^{★}\Vert }}$ to measure the algorithm’s convergence.

This paper presents a communication-efficient ADMM algorithm for composite optimization, named as CE-DADMM. The algorithm utilizes the ADMM framework with the 3PC communication mechanism, effectively adapting to various communication and computational demands while balancing communication efficiency and computational cost. Notably, when employing quasi-Newton updates, CE-DADMM becomes the first compression-based second-order communication-efficient algorithm. Theoretical analysis demonstrates that the proposed algorithm achieves linear convergence when the local objective functions are strongly convex. Numerical experiments further validate the effectiveness and superior performance of the algorithm. Future work will focus on extending the algorithm to fully asynchronous settings and stochastic problems.