Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling

Zeyuan Allen-Zhu, Yang Yuan

Published 2015-12-30Version 1

Accelerated coordinate descent methods are widely used in optimization and machine learning. By taking cheap-to-compute coordinate gradients in each iteration, they are usually faster than accelerated full gradient descent, and thus suitable for large-scale optimization problems. In this paper, we improve the running time of accelerated coordinate descent, using a clean and novel non-uniform sampling method. In particular, if a function $f$ is coordinate-wise smooth with parameters $L_1,L_2,\dots,L_n$, we obtain an algorithm that converges in $O(\sum_i \sqrt{L_i} / \sqrt{\varepsilon})$ iterations for convex $f$ and in $\tilde{O}(\sum_i \sqrt{L_i} / \sqrt{\sigma})$ iterations for $\sigma$-strongly convex $f$. The best known result was $\tilde{O}(\sqrt{n \sum_i L_i} / \sqrt{\varepsilon})$ for convex $f$ and $\tilde{O}(\sqrt{n \sum_i L_i} / \sqrt{\sigma})$ for $\sigma$-strongly convex $f$, due to Lee and Sidford. Thus, our algorithm improves the running time by a factor up to $\sqrt{n}$. Our speed-up naturally applies to important problems such as empirical risk minimizations and solving linear systems.