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.
One of the most influential papers on coordinate descent is the work @cite_9 by Nesterov, where he proposed a coordinate gradient method (which we will refer to as RCD) with a special rule for selecting coordinates. In RCD, each coordinate is sampled with probability proportional to the corresponding coordinate Lipschitz constant. Nesterov then derived the complexity bound for RCD and showed that it can be even better than that of the standard gradient method. Our method generalizes RCD in the sense that it coincides with it in the special case when the number of coordinates selected at each iteration equals one.
@cite_9
2095984592
In this paper we propose new methods for solving huge-scale optimization problems. For problems of this size, even the simplest full-dimensional vector operations are very expensive. Hence, we propose to apply an optimization technique based on random partial update of decision variables. For these methods, we prove the global estimates for the rate of convergence. Surprisingly enough, for certain classes of objective functions, our results are better than the standard worst-case bounds for deterministic algorithms. We present constrained and unconstrained versions of the method, and its accelerated variant. Our numerical test confirms a high efficiency of this technique on problems of very big size.