We propose a new randomized coordinate descent method for unconstrained minimization of convex functions that are smooth with respect to a given real symmetric positive semidefinite curvature matrix. At each iteration, this method works with a random coordinate subset selected with probability proportional to the determinant of the corresponding principal submatrix of the curvature matrix (volume sampling). When the size of the subset equals one, the method reduces to the well-known randomized coordinate descent which samples coordinates with probabilities proportional to the coordinate Lipschitz constants. We establish the convergence rates both for convex and strongly convex functions. Our theoretical results show that by increasing the size of the subset from one number to another, 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.
Another closely related work to this one is @cite_17 , where the authors propose a new randomized optimization method for minimizing quadratic functions given @math eigenvectors corresponding to the @math smallest eigenvalues of the Hessian. Although the complexity estimates for this method look similar to ours, there are several key differences. First, the results in @cite_17 show that the increase in the number of coordinates from @math to @math in their method leads to the acceleration rate that depends on the spectral gap between the @math st and @math nd eigenvalues. The corresponding acceleration rate of our method depends, on the contrary, on the spectral gap between the @math st and @math nd eigenvalues. Second, their method is not, strictly speaking, a coordinate descent algorithm since it uses eigenvectors as search directions instead of the coordinate directions. Finally, it is also less practical than ours. For example, even in the simplest non-trivial regime @math , it requires an eigenvector corresponding to the smallest eigenvalue; the complexity of obtaining such a vector is in general @math . In contrast, the simplest non-trivial choice for our method is @math which can be implemented in time @math (or even smaller for sparse problems).
@cite_17
2963651662
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.