  The state-of-the-art methods for solving optimization problems in big
dimensions are variants of randomized coordinate descent (RCD). In this paper
we introduce a fundamentally new type of acceleration strategy for RCD based on
the augmentation of the set of coordinate directions by a few spectral or
conjugate directions. As we increase the number of extra directions to be
sampled from, the rate of the method improves, and interpolates between the
linear rate of RCD and a linear rate independent of the condition number. We
develop and analyze also inexact variants of these methods where the spectral
and conjugate directions are allowed to be approximate only. We motivate the
above development by proving several negative results which highlight the
limitations of RCD with importance sampling.
