File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Quartz: Randomized dual coordinate ascent with arbitrary sampling

TitleQuartz: Randomized dual coordinate ascent with arbitrary sampling
Other TitlesRandomized dual coordinate ascent with arbitrary sampling
Authors
KeywordsArbitrary sampling
Data-driven speedup
Dual coordinate ascent
Empirical risk minimization
Issue Date2015
PublisherMorgan Kaufmann Publishers, Inc.
Citation
The 29th Annual Conference on Neural Information Processing Systems (NIPS 2015), Montreal, Canada, 7-12 December 2015. In Conference Proceedings, 2015, v. 28, p. 865-873 How to Cite?
AbstractWe 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.
DescriptionFree Access of NIPS Proceedings' website located at: http://papers.nips.cc/
Persistent Identifierhttp://hdl.handle.net/10722/235016
ISSN

 

DC FieldValueLanguage
dc.contributor.authorQu, Z-
dc.contributor.authorRichtarik, P-
dc.contributor.authorZhang, T-
dc.date.accessioned2016-10-14T13:50:44Z-
dc.date.available2016-10-14T13:50:44Z-
dc.date.issued2015-
dc.identifier.citationThe 29th Annual Conference on Neural Information Processing Systems (NIPS 2015), Montreal, Canada, 7-12 December 2015. In Conference Proceedings, 2015, v. 28, p. 865-873-
dc.identifier.issn1049-5258-
dc.identifier.urihttp://hdl.handle.net/10722/235016-
dc.descriptionFree Access of NIPS Proceedings' website located at: http://papers.nips.cc/-
dc.description.abstractWe 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.-
dc.languageeng-
dc.publisherMorgan Kaufmann Publishers, Inc.-
dc.relation.ispartofAdvances in Neural Information Processing Systems-
dc.subjectArbitrary sampling-
dc.subjectData-driven speedup-
dc.subjectDual coordinate ascent-
dc.subjectEmpirical risk minimization-
dc.titleQuartz: Randomized dual coordinate ascent with arbitrary sampling-
dc.title.alternativeRandomized dual coordinate ascent with arbitrary sampling-
dc.typeConference_Paper-
dc.identifier.emailQu, Z: zhengqu@hku.hk-
dc.identifier.authorityQu, Z=rp02096-
dc.identifier.scopuseid_2-s2.0-84965123044-
dc.identifier.hkuros269838-
dc.identifier.volume28-
dc.identifier.spage865-
dc.identifier.epage873-
dc.publisher.placeUnited States-
dc.customcontrol.immutablesml 161130-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats