Can I read Accelerated Coordinate Descent with Arbitrary Sampling and Best Rates for Minibatches on EtoBox?

Accelerated Coordinate Descent with Arbitrary Sampling and Best Rates for Minibatches by Hanzely, Filip; Richtárik, Peter is a scholarly article available to read on EtoBox.

What is Accelerated Coordinate Descent with Arbitrary Sampling and Best Rates for Minibatches about?

Accelerated coordinate descent is a widely popular optimization algorithm due to its efficiency on large-dimensional problems. It achieves state-of-the-art complexity on an important class of empirical risk minimization problems. In this paper we design and analyze an accelerated coordinate descent (ACD) method which in each iteration updates a random subset of coordinates according to an arbitrary but fixed probability law, which is a parameter of the method. If all coordinates are updated in each iteration, our method reduces to the classical accelerated gradient descent method AGD of Nesterov. If a single coordinate is updated in each iteration, and we pick probabilities proportional to the square roots of the coordinate-wise Lipschitz constants, our method reduces to the currently fastest coordinate descent method NUACDM of Allen-Zhu, Qu, Richt\'{a}rik and Yuan. While mini-batch variants of ACD are more popular and relevant in practice, there is no importance sampling for ACD that outperforms the standard uniform mini-batch sampling. Through insights enabled by our general analysis, we design new importance sampling for mini-batch ACD which significantly outperforms previous st

Author

Hanzely, Filip; Richtárik, Peter

Published

2018

Language

EN