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.
@cite_22 , the authors propose three different randomized methods for unconstrained minimization of a smooth function. Their Method 1 is exactly the same method as ours with the only difference that they consider an sampling for selecting coordinates. As a result, the convergence rate of their method is expressed in terms of the minimal eigenvalue of the expectation of some matrix, and it is not clear how this quantity depends on the number of coordinates used at each iteration. Although the authors consider a particular example of a @math matrix for which their method should be very efficient, they do not establish any general results. In this regard, our work can be considered a further development of @cite_22 , where we establish more interpretable complexity results for a particular kind of coordinate sampling, namely volume sampling. In addition to that, we also consider both the convex and strongly convex cases, while the authors of @cite_22 only consider the latter.
@cite_22
134812657
We propose a new algorithm for minimizing regularized empirical loss: Stochastic Dual Newton Ascent (SDNA). Our method is dual in nature: in each iteration we update a random subset of the dual variables. However, unlike existing methods such as stochastic dual coordinate ascent, SDNA is capable of utilizing all local curvature information contained in the examples, which leads to striking improvements in both theory and practice -- sometimes by orders of magnitude. In the special case when an L2-regularizer is used in the primal, the dual problem is a concave quadratic maximization problem plus a separable term. In this regime, SDNA in each step solves a proximal subproblem involving a random principal submatrix of the Hessian of the quadratic function; whence the name of the method.