Approximate Steepest Coordinate Descent

By Sebastian U. Stich, Anant Raj, Martin Jaggi. 2017

17 citations recorded by the source corpus.

We propose a new selection rule for the coordinate selection in coordinate descent methods for huge-scale optimization. The efficiency of this novel scheme is provably better than the efficiency of uniformly random selection, and can reach the efficiency of steepest coordinate descent (SCD), enabling an acceleration of a factor of up to $n$, the number of coordinates. In many practical applications, our scheme can be implemented at no extra cost and computational efficiency very close to the faster uniform selection. Numerical experiments with Lasso and Ridge regression show promising improvements, in line with our theoretical guarantees.

Subfields: Aerospace Engineering, Artificial Intelligence, Computational Mechanics

How researchers see this paper

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

In Aerospace Engineering

Mark W. Schmidt

In Artificial Intelligence

In Computational Mechanics

Citations in the corpus

Let's Make Block Coordinate Descent Go Fast: Faster Greedy Rules, Message-Passing, Active-Set Complexity, and Superlinear Convergence (2017, background): “However, several recent works show that certain problem structures allow efficient calculation of GS-style rules [52, 61, 25, 46], allow efficient approximation of GS-style rules [20, 90, 87], or allow other rules that try to improve on the progress made at each iteration [30, 13].”
Safe Adaptive Importance Sampling (2017, background): “For general smooth h (again with arbitrary separable regularizers ψ i ), (11) can readily be extended to hold [32, Lemma 4.1], the inner product change term becoming (cid:104) a i , ∇ 2 f ( A ˜ x ) a i k instead, when assuming h is twice-differentiable.”