Markov Chain Lifting and Distributed ADMM

Abstract

The time to converge to the steady state of a finite Markov chain can be greatly reduced by a lifting operation, which creates a new Markov chain on an expanded state space. For a class of quadratic objectives, we show an analogous behavior where a distributed ADMM algorithm can be seen as a lifting of Gradient Descent algorithm. This provides a deep insight for its faster convergence rate under optimal parameter tuning. We conjecture that this gain is always present, as opposed to the lifting of a Markov chain which sometimes only provides a marginal speedup.

This work was also selected for a talk at NIPS 2016, Optimization for Machine Learning Workshop (OPT 2016)

References in corpus (5)

• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• Optimal parameter selection for the alternating direction method of multipliers (ADMM): quadratic problems
• Location-Aided Fast Distributed Consensus in Wireless Networks
• Optimal scaling of the ADMM algorithm for distributed quadratic programming
• An Explicit Rate Bound for the Over-Relaxed ADMM