Study Of Distributed Alternating Direction Method Of Multipliers

Nowadays,with the explosive growth of the data,these conventional algorithms,which run on a single computer,become infeasible and impracticable for directly handling large-scale datasets in real-world applications.Furthermore,the centralized process-ing of distributed data will results in the additional overhead for data collection.These situations create several new challenges for big data analysis.Distributed machine learning rises with the concept of big data,and distributed techniques have been de-veloped for solving the large-scale machine learning problem.In these distributed algorithms,the Alternating Direction Method of Multipliers(ADMM)is a well-known optimization algorithm that has gained lots of attention due to its superior convergence properties and decomposability.By formulating the optimization problem as a glob-al consensus problem,ADMM can be used flexibly to solve many machine learning problems in a distributed manner.In distributed ADMM,the computing nodes solve small sub-problems by training its own local model variable in parallel,and aggregate all local variables to update the global variable until finding the global solution itera-tively.It has been proved that ADMM has a sublinear convergence rate under some mild conditions.Therefore,the thesis follows the study of distributed ADMM.The details can be summarized as the following four folds:1.Global consensus framework for distributed machine learning:To construct a framework for distributed machine learning,we propose a global consensus frame-work via distributed Alternating Direction Method of Multipliers(ADMM).The framework can decompose the original problem as a series of subproblems which can be solved efficiently by optimization algorithms in parallel,and then aggre-gate these local results of sub-problems to obtain a global result.The framework provides the foundation for the study of distributed machine learning algorithm-s,and the global consensus constraint is used to ensure all local results reach a global consensus.2.Group-based alternating direction method of multipliers for distributed linear classification:to solve the relative low convergence speed and an expensive time cost problem,we propose the Group-based Alternating Direction Method of Multipliers(GADMM)for the distributed linear classification task.To seek a faster convergence speed and better global consensus.GADMM casts a large-scale global problem into a number of medium size local sub-problems that can be solved by the dual coordinate descent method in parallel.In particular,the slave nodes that have similar local variables are divided into the same group by the model similarity-based grouping methods.In the group layer,the local variables are gathered to generate the group variables,and then the group vari-ables are aggregated to update the global variable,and that process repeats until global convergence.The theoretical analysis demonstrates that GADMM has an O(1/k)convergence rate and converges faster than the conventional distributed ADMM,where k is the number of outer iterations.The experimental results show that GADMM can reduce the number of outer iterations and improve the convergence speed,and thus can reduce the training time.This is consistent with the theoretical analysis.3.A fast distributed classification algorithm for large-scale imbalanced data:in the literature,the widely-existing class imbalance problem has not been well inves-tigated.Furthermore,previous imbalanced classification methods lack of efforts in studying the complex imbalance problem in a distributed environment.In a distributed environment,we consider the imbalance problem as distributed data imbalance which includes three imbalance issues:(i)within-node class imbal-ance,(ii)between-node class imbalance,and(iii)between-node structure imbal-ance.In order to adequately deal with imbalanced data as well as improve time efficiency,a novel distributed Cost-Sensitive classification algorithm via Group-based ADMM(CS-GADMM)is proposed.Briefly,CS-GADMM derives the classification problem as a series of sub-problems with within-node class im-balance.To alleviate the time delay caused by between-node class imbalance,we propose a extension of dual coordinate descent method for the sub-problem optimization.Meanwhile,for between-node structure imbalance,we discreetly study the relationship between local functions,and combine the resulting local variables intra-group to update the global variables for prediction.The experi-mental results on various imbalanced datasets validate that CS-GADMM could be a efficient algorithm for imbalanced classification.4.Distributed alternating direction method of multipliers integrated with variance reduction and Nesterov's acceleration:The Alternating Direction Method of Multipliers(ADMM)is a widely used optimization algorithm in machine learn-ing.Recently,a few advanced techniques have been developed to accelerate the convergence of ADMM,including variance reduction and Nesterov's accelera-tion method.Moreover,parallelization of ADMM has also been investigated to alleviate the big data problem.Then,a natural question is whether these tech-niques can be seamlessly integrated with ADMM.We focus on this question,and propose a novel distributed accelerated ADMM method by leveraging variance reduction and Nesterov's method.In particular,stochastic ADMM with variance reduction is introduced for sub-problem optimization.In addition to the acceler-ation step motivated by Nesterov's method,we propose a corrected local update symmetric dual update in the framework of D-A2DM2.Theoretically,we proved that these acceleration methods can be well integrated with ADMM,and acceler-ate the convergence rate.Empirically,we test our method on several benchmark datasets.The experimental results demonstrate that our method is much faster than distributed ADMM,and could be a highly efficient algorithm for practical use.