{'fraction_non_alphanumeric': 0.07372028993650616, 'fraction_numerical': 0.03433162892622352, 'mean_word_length': 3.578852585541549, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Linear convergence of a dual optimization formulation for distributed optimization on directed graphs with unreliable communications

This work builds on our recent work on a distributed optimization algorithm for graphs with directed unreliable communications. We show its linear convergence when we take either the proximal of each function or an affine minorant for when the function is smooth.


Introduction
Let G = (V, E) be a directed graph. Consider the distributed optimization problem min x∈R m i∈V (1.1) Here, f i (·) are closed convex functions. The challenge in distributed optimization is that the communications in the algorithm need to be along the directed edges in the underlying graph. Ideally, one would like to solve the problem in (1.1) without the quadratic regularization term, but this regularization term shall be useful for algorithm we describe in this paper. If f i (·) are the zero functions and m = 1, then the minimizer of (1.1) is exactly 1 |V | i∈Vx i , which is precisely the averaging consensus problem. Some results on averaged consensus include [BGPS06, DKM + 10]. Recently, a distributed asynchronous algorithm for averaged consensus on a directed graph with unreliable communications was designed in [BCS17], building on the work of [BBT + 10, VHDG11,HVDG16]. The averaged consensus algorithm is useful as a building block for further distributed optimization algorithms.
If the averaged consensus algorithm were made to be a building block of a distributed algorithm, then one has to decide whether the averaged consensus algorithm has run for sufficiently long. This introduces communication problems to the algorithm, which affects its effectiveness and applicability. If the distributed optimization algorithm were extended from the averaged consensus algorithm instead, then we do not have this issue.
1.1. Distributed dual ascent algorithms for (1.1). We showed in [Pan18a] that a dual ascent interpretation of (1.1) leads to a distributed, asynchronous, decentralized algorithm with deterministic convergence (while also showing that the algorithm also works for time-varying graphs) on undirected graphs. The dual ascent interpretation can be traced to [CDV10, CDV11, ACP + 17] and perhaps earlier, and in the case where the f i (·) are all indicator functions of closed convex sets, to Dykstra's algorithm [Dyk83,BD85,Han88,GM89] (see also [Deu01,BC11,ER11]). Our proof in [Pan18a] was adapted from [GM89], and also makes use of ideas in [HD97] in order to show the asynchronous nature of our algorithm. We also developed this dual ascent interpretation more extensively for undirected graphs in subsequent works by looking at convergence rates [Pan18c] and for the case when f i (·) are level sets of subdifferentiable functions [Pan18d].
An algorithm for the averaged consensus problem on directed graphs with unreliable communications was recently proposed in [BCS17]. It is natural to ask whether the results for undirected graphs carry over to the case of directed unreliable communications. In [Pan18e], we showed that the algorithm of [BCS17] can be generalized to the problem (1.1) and has a similar dual ascent intepretation as [Pan18a].
1.2. Contributions of this paper. We consider the algorithm in [Pan18e] for the case where the edges are directed and unreliable. We show that we can apply the techniques in [Pan18b] (proved for the case of undirected graphs) to avoid proximal operations on f i (·) by taking subgradient approximations and using affine minorants. The techniques in [Pan18c] are generalized to give linear convergence of the dual objective value when the smooth functions f i (·) may be approximated by affine minorants, which leads to the linear convergence to the primal minimizer.

Preliminaries: Algorithm description
In this section, we incorporate [Pan18b,Pan18c] (for the case when some of the functions f i (·) in (1.1) are treated as subdifferentiable functions) into [Pan18e], stating the dual optimization interpretation of (1.1) and our algorithm.
and let the hyperplane H {α1,α2} , where {α 1 , α 2 } ∈ F , be defined by We assume the underlying graph is strongly connected, so the intersection ∩ β∈F H β is the diagonal set D defined by The primal problem (1.1) can then be equivalently written in the product space formulation as where C is as marked in (2.1). Any component of an optimal solution to (2.6) is an optimal solution to (1.1). The (Fenchel) dual of (2.6) can be calculated to be (2.7) The case when s α = 1 for all α ∈ V and s α = 0 for all α ∈ E has been discussed in detail in [Pan18a,Pan18b,Pan18c,Pan18d]. The treatment there implies that there is strong duality between (2.6) and (2.7), even if dual optimizers may not exist. We can define the values {x α } α∈V ∪E by which simplifies the formula in (2.7). As explained in [Pan18e], this x α is precisely the primal value that is being tracked by each vertex or edge α. To simplify discussions, we let Note that (2.7) and (2.9) are related by a sign change and a constant. We partition the vertex set V as the disjoint union V = V 1 ∪ V 2 so that • f i (·) are proximable functions for all i ∈ V 1 .
• f i (·) are subdifferentiable functions (i.e., a subgradient is easy to obtain) such that dom(f i ) = R m for all i ∈ V 2 . In [Pan18e], we showed that in the case when all the functions f i (·) are treated as proximable functions (i.e., V 2 = ∅), the algorithm there produces iterates (z, x, s) such that the function values in (2.9) are nonincreasing. For functions in V 2 , the strategy in [Pan18b,Pan18c] is to create approximations f k i (·) ≤ f i (·) so that the conjugates satisfy [f k i ] * (·) ≥ f * i (·). Let f k i (·) be defined in a similar manner as f i (·), and (2.10) would be a majorization of the function in (2.9). We shall prove in Section 3 that solving subproblems of the form (2.10) gives us linear convergence of the minimal value of (2.9) when all the functions f i (·) are smooth.
Just like in [BCS17], we introduce the variable y α so that With these preliminaries, we present Algorithm 2.1 on the following page. Operations A and B in Algorithm 2.2 are the same as in [BCS17,Pan18e], but Operation C is now modified from [Pan18e] to take into account the setup in [Pan18b,Pan18c]. We now give a short explanation of Algorithms 2.1 and 2.2, explaining what was being done in [BCS17] and [Pan18e].
Remark 2.3. (Algorithms 2.1 and 2.2, and [BCS17]) Operations A and B of Algorithm 2.2 are described in [BCS17]. When operation A is carried out, node i sends data to all its out-neighbors. In operation B, a node receives data from its in-neighbors. Even if node j does not receive information from node i immediately, the information is delayed and not lost. For each (i, j) ∈ E, the variable y (i,j) ∈ R m defined by y (i,j) := σ i,y − ρ (i,j),y to be the data that is sent by node i but not yet received by node j. If all information from a node is eventually received by all its out-neighbors and f i (·) are zero for all i ∈ V , then then [BCS17] proved that y k i /s k i converges linearly to 1   [BCS17]. The bottom diagram illustrates that in [BCS17], the value y α /s α converges to the desired average for all α ∈ V ∪ E.
% Carry all data from last iteration.

Algorithm 2.2. (Operations A, B and C) We describe operations A, B and C: 01 A (Node i sends data to all out-neighbors) 02
Choose a node i ∈ V . 03 Choose edge (i, j) ∈ E so that j receives data along (i, j). 07 If j ∈ V 1 (i.e., f j (·) to be treated as a proximable function):

as a subdifferentiable function) 16
Recall is an affine approximate from previous iterations. 17 Let Remark 2.4. (Algorithms 2.1 and 2.2, and [Pan18e]) In [Pan18e], we noticed that the operations A and B reduces the dual objective value in (2.10). We also noticed that if f i (·) is a proximable function, then lines 13 and 14 in Operation C of Algorithm 2.2 result in a decrease in the dual objective value (2.10). Lines 16 to 22 of Operation C incorporates the procedure described in [Pan18b] to decrease a majorization (2.9) of (2.10) for the case when f i (·) is subdifferentiable; this step allows for a more direct treatment of subdifferentiable functions f i (·) without having the compute the proximal operations of lines 13 and 14. Under reasonable conditions, the values {x k α } ∞ k=0 all converge to the optimal primal solution for all α ∈ V ∪ E. We shall show in Theorem 3.4 the linear convergence when all f i (·) are smooth.
The following result will be useful for later discussions.

Proposition 2.5. (Sparsity) The following results below hold:
( Proof. The proof is elementary and exactly the same as that in [Pan18a]. (Part (1) makes use of the fact that f i (·) depends on only the i-th coordinate of the input, while part (2) makes use of the fact that δ * The following result is a slight extension of a result in [Pan18b].
Strong duality is satisfied for this primal dual pair. Let the common objective value be v * . Let f 1 : X → R be an affine function and let z 2 be the dual solution. Let f 2 : X → R be the affine function such that the problem x −x 2 has the same primal and dual solutions x 2 and z 2 . Let One can see that α i ≥ 0, and α i is the measure of the gap between the estimate of the dual objective value (2.13) and its true value v * . If f (·) is smooth and ∇f (·) is Lipschitz with constant L , then Proof. We note that the case where s = 1 was already treated in [Pan18b]. For the case where s = 1, we can look at the function f (·) s + 1 2 x −x 2 . Then ∇ f s (·) has a Lipschitz constant of L /s, which gives the formula (2.15).

Main result
In this section, we prove the linear convergence of Algorithm 2.1. Throughout this section, we make the following assumption.
(2) There are constants s min , are subdifferentiable for all i ∈ V 2 , but we now limit to only smooth f i (·) for our linear convergence result.] 3.1. Outline of proof. We first give an outline of the proof before proceeding with more technical details. Since Algorithm 2.1 is time invariant, we can assume that we start with the iterates {z 0 , x 0 , s 0 } and the functions f 0 We assume that in the first iteration to get {z 1 , x 1 , s 1 } and the functions (We feel that it is simplest to explain in this manner.) Since Operation C does not change s, we have s 0 = s 1 .
We also define {z + , x + , s 0 } to be obtained from {z 0 , x 0 , s 0 } when operation C is conducted for all nodes i ∈ V , but by assuming the functions f i (·) to be all proximable (i.e., the first option in Operation C is performed on all nodes). We make use of Lemma 2.6 to relate betweenF 1 S (z 1 , x 1 , s 1 ) and F S (z + , x + , s 1 ). By the case of s i = 1 for all i ∈ V and s α = 0 for all α ∈ E, we know that there is a finite dual optimal value, say F * S . We assume that there is a constant K such that for all edges (i, j) ∈ E, there is a k ∈ {1, . . . , K − 1} such that in iterating from (z k , x k , s k ) to (z k+1 , x k+1 , s k+1 ), operation A is conducted on node i and operation B is conducted on edge (i, j) for some j ∈ N out (i). We then show that there is some constant c ∈ (0, 1) such thatF K , which gives linear convergence to the optimal dual objective value.
(3.1) Let x * ∈ R m be the optimal solution to (1.1), and let x * ∈ [R m ] |V ∪E| be such that all |V ∪ E| components of x * are x * . Fenchel duality gives us Similar to the techniques that we used in [Pan18a,Pan18e] that can be traced back to [GM89], the duality gap (in the first line of (3.4) below, which is the optimal value of (2.6) minus the value of the dual problem (2.7)) satisfies We will prove that the duality gap converges to zero at a linear rate in Theorem 3.4. Thus, by (3.4) and Assumption 3.1(2), {x k i } k converges to x * at a linear rate for all i ∈ V .
3.2. The proof. We writeẑ 0 ∈ R m aŝ ] |V ∪F | be an optimal solution to the dual problem F S (·, s 0 ), and letẑ * ∈ R m be defined in a similar manner to (3.5) to beẑ * = −m + We define e ∈ [R m ] |V ∪E| so that The valueF 0 S (z 0 , x 0 , s 0 ) can be written as (3.9) Let z * be a minimizer of F S (·, s 0 ). The strong convexity of the f * i (·) for all i ∈ V ensures that z * i is unique if i ∈ V . (Though z * α need not be unique if α ∈ F .) Since x * is the optimal primal solution, we haveẑ * = − 1 |V | α∈V ∪E s 0 α x * (2.2) = −x * . So the unique solution has the value (3.12) Then recalling (3.1), one can check that Let z * be a minimizer of F S (·, s 0 ), and let z + β = z 0 β for all β ∈ F . Then there exists constants γ ∈ (0, 1) and M > 0 such that if z 0 and z + are related as described, then Proof. For this proof, s will stay as s 0 throughout, so we shall just use s. The second inequality of (3.13) is obvious from We prove the first inequality. By (3.11) and Assumption 3.1(3), we have, for all α ∈ V ∪ E such that s α > 0, (3.14) Also, the optimality condition of (3.11) implies that −ẑ 0 . So together with Assumption 3.1(3), for all α ∈ V ∪E such that s α > 0, we have For the terms not involving [e] α in the last formula of (3.15), we have For the terms involving [e] α in the last formula in (3.15), we have Summing up the right hand sides of (3.16), (3.17) and (3.18) and α∈V Note that 1 σ + 1 σsmin + 1 2smin = 2smin+2+σ 2σsmin . Summing the formulas in (3.15) to (3.19), we have (We say a bit more about (3.20). Recall from (2.2) that were to be finite, then it has to be zero. Thus f * α ([z α ] α ) can be dropped from future sums as needed.) We can then sum up (3.14) multiplied by α∈V ∪E,sα>0 [e] α 2 .
Letting γ = Another part of the proof is to show a formula relating the decrease in objective value to the distance between consecutive iterates. In order to prove the following result, we need to adopt the convention throughout the rest of the paper, in addition to (2.11), that x (i,j) = x i whenever s (i,j) = 0.
(3.22) Lemma 3.3. We can assume without loss of generality that Operation B on the edge (i, j) always follows immediately after Operation A on the node i. Then there is a constant γ 4 > 0 such that for all consecutive iterates, we havẽ Proof. We split into three different cases: Case 1: Operation C on node i. In this case, only x i changes and s k+1 = s k , so i 2 . Now, the form of the optimization problem gives Case 2: Operation A on node i.
We first state an easily checkable identity that would be used often in this proof: (3.24) There are two further cases. Case 2a: When the data is received by a node j ∈ N out (i).
We have x k+1 We first try to show that there is a constant γ 4 > 0 such that Note that if s k (i,j) = 0, then x k+1 , so one can check that the left and right hand sides of (3.26) are both zero, so (3.26) would automatically be satisfied.
Next, note that x k+1 Summing up (3.26) and (3.28) easily leads to a choice of γ 4 > 0 so that (3.25) holds. Case 2b: When the data is not received by a node j ∈ N out (i).
In this case, note that x k+1 . Just like in (3.27), in the case when s k (i,j) > 0, we have x k+1 and so we can reduce γ 4 in (3.25) if necessary so that If s k (i,j) = 0, then we see that both sides of (3.29) are zero, so the choice of γ 4 is irrelevant for (3.29) to hold.
After establishing the inequalities (3.25) and (3.29) for the cases 2a and 2b, we now prove that (3.23) holds. If j receives data from i, then by recalling the convention in (3.22), we have Combining the inequalities (3.31), (3.30) gives us (3.23) as required.
We conclude with the theorem on the linear convergence of Algorithm 2.1.
Claim: There is some (zk +0.5 , xk +0.5 , sk +0.5 ) such that the γ 4 > 0 in Lemma 3.3 can be adjusted if necessary so that were replaced by the constant 1. Case 2b: β * = {i, j} Define xk +0.5 and sk +0.5 by and sk +0.5 (3.41) We first show (3.39). From how zk +0.5 and xk +0.5 are defined, we havẽ Fk S (zk, sk) −Fk S (zk +0.5 , sk +0.5 ) (3.42) We now show the first inequality in (3.39). Recall (2.11), and let d i = deg out (i) + 1. The formulas in (3.41) can be equivalently written as and sk +0.5 (3.43) One way to interpret (3.43) is that the change from (zk, xk, sk) to (zk +0.5 , xk +0.5 , sk +0.5 ) is a transfer of mass from i to j. One can see that the change from (zk +0.5 , xk +0.5 , sk +0.5 ) to (zk +1 , xk +1 , sk +1 ) involves a transfer of mass from (i, j) to j, from i to (i, j ) for all other j ∈ N out (i)\{j}, as well as possibly from (i, j ) to j for j ∈ N out (i)\{j} if the corresponding Operation B were carried out. As we saw in the derivation in (3.42), each transfer of mass reduces the dual objective value, which will give the first inequality in (3.39).

Numerical experiments
We conduct some simple experiments by looking at the case where m = 6 and the graph has 6 nodes and contains two cycles, 1 → 2 → 3 → 5 → 1 and 2 → 4 → 6 → 2. Let e be ones(m,1). First, we find {v i } i∈V andx such that i∈V v i +|V |(e−x) = 0. We then find closed convex functions f i (·) such that v i ∈ ∂f i (e). It is clear from the KKT conditions that e is the primal optimum solution to (1.1) ifx i =x for all i ∈ V .
We define f i (·) as functions of the following type: where v is generated by rand(m,1), r is generated by rand(1). b i is chosen to be such that v i = ∇f (e), and c i = 0.
The first and last formulas of (3.4) indicate how fast the primal iterates {x α } α∈V ∪E are converging to the optimal solution x * , and we call these values the "duality gap" and the "norms squared s-sum" Figure 4.1 shows a plot of the results obtained by a random experiment where we perform 1000 iterations of the smooth case. We conduct two different experiments: one for when all functions are treated to be in V 1 (called the prox case) and one when all functions are treated to be in V 2 (called the subdifferentiable case). We observe linear convergence for both cases.