A General Analysis of the Convergence of ADMM

By Robert Nishihara, Laurent Lessard, B. Recht, A. Packard, Michael I. Jordan. International Conference on Machine Learning, 2015

339 citations recorded by the source corpus.

We provide a new proof of the linear convergence of the alternating direction method of multipliers (ADMM) when one of the objective terms is strongly convex. Our proof is based on a framework for analyzing optimization algorithms introduced in Lessard et al. (2014), reducing algorithm convergence to verifying the stability of a dynamical system. This approach generalizes a number of existing results and obviates any assumptions about specific choices of algorithm parameters. On a numerical example, we demonstrate that minimizing the derived bound on the convergence rate provides a practical approach to selecting algorithm parameters for particular ADMM instances. We complement our upper bound by constructing a nearly-matching lower bound on the worst-case rate of convergence.

Subfields: Computational Mechanics, Control and Systems Engineering, Signal Processing

View Paper: https://www.semanticscholar.org/paper/aecf628ad1f28b8ae903bcfbd45af05c05c511fa

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Control and Systems Engineering

In Signal Processing

Citations in the corpus

An introduction to continuous optimization for imaging (2016, background): “…to be found in the literature, from the thesis of Eckstein (1989) to more recent 226 A. Chambolle and T. Pock convergence analyses (with rates) such as that of Nishihara et al. (2015) (Shefi and Teboulle 2014, He and Yuan 2015b, He and Yuan 2015c, Goldstein, O’Donoghue, Setzer and Baraniuk 2014).”
Adaptive Consensus ADMM for Distributed Optimization (2017, methodology): “In practice, however, the efficiency of ADMM is highly sensitive to this parameter choice (Nishihara et al., 2015; Ghadimi et al., 2015), and can be improved via adaptive penalty selection methods (He et al.”
Responsive Safety in Reinforcement Learning by PID Lagrangian Methods (2020, background): “Other recent works bring yet other perspectives from dynamical systems to deep learning and optimization, see for example (Lessard et al., 2014; Nishihara et al., 2015; Liu & Theodorou, 2019)).”
Decomposition into Low-rank plus Additive Matrices for Background/Foreground Separation: A Review for a Comparative Evaluation with a Large-Scale Dataset (2015, background): “The convergence of ADMM for convex objective functions has been proved [275][359][379][224][227][226].”
OSQP: an operator splitting solver for quadratic programs (2017, background): “Unfortunately, it is still an open research question how to select the optimal ADMM parameters, see [44,47,75].”