Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems

By Yin Tat Lee, Aaron Sidford. 2013

232 citations recorded by the source corpus.

In this paper we show how to accelerate randomized coordinate descent methods and achieve faster convergence rates without paying per-iteration costs in asymptotic running time. In particular, we show how to generalize and efficiently implement a method proposed by Nesterov, giving faster asymptotic running times for various algorithms that use standard coordinate descent as a black box. In addition to providing a proof of convergence for this new general method, we show that it is numerically stable, efficiently implementable, and in certain regimes, asymptotically optimal. To highlight the power of this algorithm, we show how it can used to create faster linear system solvers in several regimes: - We show how this method achieves a faster asymptotic runtime than conjugate gradient for solving a broad class of symmetric positive definite systems of equations. - We improve the convergence guarantees for Kaczmarz methods, a popular technique for image reconstruction and solving over determined systems of equations, by accelerating an algorithm of Strohmer and Vershynin. - We achieve the best known running time for solving Symmetric Diagonally Dominant (SDD) system of equations in the unit-cost RAM model, obtaining a running time of O(m log3/2n (log log n)1/2 log((log n)/eps)) by accelerating a recent solver by Kelner et al. Beyond the independent interest of these solvers, we believe they highlight the versatility of the approach of this paper and we hope that they will open the door for further algorithmic improvements in the future.

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

Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, background): “All of these three properties were connected in a single algorithm in [35], to which we refer the reader for a review of the early developments in the area of RCD, particularly to overview in Table 1 therein.”
Coordinate descent algorithms (2015, methodology): “” The more effective approach of [23] performs a change of variables from ṽk and ỹk to two other vectors v̂k and ŷk that can be updated in O(|Aik |) operations.”
A Proximal Stochastic Gradient Method with Progressive Variance Reduction (2014, methodology): “Such weighted sampling schemes have also been proposed for the Prox-SDCA method [35], as well as for coordinate descent methods [24, 26, 18].”
Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods (2017, methodology): “Accelerated variants of RCD were studied in [2,20,43].”
Stochastic Optimization with Importance Sampling for Regularized Loss Minimization (2014, neutral): “M L ] 1 3 Ja n 20”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, background): “Numerous follow-up works extended the concept to proximal setting [148], single processor parallelism [24, 151] and develop efficiently implementable acceleration [96].”
Accelerated, Parallel, and Proximal Coordinate Descent (2013, methodology): “Fix ω and ω1, . . . , ωj and let us ask the question: for what data matrix A will the ratio θ = ‖vrt‖1/‖vfr‖1 be maximized?”
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations (2013, unknown): “3.1 Gradient Descent: Let ‖ · ‖ : Rn → R be an arbitrary norm on Rn and recall that the gradient of a function f : Rn → R at ~x is defined as the vector ∇f(~x) ∈ Rn such that (3.1) f(~y) = f(~x) + 〈∇f(~x), ~y − ~x〉+ o(‖~y − ~x‖).”
Randomized Iterative Methods for Linear Systems (2015, background): “While classical iterative methods are deterministic, recent breakthroughs suggest that randomization can play a powerful role in the design and analysis of efficient algorithms [38, 19, 22, 9, 41, 18, 21, 29] which are in many situations competitive or better than existing deterministic methods.”
Separable approximations and decomposition methods for the augmented Lagrangian (2013, unknown): “The methods are used in a number of applications, including linear classification [5,15,41], compressed sensing [17], truss topology design [28], solving linear systems of equations [16] and group lasso problems [27].”
Distributed Block Coordinate Descent for Minimizing Partially Separable Functions (2014, background): “In view of the above, from now on we write x(i) :=UTi x ∈ RNi , and refer to x(i) as the i-th block of x. Projection onto a set of blocks.”
Convergence Analysis of Inexact Randomized Iterative Methods (2019, background): “a Gauss-Seidel for linear systems) and its block variant, Randomized Block Coordinate Descent we suggest [25, 36, 44, 45, 40, 41, 43, 7, 24, 14, 1, 54].”
Exploiting the Structure: Stochastic Gradient Methods Using Raw Clusters (2016, methodology): “2 • In contrast, for an accelerated method, if all the data vectors were identical, an accelerated method could converge in Õ( 1√ λ ) iterations, yielding a total running time O(d/ √ λ).”
Batched Stochastic Gradient Descent with Weighted Sampling (2016, background): “Other papers exploring advantages of importance sampling in various adaptations of stochastic gradient descent include but are not limited to [19, 20, 21, 22].”
Choosing the Sample with Lowest Loss makes SGD Robust (2020, unknown): “Other popular weighted sampling techniques include [26, 25, 23].”
Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent (2017, methodology): “The basic idea of momentum acceleration has been used to design faster algorithms for a range of other convex optimization problems (Beck and Teboulle, 2009; Nesterov, 2012; Lee and Sidford, 2013).”