A General Analysis of the Convergence of ADMM

Abstract

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.

10 pages, 6 figures

References in corpus (3)

• Online Alternating Direction Method
• Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions
• Douglas-Rachford Splitting: Complexity Estimates and Accelerated Variants

Cited by in corpus (37)

• OSQP: An Operator Splitting Solver for Quadratic Programs
• Provable Tensor Ring Completion
• Responsive Safety in Reinforcement Learning by PID Lagrangian Methods
• Adaptive ADMM with Spectral Penalty Parameter Selection
• Adaptive Consensus ADMM for Distributed Optimization
• The Analysis of Optimization Algorithms, A Dissipativity Approach
• Localized Linear Regression in Networked Data
• Asymptotic Errors for Teacher-Student Convex Generalized Linear Models (or : How to Prove Kabashima's Replica Formula)
• Accelerated Variance Reduced Stochastic ADMM
• Variable Selection and Task Grouping for Multi-Task Learning
• Convergent Block Coordinate Descent for Training Tikhonov Regularized Deep Neural Networks
• Dynamic Visualization and Fast Computation for Convex Clustering via Algorithmic Regularization
• A Direct Approach for Sparse Quadratic Discriminant Analysis
• Newton-Raphson Consensus under asynchronous and lossy communications for peer-to-peer networks
• Dykstra's Algorithm, ADMM, and Coordinate Descent: Connections, Insights, and Extensions
• Convex programming with fast proximal and linear operators
• A Unified Analysis of Stochastic Optimization Methods Using Jump System Theory and Quadratic Constraints
• Stochastic Variance-Reduced ADMM
• SnapVX: A Network-Based Convex Optimization Solver
• Adaptive Video Streaming over LTE Unlicensed
• Robust and Explainable Autoencoders for Unsupervised Time Series Outlier Detection---Extended Version
• Tight Linear Convergence Rate Bounds for Douglas-Rachford Splitting and ADMM
• On the Duality Gap Convergence of ADMM Methods
• Penalized Interaction Estimation for Ultrahigh Dimensional Quadratic Regression
• Alternating Direction Method of Multipliers for Decomposable Saddle-Point Problems
• Iteration-complexity analysis of a generalized alternating direction method of multipliers
• Statistical Outlier Identification in Multi-robot Visual SLAM using Expectation Maximization
• Tuning Over-Relaxed ADMM
• Localization of Control Synthesis Problem for Large-Scale Interconnected System Using IQC and Dissipativity Theories
• On the Asymptotic Linear Convergence Speed of Anderson Acceleration Applied to ADMM
• Triangle Lasso for Simultaneous Clustering and Optimization in Graph Datasets
• Accelerated Methods for the SOCP-relaxed Component-based Distributed Optimal Power Flow
• Improving Rate of Convergence via Gain Adaptation in Multi-Agent Distributed ADMM Framework
• A Derandomized Algorithm for RP-ADMM with Symmetric Gauss-Seidel Method
• Joint Hydrogeophysical Inversion: State Estimation for Seawater Intrusion Models in 3D
• Local Linear Convergence of the ADMM/Douglas--Rachford Algorithms without Strong Convexity and Application to Statistical Imaging
• Total Variation Regularized Tensor-on-scalar Regression