DQM: Decentralized Quadratically Approximated Alternating Direction Method of Multipliers

Abstract

This paper considers decentralized consensus optimization problems where nodes of a network have access to different summands of a global objective function. Nodes cooperate to minimize the global objective by exchanging information with neighbors only. A decentralized version of the alternating directions method of multipliers (DADMM) is a common method for solving this category of problems. DADMM exhibits linear convergence rate to the optimal objective but its implementation requires solving a convex optimization problem at each iteration. This can be computationally costly and may result in large overall convergence times. The decentralized quadratically approximated ADMM algorithm (DQM), which minimizes a quadratic approximation of the objective function that DADMM minimizes at each iteration, is proposed here. The consequent reduction in computational time is shown to have minimal effect on convergence properties. Convergence still proceeds at a linear rate with a guaranteed constant that is asymptotically equivalent to the DADMM linear convergence rate constant. Numerical results demonstrate advantages of DQM relative to DADMM and other alternatives in a logistic regression problem.

13 pages

References in corpus (8)

• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• Optimal parameter selection for the alternating direction method of multipliers (ADMM): quadratic problems
• Convex Optimization for Big Data
• Decentralized Maximum Likelihood Estimation for Sensor Networks Composed of Nonlinearly Coupled Dynamical Systems
• On the Convergence of Decentralized Gradient Descent
• Network Newton-Part II: Convergence Rate and Implementation
• Network Newton-Part I: Algorithm and Convergence
• EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization

Cited by in corpus (19)

• An Exact Quantized Decentralized Gradient Descent Algorithm
• Distributed Optimization for Smart Cyber-Physical Networks
• A Primal-Dual Quasi-Newton Method for Exact Consensus Optimization
• Zeroth Order Nonconvex Multi-Agent Optimization over Networks
• Communication-Censored Linearized ADMM for Decentralized Consensus Optimization
• Decentralized Sparse Multitask RLS over Networks
• Variance-Reduced Stochastic Quasi-Newton Methods for Decentralized Learning: Part I
• Scaling-up Distributed Processing of Data Streams for Machine Learning
• Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Development
• Robust and Communication-Efficient Collaborative Learning
• Towards More Efficient Stochastic Decentralized Learning: Faster Convergence and Sparse Communication
• Linear Convergence of First- and Zeroth-Order Primal-Dual Algorithms for Distributed Nonconvex Optimization
• Exact Diffusion for Distributed Optimization and Learning --- Part II: Convergence Analysis
• A Survey of Distributed Optimization Methods for Multi-Robot Systems
• Decentralized Approximate Newton Methods for Convex Optimization on Networked Systems
• A Newton Tracking Algorithm with Exact Linear Convergence Rate for Decentralized Consensus Optimization
• Achieving Acceleration in Distributed Optimization via Direct Discretization of the Heavy-Ball ODE
• Newton Method over Networks is Fast up to the Statistical Precision
• Distributed Linearized ADMM for Network Cost Minimization