Communication-efficient Alternating Direction Method Of Multipliers For Decentralized Consensus Optimization

With the advent of 5G,IoT(Internet of Things),AI(artificial intelligence),and Cloud,the decentralized optimization algorithms have attracted increasing research at-tention in the past decade.In contrast to centralized methods,which transmit all local data to the cloud center or a single agent,the decentralized algorithms are more robust,easily implemented,and provide better privacy protection.However,communication,especially message movement among computing nodes,has become a common bottle-neck for efficient decentralized algorithms when big data are involved.This is due to high latency and limited bandwidth of the underlying network.For traditional decentralized algorithms,to converge to an optimal solution,nodes mainly perform the local update steps and communication steps,wherein the overall communication costs are determined by three elements:(i)the total number of iter-ations,(ii)the transmission scheduling during iterative local variable updating,and(iii)the message length per transmission.Among the well-studied algorithms solv-ing the decentralized optimization problems,alternating direction method of multipli-ers(ADMM)is hugely popular due to its stability of computation and fast convergence within a few tens of iterations.This thesis employs ADMM as the basic framework to design communication-efficient decentralized algorithms with less number of iterations,transmission,and message length,to solve a convex consensus optimization problem over a network.The-focuses of this thesis are as follows:1.This article first proposes a decentralized weighted alternating direction method of multipliers(WADMM)by assigning different weights to different arcs.The convergence rate of ADMM is determined by both the step size and the network topology.Traditional ADMM maximizes the convergence rate only by tuning the step size,while WADMM provides more flexibility by tuning the weights and is able to obtain a faster convergence rate.Further,for a dense network,by setting some weights as zeros,WADMM is able to obtain a good convergence rate though the number of communication arcs is limited.The communication cost at every iteration is reduced.2.Despite the improved convergence rate and reduced communication cost,there are several disadvantages of WADMM,e.g.the assigned weights are only dependent on the network topology,not on the data information,and once set,the weights will not change anymore.For the above reasons,a communication-censored ADMM(COCA)is proposed to adaptively reduce the number of transmissions per iteration.Commonly,the local update is calculated based on the previous iterate results.When the difference between the current local update and the pre-viously transmitted one is small,it is not necessary to do the information exchange since nodes could still use the previous iterates to do the update.By censoring the communication with less information,COCA is able to significantly reduce the overall communication cost spent in the process.3.Further,considering the message length spent in each transmission,this article de-velops a communication-efficient algorithm based on quantized and communication-censored ADMM(DQC-ADMM)to solve the decentralized dynamic consensus optimization problem,in which the local objective functions and the optimal so-lutions are time-varying.DQC-ADMM improves the overall communication-efficiency through two complementary strategies-the communication-censoring strategy reduces the number of transmissions,while the quantization strategy de-creases the message length of each transmission.DQC-ADMM can track the dynamic optimal solutions with less communication cost in contrast to the tradi-tional one.4.Finally,the computation cost spent in the optimization process is also taken into consideration.The attempts to combine both linearized ADMM and decentral-ized stochastic gradient descent(SGD)have been shown in this article.