Accelerated Primal-Dual Proximal Block Coordinate Updating Methods for Constrained Convex Optimization

Abstract

Block Coordinate Update (BCU) methods enjoy low per-update computational complexity because every time only one or a few block variables would need to be updated among possibly a large number of blocks. They are also easily parallelized and thus have been particularly popular for solving problems involving large-scale dataset and/or variables. In this paper, we propose a primal-dual BCU method for solving linearly constrained convex program in multi-block variables. The method is an accelerated version of a primal-dual algorithm proposed by the authors, which applies randomization in selecting block variables to update and establishes an $O(1/t)$ convergence rate under weak convexity assumption. We show that the rate can be accelerated to $O(1/t^2)$ if the objective is strongly convex. In addition, if one block variable is independent of the others in the objective, we then show that the algorithm can be modified to achieve a linear rate of convergence. The numerical experiments show that the accelerated method performs stably with a single set of parameters while the original method needs to tune the parameters for different datasets in order to achieve a comparable level of performance.

Accepted to Computational Optimization and Applications

References in corpus (5)

• Randomized Primal-Dual Proximal Block Coordinate Updates
• A Class of Randomized Primal-Dual Algorithms for Distributed Optimization
• Accelerated Douglas-Rachford methods for the solution of convex-concave saddle-point problems
• Accelerated Alternating Direction Method of Multipliers: an Optimal $O(1/K)$ Nonergodic Analysis
• Hybrid Jacobian and Gauss-Seidel proximal block coordinate update methods for linearly constrained convex programming

Cited by in corpus (1)

• First-order methods for constrained convex programming based on linearized augmented Lagrangian function