Latency Aware Distributed ADMM over Networks

Methods based on the alternating direction method of multipliers (ADMM) has attracted academic attention because of its excellent convergence performance and potential application scenarios in many machine learning or optimization fields. However, classical distributed ADMM algorithm assumed ideal network communication, which do not consider the impact of network delay on computing performance. In this paper, based on the strategy of selecting bridges with lowest network latency and appropriate iterative process, we propose a latency aware distributed ADMM algorithm to alleviate the impact of network delay. The classical algorithm and proposed algorithm are tested and compared in real network scenarios. Experiments show that the proposed algorithm reduces the running time and improves the computing performance. Especially in networks with large delay, the effect is more obvious.


Introduction
Methods based on the alternating direction method of multipliers (ADMM) is a simple method to solve the problem of decomposable convex optimization, since Boyd proves that it is suitable for solving large-scale distributed optimization problem [1], this method has attracted academic research, and is widely used in various fields in recent years, including distributed machine learning, image processing, communications network optimization, Power system scheduling, etc. [2][3][4][5] The basic form of ADMM algorithm is as follows: ( ) In the above equation, ∈ , ∈ , ∈ × , ∈ × , ∈ , the objective function can be separated into several convex functions ( ) and ( ). There are two common architectures for parallel computing. One is the classical C/S architecture, it is a star-like network composed of a master node and several worker nodes. The other architecture is peer-to-peer. In this architecture, there is no master node, and each node has a piece of data, forming a decentralized network. Each node exchanges calculation results with its neighbors, and then achieves global convergence through continuous iteration. The ADMM algorithms implemented by the above two methods are Star-ADMM [6] and decentralized ADMM [7][8][9] respectively. Centralized networks are the earliest and most widely used networks, but also has very obvious flaws, the bottleneck lies in the center node traffic jams because all nodes need to communicate. Decentralized networks have similar total computational complexity, but the busiest nodes have much lower traffic than centralized ones. Therefore, the algorithms with decentralized networks is faster than centralized blocks in the case of low bandwidth or high latency [10]. In order to accelerate distributed ADMM, some scholars have proposed many different schemes [11][12], and we are very interested in a semi-centralized algorithm proposed in [7] [9]. This method is to select a group of nodes in the network as the master node, and their neighbor nodes as the worker node, this group of master nodes is called bridge nodes, the worker node can only communicate and exchange updates with the specified bridge node. We call it B-ADMM. B-ADMM greatly improves the convergence of the algorithm in the presence of noise, and greatly reduces the communication traffic of the master node in the centralized algorithm. It has excellent performance in the distributed ADMM solution. Of course, The acceleration of decentralized network largely depends on the choice of bridge nodes, but the existing research does not consider the network latency when selecting the bridge node.
Our research is based on B-ADMM and takes network latency into consideration in the selection strategy of bridge nodes and we propose a latency aware distributed ADMM algorithm (Greedy-Bridge-ADMM). Our proposed algorithm can select appropriate bridge nodes according to the latency of a specific network, and we allow the bridge nodes to communicate only with the work nodes. We use a virtual network simulation platform [13] to implement this algorithm and carry out a lot of research. The results show that the proposed algorithm has a faster convergence rate than the traditional algorithms when the network connectivity is poor or the network connection latency and variance cannot be ignored.
In the follow parts of this paper, we analyse the formulation of ADMM problem and propose our algorithm in section 2. In section 3, we compared our algorithm with traditional algorithm under different network conditions in real situation through virtual simulation platform. In section 4, we conclude the paper.

Problem formulation
We target at solving some optimization or machine learning problem over a computer network based on distributed ADMM algorithm. For example, consider solving the following problem over a network.
Let a graph G = (V, E) denoted the network, where V= {1..., n} is the set of nodes and E= {1..., m} is the set of edges. The Star-ADMM algorithm (the classical distributed ADMM algorithm) for solving (2) is presented in Algorithm 1 as follow.
Algorithm 1 Star-ADMM algorithm (the classical distributed ADMM algorithm) Form the graph G into a star network with a master node and n-1 worker nodes. for The master initializes and sends 0 z to worker i.
The worker i calculate the following formula.  The master calculates the following formula. ( The master sends From the iterative process of algorithm 1, we can see that each iteration of the algorithm has to wait for the feedback of all workers. Once the communication delay of nodes in the network is prone to fluctuation, deterioration or abnormality, the algorithm will be greatly limited.

Proposed algorithm
The basic idea of the proposed algorithm is to split the master node in the Star-ADMM algorithm into multiple bridges. And each bridge has some nodes as its own workers. The proposed algorithm plans these bridges and workers as little delay as possible, and makes all bridges in the computing cluster converge to the final calculation result through some precise iterative calculation. Specifically, the algorithm first selects a worker, and then checks whether it and its every neighbor have a common bridge. If it does not exist, a public bridge is selected according to the principle of minimum network delay. This goes back and forth until each worker and its every neighbor have a common bridge. Then, in the iterative process, each bridge and its workers perform iterative calculation. Because the bridges and workers in the whole computing cluster are cross connected with each other, the optimization or machine learning problem finally converges.
We call the proposed algorithm Greedy-Bridge-ADMM algorithm because the algorithm performs greedy search according to delay when selecting bridges and their workers. The pseudocode of the Greedy-Bridge-ADMM algorithm is shown in Algorithm 2. The symbols used in the algorithm are defined as follows.

Algorithm 2 Greedy-Bridge-ADMM algorithm (the proposed distributed ADMM algorithm) for
The worker i calculate the following formula.
The worker i calculate the following formula.
to their workers. end for end for k = k+1 end while

Algorithm analysis
As mentioned earlier, the proposed algorithm does not use the master in the Star-ADMM algorithm as a single computing center node, but selects multiple bridges and their workers in the network for calculation respectively. On the one hand, it reduces the computing pressure of the master. On the other hand, more importantly, compared with the master and workers in the Star-ADMM algorithm, the network delays between each bridge and its workers are smaller, which makes the whole computing process not limited to some links with poor delay. In the proposed algorithm, each pair of neighbors ensures that there is at least one common bridge, and the calculation results of each small calculation cluster composed of bridge and its workers are fully integrated in the step of

Experiments
Experiments run on a full connectivity cluster of 16 nodes on GENI [13]. Experiments setting retain part of the links and their delays to simulate various real network scenarios. The implemented LASSO problem is defined as follow.  In Figure 1, we compare the real convergence time of the Star-ADMM algorithm and Greedy-Bridge-ADMM algorithm in typical random network. In the figure, the abscissa is the running time(s) and the ordinate is the accuracy. As can be seen from Figure 1, the Greedy-Bridge-ADMM algorithm converges faster and can converge to a reasonable value in about 40 seconds, while the Star-ADMM algorithm needs to converge to a reasonable value in about 80 seconds. The final accuracy of the Greedy-Bridge-ADMM algorithm is slightly worse than that of the Star-ADMM algorithm, but within the acceptable range.  Figure 2, we compare the performance of the Star-ADMM algorithm and the Greedy-Bridge-ADMM algorithm in different network scenarios. Specifically, in Figure 2(a), the performance of the algorithm under different network connectivity is described. The abscissa in the figure is the connection probability between any two nodes, and the ordinate is the running time. It can be seen that the running time of the Star-ADMM algorithm and Greedy-Bridge-ADMM algorithm decreases with the increase of connection probability. However, the running time of the Greedy-Bridge-ADMM algorithm is always lower than that of the Star-ADMM algorithm, so the performance is better. At the same time, in Figure  2(b), lines describe the performance of the algorithm under different scenarios of network delay variance. The abscissa in the figure is the probability of the edge with large delay in the network, and the ordinate is the running time of the algorithm. It can be seen that the running time of the Star-ADMM algorithm and Greedy-Bridge-ADMM algorithm increases with the increase of large delay edge. However, the running time of the Greedy-Bridge-ADMM algorithm is always lower than that of the Star-ADMM algorithm, so the performance is better. Moreover, with the increase of large delay edges, the advantages of the Greedy-Bridge-ADMM algorithm are more obvious.

Conclusions
Distributed ADMM algorithm has been studied more and more widely because of its excellent convergence performance and potential application in many fields like the emerging machine learning, data analytics, and largescale network system applications. However, the existing research is still lacking, especially ignoring the real network situation such as the latency.
In this paper, we propose an algorithm to construct ADMM networks based on network latency. It selects the bridges according to the principle of minimum network latency on the premise that every worker node and its neighbor have the same bridge node. We call the proposed algorithm Greedy-Bridge-ADMM algorithm. We implemented and evaluated the algorithm in an emulated network. The results show that proposed algorithm achieves real convergence time acceleration with little precision sacrifice, and demonstrate better performance than classical ADMM in different network scenarios, especially in cases of large delay.