Randomized Primal-Dual Proximal Block Coordinate Updates

Abstract

In this paper we propose a randomized primal-dual proximal block coordinate updating framework for a general multi-block convex optimization model with coupled objective function and linear constraints. Assuming mere convexity, we establish its $O(1/t)$ convergence rate in terms of the objective value and feasibility measure. The framework includes several existing algorithms as special cases such as a primal-dual method for bilinear saddle-point problems (PD-S), the proximal Jacobian ADMM (Prox-JADMM) and a randomized variant of the ADMM method for multi-block convex optimization. Our analysis recovers and/or strengthens the convergence properties of several existing algorithms. For example, for PD-S our result leads to the same order of convergence rate without the previously assumed boundedness condition on the constraint sets, and for Prox-JADMM the new result provides convergence rate in terms of the objective value and the feasibility violation. It is well known that the original ADMM may fail to converge when the number of blocks exceeds two. Our result shows that if an appropriate randomization procedure is invoked to select the updating blocks, then a sublinear rate of convergence in expectation can be guaranteed for multi-block ADMM, without assuming any strong convexity. The new approach is also extended to solve problems where only a stochastic approximation of the (sub-)gradient of the objective is available, and we establish an $O(1/\sqrt{t})$ convergence rate of the extended approach for solving stochastic programming.

convergence rate results are presented in a more explicit way; numerical results are added

References in corpus (8)

• Global Convergence of ADMM in Nonconvex Nonsmooth Optimization
• On the Linear Convergence of the Alternating Direction Method of Multipliers
• A Block Successive Upper Bound Minimization Method of Multipliers for Linearly Constrained Convex Optimization
• On the convergence properties of a majorized ADMM for linearly constrained convex optimization problems with coupled objective functions
• Randomized First-Order Methods for Saddle Point Optimization
• On the Efficiency of Random Permutation for ADMM and Coordinate Descent
• Extended ADMM and BCD for Nonseparable Convex Minimization Models with Quadratic Coupling Terms: Convergence Analysis and Insights
• Hybrid Jacobian and Gauss-Seidel proximal block coordinate update methods for linearly constrained convex programming

Cited by in corpus (12)

• Decentralized Charging Control of Electric Vehicles in Residential Distribution Networks
• A Coordinate Descent Primal-Dual Algorithm with Large Step Size and Possibly Non Separable Functions
• A Primer on Coordinate Descent Algorithms
• First-order methods for constrained convex programming based on linearized augmented Lagrangian function
• Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
• A Primal-Dual Parallel Method with $O(1/\epsilon )$ Convergence for Constrained Composite Convex Programs
• Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming
• Hybrid Jacobian and Gauss-Seidel proximal block coordinate update methods for linearly constrained convex programming
• Accelerated Primal-Dual Proximal Block Coordinate Updating Methods for Constrained Convex Optimization
• Stochastic Primal-Dual Coordinate Method for Nonlinear Convex Cone Programs
• Stochastic Primal-Dual Coordinate Method with Large Step Size for Composite Optimization with Composite Cone-constraints
• A generic coordinate descent solver for nonsmooth convex optimization