Skip to yearly menu bar Skip to main content


Poster

Universal Gradient Methods for Stochastic Convex Optimization

Anton Rodomanov · Ali Kavis · Yongtao Wu · Kimon Antonakopoulos · Volkan Cevher


Abstract:

We develop universal gradient methods for Stochastic Convex Optimization (SCO).Our algorithms automatically adapt not only to the oracle's noisebut also to the Hölder smoothness of the objective function without apriori knowledge of the particular setting.The key ingredient is a novel strategy for adjusting step-size coefficientsin the Stochastic Gradient Method (SGD).Unlike AdaGrad, which accumulates gradient norms, ourUniversal Gradient Method accumulates appropriate combinations of gradient-and iterate differences.The resulting algorithm has state-of-the-art worst-case convergencerate guarantees for the entire Hölder class including, in particular, bothnonsmooth functions and those with Lipschitz continuous gradient.We also present the Universal Fast Gradient Method for SCO enjoying optimalefficiency estimates.

Live content is unavailable. Log in and register to view live content