Accelerated Alternating Direction Method of Multipliers: an Optimal $O(1/K)$ Nonergodic Analysis
For researchers and practitioners using ADMM in sparse and low-rank learning, this method provides faster convergence without sacrificing solution structure.
The paper proposes an accelerated ADMM variant that achieves an optimal O(1/K) nonergodic convergence rate for linearly constrained convex problems, improving over the standard O(1/√K) nonergodic rate. This is the first ADMM-type method with such a rate, and it preserves sparsity and low-rankness better than ergodic averaging.
The Alternating Direction Method of Multipliers (ADMM) is widely used for linearly constrained convex problems. It is proven to have an $o(1/\sqrt{K})$ nonergodic convergence rate and a faster $O(1/K)$ ergodic rate after ergodic averaging, which may destroy the sparsity and low-rankness in sparse and low-rank learning, where $K$ is the number of iterations. In this paper, we modify the accelerated ADMM proposed in [Y. Ouyang, Y. Chen, G. Lan, and E. Pasiliao, An Accelerated Linearized Alternating Direction Method of Multipliers, SIAM J. on Imaging Sciences, 2015, 1588-1623] and give an $O(1/K)$ nonergodic convergence rate analysis, which satisfies $|F(x^K)-F(x^*)|\leq O(1/K)$, $\|Ax^K-b\|\leq O(1/K)$ and $x^K$ has a more favorable sparseness and low-rankness than the ergodic result. As far as we know, this is the first $O(1/K)$ nonergodic convergent ADMM type method for general linearly constrained convex problems. Moreover, we show that the lower complexity bound of ADMM type methods for the separable linearly constrained nonsmooth convex problems is $O(1/K)$, which means that our method is optimal.