Randomized dual coordinate ascent with arbitrary sampling
Abstract
We design a novel randomized dual coordinate ascent method (QUARTZ) for minimizing regularized empirical loss; that is, for minimizing the average of a very large number of smooth loss functions (each corresponding to a data vector/example) plus a strongly convex regularizer. The method operates by updating a random set of coordinates of the dual problem at every iteration. We allow for an arbitrary probability law (sampling) to govern the choice of the set of coordinates and show how this enters the complexity bound. For specific choices of the sampling we obtain variants of QUARTZ closely related to SDCA with importance sampling, mini-batch SDCA and distributed SDCA. In a statistically interesting regime for the choice of the regularization parameter, we obtain a linear speedup up to the square root of the number of coordinates (examples). However, our method also enjoys further data-dependent speedup, driven by sparsity and/or spectral properties of the data. Lastly, unlike traditional analysis of SDCA, in our analysis we directly control the decrease of the duality gap. Time permitting, I will comment on other variants of coordinate descent.
Background
Peter Richtarik is a tenured Assistant Professor of Optimization at the School of Mathematics, University of Edinburgh. He obtained his PhD in Operations Research from Cornell University in 2007 and prior to his current appointment has held a postdoctoral fellowship position (2007-2009) at the Centre for Operations Research and Econometrics, Catholic University of Louvain, Belgium.
Research Interests
Dr. Richtarik’s research interests lie in the area of big data optimization, parallel algorithms, gradient methods and machine learning. In a series of recent papers he has developed a general complexity theory of serial and parallel coordinate descent methods. These highly efficient codes are publicly available in the package ACDC. Dr. Richtarik’s research is supported by several grants, most notably a $1.1 million grant from the Engineering and Physical Sciences Research Council (EPSRC) for studying optimization algorithms for analyzing big digital resources.