Show simple item record

dc.contributor.authorOrecchia, Lorenzoen_US
dc.contributor.authorAllen-Zhu, Zeyuanen_US
dc.date.accessioned2018-02-14T15:01:08Z
dc.date.available2018-02-14T15:01:08Z
dc.date.issued2017
dc.identifierhttp://drops.dagstuhl.de/opus/volltexte/2017/8185/
dc.identifier.citationL Orecchia, Zeyuan Allen-Zhu. "Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent." Innovations in Theoretical Computer Science
dc.identifier.urihttps://hdl.handle.net/2144/27036
dc.description.abstractFirst-order methods play a central role in large-scale machine learning. Even though many variations exist, each suited to a particular problem, almost all such methods fundamentally rely on two types of algorithmic steps: gradient descent, which yields primal progress, and mirror descent, which yields dual progress. We observe that the performances of gradient and mirror descent are complementary, so that faster algorithms can be designed by "linearly coupling" the two. We show how to reconstruct Nesterov's accelerated gradient methods using linear coupling, which gives a cleaner interpretation than Nesterov's original proofs. We also discuss the power of linear coupling by extending it to many other settings that Nesterov's methods cannot apply to.en_US
dc.description.urihttps://arxiv.org/abs/1407.1537
dc.rights© Zeyuan Allen-Zhu and Lorenzo Orecchia; licensed under Creative Commons License CC-BY.en_US
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/
dc.subjectLinear couplingen_US
dc.subjectGradient descenten_US
dc.subjectMirror descenten_US
dc.subjectAccelerationen_US
dc.titleLinear Coupling: An Ultimate Unification of Gradient and Mirror Descenten_US
dc.typeConference materialsen_US
dc.description.versionAccepted manuscripten_US
dc.identifier.doi10.4230/LIPIcs.ITCS.2017.3
pubs.elements-sourcemanual-entryen_US
pubs.notesEmbargo: No embargoen_US
pubs.organisational-groupBoston Universityen_US
pubs.organisational-groupBoston University, College of Arts & Sciencesen_US
pubs.organisational-groupBoston University, College of Arts & Sciences, Department of Computer Scienceen_US
pubs.publication-statusPublished onlineen_US
dc.date.online2017-01-15


This item appears in the following Collection(s)

Show simple item record

© Zeyuan Allen-Zhu and Lorenzo Orecchia;
licensed under Creative Commons License CC-BY.
Except where otherwise noted, this item's license is described as © Zeyuan Allen-Zhu and Lorenzo Orecchia; licensed under Creative Commons License CC-BY.