Fast Classification Algorithms via Distributed Accelerated Alternating Direction Method of Multipliers Distributed machine learning has gained lots of attention due to the rapid growth of data. In this paper, we focus regularized empirical risk minimization problems, and propose two novel Distributed Accelerated Alternating Direction Method of Multipliers (DA2DM2) algorithms for distributed classification. Based on the framework of Alternating Direction Method of Multipliers (ADMM), we decentralize the distributed classification problem as a global consensus optimization problem with a series of subproblems. In DA2DM2, we exploit ADMM with variance reduction for subproblem optimization in parallel. Taking global update and local update into consideration respectively, we propose two acceleration mechanisms in the framework of DA2DM2. In particular, inspired by Nesterovu0027s accelerated gradient descent, we utilize it for global update to further improve time efficiency. Moreover, we also introduce Nesterovu0027s acceleration for local update, and develop the corrected local update and symmetric dual update to accelerate the convergence with only a little change in the computational effort. Theoretically, DA2DM2 has a linear convergence rate. Empirically, experimental results show that DA2DM2 converge faster than existing distributed ADMMbased classification, and could be a highly efficient algorithm for practical use.

CommunicationCensored Linearized ADMM for Decentralized Consensus Optimization In this paper, we propose a communication and computationefficient algorithm to solve a convex consensus optimization problem defined over a decentralized network. A remarkable existing algorithm to solve this problem is the alternating direction method of multipliers (ADMM), in which at every iteration every node updates its local variable through combining neighboring variables and solving an optimization subproblem. The proposed algorithm, called as  co mmunicationcensored  l inearized  A DMM (COLA), leverages a linearization technique to reduce the iterationwise computation cost of ADMM and uses a communicationcensoring strategy to alleviate the communication cost. To be specific, COLA introduces successive linearization approximations to the local cost functions such that the resultant computation is firstorder and lightweight. Since the linearization technique slows down the convergence speed, COLA further adopts the communicationcensoring strategy to avoid transmissions of less informative messages. A node is allowed to transmit only if the distance between the current local variable and its previously transmitted one is larger than a censoring threshold. COLA is proven to be convergent when the local cost functions have Lipschitz continuous gradients and the censoring threshold is summable. When the local cost functions are further strongly convex, we establish the linear (sublinear) convergence rate of COLA, given that the censoring threshold linearly (sublinearly) decays to 0. Numerical experiments corroborate with the theoretical findings and demonstrate the satisfactory communicationcomputation tradeoff of COLA.