Boston University Libraries OpenBU
    JavaScript is disabled for your browser. Some features of this site may not work without it.
    View Item 
    •   OpenBU
    • BU Open Access Articles
    • BU Open Access Articles
    • View Item
    •   OpenBU
    • BU Open Access Articles
    • BU Open Access Articles
    • View Item

    Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent

    Thumbnail
    License
    © Zeyuan Allen-Zhu and Lorenzo Orecchia;
licensed under Creative Commons License CC-BY.
    Date Issued
    2017
    Publisher Version
    10.4230/LIPIcs.ITCS.2017.3
    Author(s)
    Orecchia, Lorenzo
    Allen-Zhu, Zeyuan
    Share to FacebookShare to TwitterShare by Email
    Export Citation
    Download to BibTex
    Download to EndNote/RefMan (RIS)
    Metadata
    Show full item record
    Permanent Link
    https://hdl.handle.net/2144/27036
    Version
    Accepted manuscript
    Citation (published version)
    L Orecchia, Zeyuan Allen-Zhu. "Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent." Innovations in Theoretical Computer Science
    Abstract
    First-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.
    Rights
    © Zeyuan Allen-Zhu and Lorenzo Orecchia; licensed under Creative Commons License CC-BY.
    Collections
    • BU Open Access Articles [3866]
    • CAS: Computer Science: Scholarly Papers [189]


    Boston University
    Contact Us | Send Feedback | Help
     

     

    Browse

    All of OpenBUCommunities & CollectionsIssue DateAuthorsTitlesSubjectsThis CollectionIssue DateAuthorsTitlesSubjects

    Deposit Materials

    LoginNon-BU Registration

    Statistics

    Most Popular ItemsStatistics by CountryMost Popular Authors

    Boston University
    Contact Us | Send Feedback | Help