  We analyze the coordinate descent method with a new coordinate selection
strategy, called volume sampling. This strategy prescribes selecting subsets of
variables of certain size proportionally to the determinants of principal
submatrices of the matrix, that bounds the curvature of the objective function.
In the particular case, when the size of the subsets equals one, volume
sampling coincides with the well-known strategy of sampling coordinates
proportionally to their Lipschitz constants. For the coordinate descent with
volume sampling, we establish the convergence rates both for convex and
strongly convex problems. Our theoretical results show that, by increasing the
size of the subsets, it is possible to accelerate the method up to the factor
which depends on the spectral gap between the corresponding largest eigenvalues
of the curvature matrix. Several numerical experiments confirm our theoretical
conclusions.
