Quartz: Randomized dual coordinate ascent with arbitrary sampling

Zheng Qu, Peter Richtarik, Tong Zhang

Research output: Contribution to journalConference articlepeer-review

36 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)865-873
Number of pages9
JournalAdvances in Neural Information Processing Systems
Volume2015-January
StatePublished - Jan 1 2015
Event29th Annual Conference on Neural Information Processing Systems, NIPS 2015 - Montreal, Canada
Duration: Dec 7 2015Dec 12 2015

Keywords

  • Arbitrary sampling
  • Data-driven speedup
  • Dual coordinate ascent
  • Empirical risk minimization

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing

Fingerprint Dive into the research topics of 'Quartz: Randomized dual coordinate ascent with arbitrary sampling'. Together they form a unique fingerprint.

Cite this