Authors: Robert Nishihara , Laurent Lessard , Benjamin Recht , Andrew K. Packard , Michael I. Jordan - International Conference on Machine Learning, ICML 2015 cited by 339
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.
✨ Checking sign-in… PDF Cited by View BibTeX Hide BibTeX View BibTeX Cite
On the Douglas-Rachford splitting method and th… On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators Parallel alternating direction multiplier… Parallel alternating direction multiplier decomposition of convex programs Distributed Optimization and Statistical Learnin… Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers An Alternating Direction Method for Dual MAP LP… An Alternating Direction Method for Dual MAP LP Relaxation On the Global and Linear Convergence of the… On the Global and Linear Convergence of the Generalized Alternating Direction Method of Multipliers Efficient Distributed Linear Classification… Efficient Distributed Linear Classification Algorithms via the Alternating Direction Method of Multipliers Online Alternating Direction Method Online Alternating Direction Method Diagonal scaling in Douglas-Rachford… Diagonal scaling in Douglas-Rachford splitting and ADMM Fast Alternating Direction Optimization… Fast Alternating Direction Optimization Methods On the linear convergence of the… On the linear convergence of the alternating direction method of multipliers Convergence Rate Analysis of Several… Convergence Rate Analysis of Several Splitting Schemes Faster Convergence Rates of Relaxed… Faster Convergence Rates of Relaxed Peaceman-Rachford and ADMM Under Regularity Assumptions Tight linear convergence rate bounds for… Tight linear convergence rate bounds for Douglas-Rachford splitting and ADMM Fast-and-Light Stochastic ADMM Fast-and-Light Stochastic ADMM Convergence Rate of Distributed ADMM Over… Convergence Rate of Distributed ADMM Over Networks Adaptive ADMM with Spectral Penalty… Adaptive ADMM with Spectral Penalty Parameter Selection Adaptive Consensus ADMM for Distributed… Adaptive Consensus ADMM for Distributed Optimization Adaptive Relaxed ADMM: Convergence Theory and… Adaptive Relaxed ADMM: Convergence Theory and Practical Implementation Dykstra's Algorithm, ADMM, and Coordinate… Dykstra's Algorithm, ADMM, and Coordinate Descent: Connections, Insights, and Extensions Adaptive ADMM for Distributed AC Optimal… Adaptive ADMM for Distributed AC Optimal Power Flow Parameter Selection and Preconditioning for a… Parameter Selection and Preconditioning for a Graph Form Solver On Systems and Algorithms for… On Systems and Algorithms for Distributed Machine Learning Accelerated Variance Reduction Stochastic… Accelerated Variance Reduction Stochastic ADMM for Large-Scale Machine Learning Quantifying the asymptotic linear… Quantifying the asymptotic linear convergence speed of Anderson Acceleration applied to ADMM A General Analysis of the Convergence of ADMM A General Analysis of the Convergence of ADMM Earlier references Focus paper Citing papers Older Newer Click a node to pin it, click the empty canvas to go back to this paper, or hover to preview. Open a node’s page from its title.
