Inexact Coordinate Descent: Complexity and Preconditioning

By Rachael Tappenden, Peter Richtárik, Jacek Gondzio. 2013

103 citations recorded by the source corpus.

One of the key steps at each iteration of a randomized block coordinate descent method consists in determining the update to a block of variables. Existing algorithms assume that in order to compute the update, a particular subproblem is solved exactly. In this work, we relax this requirement and allow for the subproblem to be solved inexactly, leading to an inexact block coordinate descent method. Our approach incorporates the best known results for exact updates as a special case. Moreover, these theoretical guarantees are complemented by practical considerations: the use of iterative techniques to determine the update and the use of preconditioning for further acceleration.

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).”
Distributed optimization with arbitrary local solvers (2015, background): “For previous work on randomized block coordinate descent we refer to [65].”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, background): “For previous work on randomized block coordinate descent we refer to the reader to [175] and [174].”
Parallel coordinate descent methods for big data optimization (2012, methodology): “This lemma was recently extended in [26] so as to aid the analysis of a serial coordinate descent method with inexact updates, i.e., with h ( x ) chosen as an approximate rather than exact minimizer of H 1 ,L ( x, · ) (see (17)).”
SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization (2015, methodology): “The interpretation of SDNA as a variant of the Iterative Hessian sketch method of Pilanci & Wainwright (2014) follows immediately from the following theorem.”
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].”
On the complexity analysis of randomized block-coordinate descent methods (2013, methodology): “Instead of using a deterministic cyclic order, recently many researchers proposed randomized strategies for choosing a block to update at each iteration of the BCD methods [1, 2, 14, 3, 8, 10, 11, 15, 12, 16].”
Let's Make Block Coordinate Descent Go Fast: Faster Greedy Rules, Message-Passing, Active-Set Complexity, and Superlinear Convergence (2017, methodology): “For example, in this section we consider Newton proximal-BCD updates as in several recent works [73, 89, 26].”
Separable approximations and decomposition methods for the augmented Lagrangian (2013, unknown): “Randomized coordinate and block coordinate descent methods were proposed and analysed in several settings, such as for smooth convex minimization problems [24,29,31], L1-regularized problems [38], composite problems [18,29,42], nonsmooth convex problems [10], nonconvex problems [19,25] and problems ”
Stochastic Dual Coordinate Ascent with Adaptive Probabilities (2015, unknown): “…attention in the past few years, and include SCD (Shalev-Shwartz & Tewari, 2011), RCDM (Nesterov, 2012), UCDC (Richtárik & Takáč, 2014), ICD (Tappenden et al., 2013), PCDM (Richtárik & Takáč, 2012), SPCDM (Fercoq & Richtárik, 2013), SPDC (Zhang & Xiao, 2014), APCG (Lin et al., 2014),…”
Iteration complexity of feasible descent methods for convex optimization (2014, background): “Assumption 2.3 This assumption is the same as Assumption 2.2 except that”
On randomized distributed coordinate descent with quantized updates (2016, background): “The iteration complexities of the randomized coordinate descent algorithms are analyzed in [7], [8] under a very general setup.”
Linear Convergence of Randomized Feasible Descent Methods Under the Weak Strong Convexity Assumption (2016, background): “(See, for example, Devolder et al. 2014; Bonettini 2011; Tappenden et al. 2016; Hua and Yamashita 2012; Necoara and Nedelcu 2014b.) • Flexibility and wide applicability.”
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, methodology): “For inexact variants of the randomized block coordinate descent algorithm in different settings than ours we suggest [187, 54, 20, 46].”
Distributed Block Coordinate Descent for Minimizing Partially Separable Functions (2014, methodology): “An efficient accelerated version was introduced by Fercoq and Richtárik [5], an inexact version was studied in [35], an asynchronous variant was studied by Liu and Wright [12], nonuniform variant by Richtárik and Takáč [24] and a way of handling nonsmooth functions was described in [6].”
Convergence Analysis of Inexact Randomized Iterative Methods (2019, methodology): “For inexact variants of the randomized block coordinate descent algorithm in different settings than ours we suggest [53, 15, 6, 12].”