Markov Chain Lifting and Distributed ADMM
This provides insight into faster convergence for distributed optimization problems, though it appears incremental as it builds on known lifting concepts.
The paper shows that for quadratic objectives, distributed ADMM can be interpreted as a lifting of Gradient Descent, explaining its faster convergence rate under optimal tuning, with the gain conjectured to be always present unlike in Markov chain lifting.
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.