Distributed Algorithms for Composite Optimization: Unified Framework and Convergence Analysis

I Introduction

We study distributed multi-agent optimization over networks, modeled as undirected static graphs. Agents aim at solving

The focus of this paper is the design of a unified (first-order) algorithmic framework for Problem (P) with provably convergence rate. When $G=0$ and $\mu>0$, several distributed schemes have been proposed in the literature that enjoy linear rate; examples include EXTRA , AugDGM , NEXT , Harnessing , SONATA , DIGing , NIDS , Exact Diffusion , MSDA , and the distributed algorithms in . When $\mu=0$ and still $G=0$, a sublinear rate of $O(1/k)$ ($k$ counts the number of gradient evaluations) is achieved by some of the above methods and other primal-dual schemes, including D-ADMM . Results for $G\neq 0$ are relatively scarce; to our knowledge, the only two schemes achieving linear rate for (P) are SONATA and the one in ; the former under the assumption that $F$ is strongly convex and the latter requiring each $f_{i}$ to be so. Sublinear rate of $O(1/k)$ has been proved for a variety of schemes, including PG-EXTRA , D-FBBS and DPGA .

Although the aforementioned algorithms all achieve linear or sublinear convergence rates, they differ in the nature and strength of their convergence guarantees. No unified algorithmic design and convergence analysis can be inferred by existing studies. Furthermore, for most of the schemes, one notices a gap between theory and practice: convergence analyses yield tuning recommendations and associated rate bounds that numerical simulations prove being far too conservative. To make these algorithms work in practice, practitioners often use manual, ad-hoc tunings. This however makes the comparison of different schemes hard, running the risk of drawing misleading conclusions. These issues suggest the following questions:

Can one unify the design and analysis of distributed algorithms for Problem (P)?

How do provable rates of such schemes compare each other and with that of the centralized proximal-gradient algorithm applied to (P)?

On (Q1): Recent efforts toward a better understanding of the taxonomy of distributed algorithms are the following: provides a connection between EXTRA and DIGing; provides a canonical representation of some of the distributed algorithms above–NIDS and Exact-Diffusion are proved to be equivalent; and provides an automatic (numerical) procedure to prove linear rate of some classes of distributed algorithms. These efforts model only first-order distributed algorithms applicable to Problem (P) with $G=0$ and employing a single round of communication and gradient computation. However, existing algorithms have their rate analysis done in isolation, under ad-hoc convergence conditions and different ranges for the stepsize–see Table I. For instance, NIDS and Exact Diffusion are proved to be equivalent ; this however is not reflected by the convergence analyses and associated rate bounds and admissible stepsize values, which instead are quite different.

On (Q2): Question (Q2) has been only partially addressed in the literature. For instance, MSDA uses multiple communication steps to achieve the lower complexity bound of (P) when $\mu>0$ and $G=0$; the OPTRA algorithm achieves the lower bound when $\mu=0$ (still and $G=0$); and the algorithms in and achieve linear rate and can adjust the number of communications performed at each iteration to match the rate of the centralized gradient descent. However it is not clear how to extend (if possible) these methods and their convergence analysis to the more general composite ($G\neq 0$) setting (P). Furthermore, even when $G=0$, the rate results of existing algorithms are not theoretically comparable with each other–see Table I; they have been obtained under different stepsize range values and technical assumptions (e.g., on the weight matrices). Similarly, when $\mu=0$, EXTRA , DIGing D-ADMM , and PG-EXTRA , D-FBBS , DPGA achieve a sublinear rate of $O(1/k)$ for $G=0$ and $G\neq 0$, respectively. However, the rate expression given in terms of “big-O” notation lacks of any insight on the dependence of the rate on the key design parameters (e.g., the stepsize).

This paper aims at addressing Q1 and Q2 in the general setting (P), with either $\mu>0$ or $\mu=0$. Our major contributions are discussed next. 1) Unified framework and rate analysis: We propose a general primal-dual distributed algorithmic framework that unifies for the first time ATC (Adapt-Then-Combine)- and CTA (Combine-Then-Adapt)-based distributed algorithms, solving either smooth ($G=0$) or composite optimization problems ($G\neq 0$). Most of existing ATC and CTA schemes are special cases of the proposed framework–cf. Table II. A unified set of convergence conditions and rate expression are provided, leveraging a novel operator contraction-based analysis. By product of our unified framework and convergence conditions, several existing schemes, proposed only to solve smooth instances of (P) , gain now their “proximal” extension and thus become applicable also to composite optimization while enjoying the same (novel) convergence rate (as derived in this paper) of their “non-proximal” counterparts. 2) Improving upon existing results and tuning recommendations: Our results improve on existing convergence conditions and rate bounds, such as –Table I shows the improvement achieved by our analysis in terms of stepsize bounds and rate expression (see Sec. V-C for more details). Our rate results provide for the first time a platform for a fair comparison of these algorithms; the tightness of our rates as well as the established ranking of the algorithms based on the new rate expressions are supported by numerical results. 3) Rate separation when $G\neq 0$: For ATC-based schemes, when $\mu>0$, the dependency of the linear rate on the agents’ functions and the network topology are decoupled, matching the typical rates of the proximal gradient algorithm applied to (P) and consensus averaging. Furthermore, the optimal stepsize value is independent on the network and matches the optimal choice for the centralized proximal gradient algorithm. When $\mu=0$, we provide an explicit expression of the sublinear rate (beyond the “Big-O” decay) revealing a similar decoupling between optimization and network parameters. Our novel expression sheds also light on the choice of the stepsize minimizing the rate bound: the optimal choice is not necessarily $1/L$ but instead depends on the network parameters as well as the degree of heterogeneity of the agents’ functions (cf. Sec. VI). These results are a major departure from existing analyses, which do not show such a clear separation, and complements the results in applicable only to smooth and strongly convex instances of (P). 4) Balancing computation and communication: When $\mu>0$, the proposed scheme can adjust the ratio between the number of communication and computation steps to achieve the same rate of the centralized proximal gradient scheme. We show that Chebyshev acceleration can also be employed to further reduce the number of communication steps per computation.

The results of this work have been partially presented in . While preparing the final version of this manuscript, we noticed the arxiv submission , which is an independent and parallel work (cf. ). There are some substantial differences between our findings and : i) our algorithmic framework unifies ATC and CTA schemes while can cover only ATC ones; our analysis is based on an operator contraction-based analysis, which is of independent interest; and ii) we study convergence also when $F$ is convex but not strongly convex while focuses only on strongly convex problems.

II Problem Statement

We study Problem (P) under the following assumption, capturing either strongly convex or just convex objectives.

Network model: Agents are embedded in a network, modeled as an undirected, static graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, where $\mathcal{V}$ is the set of nodes (agents) and $\{i,j\}\in\mathcal{E}$ if there is an edge (communication link) between node $i$ and $j$. We make the blanket assumption that $\mathcal{G}$ is connected. We introduce the following matrices associated with $\mathcal{G}$, which will be used to build the proposed distributed algorithms.

where $C$ satisfies the following assumption:

Under this condition, the constraint $\sqrt{{C}}X=0$ enforces a consensus among $x_{i}$’s and thus (2) is equivalent to (P). The set of points satisfying the KKT conditions of (2) reads:

where $\nabla f(X)\triangleq[\nabla f_{1}(x_{1}),\nabla f_{2}(x_{2}),...,\nabla f_{m}(x_{m})]^{\top}$ and $\partial g(X)$ denotes the subdifferential of $g$ at $X$. Then we have the following standard result.

Building on Lemma 5, in the next section, we propose a general distributed algorithm for (P) based on a suitably defined operator splitting solving the KKT system (II).

III A General Primal-Dual Proximal Algorithm

The proposed general primal-dual proximal algorithm, termed $ABC-$Algorithm, reads

Since all agents share the same $G$, it is not difficult to check that any fixed point $(X^{\star},Z^{\star},Y^{\star})$ of Algorithm (4) is such that $X^{\star}\in\mathcal{S}_{\texttt{Fix}}$. The following are necessary and sufficient conditions on $A,B$ for $X^{\star}\in\mathcal{S}_{\texttt{Fix}}$ to be a solution of (2).

Under Assumption 4, $\mathcal{S}_{\texttt{KKT}}=\mathcal{S}_{\texttt{Fix}}$ if and only if $A,B$ satisfy Assumption 6.

Algorithm (4) contains a gamut of distributed (and centralized) schemes, corresponding to different choices of the weight matrices $A,B$ and $C$; any $A,B,C\in\mathcal{W}_{\mathcal{G}}$ leads to distributed implementations. The use of general matrices $A$ and $B$ (rather the more classical choices $A=B$ or $B=I$) permits a unification of both ATC- and CTA-based updates; this includes several existing distributed algorithms proposed for special cases of (P), as discussed next.

We begin rewriting Algorithm (4) in the following equivalent form by subtracting (4b) at iteration $k+1$ from (4b) at iteration $k$:

where $X^{k}=\text{prox}_{\gamma g}\left(Z^{k}\right)$.

We show next that the schemes in are all special cases of Algorithm (4). Table II summarizes the specific choices of $A,B$, and $C$ in (4) yielding the desired equivalence, where $W\in\mathcal{W}_{\mathcal{G}}$ is the weight matrix used in the target distributed algorithms. Notice that all these choices satisfy Assumptions 4 and 6.

1) EXTRA : EXTRA solves (P) with $G=0$, and reads

2) NIDS / Exact diffusion : The NIDS (Exact Diffusion) algorithm applies to (P) with $G=0$, and reads

which is an instance of our general scheme, with $A=B=({I+W})/{2}$ and $C=({I-W})/{2}$.

3) NEXT & AugDGM : The gradient tracking-based algorithms NEXT/AugDGM applied to (P) with $G=0$, are:

Eliminating the $Y$-variable, (10) can be rewritten as:

Clearly (11) is an instance of our scheme (4), with $A=B=W^{2},C=(I-W)^{2}$. Notice that distributed gradient tracking schemes in the so-called CTA form are also special cases of Algorithm (4). For instance, one can show that the DIGing algorithm corresponds to the setting $A=W^{2},B=I,$ and $C=(I-W)^{2}$.

4) General primal-dual scheme : A general distributed primal-dual algorithm was proposed in for (P) with $G=0$ as follows

where $B^{\prime}$ can be $bI$ or $bW$ for some positive constant $b>0$ therein. Eliminating the $Y$-variable, (12) reduces to

which corresponds to the proposed algorithm, with $A=W^{2}+\gamma(I-W)B^{\prime},B=I,C=(I-W)^{2}+\gamma(I-W)B^{\prime}$. Similarly, building on a general augmented Lagrangian, another general primal-dual algorithm was proposed in for (P) with $G=0$, which reads

where $A^{\prime},B^{\prime},C^{\prime}$ are certain weight matrices therein and $C^{\prime}=\sum_{i=0}^{K-1}(I-\alpha B^{\prime})^{i}$, with $K$ being the number of communication steps performed at each iteration. Eliminating $Y$ yields

which corresponds to Algorithm (4) with $A=(I-\alpha B^{\prime})^{K},B=C^{\prime},C=\alpha\beta C^{\prime}A^{\prime\top}A^{\prime}$. Notice that, letting $W=I-\alpha B^{\prime}$ and $B^{\prime}=\beta A^{\prime\top}A^{\prime}$, we have $A=W^{K},B=\sum_{i=0}^{K-1}W^{i}$ and $C=(I-W)\sum_{i=0}^{K-1}W^{i}=I-W^{K}$, which satisfy Assumption 6.

6) Decentralized proximal algorithm : A proximal algorithm is proposed to solve (P) with $G\neq 0$, which reads

where $X^{k}=\text{prox}_{\gamma g}\left(Z^{k}\right)$ and $B^{\prime}$ is some properly chosen matrix that ensures consensus. It is easy to show that the above algorithm corresponds to Algorithm (4) with $A=I-B^{\prime},\,B=I,\,C=\alpha B^{\prime}$. Choosing $W=I-B^{\prime}$, we have $A=W,B=I$ and $C=\alpha(I-W)$, which clearly satisfy Assumption 6. Note that, since $B=I$, this algorithm (and thus ) is of CTA form and cannot model ATC-based schemes, such as NEXT/AugDGM and NIDS/Exact Diffusion listed in Table II.

IV An Operator Splitting Interpretation

Our convergence analysis builds on an equivalent fixed-point reformulation of Algorithm (4), whose mapping enjoys a favorable decomposition in terms of contractive and nonexpansive operators. We begin introducing the following assumptions.

Under the above assumption, the following lemma provides an operator splitting form for Algorithm (4).

and $\{\widetilde{U}^{k}\}_{k}$ satisfies the following dynamics

with initialization $\widetilde{Z}^{1}=\widetilde{Y}^{1}=(D-\gamma\nabla f)(X^{0})$;

where $T_{C}$ and $T_{B}$ are the operators associated with communications while $T_{f}$ and $T_{g}$ are the gradient and proximal operators, respectively;

3) Every fixed point $\widetilde{U}^{\star}\triangleq[\widetilde{Z}^{\star},\sqrt{C}\widetilde{Y}^{\star}]$ of $T$ is such that $X^{\star}\triangleq\text{prox}_{\gamma g}(B\widetilde{Z}^{\star})\in\mathcal{S}_{\texttt{Fix}}$. Therefore, $X^{\star}=1_{m}x^{\star\top}$, where $x^{\star}$ is an optimal solution of (P).

From (4), we have $Z^{k+1}=(I-C)Z^{k}+A(X^{k}-X^{k-1})-\gamma B(\nabla f(X^{k})-\nabla f(X^{k-1}))$, which applied recursively yields

where in $(*)$ we used Assumption 17i) and 17iv).

Define $\widetilde{Z}^{k}$ such that $Z^{k}=B\widetilde{Z}^{k},$ $k\geq 1$; and let

for $k\geq 0$. It is clear from the definition of $\widetilde{Z}$ and $\widetilde{Y}$ that

Introducing $\widetilde{U}^{k}$ as defined in (14), it follows from (18) that $\widetilde{U}^{k}$ obeys the dynamics (15). The equation $Y^{k}=BC\widetilde{Y}^{k}$ follows readily from (4c) and (17). Finally, the decomposition of the transition matrix $T$ can be checked by inspection.

We prove now the last statement of the theorem. For every fixed point $\widetilde{U}^{\star}\triangleq[\widetilde{Z}^{\star},\sqrt{C}\widetilde{Y}^{\star}]$ of $T$, we have For any matrix $M$, we use ${\texttt{span}}(M)$ to denote its column space. ${\texttt{span}}(\widetilde{Z}^{\star})\subset{\texttt{span}}(1)$ and

For $X^{\star}\triangleq\text{prox}_{\gamma g}(B\widetilde{Z}^{\star})$, it holds ${\texttt{span}}(X^{\star})\subset{\texttt{span}}(1)$ and

Combining (19) and (20) leads to $1^{\top}(I-A)X^{\star}+\gamma\,1^{\top}B\nabla f(X^{\star})\in-\gamma\,1^{\top}\partial g(X^{\star}),$ which is equivalent to $X^{\star}\in\mathcal{S}_{\texttt{Fix}}$. The proof follows from Lemma 5 and 7.

The result comes readily from the definition of $T_{C}$ and the fact that $T_{C}^{\top}\Lambda_{I-C}T_{C}=V_{I-C}$. ∎

Consider the operator $T_{f}$ under Assumption 1, with $\mu>0$, and $0\prec D\preceq I$. If $0<\gamma\leq\gamma^{\star}(D)$ with

The stepsize minimizing the contraction factor is $\gamma=\gamma^{\star}(D)$, resulting in the smallest achievable $q(D,\gamma)$, given by

We conclude with the properties of $T_{g}$ and $T_{B}$, which follow readily from the non-expansive property of the proximal operator and the linear nature of $T_{B}$, respectively.

V Linear Convergence

In this section we prove linear convergence of Algorithm (4), under strong convexity of each $f_{i}.$ Since most of the algorithms in the literature considered only the case $G=0$, we begin with that setting (cf. Sec. V-A ). Sec.V-B extends our analysis to $G\neq 0$. Finally, we comment our results in Sec.V-C.

Consider Problem (P) with $G=0$. Algorithm (4) reduces to

Theorem 15 below establishes linear convergence of Algorithm (24) under the following assumption on $A,B,$ and $C$.

$1_{m}^{\top}D1_{m}=m$ and $1_{m}^{\top}B=1_{m}^{\top}$;

$0\preceq C\prec I$ and ${\texttt{null}}({C})={\texttt{span}}(1_{m})$;

${q(D,\gamma)}^{2}AB\prec(I-C)$ and $0<\gamma\leq\gamma^{\star}(D)$,

where $q(D,\gamma)$ and $\gamma^{\star}(D)$ are defined in (22) and (21), respectively.

Assumption 14 is quite mild and satisfied by a variety of algorithms; for instance, this is the case for all the schemes in Table II. In particular, the commuting property of $B$ and $C$ is trivially satisfied when $B,C\in P_{K}(W)$, for some given $W\in\mathcal{W}_{\mathcal{G}}$ (as in Table II). Also, one can show that condition v) in Assumption 14 is necessary to achieve linear rate.

Since (24) corresponds to Algorithm (4) with $G=0$, by Assumption 14 and Prop. 9, (24) can be equivalently rewritten in the form (15), with $T_{g}=I$; and thus the $Z$- and $X$-variables coincide. Define $X^{\star}=Z^{\star}\triangleq 1_{m}x^{\star\top}$. Let $\widetilde{U}^{k}={[(\widetilde{Z}^{k})^{\top},(\sqrt{C}\widetilde{Y}^{k})^{\top}]}^{\top}$ be the auxiliary sequence defined in (14) with $\widetilde{U}^{\star}\triangleq[\widetilde{Z}^{\star},\sqrt{C}\widetilde{Y}^{\star}]$ the fixed point of $T=T_{C}T_{f}T_{B}$. Then, we have

Note that Theorem 15 is the first unified convergence result stating linear rate for ATC (corresponding to $D=I$) and CTA (corresponding to $B=I$) schemes. Because of this generality and consistently with existing conditions for the convergence of CTA-based schemes, the choice of the stepsize satisfying Assumption 14 might depend on some network parameters. This is due to the fact that $\lambda_{\max}(AB(I-C)^{-1})\geq 1$, since $(I-C)^{-1/2}AB(I-C)^{-1/2}1_{m}=1_{m}$. Hence, when $\lambda_{\max}(AB(I-C)^{-1})>1$, the stepsize needs to be leveraged to guarantee that $q(D,\gamma)^{2}\lambda_{\max}(AB(I-C)^{-1})<1$, reducing the range of feasible values. For instance, this happens for i) CTA schemes ($B=I$) such that $D\preceq I-C$ does not hold; of ii) for ATC schemes ($D=I$) that do not satisfy the condition $B^{2}\preceq I-C$.

The following corollary provides a condition on the weight matrices enlarging the range of the stepsize to $[0,\gamma^{\star}(D)]$. Furthermore, the tuning minimizing the contraction factor $\delta$ in (25) is derived.

Consider the setting of Theorem 15, and further assume $AB\preceq I-C$. Then, $\left\|X^{k}-1_{m}x^{\star\top}\right\|^{2}=\mathcal{O}(\delta^{k}),$ with

The stepsize that minimizes (27) is $\gamma=\gamma^{\star}(D)=\frac{2\lambda_{\min}(D)}{L+\mu\cdot\lambda_{\min}(D)}$, resulting in the contraction factor

The smallest $\delta$ is achieved choosing $D=I$, which yields $\gamma=\gamma^{\star}\triangleq\frac{2}{\mu+L}$ and

V-B The general case G≠0G\neq 0

We establish now linear convergence of Algorithm (4) applied to Problem (P), with $G\neq 0$. We introduce the following assumption similar to Assumption 14 for $G=0$.

$1_{m}^{\top}D1_{m}=m$ and $1_{m}^{\top}B=1_{m}^{\top}$;

$0\preceq C\prec I$ and ${\texttt{null}}({C})={\texttt{span}}(1_{m})$;

${q(D,\gamma)}^{2}B^{2}\prec(I-C)$ and $0<\gamma\leq\gamma^{\star}(D)$,

where $q(D,\gamma)$ and $\gamma^{\star}(D)$ are defined in (22) and (21), respectively.

Condition v) in Assumption 17 is slightly stronger than its counterpart in Assumption 14 (as $BDB\prec B^{2}$). This is due to the complication of dealing with the nonsmooth function $G$ (the presence of the proximal operator $T_{g}$). However, as shown in Corollary 19 below, this does not affect the smallest achievable contraction rate, which coincides with the one attainable when $G=0$. Note that Assumption 17 is satisfied by all the algorithms in Table II.

Consider Problem (P) under Assumption 1 with $\mu>0$, whose optimal solution is $x^{\star}$. Let $\{(X^{k},Z^{k},Y^{k})\}_{k\geq 0}$ be the sequence generated by Algorithm (4) under Assumption 17. Then $\left\|X^{k}-1_{m}x^{\star\top}\right\|^{2}=\mathcal{O}(\delta^{k})$, with

The proof of Theorem 18 is similar to that of Theorem 15 and is provided in the Appendix.

Consider the setting of Theorem 18, and further assume $B^{2}\preceq I-C$. Then, the same conclusions as in Corollary 16 hold for Algorithm (4).

V-C Discussion

Theorems 15 and 18 offer a unified platform for the analysis and design of a gamut of linearly convergence algorithms–all the schemes, new and old, that can be written in the form (24) and (4) satisfying Assumption 14 and 17, respectively. For instance, our convergence results embrace both ATC and CTA algorithms, solving either smooth ($G=0$) or composite ($G\neq 0$) optimization problems. This improves on and and contrasts the majority of the literature, wherein proposed algorithms have been generally studied in isolation, resulting in ad-hoc convergence conditions and rates. Our results are instead widely applicable–e.g., to all the algorithms listed in Table I–and tighter than existing rate expressions; see Sec. V-C4.

V-C2 On the rate expression

We comment the expression of the rate focusing on Theorem 18 and Corollary 19 ($G\neq 0$); same conclusions can be drawn for Algorithm (24) (Theorem 15 and Corollary 16). Theorem 18 provides the explicit expression of the linear rate provably achievable by Algorithm (4), for a given choice of the weight matrices $A$, $B$, and $C$ and stepsize $\gamma$ (satisfying Assumption 17). In general, this rate depends on both optimization parameters ($L$ and $\mu$) and network-related quantities ($A$, $B$, and $C$); furthermore, feasible stepsize values and network parameters are coupled by Assumption 17v). CTA-based schemes: This is consistent with existing convergence results of CTA-based algorithms (known only for $G=0$), which are special cases of Algorithm (24). For instance, consider EXTRA and DIGing (corresponding to Algorithm (24) with $B=I$, cf. Table I): $\gamma$, $C$ and $D$ are coupled via the condition ${q(D,\gamma)}^{2}\prec(I-C)$, instrumental to achieve linear rate. ATC-based schemes: For algorithms in the ATC form, i.e., $A=B$, less restrictive conditions are required. For instance, when Assumption 17v) is satisfied by $B^{2}\prec I-C$–a condition that is met by several algorithms in Table I–the stepsize can be chosen in the larger region $[0,\gamma^{\star}(D)]$, resulting in the smaller rate $\max(q(D,\gamma),1-\lambda_{2}(C))\geq\max(q^{\star}(D),1-\lambda_{2}(C))$ (recall that, in such a case, $\lambda_{\text{max}}(B^{2}(I-C)^{-1})=1$), where the lower bound is achieved when $\gamma=\gamma^{\star}(D)$ (cf. Corollary 19).

On the other hand, when the algorithm parameters can be freely designed, Corollary 16 offers the “optimal” choice, resulting in the smallest contraction factor, as in (29). This instance enjoys two desirable properties, namely:

(i) Network-independent stepsize: The stepsize $\gamma^{\star}$ in Corollary 16 does not depend on the network parameters but only on the optimization and its value coincides with the optimal stepsize of the centralized proximal-gradient algorithm. This is a major advantage over current distributed schemes applicable to (P) (but with $G\neq 0$) and complements the results in , whose algorithm however cannot deal with the non-smooth term $G$ and use more stringent stepsize.

(ii) Rate-separation: The rate (29) is determined by the worst rate between the one due to the communication $[1-\lambda_{2}(C)]$ and that of the optimization $[((\kappa-1)/(\kappa+1))^{2}]$. This separation is the key enabler for our distributed scheme to achieve the convergence rate of the centralized proximal gradient algorithm-we elaborate on this property next.

V-C3 Balancing computation and communications

V-C4 Improvement upon existing results and tuning recommendations

Theorems 15 and 18 improve upon existing convergence conditions and rate bounds. A comparison with notable distributed algorithms in the literature is presented in Table I. Since all the schemes therein are special cases of Algorithm (24) [with the exception of that is an instance of Algorithm (4)] (cf. Table II) and satisfy Assumption 14 (or Assumption 17), one can readily apply Theorem 15 (or Theorem 18) and determine, for each of them, a new stepsize range and achievable rate: the column “Stepsize/this paper (optimal, Corollary 16)” reports the stepsize value $\gamma^{\star}(D)$ for the different algorithms (i.e., given $B$, $C$ and $D$) while the column “Rate/$\delta$ this paper” shows the resulting provably rate, as given in (28). A direct comparison with the columns “Stepsize/literature (upper bound)” and “Rate/$\delta$, literature” respectively, shows that our theorems provide strictly larger ranges for the stepsize of EXTRA NEXT /AugDGM and Exact Diffusion , and faster linear rates for all the algorithms in the table.

Furthermore, since the rates in the column “Rate/$\delta$ this paper” are obtained for the optimal stepsize value (in the sense of Corollary 16) of the associated algorithm, Table I also serves as comparison of the convergence rates provably achievable by the different algorithms. For instance, we notice that, although EXTRA and NIDS both require one communication per gradient evaluation, NIDS is provably faster, achieving a linear rate of $\delta^{\star}\log(1/\epsilon)$, with $\delta^{\star}$ defined in (29), versus the linear rate $(\kappa/(1-\rho))\log(1/\epsilon)$ of EXTRA. In Sec. VII-A we show that the ranking based on our theoretical findings in Table I is reflected by our numerical experiments–see Fig. 1

V-C5 Generalizing existing algorithms to the case G≠0G\neq 0

All the algorithms listed in Table I but and are designed for Problem (P) with $G=0$. Since they are special cases of our general framework and Algorithm (4) can deal with the case $G\neq 0$, they inherit the same feature. Their “proximal” extension is given by (III-A), with the matrices $A$, $B$, and $C$ as in original algorithm (cf. Table II). Theorem 18 and Corollary 19 show that these new algorithms enjoy the same convergence rates of their “no-proximal” counterpart. For instance, consider AugDGM, corresponding to Algorithm (24) with $A=B=W^{2},\,D=I,\,C=(I-W)^{2}$; it clearly satisfies Assumption 17 for $W\succ 0$. Its extension to the general optimization with $G\neq 0$ comes readily substituting these choices of $A,B,C$ into (III-A) (or Algorithm 24), yielding

As second example, consider the primal-dual scheme such as NIDS and Exact Diffusion; they correspond to Algorithm (24) with $A=B=\frac{I+W}{2},C=\frac{I-W}{2}$. Similarly, we can introduce their “proximal” version as follows:

V-D Application to statistical learning

We customize our rate results to the instance of (P) modeling statistical learning tasks over networks. This is an example where the local strong convexity and smoothness constants of the agent functions are different; sill, we will show that, when the data sets across the agents are sufficiently similar, the rate achieved by the proposed algorithm is within $\widetilde{\mathcal{O}}(1/\sqrt{n})$ the rate of the centralized gradient algorithm.

where in (a) we used the following two facts: [29, Corollary 6.3.8]

with probability at least $1-\delta$. Therefore, the complexity of our algorithm becomes $\mathcal{O}\left(\left(\frac{\bar{L}}{\bar{\mu}}+\widetilde{\mathcal{O}}\left(\frac{\bar{L}^{2}}{\bar{\mu}^{2}}\frac{1}{\sqrt{n}}\right)\right)\cdot\log\left(\frac{1}{\epsilon}\right)\right)$, with $\widetilde{\mathcal{O}}$ hiding the factor $\log(dm/\delta)$. This shows that when agents have enough data locally ($n$ is large), the above rate is of the same order of that of the centralized gradient descent algorithm.

VI Sublinear Convergence (convex case)

We consider now Problem (P) when $f_{i}$’s are assumed to be convex ($\mu=0$) but not strongly-convex. We study the sublinear convergence for two splitting schemes, namely: i) $T=T_{C}T_{f}T_{B}$ applied to (P) with $G=0$; and ii) $T=T_{C}T_{g}T_{f}T_{B}$ applied to (P) with $G\neq 0$.

We establish sublinear convergence of Algorithm (24) (corresponding to $T=T_{C}T_{f}T_{B}$) under the following assumption.

$D1_{m}=1_{m}$ and $1_{m}^{\top}B=1_{m}^{\top}$;

$C\succeq 0$ and ${\texttt{null}}({C})={\texttt{span}}(1_{m})$;

$I-\frac{1}{2}C-\sqrt{B}D\sqrt{B}\succeq 0$ ($\Leftrightarrow I-\frac{1}{2}C-A\succeq 0$, if $B$ commutes with $D$).

We quantify the progress of algorithms towards optimality in this setting using the following merit function:

where $X^{\star}\triangleq 1_{m}(x^{\star})^{\top}$. Note that the first term encodes consensus errors while the second term measures the optimality gap.

We begin by rewriting Algorithm (24) in an equivalent form given in Lemma 21, which does not have a mixing matrix multiplied to the gradient term.

Suppose Assumption 8 holds. Then, Algorithm (24) can be rewritten as

since $Y^{0}=0$, we know ${\texttt{span}}(X^{1}),{\texttt{span}}(Y^{1})\subset{\texttt{span}}(B)$. It is easy then to deduce from induction that ${\texttt{span}}(X^{k}),\,{\texttt{span}}(Y^{k})\subset{\texttt{span}}(B),\,\forall k.$ Setting $Y^{k}=\gamma B\underline{Y}^{k}$ and $X^{k}=B\underline{X}^{k}$ leads to this equivalent form. ∎

Define $\phi(X,Y)=f(X)+\left\langle Y,X\right\rangle.$ In Lemma 22 and 23 below, we establish two fundamental inequalities on $\phi(X^{k},Y)$ and $\phi(X,Y)$ for $X\in{\texttt{span}}(1_{m})$ and $Y\in{\texttt{span}}(C)$, instrumental to prove the sublinear rate. The proofs can be found in the Appendix.

for all $\,X\in{\texttt{span}}(1_{m})$ and $Y\in{\texttt{span}}(C)$, where $B^{\prime}=(C+bJ)^{-1}B$, $b\geq 2$.

Under the same conditions as in Lemma 22, if $\gamma\leq\frac{\lambda_{\min}(D)}{L}$, then

for all $X\in{\texttt{span}}(1_{m})$ and $Y\in{\texttt{span}}(C)$, where $\widehat{X}^{k}\triangleq\frac{1}{k}\sum_{t=1}^{k}X^{t}$.

We now prove the sublinear convergence rate.

where $\widehat{X}^{k}=\frac{1}{{k}}\sum_{t=1}^{{k}}X^{t}$.

for $Y\in{\texttt{span}}(C)$, where $h(\cdot)=\frac{1}{2k}\Big(\frac{1}{\gamma}\left\|X^{0}-X^{\star}\right\|^{2}_{D}+\gamma\frac{\rho(B-J)}{\lambda_{2}(C)}(\cdot)^{2}\Big)$. Setting $Y=-2\frac{(I-J)\widehat{X}^{k}}{\left\|(I-J)\widehat{X}^{k}\right\|}\left\|Y^{\star}\right\|$, with $Y^{\star}=-\nabla f(X^{\star})$, we have

By the convexity of $f$, $f(\widehat{X}^{k})-f(X^{\star})+\left\langle(I-J)\widehat{X}^{k},Y^{\star}\right\rangle=f(\widehat{X}^{k})-f(X^{\star})+\left\langle\widehat{X}^{k},Y^{\star}\right\rangle\geq 0$, we have $f(\widehat{X}^{k})-f(X^{\star})\geq-\left\|Y^{\star}\right\|\left\|(I-J)\widehat{X}^{k}\right\|$. Combining the above two relations, we have $M(\widehat{X}^{k})\leq h(2\left\|Y^{\star}\right\|).$ This completes the proof. ∎

Finally, we provide the choice of $\gamma$ that optimizes the rate given in Theorem 24.

Consider the setting of Theorem 24. The stepsize that minimizes the right hand side of (36) is

Note that the stepsize in (37) depends on $\left\|X^{0}-X^{\star}\right\|_{D}/\left\|\nabla f(X^{\star})\right\|$, an information that is not generally available; we discuss this issue in Sec. VI-C.

VI-B Convergence under G≠0G\neq 0

We consider now Problem (P) with $G\neq 0$ and $\mu=0$. We study convergence of a variation of the general scheme (4), where the proximal operator is employed before $T_{f}$, yielding the operator decoposiiton $T_{C}T_{g}T_{f}T_{B}$. It is not difficult to check that any fixed point of $T_{C}T_{g}T_{f}T_{B}$ has the same fixed-points of the operator in (16). This scheme reads

Note that a key difference between (4) and the above algorithm is that the former uses in the update of the dual variable $Y$ the variable $Z$, the variable before the operator $\text{prox}_{\gamma g}\left(\cdot\right)$, while the latter uses the variable $X$, i.e., the variable after the operator $\text{prox}_{\gamma g}\left(\cdot\right)$. It is not difficult to check that (39) subsumes many existing proximal-gradient methods, such as PG-EXTRA or ID-FBBS (with $A=W,B=I,C=I-W$). We present a unified result of the sublinear convergence for the algorithm (39), under the following assumption.

$C\succeq 0$ and ${\texttt{null}}({C})={\texttt{span}}(1_{m})$;

Note that the above assumption is, indeed, a customization of Assumption 20. The condition $B=I$ is introduced to deal with the complication of the proximal operator $T_{g}$.

We study convergence of Algorithm (39) using the following merit function measuring the progresses of the algorithms from consensus and optimality. Define

where $Y^{\star}=-\left(\nabla f(X^{\star})+1_{m}(\xi^{\star})^{\top}\right)$, for some $\xi^{\star}\in\partial G(x^{\star})$ such that $\xi^{\star}+\nabla F(x^{\star})=\xi^{\star}+\frac{1}{m}\sum_{i=1}^{m}\nabla f(x^{\star})=0$. Note that, since $1_{m}^{\top}Y^{\star}=0$, we have $Y^{\star}\in{\texttt{span}}(C).$

We are now ready to state our convergence result, whose proof is left to the Appendix due to its similarity to that of Theorem 24.

Consider Problem (P) under Assumption 1 with $\mu=0$; and let $x^{\star}$ be an optimal solution. Let $\{(X^{k},Y^{k})\}_{k\geq 0}$ be the sequence generated by Algorithm (39) under Assumptions 26. Then, if $\gamma<\frac{\lambda_{\min}(D)}{L}$, we have

where $\widehat{X}^{k}=\frac{1}{{k}}\sum_{t=1}^{{k}}X^{t}$.

Consider the setting of Theorem 27. The stepsize that minimizes the right hand side of (40) is

VI-C Discussion

Differently from most of the existing works, such as , the above convergence results (Corollary 25 and 28) establish the explicit dependency of the rate on the network parameter as well as the properties of the cost functions. Specifically, the rate coefficients in (38) and (42) show an explicit dependence on the network and optimization parameters, with the first term on the RHS corresponding to the rate of the centralized optimization algorithm while the second term related to both the communication network and the heterogeneity of the cost functions of the agents (i.e., $\left\|\nabla f(x^{\star})\right\|$). The smaller $\left\|\nabla f(x^{\star})\right\|$, the more similar the objective functions agents have. For instance, when $f_{i}$’s share a common minimizer, i.e., $\left\|\nabla f(x^{\star})\right\|=0$, the rate will reduce to the centralized one. The term $\sqrt{\frac{\rho(B-J)}{\lambda_{2}(C)}}$ accounts for the network effect on the rate. For instance, set $C=I-B$, so that $\lambda_{2}(C)=1-\rho(B-J).$ If $\rho(B-J)\to 0$ (meaning a network tending to a fully connected graph), $\sqrt{\frac{\rho(B-J)}{\lambda_{2}(C)}}\to 0$, leading to the rate of the centralized gradient algorithm [cf. (38)]. On the other hand, if $\rho(B-J)\to 1$ (poorly connected network), $\sqrt{\frac{\rho(B-J)}{\lambda_{2}(C)}}\to+\infty$, deteriorating the overall rate. As a result, when the agents have similar cost functions (i.e., small value of $\left\|\nabla f(x^{\star})\right\|$) or the network is well connected, the first term will dominate the second, leading to the centralized performance. The tightness of the rate expression (Corollary 25) is validated by our numerical results–see Sec. VII-B.

VI-C2 On the choice of stepsize

The optimal stepsize, as indicated in (37) (resp. (41)), is such that the two terms in (36) (resp. (40)) are balanced. Albeit (37) and (41) generally are not implementable, due to the unknown quantity $\left\|X^{0}-X^{\star}\right\|_{D}/\left\|\nabla f(X^{\star})\right\|$, the result is interesting on the theoretical side, showing that the “optimal” stepsize is not necessarily $1/L$ but depends on the the network and the degree of heterogeneity of the cost functions as well. In particular, the optimal choice is $1/L$ when the network is well connected and agents share similar “interests”, i.e., $\left\|\nabla f(x^{\star})\right\|$ is small. On the other hand, as the connectivity of the network becomes worse and/or the heterogeneity of local cost functions becomes larger, stepsize values smaller than $1/L$ ensure better performance. This observation provides recommendations on stepsize tuning and it is validated by our numerical experiments.

VII Numerical Results

We present some numerical results on strongly convex and convex instances of (P), supporting our theoretical findings. The obtained rates bounds are shown to predict well the practical behavior of the algorithms. For instance, the ATC-based schemes exhibit a clear rate separation [as predicted by (29)]: the convergence rate cannot be continuously improved by unilaterally decreasing the difficulty of the problem or increasing the connectivities of the communication matrices.

We consider a regularized least squares problem over an undirected graph consisting of $50$ nodes, generated through the Erdos-Renyi model with activating probability of $0.05$ for each edge. The problem reads

$\bullet$ Validating Table I: Comparison of the “prox”-versions of existing algorithms. In Fig. 2 we compare the “prox” version of several existing algorithms, applied to (43): we plot the optimality gap $\left\|X^{k}-1_{m}x^{\star\top}\right\|$ versus the overall number of iterations (gradient evaluations). The setting is the same as in the previous example, except that now we set $\omega=0.8.$ The stepsize of each algorithm is chosen according to (21). The network is simulated according to the Erdos-Renyi model with a connection probability of $0.25$; in this setting, the max in (29) is achieved at $(\kappa-1)/(\kappa+1)$. It follows from the figure that ATC-based schemes, such as Prox-NEXT/AugDGM, Prox-NIDS, outperform non-ATC ones, such as Prox-EXTRA and Prox-DIGing, validating the ranking established in (the last column of) Table I.

VII-B Non-strongly-convex problems

To illustrate the results for non-strongly convex problems, we report here a logistic regression problem using the Ionosphere Data Set as follows :

VIII Conclusion

We proposed a unified distributed algorithmic framework for composite optimization problems over networks; the framework subsumes many existing schemes. When the agents’ functions are strongly convex, linear convergence is proved leveraging an operator contraction-based analysis. With a proper choice of the design parameters, the rate dependency on the network and cost functions can be decoupled, which permits to achieve the rate of the centralized (proximal)-gradient methods using a finite number of communications per gradient evaluations. Our convergence conditions and rate bounds improve on existing ones. Furthermore, thanks to our unified framework and analysis, a fair comparison and ranking of the different (including existing) schemes were provided. When the functions of the agents are (not strongly) convex, a sublinear convergence rate was established, shading light on the dependency of the convergence on the connectivity of the network and the heterogeneity of the cost functions.

Appendix A Supporting Proofs of Linear Convergence Rate

where $(*)$ is due to [34, Theorem 2.1.12], with $L^{\prime}=\frac{L}{\lambda_{\min}(D)}$ and $\mu^{\prime}=\frac{\mu}{\lambda_{\max}(D)}.$ Thus, knowing that $0<\gamma\leq\frac{2\lambda_{\min}(D)}{L+\mu\cdot\eta(D)}=\frac{2}{L^{\prime}+\mu^{\prime}}$ and continuing from (44), we have

In particular, if we set $\gamma=\gamma^{\star}$, we have $1-2\gamma^{\star}\frac{L^{\prime}\mu^{\prime}}{L^{\prime}+\mu^{\prime}}=\left(\frac{L^{\prime}-\mu^{\prime}}{L^{\prime}+\mu^{\prime}}\right)^{2}=\left(\frac{\kappa-\eta(D)}{\kappa+\eta(D)}\right)^{2}$.

A-B Proof of Theorem 18

Appendix B Supporting Proofs of Sublinear Convergence Rate

where $(a)$ is due to the fact that $f(X)\geq f(X^{k})+\left\langle\nabla f(X^{k}),X-X^{k}\right\rangle$ from the convexity of $f$.

Then, we relate the gradient term $\nabla f(X^{k})$ to other quantities using (33b) as follows

where we have used (33c) to obtain the last relation. Now, substituting the above relation into (45), we further have

Adding $\left\langle Y,X^{k+1}-X\right\rangle$, with $X\in{\texttt{span}}(1_{m})$ and $Y\in{\texttt{span}}(C)$, to both sides of the above equation and noticing $(C+bJ)^{-1}C=I-J$ yields

where we have used (33c) to obtain the last relation. Knowing that $X=B\underline{X}$ from (33a), we complete the proof.

B-B Proof of Lemma 23

where $(a)$ is due to the fact that $\left\|\underline{Y}^{k+1}-\underline{Y}^{k}\right\|^{2}_{B^{\prime}}=\frac{1}{\gamma^{2}}\left\|\underline{X}^{k+1}\right\|^{2}_{BC}$ since $\underline{Y}^{k+1}-\underline{Y}^{k}=1/\gamma C\underline{X}^{k+1}$ and $B^{\prime}C^{2}=(C+bJ)^{-1}C^{2}B=CB$; $(b)$ comes from that $\gamma\leq\frac{\lambda_{\min}(D)}{L}$ and $B-\frac{1}{2}BC-AB=\sqrt{B}\left(I-\frac{1}{2}C-\sqrt{B}D\sqrt{B}\right)\sqrt{B}\succeq 0.$

Then, averaging (47) over $k$ from $0$ to $t-1$, we have

where we used: (a) $Y^{0}=0$ and $\lambda_{\max}\left((C+bJ)^{-1}\right)=1/\lambda_{\min}\left(C+bJ\right)=1/\lambda_{2}(C)$ due to $C\preceq 2I$; (b) $Y\in{\texttt{span}}(1_{m})^{\perp}$. Using the convexity of $\phi$ we complete the proof.

B-C Proof of Theorem 27

Setting $B=I$, Algorithm (39) we study becomes

The structure of this proof is similar to the proof of Theorem 24. We first establish two fundamental inequalities that are valid for any pair $(X,Y)$ such that $X\in{\texttt{span}}(1_{m})$ and $Y\in{\texttt{span}}(C)$ (cf. Lemma 29 and Lemma 30); and then apply these results with $X=X^{\star}$ and two choices of $Y$ to get the result of the sublinear convergence and rate separation.

The proof is similar to that of Lemma 22.

According to $X^{k+1}=\text{prox}_{\gamma g}\left(\underline{X}^{k+1}\right)$, we have $g(X^{k+1})-g(X)\leq\frac{1}{\gamma}\left\langle\underline{X}^{k+1}-X^{k+1},X^{k+1}-X\right\rangle.$ We define $\phi(X,Y)=f(X)+g(X)+\left\langle X,Y\right\rangle.$ Then we have for $X\in{\texttt{span}}(1_{m})$ and $Y\in{\texttt{span}}(C)$,

Under the same conditions as Lemma 29, if $\gamma\leq\frac{\lambda_{\min}(D)}{L}$, then for all $X\in{\texttt{span}}(1_{m})$ and $Y\in{\texttt{span}}(C)$ it holds

where the last step is due to that $I-\frac{C}{2}-D\succeq 0$ and $\gamma\leq\frac{\lambda_{\min}(D)}{L}.$ Then, averaging the above over $k$ from $0$ to $t-1$, we have

Using the convexity of $\phi$ completes the proof. ∎

For notational simplicity, we set $r(X)=f(X)+g(X).$ From (51), we have

where $h(\cdot)=\frac{1}{2t}\Big(\frac{1}{\gamma}\left\|X^{0}-X^{\star}\right\|^{2}_{D}+\gamma\frac{1}{\lambda_{2}(C)}(\cdot)^{2}\Big)$. Now setting $Y=-2\frac{(I-J)\widehat{X}^{t}}{\left\|(I-J)\widehat{X}^{t}\right\|}\left\|Y^{\star}\right\|$. The rest of the proof is similar to that in Theorem 24.

References