Online Adaptive Methods, Universality and Acceleration

Abstract

We present a novel method for convex unconstrained optimization that, without any modifications, ensures: (i) accelerated convergence rate for smooth objectives, (ii) standard convergence rate in the general (non-smooth) setting, and (iii) standard convergence rate in the stochastic optimization setting. To the best of our knowledge, this is the first method that simultaneously applies to all of the above settings. At the heart of our method is an adaptive learning rate rule that employs importance weights, in the spirit of adaptive online learning algorithms (Duchi et al., 2011; Levy, 2017), combined with an update that linearly couples two sequences, in the spirit of (Allen-Zhu and Orecchia, 2017). An empirical examination of our method demonstrates its applicability to the above mentioned scenarios and corroborates our theoretical findings.

Cited by in corpus (14)

• Adaptivity without Compromise: A Momentumized, Adaptive, Dual Averaged Gradient Method for Stochastic Optimization
• Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Network
• Descending through a Crowded Valley - Benchmarking Deep Learning Optimizers
• A Second look at Exponential and Cosine Step Sizes: Simplicity, Adaptivity, and Performance
• Adaptive extra-gradient methods for min-max optimization and games
• Linear Convergence of Adaptive Stochastic Gradient Descent
• Efficient Projection-Free Online Convex Optimization with Membership Oracle
• Heuristic adaptive fast gradient method in stochastic optimization tasks
• Three Operator Splitting with Subgradients, Stochastic Gradients, and Adaptive Learning Rates
• Adaptive Differentially Private Empirical Risk Minimization
• Adaptive first-order methods revisited: Convex optimization without Lipschitz requirements
• Anytime Online-to-Batch Conversions, Optimism, and Acceleration
• Geometry-Aware Universal Mirror-Prox
• Development of a method for solving structural optimization problems