Fenchel Dual Gradient Methods for Distributed Convex Optimization over Time-varying Networks
Xuyang Wu Jie Lu





Fenchel Dual Gradient Methods for Distributed Convex Optimization over Time-varying Networks
    Xuyang Wu and Jie LuX. Wu and J. Lu are with the School of Information Science and Technology, ShanghaiTech University, 201210 Shanghai, China. Email: {wuxy, lujie}@shanghaitech.edu.cn. 
This work has been supported by the National Natural Science Foundation of China under grant 61603254, the Shanghai Pujiang Program under grant 16PJ1406400, and the Natural Science Foundation of Shanghai under grant 16ZR1422500.
    December 7, 2017
===================================================================================================================================================================================================================================================================================================================================================================================================================================




In the large collection of existing distributed algorithms for convex multi-agent optimization, only a handful of them provide convergence rate guarantees on agent networks with time-varying topologies, which, however, restrict the problem to be unconstrained. Motivated by this, we develop a family of distributed Fenchel dual gradient methods for solving constrained, strongly convex but not necessarily smooth multi-agent optimization problems over time-varying undirected networks. The proposed algorithms are constructed based on the application of weighted gradient methods to the Fenchel dual of the multi-agent optimization problem, and can be implemented in a fully decentralized fashion. We show that the proposed algorithms drive all the agents to both primal and dual optimality asymptotically under a minimal connectivity condition and at sublinear rates under a standard connectivity condition. Finally, the competent convergence performance of the distributed Fenchel dual gradient methods is demonstrated via simulations.












§ INTRODUCTION


In many engineering scenarios, a network of agents often need to jointly make a decision so that a global cost consisting of their local costs is minimized and certain global constraints are satisfied. Such a multi-agent optimization problem has found a considerable number of applications, such as estimation by sensor networks <cit.>, network resource allocation <cit.>, and cooperative control <cit.>.

To address convex multi-agent optimization in an efficient, robust, and scalable way, distributed optimization algorithms have been substantially exploited, which allow each agent to reach an optimal or suboptimal decision by repeatedly exchanging its own information with neighbors <cit.>. One typical approach is to let the agents perform consensus operations so as to mix their decisions that are updated using first-order information of their local objectives (e.g., <cit.>). Recently, rates of convergence to optimality have been established for a few consensus-based algorithms. By assuming that the problem is unconstrained and smooth (i.e., the gradient of each local objective is Lipschitz) and that the network is fixed, the consensus-based multi-step gradient methods <cit.> are able to achieve sublinear rates of convergence, and also linear rates if the local objectives are further (restricted) strongly convex. Unlike these algorithms, the Subgradient-Push method <cit.>, the Gradient-Push method <cit.>, the DIGing algorithm <cit.>, and the Push-DIGing algorithm <cit.> can be implemented over time-varying networks and still provide convergence rate guarantees. Specifically, Subgradient-Push converges to optimality at a sublinear rate of O(ln k/√(k)) for unconstrained, nonsmooth problems with bounded subgradients <cit.>. In addition, when the problem is unconstrained, strongly convex, and smooth, an O(ln k/k) rate is established for Gradient-Push <cit.>, and linear rates are provided for DIGing and Push-DIGing <cit.>.

Another standard approach is to utilize dual decomposition techniques, which often lead to a dual problem with a decomposable structure, so that it can be solved in a distributed fashion by classic optimization methods including the gradient projection method, the accelerated gradient methods, the method of multipliers, and their variants (e.g., <cit.>). Compared with the aforementioned consensus-based primal methods, many distributed dual/primal-dual algorithms can handle more complicated coupling constraints, yet still manage to achieve sublinear rates of convergence to dual and primal optimality when the dual function is smooth, and achieve linear rates when the dual function is also strongly concave. Despite this advantage, most of such methods require a fixed network topology. Although the primal-dual subgradient methods in <cit.>, the primal-dual perturbation method in <cit.>, and the proximal-minimization-based method in <cit.> cope with time-varying agent networks, they only guarantee asymptotic convergence to optimality and no results on convergence rate are provided. In addition to the above two approaches, there are other lines of research on distributed optimization, including incremental optimization methods (e.g., <cit.>), 
distributed Newton methods (e.g., <cit.>), 
and continuous-time distributed optimization algorithms (e.g., <cit.>).

This paper is motivated by the lack of distributed optimization algorithms in the literature that are able to address constrained convex multi-agent optimization at a guaranteed convergence rate over time-varying networks. We propose, in this paper, a family of distributed Fenchel dual gradient methods that are able to solve a class of constrained multi-agent optimization problems at sublinear rates on time-varying undirected networks, where the local objectives of the agents are strongly convex but not necessarily differentiable and the global constraint is the intersection of the local convex constraints of the agents. 

To develop such algorithms, we first derive the Fenchel dual of the multi-agent optimization problem, which consists of a separable, smooth dual function and a coupling linear constraint. Additionally, the gradient of the Fenchel dual function can be evaluated in parallel by the agents. We then utilize a class of weighted gradient methods to solve the Fenchel dual problem, which can be implemented over time-varying networks in a distributed fashion and can be viewed as a generalization of the distributed weighted gradient methods in <cit.>. We show that the proposed Fenchel dual gradient algorithms asymptotically converge to both dual and primal optimality if the agents and their infinitely occurring interactions form a connected graph. We also show that the dual optimality is reached at an O(1/k) rate and the primal optimality is achieved at an O(1/√(k)) rate if the underlying agent interaction graph during every B iterations is connected. Finally, the efficacy of the Fenchel dual gradient methods is illustrated through numerical examples.

The outline of the paper is as follows: Section <ref> formulates the multi-agent optimization problem, and Section <ref> develops the distributed Fenchel dual gradient methods. Section <ref> establishes the convergence results of the proposed algorithms. Section <ref> presents simulation results, and Section <ref> concludes the paper. All the proofs are included in the appendix. This paper is a significantly improved version of an earlier, 6-page conference paper <cit.>.

Throughout the paper, we use · to represent the Euclidean norm and ·_1 the ℓ_1 norm. For any set X⊆ℝ^d, intX represents its interior and |X| its cardinality. Let P_X(x)=arg min_y∈ Xx-y denote the projection of x∈ℝ^d onto X, which uniquely exists if X is closed and convex. The ball centered at x∈ℝ^d with radius r>0 is denoted by B(x,r):={y∈ℝ^d:y-x≤ r}. The floor of a real number is represented by ⌊·⌋. For any 𝐱∈ℝ^nd, 𝐱=(x_1^T,…,x_n^T)^T means the even partition of 𝐱 into n blocks, i.e., x_i∈ℝ^d ∀ i=1,…,n. For any function f:ℝ^d→ℝ, ∂ f(x) denotes any subgradient of f at x∈ℝ^d, i.e., f(y)-f(x)-∂ f(x)^T(y-x)≥0 ∀ y∈ℝ^d. If f is differentiable, then ∇ f(x) denotes the gradient of f at x∈ℝ^d. In addition, I_d is the d× d identity matrix, O_d is the d× d zero matrix, 1_d∈ℝ^d is the all-one vector, 0_d∈ℝ^d is the all-zero vector, and ⊗ is the Kronecker product. For any matrices M,M'∈ℝ^n× n, M≼ M' and M'≽ M both mean M'-M is positive semidefinite. Also, [M]_ij represents the (i,j)-entry of M, ℛ(M) the range of M, and Null(M) the null space of M. If M is a block diagonal matrix with diagonal blocks M_1,…,M_m, we write it as M=diag(M_1,…,M_m). If M is symmetric positive semidefinite, we use λ_i^↓(M)≥0 to denote its ith largest eigenvalue and M^† its Moore-Penrose pseudoinverse. 









§ PROBLEM FORMULATION


Consider a set 𝒱={1,2,…,n} of agents, where each agent i∈𝒱 possesses a local objective function f_i:ℝ^d→ℝ and a local constraint set X_i⊆ℝ^d. All of the n≥2 agents attempt to solve the constrained optimization problem

    [       x∈ℝ^d ∑_i∈𝒱f_i(x);  subject to x∈⋂_i∈𝒱X_i, ]

which satisfies the following assumption.


(a) Each f_i, i∈𝒱 is strongly convex over X_i with convexity parameter θ_i>0, i.e., for any x,y∈ X_i and any subgradient ∂ f_i(x) of f_i at x, f_i(y)-f_i(x)-∂ f_i(x)^T(y-x)≥θ_iy-x^2/2.

(b) 0_d∈int⋂_i∈𝒱X_i.


Assumption <ref> ensures the existence of a unique optimal solution x^⋆∈⋂_i∈𝒱X_i to problem (<ref>). Notice that Assumption <ref>(a) is a common assumption for distributed optimization methods with convergence rate guarantees (e.g., <cit.>). In addition, unlike many existing works that require each f_i to be continuously differentiable (e.g., <cit.>), here each f_i is not necessarily differentiable. Also, Assumption <ref>(b) can always be replaced with the less restrictive condition int⋂_i∈𝒱X_i≠∅, which is also assumed in <cit.>. To see this, suppose x'∈int⋂_i∈𝒱X_i for some x'≠0_d. Consider the change of variable z=x-x', and write each f_i(x) and X_i as f_i(z+x') and {z∈ℝ^d:z+x'∈ X_i}, respectively. Then, the resulting new problem with the decision variable z is in the form of (<ref>) and satisfies Assumption <ref>.

We model the n agents and their interactions as an undirected graph 𝒢^k=(𝒱,ℰ^k) with time-varying topologies, where k∈{0,1,…} represents time, 𝒱={1,2,…,n} is the set of nodes (i.e., the agents), and ℰ^k⊆{{i,j}:i,j∈𝒱,i≠ j} is the set of links (i.e., the agent interactions) at time k. Without loss of generality, we assume that ℰ^k≠∅ ∀ k≥0. In addition, for each node i∈𝒱, let 𝒩_i^k={j∈𝒱:{i,j}∈ℰ^k} be the set of its neighbors (i.e., the nodes that it directly communicates with) at time k.

To enable cooperation of the nodes, we need to impose an assumption on network connectivity, so that the local decisions of the nodes can be mixed across the network. To this end, define ℰ_∞:={{i,j}:{i,j}∈ℰ^k for infinite many k≥ 0}. Then, consider the following assumption.

[Infinite connectivity]
The graph (𝒱, ℰ_∞) is connected.


Assumption <ref> is equivalent to the connectivity of the graph (𝒱,∪_t=k^∞ℰ^t) for all k≥0. This is a minimal connectivity condition for distributed optimization algorithms to converge to optimality, which ensures every node to directly or indirectly influence any other nodes infinitely many times <cit.>. As Assumption <ref> does not quantify how quickly the local decisions of the nodes diffuse throughout the network, we need a stronger connectivity condition to derive performance guarantees for the algorithms to be developed.

[B-connectivity]
There exists an integer B>0 such that for any integer k≥0, the graph (𝒱,⋃_t=kB^(k+1)B-1ℰ^t) is connected.


Assumption <ref> forces each node to have an impact on the others in the time intervals [kB,(k+1)B-1] ∀ k≥0 of length B. Compared with Assumption <ref>, Assumption <ref> is more restrictive but more commonly adopted in the literature (e.g., <cit.>). 










§ FENCHEL DUAL GRADIENT ALGORITHMS


In this section, we develop a family of distributed algorithms to solve (<ref>) based on Fenchel duality.



 §.§ Fenchel Dual Problem


We first transform (<ref>) into the following equivalent problem:

    [              𝐱∈ℝ^nd F(𝐱):=∑_i∈𝒱f_i(x_i);          subject to   x_i∈ X_i,  ∀ i∈𝒱,;                                   𝐱∈ S, ]

where 𝐱=(x_1^T,…,x_n^T)^T and S:={𝐱∈ℝ^nd:x_1=x_2=⋯=x_n}. Note that problem (<ref>) has a unique optimal solution 𝐱^⋆=((x^⋆)^T,…,(x^⋆)^T)^T, where x^⋆∈⋂_i∈𝒱X_i is the unique optimum of problem (<ref>). In addition, its optimal value F^⋆ is equal to that of problem (<ref>).

Next, we construct the Fenchel dual problem <cit.> of (<ref>). To this end, we introduce a function q_i:ℝ^d×ℝ^d→ℝ for each i∈𝒱 defined as

    q_i(x_i,w_i)=w_i^Tx_i-f_i(x_i).

The conjugate convex function d_i:ℝ^d→ℝ is then given by

    d_i(w_i) = sup_x_i∈ X_iq_i(x_i,w_i).

With the above, the Fenchel dual problem of (<ref>) can be described as

    [                 𝐰∈ℝ^nd -D(𝐰):=-∑_i∈𝒱 d_i(w_i);             subject to                 𝐰∈ S^, ]

where 𝐰=(w_1^T,…,w_n^T)^T and S^:={𝐰∈ℝ^nd:w_1+w_2+⋯+w_n=0_d} is the orthogonal complement of S. Note that (<ref>) is a convex optimization problem. Also, with Assumption <ref>, it can be shown that strong duality between (<ref>) and (<ref>) holds, i.e., the optimal value -D^⋆ of (<ref>) equals F^⋆, and that the optimal set of (<ref>) is nonempty <cit.>. Moreover, 𝐰^⋆=((w_1^⋆)^T,…,(w_n^⋆)^T)^T∈ S^ is an optimal solution to (<ref>) if and only if ∇ d_i(w_i^⋆)=∇ d_j(w_j^⋆) ∀ i,j∈𝒱 <cit.>, i.e., ∇ D(𝐰^⋆)∈ S.

Below we acquire a couple of properties regarding the Fenchel dual problem (<ref>). Notice from Assumption <ref>(a) that for each i∈𝒱 and each w_i∈ℝ^d, there uniquely exists

    x̃_i(w_i):=arg max_x∈ X_i q_i(x,w_i).

Thus, d_i is differentiable <cit.> and

    ∇ d_i(w_i) = x̃_i(w_i).

The following proposition shows that d_i is smooth, i.e., ∇ d_i is Lipschitz.

<cit.>
Suppose Assumption <ref> holds. Then, for each i∈𝒱, ∇ d_i is Lipschitz continuous with Lipschitz constant L_i=1/θ_i, where θ_i>0 is defined in Assumption <ref>, i.e., ∇ d_i(u_i)-∇ d_i(v_i)≤ L_iu_i-v_i ∀ u_i,v_i∈ℝ^d.


In fact, the strong convexity of f_i on X_i assumed in Assumption <ref>(a) is both sufficient and necessary for the smoothness of d_i <cit.>. 

Likewise, we can see that D(𝐰) is differentiable and

    ∇ D(𝐰)=𝐱̃(𝐰):=(x̃_1(w_1)^T,…,x̃_n(w_n)^T)^T.

According to (<ref>) and (<ref>), if each w_i is known to node i, then the gradient of the Fenchel dual function D can be evaluated in parallel by the nodes, while the Lagrange dual of (equivalent forms of) problem (<ref>) does not have such a favorable feature when the network is time-varying and not necessarily connected at each time instance. Further, notice that F(𝐱) in problem (<ref>) is strongly convex over X_1×⋯× X_n with convexity parameter θ_min:=min_i∈𝒱θ_i. Also note that D(𝐰)=sup_𝐱∈ X_1×⋯× X_n𝐰^T𝐱-F(𝐱). Like Proposition <ref>, we can establish the Lipschitz continuity of ∇ D.


Suppose Assumption <ref> holds. Then, ∇ D is Lipschitz continuous with Lipschitz constant L=1/θ_min.


Finally, we show that the dual optimal set and the level sets of D on S^ are bounded.

Suppose Assumption <ref> holds. For any optimal solution 𝐰^⋆∈ S^ of problem (<ref>),

    𝐰^⋆≤(∑_i∈𝒱max_x_i∈ B(0_d,r_c)f_i(x_i))-F^⋆/r_c<∞,

where r_c∈(0,∞) is such that B(0_d,r_c)⊆⋂_i∈𝒱X_i. In addition, for any 𝐰∈ S^, the level set S_0(𝐰):={𝐰'∈ S^:D(𝐰')≤ D(𝐰)} is compact.



See Appendix <ref>.


The boundedness of the dual optimal set relies on the nonemptyness of int⋂_i∈𝒱X_i assumed by Assumption <ref>(b), without which the dual optimal set can be unbounded (e.g., X_i={(z_1,z_2)^T∈ℝ^2:z_1=0} ∀ i∈𝒱).



 §.§ Algorithms


In <cit.>, a set of weighted gradient methods are proposed to solve a network resource allocation problem, which can be cast in the form of (<ref>). Inspired by this, we consider a class of weighted gradient methods as follows: Starting from an arbitrary 𝐰^0∈ S^, the subsequent iterates are generated by

    𝐰^k+1=𝐰^k-α^k(H_𝒢^k⊗ I_d)∇ D(𝐰^k),  ∀ k≥0,

where α^k>0 is the step-size and H_𝒢^k∈ℝ^n× n is the weight matrix that depends on the topology of 𝒢^k, defined as

    [H_𝒢^k]_ij=∑_s∈𝒩_i^k h_is^k,    if i=j,
    -h_ij^k,   if {i,j}∈ℰ^k,
    0,    otherwise,  ∀ i,j∈𝒱.

We require h_ij^k=h_ji^k>0 ∀{i,j}∈ℰ^k ∀ k≥0. We also assume that there exists a finite interval [h,h̅] such that

    h_ij^k∈ [h,h̅]⊂(0,∞),  ∀ k≥0, ∀ i∈𝒱, ∀ j∈𝒩_i^k.

Since ℰ^k≠∅, H_𝒢^k≠ O_n for any k≥0. Moreover, H_𝒢^k is symmetric positive semidefinite and H_𝒢^k1_n=0_n. Thus, using the same rationale as <cit.>, the proposition below shows that as long as 𝐰^0 is feasible, so are 𝐰^k ∀ k≥1.


Let (𝐰^k)_k=0^∞ be the iterates generated by (<ref>). If 𝐰^0∈ S^, then (𝐰^k)_k=0^∞⊆ S^.



The weighted gradient method (<ref>) can be tuned to solve problems of minimizing ∑_i∈𝒱d_i(w_i) subject to ∑_i∈𝒱w_i=c, ∀ c∈ℝ^d. To do so, we can simply replace the initial condition 𝐰^0∈ S^ with ∑_i∈𝒱w_i^0=c.


Next, we introduce primal iterates to the weighted gradient method (<ref>) that is intended for the Fenchel dual problem (<ref>). Note from (<ref>) and (<ref>) that (<ref>) can be written as

    x_i^k=x̃_i(w_i^k),  ∀ i∈𝒱,[0]
       w_i^k+1=w_i^k-α^k∑_j∈𝒩_i^kh_ij^k(x_i^k-x_j^k),  ∀ i∈𝒱,

where w_i^k∈ℝ^d is the ith d-dimensional block of 𝐰^k and x̃_i(w_i^k) is defined in (<ref>). We assign each w_i^k and x_i^k to node i as its dual and primal iterates, with x_i^k being node i's estimate on the optimal solution x^⋆ of problem (<ref>). Thus, the above algorithm with both dual and primal iterates can be implemented in a distributed and possibly asynchronous way on the time-varying network, as is shown in Algorithm <ref>.





In Algorithm <ref>, the initial condition 𝐰^0∈ S^ can simply be realized by setting w_i^0=0_d ∀ i∈𝒱. Subsequently at each iteration, every node i with at least one neighbor updates its dual iterate w_i^k via local interactions with its current neighbors and then updates its primal iterate x_i^k on its own. 

To implement Algorithm <ref>, each node i needs to select the weights h_ij^k ∀ j∈𝒩_i^k that satisfy h_ij^k=h_ji^k in a predetermined interval [h,h̅]⊂(0,∞), where h and h̅ may or may not be related with 𝒢^k ∀ k≥0. This can be done through inexpensive interactions between neighboring nodes. Two typical examples of H_𝒢^k are the graph Laplacian matrix

    [H_𝒢^k]_ij=[L_𝒢^k]_ij:=|𝒩_i^k|,    if i=j,
    -1,   if {i,j}∈ℰ^k,
    0,    otherwise,

and the Metropolis weight matrix <cit.>

    [H_𝒢^k]_ij=∑_s∈𝒩_i^k1/max{|𝒩_i^k|L_i, |𝒩_s^k|L_s},    if i=j,
    -1/max{|𝒩_i^k|L_i, |𝒩_j^k|L_j},   if {i,j}∈ℰ^k,
    0,    otherwise.

When H_𝒢^k is set to (<ref>), each node i does not need any additional efforts in computing the weights h_ij^k ∀ j∈𝒩_i^k since they are 1 by default. When H_𝒢^k is set to (<ref>), each node i only needs to obtain from every neighbor j∈𝒩_i^k the product of node j's neighborhood size |𝒩_j^k| and Lipschitz constant L_j=1/θ_j of ∇ d_j. 

The remaining parameter to be determined is the step-size α^k. Later in Section <ref>, we will show that the following step-size condition is sufficient to guarantee the convergence of Algorithm <ref>: Suppose there is a finite interval [α,α̅] such that

    α^k∈[α,α̅]⊂(0,2/δ),  ∀ k≥0,

where δ>0 can be any positive constant satisfying

    H_𝒢^k≼δΛ_L^-1,  ∀ k≥ 0,

with Λ_L:=diag(L_1,…,L_n).
Note that such δ always exists because Λ_L^-1 is positive definite and H_𝒢^k is positive semidefinite. For example, we may choose δ=Lsup_k≥ 0λ_1^↓(H_𝒢^k), where L=1/θ_min=max_i∈𝒱L_i. More conservatively, because H_𝒢^k≼h̅L_𝒢^k and λ_1^↓(L_𝒢^k)≤ n, we can always let δ=Lh̅n and thus

    [α,α̅]⊂(0,2/Lh̅n).

Since h̅ can be predetermined and known to all the nodes, this condition only requires the nodes to obtain the global quantities n and L=max_i∈𝒱L_i, which can be computed decentralizedly by some consensus schemes (e.g., <cit.>). Below, we provide less conservative step-size conditions for the two specific choices of H_𝒢^k in (<ref>) and (<ref>), which also can be satisfied by the nodes without any centralized coordination.


When H_𝒢^k is set to the graph Laplacian matrix L_𝒢^k as in (<ref>), in addition to the aforementioned choice δ=Lsup_k≥ 0λ_1^↓(L_𝒢^k), another option for δ could be δ=2sup_k≥0max_i∈𝒱|𝒩_i^k|L_i, so that δΛ_L^-1-L_𝒢^k is diagonally dominant and thus positive semidefinite for each k≥ 0. Therefore, α^k can be selected in the interval [α,α̅] satisfying

    0<α≤α̅<   1/min{L/2sup_k≥ 0λ_1^↓(L_𝒢^k),sup_k≥0max_i∈𝒱|𝒩_i^k|L_i}.

The above step-size condition can be simplified for some special interaction patterns. For instance, if the nodes interact in a gossiping pattern, i.e., each ℰ^k contains only one link, then we may let 0<α≤α̅<1/L.
Even though the topologies of (𝒢^k)_k=0^∞ are completely unknown, since λ_1^↓(L_𝒢^k)≤ n, we can adopt a more conservative step-size condition 0<α≤α̅<2/(nL). 



When H_𝒢^k is set according to (<ref>), we can simply take δ=2, because 2Λ_L^-1-H_𝒢^k is diagonally dominant and thus 2Λ_L^-1≽ H_𝒢^k. Hence, the step-sizes can be selected as

    0<α≤α^k≤α̅<1,  ∀ k≥0,

which requires no global information and is independent of the network and the problem.


The underlying weighted gradient method (<ref>) in Algorithm <ref> can be viewed as a generalization of the distributed weighted gradient methods in <cit.>. By assuming the (directed) network to be time-invariant and connected, <cit.> proposes a class of weighted gradient methods in the form of (<ref>) but with a constant weight matrix. It is also shown in <cit.> that if the time-invariant network is further undirected, the constant weight matrix can be determined in a distributed fashion via (<ref>) or (<ref>). The step-size conditions in <cit.> for fixed undirected networks and fixed weight matrices given by (<ref>) and (<ref>) are extended here in Examples <ref> and <ref> to handle time-varying networks and time-varying weight matrices. On the other hand, <cit.> considers time-varying undirected networks satisfying Assumption <ref>. By setting H_𝒢^k to L_𝒢^k in (<ref>) and α^k=1/(2nL) ∀ k≥0, (<ref>) reduces to the algorithm in <cit.>. Note from Example <ref> that here we allow for a much broader step-size range for this particular weight matrix.







§ CONVERGENCE ANALYSIS


This section is dedicated to analyzing the convergence performance of Algorithm <ref>.








 §.§ Asymptotic convergence under infinite connectivity


In this subsection, we show that Algorithm <ref> asymptotically converges to the optimum of problem (<ref>) under Assumption <ref>. 

We first show that the step-size condition (<ref>) ensures (D(𝐰^k))_k=0^∞ to be non-increasing.


Suppose Assumption <ref> holds. Let (𝐰^k)_k=0^∞ be the dual iterates generated by Algorithm <ref>. If the step-sizes (α^k)_k=0^∞ satisfy (<ref>), then for each k≥0,

    D(𝐰^k+1)-D(𝐰^k)≤-ρ∇ D(𝐰^k)^T(H_𝒢^k⊗ I_d)∇ D(𝐰^k),

where ρ:=min{α-α^2δ/2, α̅-α̅^2δ/2}∈(0,∞), with α,α̅>0 in (<ref>) and δ>0 in (<ref>).



See Appendix <ref>.


Lemma <ref>, along with Propositions <ref> and <ref>, implies that for each k≥0, 𝐰^k∈ S_0(𝐰^0) and 𝐰^k-𝐰^⋆≤ M_0, where 𝐰^⋆ is any optimum of problem (<ref>) and

    M_0:=max_𝐰∈ S_0(𝐰^0), 𝐰^⋆∈ S^:D(𝐰^⋆)=D^⋆𝐰-𝐰^⋆∈[0,∞).

Another important consequence of Lemma <ref> is that the differences of the primal iterates along the time-varying links are vanishing. To see this, by adding the inequality in Lemma <ref> from k=0 to ∞,

    ∑_k=0^∞⟨𝐱^k,(H_𝒢^k⊗I_d)𝐱^k⟩   =∑_k=0^∞⟨∇ D(𝐰^k),(H_𝒢^k⊗I_d)∇ D(𝐰^k)⟩[0]
       ≤(D(𝐰^0)-D^⋆)/ρ<∞,

where 𝐱^k=((x_1^k)^T,…,(x_n^k)^T)^T. This implies that ⟨𝐱^k,(H_𝒢^k⊗ I_d)𝐱^k⟩→ 0 as k→∞. Since
⟨𝐱^k, (H_𝒢^k⊗ I_d)𝐱^k⟩= ∑_{i,j}∈ℰ^k h_ij^kx_i^k-x_j^k^2 and h_ij^k≥h>0 ∀{i,j}∈ℰ^k, we have

    lim_k→∞max_{i,j}∈ℰ^kx_i^k-x_j^k=0.

Because 𝒢^k may not be connected at each k≥0, (<ref>) alone is insufficient to assert that the primal iterates x_i^k ∀ i∈𝒱 asymptotically reach a consensus. Nevertheless, by integrating (<ref>) with Assumption <ref>, we are able to show in Lemma <ref> below that such an assertion is indeed true. The main idea of proving this can be summarized as follows: By (<ref>) we know that x_i^k-x_j^k ∀{i,j}∈ℰ^k can be arbitrarily small after some time T≥0. Then, instead of studying the differences x_i^k-x_j^k ∀ i,j∈𝒱 across the entire network, we show that such differences within each connected component of the graph (𝒱,∪_t=T^kℰ^t) become sufficiently small after some k≥ T. Finally, note from Assumption <ref> that the graph (𝒱,∪_t=T^kℰ^t) must be connected when k≥ T is sufficiently large. The dissipation of the differences among all the x_i^k's can thus be concluded.


Suppose Assumptions <ref> and <ref> hold. Let (𝐱^k)_k=0^∞ be the primal iterates generated by Algorithm <ref>. If the step-sizes (α^k)_k=0^∞ satisfy (<ref>), then lim_k→∞max_i,j∈𝒱x_i^k-x_j^k=0.



See Appendix <ref>.


Since x_i^k∈ X_i ∀ i∈𝒱, 𝐱^k is feasible if and only if 𝐱^k∈ S. Thus, P_S^(𝐱^k) can be used to quantify the infeasibility of 𝐱^k. Note that P_S^(𝐱^k)^2=𝐱^k-P_S(𝐱^k)^2=∑_i∈𝒱x_i^k-1/n∑_j∈𝒱x_j^k^2≤1/n∑_i∈𝒱∑_j∈𝒱x_i^k-x_j^k^2. It follows from Lemma <ref> that P_S^(𝐱^k)^2→ 0 as k→∞. This can further be utilized to establish the asymptotic convergence to both dual and primal optimality, as is shown in the theorem below.


Suppose Assumptions <ref> and <ref> hold. Let (𝐰^k)_k=0^∞ and (𝐱^k)_k=0^∞ be the dual and primal iterates generated by Algorithm <ref>, respectively. If the step-sizes (α^k)_k=0^∞ satisfy (<ref>), then lim_k→∞P_S^(𝐱^k)=0, lim_k→∞D(𝐰^k)=D^⋆, lim_k→∞F(𝐱^k)=F^⋆, and lim_k→∞𝐱^k= 𝐱^⋆.



See Appendix <ref>.










 §.§ Convergence rates under B-connectivity


In this subsection, we offer sublinear rates of convergence for Algorithm <ref> under Assumption <ref>.

Inspired from <cit.>, we first provide a bound on the accumulative drop in the value of D over each time interval [tB,(t+1)B-1], t∈{0,1,…}, which depends only on the dual iterate at time tB and the underlying interaction graph during these B iterations. To this end, for each k≥0, let 𝒢̃^k=(𝒱,ℰ̃^k) be any spanning subgraph of (𝒱, ⋃_t=k^k+B-1ℰ^t), which, owing to Assumption <ref>, is chosen to be connected at k∈{0,B,2B,…}. Also let ϖ^k be the maximum degree of 𝒢̃^k and ϖ̅:=sup_t∈{0,1,…}ϖ^tB. Clearly, 1≤ϖ^tB≤ϖ̅≤ n-1 ∀ t∈{0,1,…}. 


Suppose Assumptions <ref> and <ref> hold. Let (𝐰^k)_k=0^∞ be the dual iterates generated by Algorithm <ref>. If the step-sizes (α^k)_k=0^∞ satisfy (<ref>), then for each k∈{0,B,2B,…},

    ∑_t=k^k+B-1∇ D(𝐰^t)^T(H_𝒢^t⊗ I_d)∇ D(𝐰^t)≥∇ D(𝐰^k)^T(L_𝒢̃^k⊗ I_d)∇ D(𝐰^k)/η,

where η:=3Bϖ̅α̅^2δ L+3/h∈(0,∞), with α̅>0 in (<ref>), δ>0 in (<ref>), L>0 in Corollary <ref>, and h>0 in (<ref>).



See Appendix <ref>.


When H_𝒢^k=L_𝒢^k and α^k=1/(2nL), <cit.> provides a similar bound to (<ref>) with η replaced by 3B/2 and 𝒢̃^k being a spanning tree. Lemma <ref> improves this bound since η≤ 3B/4+3 for such a particular choice of H_𝒢^k and α^k, allows for more general selections of H_𝒢^k and α^k, and sheds light on how the network topologies come into play.

Lemma <ref> and Lemma <ref> together bound the decrease in the value of D during every B iterations, with which we are able to provide a rate for D(𝐰^k)→ D^⋆. Prior to doing that, we define a sequence (M̃_k)_k=0^∞ as follows: Let M̃_0∈ℝ be any positive constant and define

    M̃_k=max_t=0,…,k-1min_𝐰^⋆∈ S^:D(𝐰^⋆)=D^⋆𝐰^tB-𝐰^⋆, ∀ k≥1.

Notice that 0≤M̃_k≤ M_0<∞, where M_0 is given by (<ref>). 


Suppose Assumptions <ref> and <ref> hold. Let (𝐰^k)_k=0^∞ be the dual iterates generated by Algorithm <ref>. If the step-sizes (α^k)_k=0^∞ satisfy (<ref>), then for each k≥0,

    D(𝐰^k)-D^⋆   ≤ηM̃_⌊ k/B⌋^2(D(𝐰^0)-D^⋆)/ηM̃_⌊ k/B⌋^2+ρλ(D(𝐰^0)-D^⋆)⌊ k/B⌋,

where M̃_⌊ k/B⌋∈ [0,M_0] is defined in (<ref>) with M_0≥0 in (<ref>), λ:=inf_t∈{0,1,…}λ_n-1^↓(L_𝒢̃^tB)∈(0,∞), and η,ρ>0 are given in Lemma <ref> and Lemma <ref>, respectively.



See Appendix <ref>.


Theorem <ref> says that Algorithm <ref>, or equivalently, the underlying weighted gradient method (<ref>), converges to the optimal value D^⋆ of problem (<ref>) at an O(1/k) rate. The derivation of this result requires each d_i to be smooth and the dual optimal set to be compact. These two conditions on problem (<ref>) may not hold if Assumption <ref> is not satisfied (cf. Section <ref>). Note that without the compactness of the dual optimal set, (<ref>) still holds, but we cannot guarantee (𝐰^k)_k=0^∞ and thus M̃_⌊ k/B⌋ ∀ k≥0 to be bounded.

The distributed weighted gradient methods in <cit.> also require the above two conditions on problem (<ref>) to establish their convergence to D^⋆. By imposing an additional assumption that the Hessian matrices of d_i ∀ i∈𝒱 are positive definite, the methods in <cit.> are proved to achieve linear convergence rates on fixed networks. In contrast, Theorems <ref> and <ref> allow for time-varying networks and do not even require the existence of the Hessian matrices of d_i ∀ i∈𝒱. The algorithm in <cit.> is shown to asymptotically drive D(𝐰^k) to D^⋆ and satisfy min_t=1,…,kP_S^(∇ D(𝐰^tB))^2≤ C· n^3B/k for some C>0. Our results in Theorems <ref> and <ref> for the more general algorithm (<ref>) are still stronger. We show that lim_k→∞D(𝐰^k)=D^⋆ under the less restrictive Assumption <ref>, and that D(𝐰^k) converges to D^⋆ at an O(1/k) rate under Assumption <ref>. Also, since ∇ D(𝐰^k)=𝐱^k, the first inequality in Theorem <ref> below is comparable to and slightly stronger than the aforementioned convergence rate in <cit.>.

Based on Theorem <ref>, below we show that the primal errors 𝐱^k-𝐱^⋆ and |F(𝐱^k)-F^⋆| in optimality and P_S^(𝐱^k) in feasibility all converge to zero at rates of O(1/√(k)). Like many Lagrange dual gradient methods (e.g., <cit.>), we do so by relating such primal errors with the dual error D(𝐰^k)-D^⋆.


Suppose Assumptions <ref> and <ref> hold. Let (𝐱^k)_k=0^∞ be the primal iterates generated by Algorithm <ref>. If the step-sizes (α^k)_k=0^∞ satisfy (<ref>), then for each k≥0,

    P_S^(𝐱^k)≤𝐱^k-𝐱^⋆≤√(2LηM̃_⌊ k/B⌋^2(D(𝐰^0)-D^⋆)/ηM̃_⌊ k/B⌋^2+ρλ(D(𝐰^0)-D^⋆)⌊ k/B⌋),[0]
       F(𝐱^k)-F^⋆≤𝐰^k√(2LηM̃_⌊ k/B⌋^2(D(𝐰^0)-D^⋆)/ηM̃_⌊ k/B⌋^2+ρλ(D(𝐰^0)-D^⋆)⌊ k/B⌋),[0]
       F(𝐱^k)-F^⋆≥-𝐰^⋆√(2LηM̃_⌊ k/B⌋^2(D(𝐰^0)-D^⋆)/ηM̃_⌊ k/B⌋^2+ρλ(D(𝐰^0)-D^⋆)⌊ k/B⌋),

where 𝐰^⋆ is any optimal solution of problem (<ref>), L is given in Corollary <ref>, and the remaining constants have been introduced in Theorem <ref>.



See Appendix <ref>.


Since 𝐰^k∈ S_0(𝐰^0) ∀ k≥0 and S_0(𝐰^0) is compact, the term 𝐰^k that appears in the convergence rate of F(𝐱^k)-F^⋆ is uniformly bounded above by M_0+𝐰^⋆. Consequently, the primal convergence rates of Algorithm <ref> in Theorem <ref> are all of order O(1/√(k)), which commensurate with the convergence rate of the classic (centralized) subgradient projection method <cit.>. 

In the final part of this section, we compare the primal convergence rates of Algorithm <ref> with those of the existing distributed optimization algorithms that also have guaranteed convergence rates over time-varying networks, including Subgradient-Push <cit.>, Gradient-Push <cit.>, DIGing <cit.>, and Push-DIGing <cit.>. Different from Algorithm <ref> that is developed by applying distributed weighted gradient methods to the Fenchel dual, Subgradient-Push and Gradient-Push are constructed by incorporating the subgradient method and the stochastic gradient descent method into the Push-Sum consensus protocol <cit.>, DIGing is designed by combining a distributed inexact gradient method with a gradient tracking technique, and Push-DIGing is derived by introducing Push-Sum into DIGing.

The convergence rates of the aforementioned algorithms are all established under Assumption <ref>.[When it comes to Subgradient-Push, Gradient-Push, and Push-DIGing, “connected” in Assumption <ref> is indeed “strongly connected” since they consider directed networks.] For each of these algorithms, Table <ref> lists its assumptions and convergence rate. Observe that only Algorithm <ref> is capable of solving problems with different local constraints of the agents, while the remaining algorithms all require the problem to be unconstrained and their extensions to constrained problems are still open challenges. Also, Gradient-Push, DIGing, and Push-DIGing require both strong convexity and smoothness of the f_i's, leading to faster convergence rates than the O(1/√(k)) rate of Algorithm <ref>. This is natural because we assume a weaker condition on f_i ∀ i∈𝒱, which allows the strongly convex f_i's to be nonsmooth. Subgradient-Push needs neither strong convexity nor smoothness of each f_i, and the resulting convergence rate O(ln k/√(k)) is slower than our O(1/√(k)) result. Note that the assumption on the f_i's for Algorithm <ref> is not necessarily more restrictive than that for Subgradient-Push, since Subgradient-Push requires the subgradients of each f_i to be uniformly bounded over ℝ^d but Algorithm <ref> does not. Unlike Subgradient-Push, Gradient-Push, and Push-DIGing that admit directed links, DIGing and Algorithm <ref> are only applicable to undirected graphs. With that said, Algorithm <ref> is guaranteed to converge to the optimum with the minimal connectivity condition, i.e., Assumption <ref>, while the other methods have no such convergence results. 





§ NUMERICAL EXAMPLES


In this section, we demonstrate the competent convergence performance of the proposed distributed Fenchel dual gradient methods by comparing them with a number of existing distributed optimization algorithms via simulations.



 §.§ Constrained case




We first compare the convergence performance of a consensus-based subgradient projection method <cit.>, a proximal-minimization-based method <cit.>, and Algorithm <ref> with H_𝒢^k given by the graph Laplacian matrix (<ref>) and the Metropolis weight matrix (<ref>), respectively, in solving constrained distributed optimization problems in the form of (<ref>). It has been proved that when each local constraint X_i is compact, the consensus-based subgradient projection method and the proximal-minimization-based method, with diminishing step-sizes (e.g., 1/k), asymptotically converge to an optimum over time-varying networks satisfying Assumption <ref> <cit.>. Thus, consider the following multi-agent ℓ_1-regularization problem that often arises in machine learning:

    [                        x∈ℝ^5 ∑_i∈𝒱(x^TA_ix+b_i^Tx+1/nx_1);                   subject to x∈⋂_i∈𝒱{x∈ℝ^5:p_i ≤ x≤ q_i}, ]

where each A_i∈ℝ^5× 5 is symmetric positive definite, b_i∈ℝ^5, and p_i≤ x≤ q_i with p_i,q_i∈ℝ^5 means an elementwise inequality. In addition, for each i∈𝒱, the convexity parameter of its local objective is θ_i=λ_5^↓(A_i)>0.

For Algorithm <ref>, we adopt α^k=1/(Ln) for H_𝒢^k in (<ref>) and α^k=1/2 for H_𝒢^k in (<ref>) to satisfy the step-size condition (<ref>). For the other two methods, we adopt the diminishing step-size 1/k and the local (unweighted) averaging operation as the consensus scheme to guarantee convergence. We also let the algorithms all start from the same initial primal iterate.

Figure <ref> presents the average primal errors produced by the aforementioned algorithms with different values of n, B and θ_i ∀ i∈𝒱. Observe that Algorithm <ref> with the Metropolis weight matrix (<ref>) outperforms the others in all six cases. Moreover, although at early stage the subgradient projection method and the proximal minimization method converge faster than Algorithm <ref> with the Laplacian weight matrix (<ref>), their convergence gradually becomes much slower due to the diminishing nature of the step-size. By comparing Figure <ref> versus <ref> and Figure <ref> versus <ref>, we can see that smaller B leads to faster convergence of Algorithm <ref>, which is consistent with our convergence analysis in Section <ref>, while the impact of B on the subgradient projection method and the proximal minimization method is not apparent. Besides, Figure <ref> versus <ref> and Figure <ref> versus <ref> suggest that Algorithm <ref> with H_𝒢^k in (<ref>) is more scalable to the network size n than the others. Additionally, by comparing Figures <ref> and <ref> with Figure <ref>, it can be inferred that the larger the θ_i's are, the better Algorithm <ref> performs.



 §.§ Unconstrained case


In Section <ref>, we have compared Algorithm <ref> versus Subgradient-Push <cit.>, Gradient-Push <cit.>, DIGing <cit.>, and Push-DIGing <cit.> in the theoretical aspects. Here, we compare, via simulation, their convergence performance in solving the following unconstrained quadratic program that satisfies all the assumptions in <cit.>:

    minimize_x∈ℝ^5∑_i∈𝒱(x^TA_ix+b_i^Tx),

where we let θ_i=λ_5^↓(A_i)∈(2,3) ∀ i∈𝒱 and (n,B)=(50,10). For fair comparison, we assume there is no stochastic error in gradient evaluation for Gradient-Push. Then, Gradient-Push and Subgradient-Push have the same algorithmic form when the local objectives are differentiable, and below we omit Subgradient-Push.

Figure <ref> plots the evolution of the average primal error for Gradient-Push, DIGing, Push-DIGing, and Algorithm <ref> with the Laplacian weight matrix (<ref>) and with the Metropolis weight matrix (<ref>). We adopt the same step-sizes for Algorithm <ref> as in Section <ref>. For the other three methods, we fine-tune the step-sizes while satisfying the step-size conditions in <cit.> that theoretically ensure their convergence rates. Observe that Gradient-Push, DIGing, and Push-DIGing almost stop making progress after a few iterations with a non-negligible primal error, while Algorithm <ref> achieves much better accuracy with the above two choices of H_𝒢^k. 

As all the convergence rate results in <cit.> and this paper are derived from worst-case analysis, the theoretical step-size conditions could be very conservative. Thus, in Figure <ref> we empirically choose the step-sizes for these algorithms, whose values may violate the theoretical conditions but speed up convergence. After some tuning, we select the step-sizes to be 1/(nL), 1.7, 0.15/k, 0.05, and 0.04 for Algorithm <ref> with H_𝒢^k in (<ref>), Algorithm <ref> with H_𝒢^k in (<ref>), Gradient-Push, DIGing, and Push-DIGing, respectively. Note that for Algorithm <ref> with H_𝒢^k in (<ref>), the empirical step-size coincides with the theoretical one in Figure <ref>. By comparing Figure <ref> with Figure <ref>, we can observe that with the above empirically-selected step-sizes, Gradient-Push slightly accelerates its convergence, DIGing and Push-DIGing exhibit prominently improved convergence performance, yet Algorithm <ref> with H_𝒢^k in (<ref>) still performs best.





§ CONCLUSION


We have constructed a family of distributed Fenchel dual gradient methods for solving multi-agent optimization problems with strongly convex local objectives and nonidentical local constraints over time-varying networks. The proposed algorithms have been proved to asymptotically converge to the optimal solution under a minimal connectivity condition, and have an O(1/√(k)) convergence rate under a standard connectivity condition. Simulation results have illustrated the competitive performance of the distributed Fenchel dual gradient methods by comparing them with related algorithms. In future, this work may be extended in a number of directions such as problems with general convex objective functions and networks with directed links. 



§ APPENDIX




 §.§ Proof of Proposition <ref>


Let 𝐰^⋆=((w_1^⋆)^T,…,(w_n^⋆)^T)^T be an optimal solution of problem (<ref>). Since Assumption <ref>(b) assumes 0_d∈int⋂_i∈𝒱X_i, there exists r_c∈(0,∞) such that B(0_d,r_c)⊆⋂_i∈𝒱X_i. For each i∈𝒱, if w_i^⋆≠0_d, let x_i'=r_cw_i^⋆/w_i^⋆; otherwise let x_i'=0_d. Clearly, x_i'∈ B(0_d,r_c). Consequently,

    D^⋆=D(𝐰^⋆)=∑_i∈𝒱(sup_x_i∈ X_i(w_i^⋆)^Tx_i-f_i(x_i))[0]
       ≥∑_i∈𝒱((w_i^⋆)^Tx_i'-f_i(x_i'))=r_c∑_i∈𝒱w_i^⋆-∑_i∈𝒱f_i(x_i').

This, along with 𝐰^⋆≤∑_i∈𝒱w_i^⋆ and D^⋆=-F^⋆, implies that 𝐰^⋆≤((∑_i∈𝒱f_i(x_i'))-F^⋆)/r_c. Note that ∑_i∈𝒱f_i(x_i')≤∑_i∈𝒱max_x_i∈ B(0_d,r_c)f_i(x_i), where F^⋆≤∑_i∈𝒱max_x_i∈ B(0_d,r_c)f_i(x_i)<∞ because B(0_d,r_c) is compact. Therefore, (<ref>) holds, which suggests that the optimal set of problem (<ref>) is compact. Then, due to the convexity of D and S^, the level sets S_0(𝐰) ∀𝐰∈ S^ are compact <cit.>.



 §.§ Proof of Lemma <ref>


For convenience, let 𝐲^k = (H_𝒢^k⊗ I_d)∇ D(𝐰^k). Due to the Descent Lemma <cit.> and (<ref>),

    D(𝐰^k+1)-D(𝐰^k)   ≤⟨∇ D(𝐰^k),𝐰^k+1-𝐰^k⟩+(𝐰^k+1-𝐰^k)^TΛ_L⊗ I_d/2(𝐰^k+1-𝐰^k)
       =-α^k⟨∇ D(𝐰^k), 𝐲^k⟩+(α^k)^2(𝐲^k)^TΛ_L⊗ I_d/2𝐲^k.


Then, consider the following lemma. 

Suppose M, M̅∈ℝ^n× n are symmetric positive semidefinite and M≼M̅. Then, for any 𝐱∈ℝ^nd and any 𝐲∈ℛ(M⊗ I_d),

    ⟨𝐱, (M⊗ I_d)𝐱⟩≥⟨ (M⊗ I_d)𝐱, (M̅^†⊗ I_d)(M⊗ I_d)𝐱⟩.




Let 𝐱∈ℝ^nd. Then,

    ⟨𝐱, (M⊗ I_d)𝐱⟩-⟨ (M⊗ I_d)𝐱, (M̅^†⊗ I_d)(M⊗ I_d)𝐱⟩= 𝐱^T[(M-MM̅^†M)⊗ I_d]𝐱.

In addition, by Schur complement condition, M≽ O_n and M̅≽ M implies

    (
          [  M  M;  M M̅;    ]) ≽ O_2n

and the inequality above leads to M-MM̅^†M≽ O_n. Combining this with (<ref>), the proof can be completed.


From Lemma <ref>, (𝐲^k)^T(Λ_L ⊗ I_d)𝐲^k≤δ⟨∇ D(𝐰^k), 𝐲^k⟩. Combining this with (<ref>) leads to

    D(𝐰^k+1)-D(𝐰^k) ≤ ((α^k)^2δ/2-α^k)⟨∇ D(𝐰^k), 𝐲^k⟩.

This, along with (<ref>), completes the proof.



 §.§ Proof of Lemma <ref>


We first consider the following optimization problem: For any ℐ⊆𝒱, ℐ≠∅ and any c∈ℝ^d,

    [  w_i∈ℝ^d ∀ i∈ℐ ∑_i∈ℐ d_i(w_i);     subject to   ∑_i∈ℐ w_i=c. ]

Similar to problem (<ref>), w_i' ∀ i∈ℐ compose an optimum to (<ref>) if and only if for any i,j∈ℐ, ∇ d_i(w_i')=∇ d_j(w_j') <cit.>, or equivalently, x̃_i(w_i')=x̃_j(w_j'). With the above setting, consider the following lemma.


Suppose Assumption <ref> and the step-size condition (<ref>) hold. Let 𝐮,𝐯∈ℝ^nd be two feasible solutions of problem (<ref>) such that u_i ∀ i∈ℐ and v_i ∀ i∈ℐ are feasible to problem (<ref>). Suppose x̃_i(v_i)-x̃_j(v_j)≤ϵ' ∀ i,j∈ℐ for some ϵ'>0, ∑_i∈ℐ d_i(u_i)≤∑_i∈ℐ d_i(v_i), and D(𝐯)≤ D(𝐰^0), where 𝐰^0∈ S^ is the initial dual iterate of Algorithm <ref>. Then,
    
    x̃_i(u_i)-x̃_j(u_j)≤4√(LM_0(|ℐ|-1)ϵ'),  ∀ i,j∈ℐ,

where M_0 is defined in (<ref>).



Let 𝐰'=(w_1'^T,…,w_n'^T)^T∈ℝ^nd be such that w_i'∈ℝ^d ∀ i∈ℐ compose an optimal solution to (<ref>) and w_j'=v_j ∀ j∉ℐ. Due to the convexity of each d_i and (<ref>),

    ∑_i∈ℐ d_i(v_i)-∑_i∈ℐ d_i(w_i')≤∑_i∈ℐ⟨x̃_i(v_i), v_i-w_i'⟩.

Let x̅_v:=1/|ℐ|∑_i∈ℐx̃_i(v_i). Since w_i' ∀ i∈ℐ and v_i ∀ i∈ℐ are feasible to (<ref>), we have ∑_i∈ℐw_i'=∑_i∈ℐv_i, which gives

    ∑_i∈ℐ⟨x̃_i(v_i), v_i-w_i'⟩   =∑_i∈ℐ⟨x̃_i(v_i)-x̅_v, v_i-w_i'⟩≤∑_i∈ℐx̃_i(v_i)-x̅_v·v_i-w_i'.

Also note that for each i∈ℐ, x̃_i(v_i)-x̅_v=1/|ℐ|∑_j∈ℐ (x̃_i(v_i)-x̃_j(v_j))≤|ℐ|-1/|ℐ|ϵ'. Combining the above,

    ∑_i∈ℐ d_i(v_i)-∑_i∈ℐ d_i(w_i')≤|ℐ|-1/|ℐ|ϵ'∑_i∈ℐv_i-w_i'≤ (|ℐ|-1)ϵ'√(∑_i∈ℐv_i-w_i'^2).

Since ∑_i∈ℐd_i(w_i')≤∑_i∈ℐd_i(v_i) and w_j'=v_j ∀ j∉ℐ, we have D(𝐰')≤ D(𝐯)≤ D(𝐰^0), implying that 𝐰',𝐯∈ S_0(𝐰^0) and that for any optimum 𝐰^⋆ of problem (<ref>),

    𝐰'-𝐯≤𝐰'-𝐰^⋆+𝐯-𝐰^⋆≤ 2M_0.

This inequality and (<ref>) together yield

    ∑_i∈ℐ d_i(v_i)-∑_i∈ℐ d_i(w_i')≤ 2M_0(|ℐ|-1)ϵ'.

Due to the optimality of w_i' ∀ i∈ℐ with respect to (<ref>), we have ∇ d_i(w_i')=∇ d_j(w_j') ∀ i,j∈ℐ. Also, because of the feasibility of u_i ∀ i∈ℐ, ∑_i∈ℐu_i=∑_i∈ℐw_i'. Therefore, ∑_i∈ℐ⟨∇ d_i(w_i'), u_i-w_i'⟩ =0. This, along with (<ref>), (<ref>), and the inequality d_i(u_i)-d_i(w_i')≥⟨∇ d_i(w_i'), u_i-w_i'⟩ + 1/2L∇ d_i(w_i')-∇ d_i(u_i)^2 <cit.>, implies

    ∑_i∈ℐx̃_i(u_i)-x̃_i(w_i')^2≤ 2L∑_i∈ℐ(d_i(u_i)-d_i(w_i'))[0]
       ≤ 2L∑_i∈ℐ(d_i(v_i)-d_i(w_i'))≤ 4LM_0(|ℐ|-1)ϵ'.

Hence, for any i,j∈ℐ, we have
x̃_i(u_i)-x̃_j(u_j)≤x̃_i(u_i)-x̃_i(w_i')+x̃_j(u_j)-x̃_j(w_j')≤4√(LM_0(|ℐ|-1)ϵ'), where the first inequality is from the optimality of w_i' ∀ i∈ℐ and (<ref>).


Next, we define the following: Arbitrarily pick ϵ>0. Due to (<ref>), ∃ T_ϵ≥0 such that

    x_i^k-x_j^k≤ϵ,  ∀{i,j}∈ℰ^k, ∀ k≥ T_ϵ.

Then, for each i∈𝒱, let 𝒞_i,ϵ^k=∅ ∀ k∈[0,T_ϵ). For each k≥ T_ϵ, let

    𝒞_i,ϵ^k=   {i}∪{j∈𝒱:There exists a path between i and jin the graph (𝒱,∪_t=T_ϵ^kℰ^t)}⊆𝒱.

For each k≥ T_ϵ, observe that in the graph (𝒱,∪_t=T_ϵ^kℰ^t), the subgraph induced by 𝒞_i,ϵ^k is the largest connected component that contains node i.
Thus, for any two nodes i and j, i≠ j, 𝒞_i,ϵ^k and 𝒞_j,ϵ^k are either identical or disjoint. Additionally, for every s∈𝒞_i,ϵ^k+1, 𝒞_s,ϵ^k is always contained in 𝒞_i,ϵ^k+1. This implies that the number of distinct sets in the collection {𝒞_i,ϵ^k}_i∈𝒱 is non-increasing with k over [T_ϵ,∞). In particular, from each k to k+1, 𝒞_i,ϵ^k+1 either equals 𝒞_i,ϵ^k or is the union of 𝒞_i,ϵ^k and some other 𝒞_j,ϵ^k's that are disjoint from 𝒞_i,ϵ^k. Also due to Assumption <ref>, there exists K_ϵ∈[T_ϵ,∞) such that 𝒞_i,ϵ^k=𝒱 ∀ i∈𝒱 ∀ k≥ K_ϵ.
By means of the 𝒞_i,ϵ^k's and Lemma <ref>, below we show that ∀ i∈𝒱, ∀ k≥ T_ϵ,

    max_j,ℓ∈𝒞_i,ϵ^kx_j^k-x_ℓ^k≤Φ_i^k(ϵ).

Here, Φ_i^k(ϵ) ∀ i∈𝒱 ∀ k≥ T_ϵ are defined recursively as follows:
Initially at k=T_ϵ, Φ_i^k(ϵ)=(|𝒞_i,ϵ^k|-1)ϵ. At each subsequent k≥ T_ϵ+1,

    Φ_i^k(ϵ)=4√(LM_0(|𝒞_i,ϵ^k|-1)Φ_i^t^k(ϵ)),   if 𝒞_i,ϵ^k=𝒞_i,ϵ^k-1,
    
    (1+2Lα̅h̅n)|𝒞_i,ϵ^k|ϵ
    +∑_s∈𝒞_i,ϵ^kΦ_s^k-1(ϵ),     otherwise,

where t^k:= max{t∈[T_ϵ,k]:𝒞_i,ϵ^t≠𝒞_i,ϵ^t-1}. Note that 𝒞_i,ϵ^k=𝒞_i,ϵ^t ∀ t∈[t^k,k].

We prove (<ref>) by induction. At time k=T_ϵ, for each i∈𝒱, if |𝒞_i,ϵ^k|=1, then max_j,ℓ∈𝒞_i,ϵ^kx_j^k-x_ℓ^k=Φ_i^k(ϵ)=0, i.e., (<ref>) is satisfied; otherwise for any j,ℓ∈𝒞_i,ϵ^k, j≠ℓ, there exists a path of length at most |𝒞_i,ϵ^k|-1 connecting j and ℓ. It follows from (<ref>) that x_j^k-x_ℓ^k≤(|𝒞_i,ϵ^k|-1)ϵ=Φ_i^k(ϵ), i.e., (<ref>) also holds. Next, suppose max_j,ℓ∈𝒞_i,ϵ^tx_j^t-x_ℓ^t≤Φ_i^t(ϵ) ∀ i∈𝒱 ∀ t∈[T_ϵ,k-1] for some k≥ T_ϵ+1. For each i∈𝒱, to show that (<ref>) holds, consider the following two cases.

Case i: 𝒞_i,ϵ^k=𝒞_i,ϵ^k-1. In this case, we have T_ϵ≤ t^k≤ k-1. Also, ∀ t∈[t^k+1,k], ∀ j∈𝒞_i,ϵ^t-1, we have 𝒩_j^t⊆𝒞_i,ϵ^t-1=𝒞_i,ϵ^k . Hence, using the same arguments as the proofs of Proposition <ref> and Lemma <ref>, it can be shown that ∑_s∈𝒞_i,ϵ^kw_s^k=∑_s∈𝒞_i,ϵ^kw_s^k-1=⋯=∑_s∈𝒞_i,ϵ^kw_s^t^k and that ∑_s∈𝒞_i,ϵ^kd_s(w_s^k)≤∑_s∈𝒞_i,ϵ^kd_s(w_s^k-1)≤⋯≤∑_s∈𝒞_i,ϵ^kd_s(w_s^t^k). Let ℐ=𝒞_i,ϵ^k and c=∑_s∈𝒞_i,ϵ^kw_s^t^k in problem (<ref>). It then follows from Lemma <ref> and Lemma <ref> with
ϵ'=Φ_i^t^k(ϵ), 𝐮=𝐰^k, and 𝐯=𝐰^t^k that (<ref>) holds.

Case ii: 𝒞_i,ϵ^k≠𝒞_i,ϵ^k-1. Pick any j,ℓ∈𝒞_i,ϵ^k, j≠ℓ and consider the following two subcases.

Subcase ii(a): 𝒞_j,ϵ^k-1=𝒞_ℓ,ϵ^k-1. Then,
x_j^k-x_ℓ^k≤x_j^k-x_j^k-1+x_j^k-1-x_ℓ^k-1+x_ℓ^k-1-x_ℓ^k≤x_j^k-x_j^k-1+x_ℓ^k-x_ℓ^k-1+Φ_j^k-1(ϵ).
Also, from (<ref>), Proposition <ref>, (<ref>), and (<ref>), we have

    x_p^k-x_p^k-1≤ L_pw_p^k-w_p^k-1≤ Lα̅∑_q∈𝒩_p^k-1h_pq^k-1(x_p^k-1-x_q^k-1)[0]
       ≤ Lα̅h̅∑_q∈𝒩_p^k-1x_p^k-1-x_q^k-1≤ Lα̅h̅nϵ,  ∀ p∈𝒱.

Consequently, x_j^k-x_ℓ^k≤2Lα̅h̅nϵ+Φ_j^k-1(ϵ).

Subcase ii(b): 𝒞_j,ϵ^k-1∩𝒞_ℓ,ϵ^k-1=∅. Then, there exists a path from j to ℓ belonging to the subgraph induced in the graph (𝒱,∪_t=T_ϵ^kℰ^t) by 𝒞_i,ϵ^k. Along the path are nodes p_1=j,s_1,p_2,s_2,…,p_τ,s_τ=ℓ such that (1) 𝒞_p_r,ϵ^k-1=𝒞_s_r,ϵ^k-1 ∀ r=1,…,τ; (2) 𝒞_p_r,ϵ^k-1 ∀ r∈{1,…,τ} are disjoint from each other; and (3) {s_r,p_r+1}∈ℰ^k ∀ r∈{1,…,τ-1}. Here, τ∈{2,…,|𝒞_i,ϵ^k|} is an integer whose value is no more than the number of distinct sets in the collection {𝒞_s,ϵ^k-1}_s∈𝒞_i,ϵ^k. Hence, x_j^k-x_ℓ^k≤x_p_1^k-x_s_1^k+∑_r=1^τ-1(x_s_r^k-x_p_r+1^k+x_p_r+1^k-x_s_r+1^k). For each r=1,…,τ, since p_r,s_r∈𝒞_p_r,ϵ^k-1, we obtain from Subcase ii(a) that x_p_r^k-x_s_r^k≤2Lα̅h̅nϵ+Φ_p_r^k-1(ϵ). It then follows from (<ref>) that x_j^k-x_ℓ^k≤(τ-1)ϵ+2τ Lα̅h̅nϵ+∑_r=1^τΦ_p_r^k-1(ϵ)≤(1+2Lα̅h̅n)|𝒞_i,ϵ^k|ϵ
+∑_s∈𝒞_i,ϵ^kΦ_s^k-1(ϵ).

Combining the above two subcases, we obtain (<ref>). This completes the proof of (<ref>) for all i∈𝒱 and all k≥ T_ϵ. Further, notice that for each i∈𝒱, Φ_i^k(ϵ) is updated only if either 𝒞_i,ϵ^k or 𝒞_i,ϵ^k-1 is changed. Also note that 𝒞_i,ϵ^k can be expanded at most n times and remains unchanged since time K_ϵ. Therefore, for any k≥ K_ϵ+1,

    max_i,j∈𝒱x_i^k-x_j^k=max_i∈𝒱max_j,ℓ∈𝒞_i,ϵ^kx_j^k-x_ℓ^k≤max_i∈𝒱Φ_i^k(ϵ)≤ O(ϵ^1/2^n),

which implies max_i,j∈𝒱x_i^k-x_j^k→0 as k→∞.



 §.§ Proof of Theorem <ref>


Let 𝐰^⋆ be an optimal solution to the dual problem (<ref>). Due to the convexity of D, (<ref>), and Proposition <ref>,

    D(𝐰^k)-D^⋆≤⟨∇ D(𝐰^k), 𝐰^k-𝐰^⋆⟩=⟨𝐱^k, 𝐰^k-𝐰^⋆⟩[0]
         ≤P_S^(𝐱^k)·𝐰^k-𝐰^⋆[0]≤ M_0P_S^(𝐱^k),

where M_0 is defined in (<ref>). As k→∞, we have shown in the paragraph below Lemma <ref> that P_S^(𝐱^k)→ 0. This, along with the above inequality, implies D(𝐰^k)→ D^⋆. In addition, since Assumption <ref> guarantees zero duality gap, we have F(𝐱^k)→ F^⋆. Finally, for any 𝐰∈ S^, due to Corollary <ref>, <cit.>, and (<ref>),

    D(𝐰)-D^⋆≥⟨∇ D(𝐰^⋆), 𝐰-𝐰^⋆⟩+1/2L∇ D(𝐰)-∇ D(𝐰^⋆)^2=1/2L𝐱̃(𝐰)-𝐱^⋆^2,

where the last equality is because ∇ D(𝐰^⋆)=𝐱^⋆∈ S and 𝐰, 𝐰^⋆∈ S^. Thus, because lim_k→∞D(𝐰^k)-D^⋆=0 and L>0, 𝐱^k-𝐱^⋆^2→ 0 as k→∞.




 §.§ Proof of Lemma <ref>


Let k∈{0,B,2B,…}. For each {i,j}∈ℰ̃^k, let t_{i,j}^k∈{k,…,k+B-1} be such that {i,j}∈ℰ^t_{i,j}^k. Then, note from Proposition <ref> that

    ∇ d_i(w_i^k)-∇ d_i(w_i^t_{i,j}^k)^2 =∑_t=k^t_{i,j}^k-1(∇ d_i(w_i^t+1)-∇ d_i(w_i^t))^2[0]
       ≤ B∑_t=k^k+B-1∇ d_i(w_i^t+1)-∇ d_i(w_i^t)^2≤ L_i^2B∑_t=k^k+B-1w_i^t+1-w_i^t^2.

Thus,

    ∑_{i,j}∈ℰ̃^k(∇ d_i(w_i^k)-∇ d_i(w_i^t_{i,j}^k)^2+∇ d_j(w_j^t_{i,j}^k)-∇ d_j(w_j^k)^2)[0]
    ≤    B∑_{i,j}∈ℰ̃^k∑_t=k^k+B-1 (L_i^2w_i^t+1-w_i^t^2+L_j^2w_j^t+1-w_j^t^2)[0]
    ≤    Bϖ̅∑_t=k^k+B-1∑_i∈𝒱L_i^2w_i^t+1-w_i^t^2[0]
    ≤    Bϖ̅α̅^2∑_t=k^k+B-1⟨∇ D(𝐰^t), ((H_𝒢^tΛ_L^2H_𝒢^t)⊗ I_d)∇ D(𝐰^t)⟩.

Note that H_𝒢^tΛ_L^2H_𝒢^t≼ LH_𝒢^tΛ_LH_𝒢^t. Also, from (<ref>) and Lemma <ref>, H_𝒢^tΛ_LH_𝒢^t≼δ H_𝒢^t. Hence,

    ∑_{i,j}∈ℰ̃^k(∇ d_i(w_i^k)-∇ d_i(w_i^t_{i,j}^k)^2+∇ d_j(w_j^t_{i,j}^k)-∇ d_j(w_j^k)^2)[0]
       ≤ Bϖ̅α̅^2δ L∑_t=k^k+B-1∇ D(𝐰^t)^T(H_𝒢^t⊗ I_d)∇ D(𝐰^t).

In addition,

    ∑_{i,j}∈ℰ̃^k∇ d_i(w_i^t_{i,j}^k)-∇ d_j(w_j^t_{i,j}^k)^2   ≤1/h∑_t=k^k+B-1∑_{i,j}∈ℰ^th_ij^k∇ d_i(w_i^t)-∇ d_j(w_j^t)^2[0]
       ≤1/h∑_t=k^k+B-1∇ D(𝐰^t)^T(H_𝒢^t⊗ I_d)∇ D(𝐰^t).

It follows from (<ref>) and (<ref>) that

    ∇ D(𝐰^k)^T(L_𝒢̃^k⊗ I_d)∇ D(𝐰^k)=∑_{i,j}∈ℰ̃^k∇ d_i(w_i^k)-∇ d_j(w_j^k)^2[0]
       ≤3∑_{i,j}∈ℰ̃^k(∇ d_i(w_i^k)-∇ d_i(w_i^t_{i,j}^k)^2+∇ d_j(w_j^t_{i,j}^k)-∇ d_j(w_j^k)^2+∇ d_i(w_i^t_{i,j}^k)-∇ d_j(w_j^t_{i,j}^k)^2)[0]
       ≤η∑_t=k^k+B-1∇ D(𝐰^t)^T(H_𝒢^t⊗ I_d)∇ D(𝐰^t).




 §.§ Proof of Theorem <ref>


Let k≥0. By Lemmas <ref> and <ref>,

    (D(𝐰^(k+1)B)-D^⋆)-(D(𝐰^kB)-D^⋆)=∑_t=kB^(k+1)B-1(D(𝐰^t+1)-D(𝐰^t))[0]
       ≤-ρ∑_t=kB^(k+1)B-1∇ D(𝐰^t)^T(H_𝒢^t⊗ I_d)∇ D(𝐰^t)≤-ρ/η∇ D(𝐰^kB)^T(L_𝒢̃^kB⊗ I_d)∇ D(𝐰^kB)[0]
       ≤-ρλ/ηP_S^(∇ D(𝐰^kB))^2,

where the last inequality is because 𝒢̃^kB is connected and thus Null(L_𝒢̃^kB⊗ I_d)=S. Also, since 𝒢̃^tB ∀ t=0,1,… are connected, we have λ>0. From Proposition <ref>, we know that 𝐰^kB∈ S^. Also, for any optimal solution 𝐰^⋆ to (<ref>), because 𝐰^⋆∈ S^, we have 𝐰^kB-𝐰^⋆∈ S^. Then,

    D(𝐰^kB)-D^⋆≤   ⟨∇ D(𝐰^kB), 𝐰^kB-𝐰^⋆⟩=⟨ P_S^(∇ D(𝐰^kB)), 𝐰^kB-𝐰^⋆⟩[0]
    ≤   P_S^(∇ D(𝐰^kB))·𝐰^kB-𝐰^⋆.

This, along with (<ref>), gives

    (D(𝐰^(k+1)B)-D^⋆)-(D(𝐰^kB)-D^⋆)≤-ρλ(D(𝐰^kB)-D^⋆)^2/(ηmin_𝐰^⋆∈ S^:D(𝐰^⋆)=D^⋆𝐰^kB-𝐰^⋆^2).

Finally, using Lemma 6 in <cit.>, we obtain

    D(𝐰^kB)-D^⋆≤   D(𝐰^0)-D^⋆/1+ρλ(D(𝐰^0)-D^⋆)/η∑_t=0^k-1(min_𝐰^⋆∈ S^:D(𝐰^⋆)=D^⋆𝐰^tB-𝐰^⋆^2)^-1[0]
    ≤   D(𝐰^0)-D^⋆/1+ρλ(D(𝐰^0)-D^⋆)k/(ηM̃_k^2).

Note that the above inequality is equivalent to (<ref>) since (D(𝐰^k))_k=0^∞ is non-increasing.



 §.§ Proof of Theorem <ref>


Let 𝐰∈ S^. Note that P_S^(𝐱̃(𝐰))=𝐱̃(𝐰)-P_S(𝐱̃(𝐰))≤𝐱̃(𝐰)-𝐱^⋆. Thus, from (<ref>),

    P_S^(𝐱̃(𝐰))≤𝐱̃(𝐰)-𝐱^⋆≤√(2L(D(𝐰)-D^⋆)).

Also note that

    F(𝐱̃(𝐰))-F^⋆ = ⟨𝐰,𝐱̃(𝐰)⟩-D(𝐰)+D^⋆≤⟨𝐰,𝐱̃(𝐰)⟩=⟨𝐰,P_S^(𝐱̃(𝐰))⟩.

On the other hand, for any dual optimum 𝐰^⋆∈ S^, we have -F^⋆=D^⋆≥⟨𝐰^⋆,𝐱̃(𝐰)⟩-F(𝐱̃(𝐰)), which leads to

    F(𝐱̃(𝐰))-F^⋆≥⟨𝐰^⋆,P_S^(𝐱̃(𝐰))⟩.

As a result,

    -𝐰^⋆·P_S^(𝐱̃(𝐰))≤ F(𝐱̃(𝐰))-F^⋆≤𝐰·P_S^(𝐱̃(𝐰)).

Combining (<ref>) and (<ref>) with Proposition <ref> and Theorem <ref> completes the proof.

IEEEtran

