Accelerated Coordinate Descent with Arbitrary Sampling and Best Rates for Minibatches

Understand

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.