On the Complexity Analysis of Randomized Block-Coordinate Descent Methods

Abstract

In this paper we analyze the randomized block-coordinate descent (RBCD) methods proposed in [8,11] for minimizing the sum of a smooth convex function and a block-separable convex function. In particular, we extend Nesterov's technique developed in [8] for analyzing the RBCD method for minimizing a smooth convex function over a block-separable closed convex set to the aforementioned more general problem and obtain a sharper expected-value type of convergence rate than the one implied in [11]. Also, we obtain a better high-probability type of iteration complexity, which improves upon the one in [11] by at least the amount $O(n/\epsilon )$, where $\epsilon$ is the target solution accuracy and $n$ is the number of problem blocks. In addition, for unconstrained smooth convex minimization, we develop a new technique called {\it randomized estimate sequence} to analyze the accelerated RBCD method proposed by Nesterov [11] and establish a sharper expected-value type of convergence rate than the one given in [11].

26 pages (submitted)

References in corpus (4)

• Proximal Stochastic Dual Coordinate Ascent
• Parallel Coordinate Descent Methods for Big Data Optimization
• Inexact Coordinate Descent: Complexity and Preconditioning
• Iteration Complexity of Randomized Block-Coordinate Descent Methods for Minimizing a Composite Function

Cited by in corpus (14)

• Accelerated, Parallel and Proximal Coordinate Descent
• An Accelerated Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization
• Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity
• Iteration Complexity Analysis of Block Coordinate Descent Methods
• Randomized First-Order Methods for Saddle Point Optimization
• On Optimal Probabilities in Stochastic Coordinate Descent Methods
• Coordinate Descent with Arbitrary Sampling II: Expected Separable Overapproximation
• A Randomized Nonmonotone Block Proximal Gradient Method for a Class of Structured Nonlinear Programming
• Large-scale randomized-coordinate descent methods with non-separable linear constraints
• Stochastic Block Mirror Descent Methods for Nonsmooth and Stochastic Optimization
• Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties
• Linear Convergence of the Randomized Feasible Descent Method Under the Weak Strong Convexity Assumption
• Robust Block Coordinate Descent
• Separable Approximations and Decomposition Methods for the Augmented Lagrangian