Universal Gradient Methods for Stochastic Convex Optimization

2024/02/05 by Anton Rodomanov, Ali Kavis, Rodomanov, Anton +7 · 2 citations
Computer Science · Engineering · Mathematics · #FOS: Mathematics #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Statistical Methods and Inference #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2402.03210

openalex publication_date 2024/02/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 gradient- and 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.

Cited by

• Optimistic Online-to-Batch Conversions for Accelerated Convergence and Universality
• Accelerated Distance-adaptive Methods for Hölder Smooth and Convex Optimization

Related

• Universality of AdaGrad Stepsizes for Stochastic Optimization: Inexact Oracle, Acceleration and Variance Reduction
• Online and Stochastic Universal Gradient Methods for Minimizing Regularized Hölder Continuous Finite Sums
• Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimization
• How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD
• High Probability Convergence of Stochastic Gradient Methods