Poster
Quartz: Randomized Dual Coordinate Ascent with Arbitrary Sampling
Zheng Qu · Peter Richtarik · Tong Zhang

Wed Dec 9th 07:00 -- 11:59 PM @ 210 C #85 #None

We study the problem of minimizing the average of a large number of smooth convex functions penalized with a strongly convex regularizer. We propose and analyze a novel primal-dual method (Quartz) which at every iteration samples and updates a random subset of the dual variables, chosen according to an arbitrary distribution. In contrast to typical analysis, we directly bound the decrease of the primal-dual error (in expectation), without the need to first analyze the dual error. Depending on the choice of the sampling, we obtain efficient serial and mini-batch variants of the method. In the serial case, our bounds match the best known bounds for SDCA (both with uniform and importance sampling). With standard mini-batching, our bounds predict initial data-independent speedup as well as additional data-driven speedup which depends on spectral and sparsity properties of the data.

Author Information

Zheng Qu (University of Hong Kong)
Peter Richtarik (University of Edinburgh)
Tong Zhang (Rutgers)

More from the Same Authors