On the complexity analysis of randomized block-coordinate descent methods

By Zhaosong Lu, Lin Xiao. 2013

262 citations recorded by the source corpus.

In this paper we analyze the randomized block-coordinate descent (RBCD) methods proposed in Nesterov (SIAM J Optim 22(2):341–362, 2012), Richtárik and Takáč (Math Program 144(1–2):1–38, 2014) for minimizing the sum of a smooth convex function and a block-separable convex function, and derive improved bounds on their convergence rates. In particular, we extend Nesterov’s technique developed in Nesterov (SIAM J Optim 22(2):341–362, 2012) 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 Richtárik and Takáč (Math Program 144(1–2):1–38, 2014). As a result, we also obtain a better high-probability type of iteration complexity. In addition, for unconstrained smooth convex minimization, we develop a new technique called randomized estimate sequence to analyze the accelerated RBCD method proposed by Nesterov (SIAM J Optim 22(2):341–362, 2012) and establish a sharper expected-value type of convergence rate than the one given in Nesterov (SIAM J Optim 22(2):341–362, 2012).

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computational Theory and Mathematics

Citations in the corpus

Distributed Coordinate Descent Method for Learning with Big Data (2013, neutral): “Methods of this type, in various settings, were studied by several authors, including Hsieh et al. (2008); Shalev-Shwartz & Tewari (2009); Nesterov (2012); Richt´arik & Tak´aˇc (2012c); Necoara et al. (2012); Tappenden et al. (2013b); Shalev-Shwartz & Zhang (2013b); Lu & Xiao (2013).”
Adding vs. Averaging in Distributed Primal-Dual Optimization (2015, neutral): “…coordinate descent papers, including (Richt´arik & Tak´aˇc, 2014; 2013b; 2012; Tappenden et al., 2015; Mareˇcek et al., 2014; Fercoq & Richt´arik, 2013; Lu & Xiao, 2013; Fercoq et al., 2014; Qu & Richt´arik, 2014; Qu et al., 2014) (Efﬁcient accelerated variants were considered in (Fercoq &…”
An asynchronous parallel stochastic coordinate descent algorithm (2013, methodology): “Extensions to minimization of composite functions are described by Richt´arik and Tak´aˇc [2011] and Lu and Xiao [2013].”
Katyusha: the first direct acceleration of stochastic gradient methods (2016, neutral): “t descent. Designing accelerated methods for coordinate descent is signicantly easier than designing that for stochastic gradient descent, and has indeed been done in many previous results including [16, 37, 38, 45].19 The fastest rate is O P i p L i=" where parameters L icorrespond to the coor”
Accelerated, Parallel, and Proximal Coordinate Descent (2013, neutral): “& parallel Tappenden et al, 2013 [22] YES × × 1st inexact Necoara & Clipici, 2013 [8] YES × × coupled constraints Lin & Xiao, 2013 [25] × × YES improvements Fercoq & Richtárik, 2013 [3] YES YES × 1st nonsmooth f Lee & Sidford, 2013 [4] × × YES 1st efficient accelerated Richtárik & Takáč, 2013 [14] Y”
The Physical Systems Behind Optimization Algorithms (2016, background): “RCGD has similar convergence rates to VGD, but has a smaller overall computational complexity, since its computational cost per iteration of RCGD is much smaller than VGD [10, 7].”
On optimal probabilities in stochastic coordinate descent methods (2013, methodology): “Serial stochastic coordinate descent methods were proposed and analyzed in [6, 13, 15, 18], and more recently in various settings in [12, 7, 8, 9, 21, 19, 24, 3].”
Randomized Block Coordinate Descent for Online and Stochastic Optimization (2014, background): “RBCD can choo se a constant step size and converge at the same rate as GD, although the constant is usually J times worse [22, 23, 17].”
Distributed Mini-Batch SDCA (2015, methodology): “Our analysis allows for flexible sampling schemes, including where data is distribute across machines, and combines a dependence on thsmoothness of the loss and/or the data spread (measured through the spectral norm).”
Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties (2014, result): “ and separably constrained convex smooth optimization, proving linear convergence for the strongly convex case and a sublinear 1/krate for the convex case. Richta´rik and Taka´ˇc [33] and Lu and Xiao [23] extended this work to composite minimization, in which the objective is the sum of a smooth con”
Coordinate descent with arbitrary sampling I: algorithms and complexity† (2014, methodology): “After the seminal work of Nesterov [24], which provided an early theoretical justification of these methods for unconstrained convex minimization, the study has been successively extended to L1-regularized [28,34], proximal [17,30], parallel [6,32], distributed [7,26,29] and primal-dual [26,38] vari”
A Unified Algorithmic Framework for Block-Structured Optimization Involving Big Data: With applications in machine learning and signal processing (2015, background): “Table 3) to solve convex problems; for example; see [5], [8], and [39]–[43].”
Linear Convergence of Randomized Feasible Descent Methods Under the Weak Strong Convexity Assumption (2016, methodology): “We can define a composite gradient mapping Lu and Xiao (2013); Nesterov (2013); Tappenden et al.”
Randomized First-Order Methods for Saddle Point Optimization (2014, unknown): “This paper is also motivated by the currently active research on block coordinate descent methods (see, e.g., [17, 11, 18, 20, 1, 13, 3]) for solving problems with a separable feasible set.”
A Globally Convergent Algorithm for Nonconvex Optimization Based on Block Coordinate Update (2014, methodology): “In recent works (e.g., [7, 22, 31, 37, 42, 44]), BCD methods have become very popular towards solving “big data” problems.”
On the Convergence of Asynchronous Parallel Iteration with Unbounded Delays (2016, background): “It was firstly established for convex smooth problems (both unconstrained and constrained) in [22] and then generalized to nonsmooth cases in [26,18].”
Parallel Random Coordinate Descent Method for Composite Minimization: Convergence Analysis and Error Bounds (2016, methodology): “Moreover, our proof for linear convergence is different from those in [18, 10, 23, 7].”