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 alternating direction method of multipliers (ADMM) algorithm can be seen as a lifting of gradient descent. 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.
For quadratic problems, there are explicit results on the convergence rate and optimal parameters of ADMM @cite_0 @cite_10 @cite_13 . However, their assumptions do not hold for the non strongly convex distributed problem considered in this paper. Moreover, there are very few results comparing the optimal convergence rate of ADMM as a function of the optimal convergence rate of GD. For a centralized setting, an explicit comparison is provided in @cite_12 , but it assumes strong convexity.
@cite_0 @cite_10 @cite_12 @cite_13
2068628888 2037603831 2194067778 1537500458
This paper addresses the optimal scaling of the ADMM method for distributed quadratic programming. Scaled ADMM iterations are first derived for generic equality-constrained quadratic problems and then applied to a class of distributed quadratic problems. In this setting, the scaling corresponds to the step-size and the edge-weights of the underlying communication graph. We optimize the convergence factor of the algorithm with respect to the step-size and graph edge-weights. Explicit analytical expressions for the optimal convergence factor and the optimal step-size are derived. Numerical simulations illustrate our results. The alternating direction method of multipliers (ADMM) has emerged as a powerful technique for large-scale structured optimization. Despite many recent results on the convergence properties of ADMM, a quantitative characterization of the impact of the algorithm parameters on the convergence times of the method is still lacking. In this paper we find the optimal algorithm parameters that minimize the convergence factor of the ADMM iterates in the context of l 2 -regularized minimization and constrained quadratic programming. Numerical examples show that our parameter selection rules significantly outperform existing alternatives in the literature. The framework of Integral Quadratic Constraints of (2014) reduces the computation of upper bounds on the convergence rate of several optimization algorithms to semi-definite programming (SDP). Follow up work by (2015) applies this technique to the entire family of over-relaxed Alternating Direction Method of Multipliers (ADMM). Unfortunately, they only provide an explicit error bound for sufficiently large values of some of the parameters of the problem, leaving the computation for the general case as a numerical optimization problem. In this paper we provide an exact analytical solution to this SDP and obtain a general and explicit upper bound on the convergence rate of the entire family of over-relaxed ADMM. Furthermore, we demonstrate that it is not possible to extract from this SDP a general bound better than ours. We end with a few numerical illustrations of our result and a comparison between the convergence rate we obtain for ADMM with known convergence rates for Gradient Descent (GD). Consider a set of @math agents seeking to solve distributively the minimization problem @math where the convex functions @math are local to the agents. The popular Alternating Direction Method of Multipliers has the potential to handle distributed optimization problems of this kind. We provide a general reformulation of the problem and obtain a class of distributed algorithms which encompass various network architectures. The rate of convergence of our method is considered. It is assumed that the infimum of the problem is reached at a point @math , the functions @math are twice differentiable at this point and @math in the positive definite ordering of symmetric matrices. With these assumptions, it is shown that the convergence to the consensus @math is linear and the exact rate is provided. Application examples where this rate can be optimized with respect to the ADMM free parameter @math are also given.