{'fraction_non_alphanumeric': 0.05350137209065962, 'fraction_numerical': 0.010224616322797033, 'mean_word_length': 4.128857381150959, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Maximal Dissent: a State-Dependent Way to Agree in Distributed Convex Optimization

Consider a set of agents collaboratively solving a distributed convex optimization problem, asynchronously, under stringent communication constraints. In such situations, when an agent is activated and is allowed to communicate with only one of its neighbors, we would like to pick the one holding the most informative local estimate. We propose new algorithms where the agents with maximal dissent average their estimates, leading to an information mixing mechanism that often displays faster convergence to an optimal solution compared to randomized gossip. The core idea is that when two neighboring agents whose distance between local estimates is the largest among all neighboring agents in the network average their states, it leads to the largest possible immediate reduction of the quadratic Lyapunov function used to establish convergence to the set of optimal solutions. As a broader contribution, we prove the convergence of max-dissent subgradient methods using a unified framework that can be used for other state-dependent distributed optimization algorithms. Our proof technique bypasses the need of establishing the information flow between any two agents within a time interval of uniform length by intelligently studying convergence properties of the Lyapunov function used in our analysis.


Introduction
In distributed convex optimization, a collection of agents collaborate to minimize the sum of local objective functions by exchanging information over a communication network. The primary goal is to design algorithms that converge to an optimal solution via local interactions dictated by the underlying communication network. A standard strategy to solving distributed optimization problems consists of each agent first combining the local estimates shared by its neighbors followed by a first-order subgradient method on its local objective function [1][2][3]. Of particular relevance herein are the so-called gossip algorithms [4], where the information mixing step consists of averaging the sates of two agents connected by one of the edges selected from the network graph.
Two benefits of gossip algorithms are their simple asynchronous implementation and a reduction in communication costs. One common gossip algorithm is randomized, in which an agent is randomly activated and chooses one of its neighbors randomly to average its state [5][6][7]. The randomization mechanism used in this gossip scheme is usually state-independent. We consider a different approach to gossip in which the agent chooses one of its neighbors based on its state. At one extreme, we may think of agents who prefer to gossip with neighbors with similar "opinions". As in an echo-chamber, where agents may only talk to others if they reinforce their own opinions, it does not lead to an effective information mixing mechanism. At the opposite extreme, we consider agents who prefer to gossip with neighbors with maximal disagreement or dissent. In this paper, we focus on the concept of max-dissent gossip as a state-dependent information mixing mechanism for distributed optimization. We establish the convergence of the resulting distributed subgradient method under minimal assumptions on the underlying communication graph, and the local functions.
The idea of enabling a consensus protocol to use state-dependent matrices dates back to the Hegselmann and Krause [8] model for opinion dynamics. However, the literature on state-dependent averaging in distributed optimization is scarce and mostly motivated by applications in which the state represents the physical location of mobile agents (e.g. robots, autonomous vehicles, drones, etc.). In such settings, the state-dependency arises from the fact that agents that are physically closer have a higher probability of successfully communicating with each other [9][10][11]. Existing results assume that the local interactions between agents lead to strong connectivity over time. Unlike previous work, our model does not assume that the state of an agent represents its the position in space. Moreover, we do not impose strong assumptions on the network's connectivity over time such as in [3] and [9].
Our work is closely related to state-dependent averaging schemes known as Load-Balancing [12] and Greedy Gossip with Eavesdropping [13]. The main idea in these methods is to accelerate averaging by utilizing the information from the most informative neighbor, i.e., the neighbors whose states are maximally different with respect to some norm from each agent. We refer to it as the maximal dissent heuristics. The challenges of convergence analysis for maximal dissent averaging are highlighted in [12][13][14]. However, concepts akin to max-dissent have only been explored for the specific problem of averaging [13]. Our work, on the other hand, focuses on distributed convex optimization, whose convergence is not guaranteed by the convergence of the averaging scheme alone.
As a broader impact of the results herein, we show that schemes that incorporate mixing of information between max-dissent agents will converge to a global optimizer of the underlying distributed optimization problem almost surely. Our result enables us to propose and extend the use of load-balancing, and max-dissent gossip to distributed optimization. The key property of max-dissent averaging is that it leads to a contraction of the Lyapunov function used to establishing convergence. While recent work has considered similar contraction results (e.g. [15,16]), they are not applicable to state-dependent schemes, and do not establish almost sure convergence, but only convergence in expectation.

Contributions
A preliminary version of some of the ideas herein has previously appeared in [17], which addressed only one of the schemes, namely Global Max-Gossip for distributed optimization of univariate functions. The results reported here are much more general than the ones in [17] addressing ddimensional optimization, and covering multiple state-dependent schemes (e.g. Load-Balancing, Global and Local-Max Gossip) in which the max-dissent agents communicate with non-zero probability at each time. The main contributions of this paper are: • We present state-dependent distributed optimization schemes that do not rely on or imply explicit strong connectivity conditions (such as B-connectivity).
• We characterize a general result highlighting the importance of max-dissent agents on a graph for distributed optimization, significantly simplifying the task of establishing contraction results for a large class of consensus-based subgradient methods.
• We prove the convergence of state-dependent algorithms to a global optimizer for distributed optimization problems using a technique involving the aforementioned contraction property of a quadratic Lyapunov function.
• We present numerical experiments that suggest that the proposed state-dependent subgradient methods improve the convergence rate of distributed estimation problems relative to conventional (state-independent) gossip algorithms.

Organization
The rest of the paper is organized as follows. First, we formulate distributed optimization problems, and outline a generic state-dependent distributed subgradient method in Section 2. In Section 3 we introduce Local and Global Max-Gossip, and review Randomized Gossip and Load Balancing distributed averaging schemes. We discuss the role of maximal dissent agents and their selection in averaging algorithms in Section 4. In Section 5, we present our main results on the convergence of maximal dissent state-dependent distributed subgradient methods. We provide a numerical example that shows the benefit of using algorithms based on the maximal dissent averaging in Section 7. We conclude the paper in Section 8 where we outline future research directions.

Notation
For a positive integer n, we define [n] = {1, 2, . . . , n}. We denote the d-dimensional Euclidean space by R d . We use boldface letters such as x to represent vectors, and lower-case letters such as x to represent scalars. Upper-case letters such as A represent matrices. We use A T to denote the transpose of a matrix A. For i ∈ [n], we denote by b i the i-th standard basis vector of R n . We denote by 1, the vector with all components equal to one, whose dimension will be clear from the context. For a vector v, we denote the 2 -norm by v , and the average of its entries byv. We say that an n × n matrix A is stochastic if it is non-negative and the elements in each of its rows add up to one. We say that A is doubly stochastic if both A and A T are stochastic. For two vectors a, b ∈ R n , we define a, b = a T b. The trace of a square matrix A is defined to be the sum of entries on the main diagonal of A and is denoted by tr(A). For matrices A, B ∈ R n×m we define A, B = tr(A T B) as the inner product and A F to denote the Frobenius norm of A.

Problem Formulation
Consider distributed system with n agents with an underlying communication network defined by a graph G = ([n], E). Each agent i ∈ [n] has access to a local convex function f i : The agents can communicate only with their one-hop neighbours as dictated by the network graph G. Our goal is to design a distributed algorithm to solve the following unconstrained optimization problem We assume that the local objective function f i is known only to node i and the nodes can only communicate by exchanging information about their local estimates of the optimal solution.
The solution set of the problem is defined as Throughout the paper, we make extensive use of the notion of the subgradient of a function.
for all w ∈ R d . We denote the set of all subgradients of f at w 0 by ∂f (w 0 ), which is called the subdifferential of f at w 0 .
We make the following assumptions on the structure of the optimization problem in Eq. (1).
Assumption 2 (Bounded Subgradients). Each local objective function f i 's subgradients are uniformly bounded. In other words, for each i ∈ [n], there exists a finite constant L i such that for all w ∈ R d , we have g ≤ L i , g ∈ ∂f i (w).
There exist many algorithms to solve the problem in Eq. (1). Nedic and Ozdaglar [2] introduced one of the pioneering schemes, in which each agent keeps an estimate of the optimal solution and at each time step, the agents share their local estimate with their neighbors. Then, each agent updates its estimate using a time-varying, state-independent convex combination of the information received from their neighbors and its own local estimate. For t ≥ 0, let a ij (t) denote the coefficients of the aforementioned convex combination at time t such that a ij (t) ≥ 0, for all i, j ∈ [n], a ij (t) = 0 if {i, j} / ∈ E, and n j=1 a ij (t) = 1, for all i ∈ [n]. Let x i (t) denote the i-th agent's estimate of the optimal solution at time t. The convex combination is followed by taking a step in the direction of any subgradient in the subdifferential at the local estimate, i.e., where g i (t) ∈ ∂f i x i (t) , and α(t) is a step-size sequence. Herein, we generalize the algorithm in [2] by allowing the weights in the convex combination to be state-dependent in addition to being time-varying. Let each agent i ∈ [n] initialize its estimate at an arbitrary point x i (0) ∈ R d , which is updated at discrete-time iterations t ≥ 0 based on its own subgradient and the estimates received from neighboring agents as follows where a ij t, x 1 (t), x 2 (t), . . . , x n (t) are non-negative weights, α(t) is a step-size sequence, and g i (t) ∈ ∂f i w i (t) for all t ≥ 0. We can express this update rule compactly in matrix form as and Note that another difference between Eqs. (3) and (2) is that agent i computes the subgradient for the local function f i at the computed average w i (t + 1) instead of x i (t), t ≥ 0.
Assumption 3 (Diminishing step-size). The step-sizes α(t) > 0 form a non-increasing sequence that satisfies For a step-size sequence that satisfies Assumption 3, if the sequence of matrices , is doubly stochastic and sufficiently mixing, and the objective functions satisfy the regularity conditions in Assumptions 1 and 2, then the iterates in Eq. (2) converge to an optimal solution irrespective of the initial conditions , where x * ∈ W * [3, Propositions 4 and 5]. Our goal for the remainder of the paper is to establish a similar result for state-dependent maximal dissent distributed subgradient methods.

State-dependent average-consensus
In this section, we discuss three state-dependent average-consensus schemes that can potentially accelerate the existing distributed optimization methods, in so doing, we endeavor to unify the state-dependent average-consensus methodology. The first scheme, Local Max-Gossip, was studied in [13] exclusively for the average consensus problem. We provide two novel averaging schemes, the Max-Gossip and Load-Balancing averaging schemes, that provide faster convergence. The dynamics of these algorithms can be understood as the instances of Eq. (3) with constant local cost functions f i (x) ≡ c, i ∈ [n], i.e., X(t + 1) = A t, X(t) X(t).
We will consider three (two asynchronous and one synchronous) algorithms. The first two algorithms are related to the well-known randomized gossip algorithm [4,5]. First, we present a brief description of Randomized Gossip.

Randomized Gossip
Consider a network G = ([n], E) of n agents, where each agent has an initial estimate x i (0). At each iteration t ≥ 0, a node i is chosen uniformly from [n], independently of the earlier realizations. Then, i chooses one of its neighbors j ∈ N i , where N i {j ∈ [n] : {i, j} ∈ E}, with probability P ij > 0. The two nodes exchange their current states x i (t) and x j (t), and update their states according to The states of the remaining agents are unchanged. The update rule in Eq. (4) admits a more compact matrix representation as where e = {i, j}, and It is necessary that n =1 P i = 1 for all i, where P i = 0 if and only if {i, } ∈ E. The dynamical system described in Eq. (5) and its convergence rate are studied in [5].

Global Max-Gossip
The standard gossiping algorithm described above is state-independent in the sense that the selection of the gossiping edge e does not depend on the states at the agents at any time. Herein, we propose Global Max-Gossip where we select the edge connecting the agents with the largest possible dissent (disagreement) among all edges in the graph G = ([n], E), i.e., In case there are multiple solutions to Eq. (7), we select the smallest pair of indices (i * , j * ) based on the lexicographical order, without loss of optimality. For brevity, we use e max (X) to denote the max-edge. Global Max-Gossip serves as a benchmark as to what is achievable via state-dependent averaging schemes. Global Max-Gossip requires an oracle to provide the edge resulting in the largest possible Lyapunov function reduction across all network edges. Obtaining a decentralized algorithm to determine the max-dissent edge is a challenging open problem beyond the scope of this paper.
Given an initial state matrix X(0), the Max-Gossip averaging scheme admits a state-dependent dynamics of the form A t, X(t) = B e max X(t) , where the gossiping matrix is given by Eq. (6) and the max-edge is selected according to Eq. (7).

Local Max-Gossip
In Local Max-Gossip introduced in [13] under the moniker of Greedy Gossip with Eavesdropping, a random selected node gossips with the neighbor j ∈ N i that has the largest 1 possible state discrepancy with i, i.e., j = arg max Convergence is accelerated by gossiping with the neighbor with the largest disagreement as this leads to the largest possible immediate reduction in the Lyapunov function used to capture the variance of the states in the network.
Since the edge over which the gossiping occurs depends on the current state of the neighbors, the resulting averaging matrix is a state-dependent, random matrix. For a sequence of independently and uniformly distributed index sequence {s(t)}, the Local Max-Gossip dynamics can be written as a state-dependent averaging scheme as follows where r s (X) = arg max

Load-Balancing
Another state-dependent algorithm known as Load-Balancing can also be used to speed up convergence of average-consensus [18]. However, in contrast to the previous two cases, where only two nodes update at a given time, Load-Balancing is a synchronous averaging algorithm where all the agents operate simultaneously.
In the traditional Load-Balancing algorithm, the state at each agent is a scalar, which induces a total ordering amongst the agents, i.e., the neighbours of an agent are classified by having greater or smaller state values than the agent's current state. When the states at the agents are multidimensional vectors, a total ordering is not available and must be defined. We introduce a variant of Load-Balancing based on the Euclidean distance between the states of any two agents as follows.
At time t, each agent i ∈ [n] carries out the following steps: 1. Agent i sends its state to its neighbors.
2. Agent i computes the distance between its state and each of its neighbors. Let S i denote the subset of neighbors of agent i whose state have maximal Euclidean distance, i.e., Agent i sends an averaging request to the agents in S i .
3. Agent i receives averaging requests from its neighbors. If it receives a request from a single agent j ∈ S i , then it sends an acknowledgement to that agent. In the event that agent i receives multiple requests, it sends an acknowledgement to one of the requests uniformly at random.
4. If agent i sends and receives an acknowledgement from agent j, then it updates its state as The conditions for interaction between two nodes in Load Balancing is characterized in the following proposition. Proposition 1. Consider a connected graph G and a stochastic process X(t), A t, X(t) , where A t, X(t) is the characterization of averaging according to the Load-Balancing algorithm, i.e. A t, X(t) X(t) is the output of the Load-Balancing algorithm for a network with state matrix X(t), t ≥ 0. The following statements hold: 2. Let (i, j) ∈ E. If Eq. (11) holds with strict inequality, then i, j average their states.
Proposition 1 is proven in Appendix A.

On the selection of Max-edges
Consider the stochastic process X(t), A t, X(t) , where X(t) is the network state matrix, and A t, X(t) a state-dependent averaging matrix. Let {F t } ∞ t=0 be a filtration such that F t is the σ-algebra generated by We establish a non-zero probability that a pair of agents that constitute a max-edge will update their states for the averaging schemes discussed in Section 3.
t=0 be the random process generated by either Randomized Gossip, Local Max-Gossip, Max-Gossip, or Load-Balancing consensus schemes. Then, for the random indices i * , j * ∈ [n] defined through the max-edge in Eq.
Proposition 2 establishes that given the knowledge until time t, in expectation, the agents comprising the max-edge based on the network state matrix X(t), exchange their values with a positive weight bounded away from zero. Qualitatively, for gossip-based algorithms, this implies that there is a positive probability bounded away from zero that the agents comprising the max-edge carry out exchange of information with each other. We use Proposition 2 along with Theorem 3 to establish that the averaging matrices characterizing the algorithms discussed in Section 3 are contracting. Therefore, the subgradient methods based on these averaging algorithms converge to the same optimal solution almost surely as stated in Corollary 1 of Theorem 4. In other words, as long as the averaging step involves gossip over the max-edge with positive probability (bounded away from zero), we will have a contraction in the Lyapunov function capturing the sample variance, which is a key step in proving the convergence of our averaging based-subgradient methods. Proposition 2 is proven in Appendix B.

Convergence of state-dependent Distributed Optimization
In the previous section, we have set the stage for studying the convergence of state-dependent averaging-based distributed optimization algorithms. Our proofs rely on two properties: double stochasticity and the contraction property (Theorem 3).
To state the contraction property, we define the Lyapunov function V : Theorem 3 (Contraction property). Consider a connected graph G and the stochastic process t=0 with a natural filtration {F t } t≥0 for the dynamics given by Eq. (3). If A t, X(t) ∈ F t+1 is doubly stochastic for all t ≥ 0, and for the random variables i * , j * ∈ [n] defined through the max-edge in Eq. (7) as e max X(t) = {i * , j * }, where δ > 0, holds for all t ≥ 0 and X(0) ∈ R n×d , then where Theorem 3 is proven in Appendix C and provides our key new ingredient: proving a contraction result for doubly stochastic averaging matrices containing the maximally dissenting edge. The proof of Theorem 3 makes use of the double stochasticity of the matrices to characterize the exact one-step decrease in the Lyapunov function and then uses a clever trick to characterize its fractional decrease based on the fact that underlying communication graph is connected. Remark 1. Theorem 3 also holds for time-varying graphs provided they remain connected at each time t. More precisely, the theorem holds for a sequence of connected graphs {G t } and at every time t ≥ 0, for i * , j * defined through e max (G t , X(t)), the inequality in Eq. (14) holds, then the inequality in Eq. (15) will hold with scaling at time t being Therefore, the contraction property for connected time-varying graphs holds with a factor of at For a connected graph G and the stochastic process t=0 generated according to the dynamics in Eq. (3), we define a contracting averaging matrix as follows.
holds a.s. for all t ≥ 0.
The main result of this work establishes convergence guarantees for these dynamics as stated below.
Theorem 4 (Almost sure convergence of state-dependent subgradient methods). Consider the distributed optimization problem in Eq. (1) and let Assumptions 1 and 2 hold. Assume a connected communication graph G and the subgradient method in Eq. (3). If the random matrices A t, X(t) in Eq. (3) are doubly stochastic and contracting, and the step-sizes {α(t)} follow Assumption 3, then for all initial conditions X(0) ∈ R n×d , Theorem 4 establishes the almost-sure convergence of the state variables to an optimal solution of Eq. (1), based on the consensus-based subgradient methods where the averaging matrices are doubly stochastic and contracting. Theorem 3 provides a simplified condition, the presence of averaging over the 'max-edge', which, when satisfied, implies the averaging matrix is contracting. Note that, as shown in Proposition 2, this simplified condition holds for Local Max-Gossip, Max-Gossip, and Load-Balancing averaging. Thus, we have the subsequent corollary following immediately from Proposition 2, Theorem 3, and Theorem 4.  for all initial condition X(0) ∈ R n×d , and some w * ∈ W * .
For the remainder of this section, we provide the key steps and results that are needed to prove Theorem 4. We defer the proof of these technical results to the Appendix.
The proof strategy for Theorem 4 can be broken down into two main steps: (i) showing that the evolution of the dynamics followed by the average state variable {x(t)} converges to a solution of the optimization problem in (1) and (ii) every node i ∈ [n] tracks the dynamics of this average state variable such that the tracking error goes to zero. The first step requires the following result which establishes a bound on the accumulation of the tracking error for every agent.
Lemma 1. Let G be a connected graph and consider sequences {W (t)} and {X(t)} generated by the subgradient method in Eq. (3) using sate-dependent, doubly stochastic and contracting averaging matrices A t, X(t) . If Assumptions 2 and 3 hold, then for any initial estimates X(0) ∈ R n×d , the following hold a.s. for all Lemma 1, which is proven in Appendix D, establishes guarantees on the consensus error for the local estimates w i (t). Lemma 2 will be used to bound the distance of the average statex(t) to an optimal point. Lemma 2 (Lemma 8, [19]). Suppose that Assumption 2 holds. Then, for any connected graph G, We note that Lemma 8 in [19] was originally intended for state independent dynamics. However, its proof only relies on the double stochasticity of the averaging matrices, convexity of the local functions, boundedness of the subgradients, and not on whether the averaging is statedependent or not. Finally, combining the above two results implies that the distance of each agent's local estimate x i (t) to the optimal set W * will be approximately decreasing. The following result then will be used to show that this approximate decrease results in convergence to W * . Lemma 3. Consider a minimization problem min x∈R d f (x), where f : R d → R is a continuous function. Assume that the solution set X * of the problem is nonempty. Let {x t } be a stochastic process such that for all x ∈ X * and for all t ≥ 0, where b t ≥ 0, a t ≥ 0, and c t ≥ 0 for all t ≥ 0 and ∞ t=0 b t < ∞, ∞ t=0 a t = ∞, and ∞ t=0 c t < ∞ a.s. Then the sequence {x t } converges to a solution x * ∈ X * a.s. This result has been proven as part of [20, Theorem 1] but due to the stand-alone significance of the result we have stated it as a lemma above and its proof is provided in Appendix E. Now, we are ready to formally prove Theorem 4 by combining the aforementioned results.
Proof of Theorem 4. From Lemma 2, for v = w * ∈ W * , we have for all t ≥ 0. From Lemma 1, we know that Furthermore, α(t) is not summable and ∞ t=0 α 2 (t) < ∞. Therefore, all the conditions for Lemma 3 hold with a t = 2α(t + 1)/n, b t = 0, and Therefore, from Lemma 3, the sequence {x(t)} converges to a solutionŵ ∈ W * almost surely. Finally, Lemma 1 implies that lim t→∞ w i (t + 1) −x(t) = 0 for all i ∈ [n] almost surely. Therefore, the sequences {w i (t + 1)} converge to the same solutionŵ ∈ W * for all i ∈ [n] almost surely.

Convergence Rate
In this section we discuss the convergence rate of the time-averaged version of the discussed statedependent consensus based subgradient methods when the step size at time t is set as 1/ √ t for t ≥ 1. The convergence rates for the different algorithm differ via the contraction factor λ defined for the contracting averaging matrix through (16).
Let λ t be the contraction factor defined through the contracting property of the matrices at time t. More precisely, for all t ≥ 0 where λ t = λφ t with φ t ∈ (0, 1). Here, λ is the uniform bound on the contraction factor and λ t = λ t (X(t)) is a state-dependent (and possibly time-dependent) contraction factor. We refer to the tighter contraction bound to point out the improvement in convergence rate in state-dependent consensus based subgradient method. The proof of the convergence rates closely follow the proof provided in [19].
In the following lemma, we establish the convergence rate of the accumulation of error between the estimate for each agent from the mean of the estimates over all agents. and where Repeatedly applying the above inequality and since the perturbation is bounded as V (E(t)) ≤ L 2 t for all t ≥ 1 we get For brevity, define φ(t : s) = t k=s φ(k) and rewrite the above inequality as To obtain the bound on accumulation of the errors, using (19) we get where c 1 (t), c 2 (t) are given by Using the decreasing property of α(t), the fact that φ(t) ≤ 1 for all t ≥ 0, and the expression for a sum of a geometric series, we can uniformly bound c 1 (t) by where the second inequality in (21) follows from Finally using the fact that t k=0 α(k + 1) ≥ t+1 0 du u+1 ≥ √ t + 1 we get inequality (18).
Using the accumulation of variance of the state estimates we establish an upper bound on the expected deviation of the global function at the time-averaged version of the average state estimates from the optimal value in the following lemma.
Finally, we provide a bound on the expected deviation of the global function computed at the time averaged version of the state estimates of any agent from the optimal value in the following theorem.

Proof. By the boundedness assumption of the subgradients we have
Using the above inequality and Lemma 5 we get

Discussion
The subgradient method converges to the optimal at the rate of O( ln t √ t ). For randomized gossip, the convergence rate is comparable to the result that can be obtained from the result in Theorem 5 from the result in [19,Theorem 2]. However the approach in [19] cannot be directly used to state the result in Theorem 5 since the proof involves establishing inequality for every coordinate of the vector estimates and summing up the resulting inequalities. Such an approach cannot be extended to state-dependent averaging algorithms discussed in this work since the averaging step depends on the 2 norm of the difference between the nodes' estimates and cannot be decoupled to establish result on individual coordinates. Another reason behind using the contraction factor approach is the lack of B-connectivity result for the interaction between the agents when using state-dependent averaging.
The hidden constant terms of the convergence rate, O( ln t √ t ), are influenced by the consensus algorithm used with the subgradient descent. In Theorem 5 the consensus step of the algorithms influences the convergence rate through the constants K 1 , K 2 such that the convergence becomes faster as the constants decrease. Note that K 1 , K 2 are upper bounds for c 1 (t), c 2 (t) defined through (20). Based on Theorem 3, the contraction factor λ = 1 − 2δ (n−1)diam(G) 2 is obtained in the following corollary, where δ for Randomized Gossip, Local Max-Gossip, Max-Gossip, and Load Balancing are provided through Proposition 2.

Remark 2.
We may also comment that the above result uses a conservative bound on the contraction factor λ > 0. The values mentioned in Corollary 2 are upper bounds on the constants in the convergence rate. However, tighter bounds on the constants K 1 , K 2 are possible. For Randomized Gossip, the contraction factor can be improved to the square of the second largest eigenvalue of the expected averaging matrix E[A(t, X(t))].
In principle, in the proof of Theorem 5, for each of the state-dependent algorithm, such a contraction factor would depend on the sample path (past trajectory) of the dynamics. For example, when the consensus scheme used is Load Balancing, we know that for most practical purposes, when the nodes do not have multiple neighbors with maximal disagreement, the constant δ in Proposition 2 is even grater than 1 2 , more precisely, it is Ce(X) 2 , where C e is the number of edges over which the exchange is taking place in the averaging step with the state estimate X ∈ R n×d . With the improved δ, the bound on the constants K 1 , K 2 can be improved to (n−1)diam(G) 2 2Ce(X(t)) Similarly the bounds on the convergence rate for Local Max-Gossip can be improved by using tighter contraction factor for the averaging matrices. However as seen from [13,Theorem 2], the contraction factor may take cumbersome form which cannot be readily used to establish better bounds on c 1 (t), c 2 (t).
The problem of finding useful convergence rate for state-dependent averaging is a non-trivial open problem.

Numerical Examples
To illustrate our analytical results, we present a simulation of a distributed optimization problem where the local functions' subgradients are not restricted to be uniformly bounded. In particular, we look at the standard distributed estimation problem in a sensor network setting with n = 180 agents. Here, each agent i ∈ [n] wants to estimate an unknown parameter θ 0 . Each node has access to a noisy measurement of the parameter c i = θ 0 + n i , where n i 's are independent, zero mean Gaussian random variables with variance σ 2 i > 0. In this setting, the Maximum Likelihood (ML) estimator [21,Theorem 5.3] is the minimizer of the separable cost function F (w) = n i=1 (w − c i ) 2 /σ 2 i . Note that this problem is a distributed optimization problem with the local cost function f i (w) = (w − c i ) 2 /σ 2 i . For the variance σ 2 i , we picked 1/σ 2 i independently and uniformly over (0, 1). For each node i ∈ [n], the initial local estimates x i (0) are drawn independently from a standard Gaussian distribution.
We consider the performance for different topologies of the underlying communication graph G ranging from dense graphs (Complete and Barbell), moderately dense graphs (Erdös-Rényi), to sparse graphs (Line and Star). We chose a connected graph with the edge probability p = 0.4 for Erdös-Rényi graph. For the Barbell graph, we chose equal number of nodes for the three components -two Complete graphs and the connecting Line graph.
We ran the averaging-based subgradient optimizer with four different averaging update rules: Randomized Gossip [5], Local Max-Gossip, Max-Gossip, and Load-Balancing. For the Randomized Gossip, at each time a node in [n] wakes up uniformly at random, and it chooses one of its neighbors uniformly at random for communication. To account for the stochastic nature of Randomized Gossip and Local Max-Gossip algorithms we average the error values over 10 runs keeping the initial conditions and samples at the nodes the same. The resulting plots in Fig. 1, show the decay of the error w(t) − w * 1 as a function of t, where w * = n i=1 is the optimal solution for F (w). For the Erdös-Rényi communication graph, we also plot the decay of the error with the number of bits exchanged between the nodes in Fig. 2 for Randomized Gossip, Local Max-Gossip, and Load-Balancing.
In the simulation, 32 bits are used for exchange of the estimates and 1 bit is used for the exchange of each acknowledgement. Therefore, the number of bits exchanged per step for Randomized Gossip is 64. For Local Max-Gossip, at time t with s(t) ∈ [n] being the randomly chosen node, |N s(t) | + 32|N s(t) | + 32 bits are exchanged for waking up the neighboring nodes, obtaining their values, and sending the neighbor with the maximum disagreement its own value. Finally, for Load Balancing, 32 n i=1 |N i | + n + ACK(t) bits are exchanged for sharing the values with the neighbors, sending request to the neighbour with the maximum disagreement, and sending the acknowledgement, where ACK(t) is the total number of bits exchanged for sending the acknowledgement bits at time t. 2

Comparison of Asynchronous Methods
From Fig. 1, the performance of the subgradient methods using state-dependent averaging shows an improvement in convergence rate. The convergence rates increase as we go from Randomized Gossip, Local Max-Gossip, Max-Gossip to Load-Balancing averaging based optimizers. We will refer to the subgradient methods using the state-dependent averaging by their averaging algorithm in the succeeding discussion.
In general, the performance of Max-Gossip is superior to the one of Local Max-Gossip. Clearly, Local Max-Gossip converges faster than Randomized Gossip. However convergence rate also depends on the graph topology: Local Max-Gossip applied on a Star graph has essentially the same rate as Randomized Gossip since the nodes at the periphery have only the central node as the choice to gossip with, and the probability of the first node being selected for gossiping is n−1 times larger to be a peripheral node as compared to the central node. Overall, we notice the increase in the performance of Max-Gossip and Local Max-Gossip as compared to Randomized Gossip with increasing connectivity. Moreover, from Fig. 2 we note the significantly better performance of Local Max-Gossip with respect to the number of exchanges between the nodes as opposed to that of synchronous Load-Balancing.

Max-Gossip vs. Load-Balancing
When comparing different state-dependent averaging schemes, it should be noted that unlike gossip, Max-Gossip, and Local Max-Gossip, Load-Balancing is a synchronous scheme where in addition to the max-edge, other local max-edges are often incorporated in the averaging scheme simultaneously. Therefore, it is only natural that the convergence rate of Load-Balancing is superior to that of Max-Gossip, since it averages not only the two nodes defined by the max-edge, but, additionally, other nodes connected by edges with large disagreement at the same time. By a similar logic, for the Complete graph, the performance of Load-Balancing and Max-Gossip are the same since all the nodes are holding scalar estimates and due to the ordering between the estimates,  all the nodes send their request for averaging to either the node with the maximum or minimum estimate resulting in only the max-edge performing the updates. We observe that the gap in performance of Load-Balancing and Max-Gossip, which has the best performance amongst the discussed asynchronous methods, increases with the diameter of the graph. Characterizing the analytical dependence of convergence rate as a function of graph topology metrics is of interest for future work.

Logistic Regression
In order to illustrate the applicability of the results to a more general high-dimensional convex problem, we look at an example of regularized logistic regression for classification over MNIST dataset containing 56000 samples. In the experiment we train a model with the loss function where {(x j , y j )} 56000 j=1 are the samples used for training. The samples are used to classify the digits in MNIST dataset into two classes based on whether the digits are greater than or equal to 5 or not. The experiment is run over a graph with 20 nodes with each node containing the same number of samples from the dataset. We initialize the nodes with all zero vectors.
The communication graph representing the underlying connection between the nodes is a ladder graph. We consider the performance for the averaging-based subgradient optimizer with Randomized Gossip, Local Max-Gossip, Max-Gossip, and Load Balancing. For Randomized Gossip, as in previous experiment, at each time a node in [n] wakes uniformly at random and chooses one of its neighbor uniformly at random. We average the performance for Randomized Gossip and Local Max-Gossip over 3 runs. In Fig. 3 we plot the network variance, W (t) − 11 T n W (t) 2 F for step-size α(t) = 1 t for all t ≥ 1. We observe that the decay in the loss of the function for the consensus-based subgradient method is similar to each other. However the decay of the network variance, defined as the sum of the square of the deviation of the state estimates from their mean, over time in decreasing order of speed is observed for Load Balancing, Max-Gossip, Local Max-Gossip, and finally Randomized Gossip.

Conclusions
We proposed, studied, and analyzed the role of maximal dissent nodes in distributed optimization schemes, leading to many exciting state-dependent consensus-based subgradient methods. The proof of our result relies on a certain contraction property of these schemes. Our result opens up avenues for synthesizing or extending the use of state-dependent averaging-schemes for distributed optimization including the Max-Gossip, Local Max-Gossip, and Load-Balancing algorithms. Finally, we compared simulation results of a distributed estimation problem for gossip-based subgradient methods and the proposed state-dependent algorithms. Our numerical experiments show the faster convergence speed of schemes that use maximal dissent between nodes compared with state-independent gossip schemes. These simulations strongly support the intuition behind our main result, i.e., mixing of information between the maximal dissent nodes is critically important for the working (and enhancing) of the consensus-based subgradient methods. Although, we have shown the convergence of such state-dependent algorithms, establishing their rate of convergence, and especially relating them to various graph quantities such as diameter and edge density of the graph remains open problems for future research endeavors. The introduction of a state-dependent element for other class of algorithms specifically those which provide linear convergence rates such as distributed gradient tracking method [22,23] and their convergence analysis are part of future direction for the problem.

A Proof of Proposition 1
Proof of Proposition 1. For any ω ∈ Ω, consider X(t; ω) ∈ R n×d . If nodes i and j update their values to their average, that is x i (t; ω) + x j (t; ω) /2, then we know that during the round of Load-Balancing algorithm starting at value X(t; ω) in step 2, node i and node j have sent their averaging request to each other. Therefore, we have j ∈ arg max r∈N i x j (t; ω) − x r (t; ω) and i ∈ arg max r∈N j x i (t; ω) − x r (t; ω) . Hence, for any ω ∈ Ω, On the other hand, if Eq. (23) holds with strict inequality, then node i and node j send averaging requests only to each other in step 2 and respond to each other in step 3, and carry out their averaging according to step 4.

B Proof of Proposition 2
Proof. We first discuss the result for Randomized Gossip, Local Max-Gossip, and Max-Gossip averaging. The averaging matrices for the gossip algorithms where two agents update their states to their average takes the form of Eq. (6). Therefore, for these gossip algorithms we have and Consider two nodes i, j ∈ [n] such that {i, j} ∈ E. For Randomized Gossip, E A t, X(t) ij | F t = (P ij + P ji )/2n. Moreover, since {i, j} ∈ E, we have P ij , P ji > 0. Let P * = min {i,j}∈E P ij . For the max-edge {i * , j * }, Eq. (12) holds with δ = P * /n > 0.
Let i ∈ [n] and state estimate matrix X(t). For Local Max-Gossip, let r i X(t) be determined according to Eq. (9). Consider the max-edge e max X(t) = {i * , j * }. Then, r i * X(t) = j * and r j * X(t) = i * . Thus, and Local Max-Gossip averaging satisfies inequality Eq. (12) with δ = 1/n.
Similarly, for the Max-Gossip averaging with state estimate X(t) at time t, for the max-edge e max X(t) = {i * , j * }, we have and Eq. (12) holds with δ = 1/2. Let us now discuss the presence of max-edge in the Load-Balancing averaging scheme. Consider the state estimate matrix X(t) and e max X(t) = {i * , j * } to be the max-edge with respect to X(t). By the definition of a max-edge we know that nodes i * , j * satisfy inequality Eq. (11).
Consider the case when nodes i * , j * satisfy Eq. (11) with strict inequality. From Proposition 1, we know that A(t, X(t)) i * j * , A t, X(t) j * i * , A t, X(t) i * i * , A t, X(t) j * i * are equal to 1/2, which implies that A t, X(t) i * = A t, X(t) j * = 0 for all ∈ {i * , j * }. Therefore, and the inequality in Eq. (12) holds with δ = 1/2.
Finally, consider the case when there are multiple neighbors of nodes i * , j * with distance equal to x i * (t) − x j * (t) . Let |S i * | ≥ 1 and |S j * | ≥ 1 where S i is given by Eq. (10). Then, according to Load-Balancing algorithm, nodes i * , j * update their states to their average with probability and Eq. (12) holds with δ = 1/2(n − 1) 2 .

C Proof of Theorem 3
To prove Theorem 3 we must first define a few quantities related to the distance between the nodes on the graph and their relationships.
Definition 3. Consider a connected graph G and a matrix X = [x 1 , . . . , x n ] T ∈ R n×d such that x i ∈ R d is the estimate at node i in the graph G. Let d(X) denote the maximal distance between the estimates of any two nodes in the graph d(X) max i,j∈{1,2,...,n} Let d G (X) denote the maximal distance between the estimates among any two connected nodes in the graph d G (X) max {i,j}∈E Finally, let diam(G) denote the longest shortest path between any two nodes of the graph G.
Proposition 6. Given a connected graph G and a matrix X = [x 1 , . . . , x n ] T ∈ R n×d , such that x i ∈ R d is the solution estimate at node i in the graph G, we have Proof. The upper bound on d G (X) follows from Eqs. (24) and (25) in Definition 3. To prove the lower bound on d G (X), we assume, without loss of generality, that the rows of the matrix X ∈ R n×d are such that d(X) = x 1 − x n . Since G is connected, its diameter is finite and there is a path of length k ≤ diam(G), denoted by is bounded as where Eq. (26) follows from the triangle inequality. Finally, each term in the sum Eq. (26) is bounded above by d G (x). Hence, Next, we state a result quantifying the decrease in the Lyapunov function defined in Eq. (13) that is the vector form of [18, Lemma 1]. Lemma 6. Given a doubly stochastic matrix A ∈ R n×n , let c ij denote the (i, j)-th entry of the matrix A T A. Then for all X = [x 1 , . . . , x n ] T ∈ R n×d , we have Proof. By definition, the Lyapunov function in Eq. (13) can be written as The doubly stochasticity of A implies AX = 11 T n AX = 11 T n X = A11 T n X = AX. Therefore, Finally, Since A T A is a symmetric and stochastic matrix, we have c ij = c ji and c ii = 1 − i =j c ij . Thus, where b i ∈ R n is the standard basis vector for all i ∈ [n]. Since we have Proof of Theorem 3. At time t ≥ 0 consider the state estimate X(t) = [x 1 (t), . . . , x n (t)] T ∈ R n , the corresponding max-edge e max (X(t)) = {i * , j * } and the doubly stochastic averaging matrix Define For legibility, we drop the time index in the variables for the rest of this proof and use X, F, A(X), Ω δ instead of X(t), F t , Ω δ (t), and A(t, X(t)).
Using arguments similar to the ones from [14, Lemma 9], for X ∈ F and doubly stochastic matrix where F is a σ-field, X ∈ F, and e max (X) = {i * , j * }. We will show that E V (A(X)X) | F ≤ λV (X) a.s. for some λ ∈ (0, 1). From Lemma 6, the difference in the quadratic Lyapunov function V evaluated at X and A(X)X is given by where c ij (X) is the (i, j)-th entry of A(X) T A(X), i.e., c ij (X) = (A(X) T A(X)) ij . Taking the conditional expectation with respect to the filtration F, we obtain where e max (X) = {i * , j * } and the first inequality follows from the non-negativity of the squared terms and the second inequality follows from Eq. (27). Recall that the constant δ depends on the averaging scheme. If V (X) = 0, more precisely for the samples path characterized by ω ∈ Ω δ (t) such that V (X(t; ω)) = 0 3 , then X = 1c T for some c ∈ R d . Therefore, A(X)X = A(X)1c T = 1c T since A(X) is doubly stochastic and V (A(X)X) = 0. Thus, the inequality E V (A(X)X) | F ≤ λV (X) is satisfied.
x n ] T ∈ L, more precisely for the samples path characterized by ω ∈ Ω δ (t) such that X(t; ω) ∈ L, the conditional expected fractional decrease in the Lyapunov function is x i . Using the definition of d G (X) and Proposition 6, we obtain the following bound Note that g(X) satisfies the following invariance relations Therefore, for X ∈ L the following inequality and identity hold Note that if n i=1 z i = 0 and n i=1 z i 2 = 1, then we have By definition, d(Z) ≥ z i − z j for all i, j ∈ [n]. Using the fact that the maximum of a set of values is greater than its average for the set { z i − z j 2 } 1≤i<j≤n , we get where the last step follows from Eq. (28) and the fact that n i=1 z i 2 = 1. Finally, using Eq. (28), we get Since E V (A(X)X) | F ≤ λV (X) for X ∈ L and for X ∈ L, we have E V (A(X)X) | F ≤ λV (X) a.s. Thus, E V (A(t, X(t))X(t)) | F t ≤ λV X(t) a.s., where λ = 1 − 2δ/ (n − 1)diam(G) 2 .

D Limiting properties of the Lyapunov function V (·)
To prove Lemma 1 we will make use of the following result.
Theorem 7 (Robbins-Siegmund Theorem). Let (Ω, F, P) be a probability space and F 0 ⊆ F 1 ⊆ · · · be a sequence of sub σ-fields of F. Let {u t }, {v t }, {q t }, and {w t } be F t -measurable random variables, where {u t } is uniformly bounded from below, and {v t }, {q t }, and {w t } are non-negative. Let ∞ t=0 w t < ∞, ∞ t=0 q t < ∞ and for all t ≥ 0. Then, the sequence {u t } converges and ∞ t=0 v t < ∞ a.s. Proof of Lemma 1. To study the convergence of V W (t) , we first derive a super-martingale like inequality for the stochastic process V W (t) . For X(t) ∈ F t using the contracting averaging property of A(t, X(t)) in Eq. (16), we get E V W (t + 1) | F t = E V A(t, X(t))X(t) | F t ≤ λV X(t) , a.s., where λ ∈ (0, 1). We know that X(t) = W (t) + E(t), so from triangle inequality on W (t) − Using the inequality above in Eq. (29), for all t ≥ 0 we get E V W (t + 1) | F t ≤ λ V W (t) + V E(t) + 2 V W (t) V E(t) a.s.

E Proof of Lemma 3
To prove Lemma 3, we follow the proof in [20,Theorem 1].
Proof. For all x ∈ X * and t ≥ 0, we have For any x ∈ X * , Theorem 7 implies that { x t − x } converges and a t (f (x t (ω)) − f * ) < ∞ is such that P(Ω x ) = 1. Note that here we denote by {x t (ω)} t≥0 the sample path for the corresponding ω. Let X * d ⊆ X * be a countable dense subset of X * and Ω d = x∈X * d Ω x . We have P(Ω d ) = 1 since X * d is countable. For any ω ∈ Ω d , since ∞ t=0 a t = ∞ and ∞ t=0 a t f (x t (ω) − f * < ∞, we have lim inf From Eq. (35) and the continuity of f , for all ω ∈ Ω d , we have lim inf t→∞ x t (ω) − x * (ω) = 0, for some x * (ω) ∈ X * 4 . Consider a subsequence {x t k (ω)} k≥0 of {x t (ω)} t≥0 such that lim k→∞ f x t k (ω) = f * .