Timezone: »

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

Wed Dec 09 04:00 PM -- 08:59 PM (PST) @ 210 C #85
in Poster Session »

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.

[ PDF] 

Author Information

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

More from the Same Authors