CISPA
Browse

Universal Gradient Methods for Stochastic Convex Optimization

Download (918.38 kB)
conference contribution
posted on 2024-10-25, 10:12 authored by Anton RodomanovAnton Rodomanov, Ali Kavis, Yongtao Wu, Kimon Antonakopoulos, Volkan Cevher
We develop universal gradient methods for Stochastic Convex Optimization (SCO). Our algorithms automatically adapt not only to the oracle’s noise but also to the Hölder smoothness of the objective function without a priori knowledge of the particular setting. The key ingredient is a novel strategy for adjusting step-size coefficients in the Stochastic Gradient Method (SGD). Unlike AdaGrad, which accumulates gradient norms, our Universal Gradient Method accumulates appropriate combinations of gradientand iterate differences. The resulting algorithm has state-of-the-art worst-case convergence rate guarantees for the entire Hölder class including, in particular, both nonsmooth functions and those with Lipschitz continuous gradient. We also present the Universal Fast Gradient Method for SCO enjoying optimal efficiency estimates.

History

Primary Research Area

  • Trustworthy Information Processing

Name of Conference

International Conference on Machine Learning (ICML)

Journal

Proceedings of the 41st International Conference on Machine Learning

Volume

235

Page Range

42620-42646

Publisher

PMLR

BibTeX

@conference{Rodomanov:Kavis:Wu:Antonakopoulos:Cevher:2024, title = "Universal Gradient Methods for Stochastic Convex Optimization", author = "Rodomanov, Anton" AND "Kavis, Ali" AND "Wu, Yongtao" AND "Antonakopoulos, Kimon" AND "Cevher, Volkan", year = 2024, month = 7, journal = "Proceedings of the 41st International Conference on Machine Learning", pages = "42620--42646", publisher = "PMLR" }

Usage metrics

    Categories

    No categories selected

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC