A new regret analysis for Adam-type algorithms

Abstract

In this paper, we focus on a theory-practice gap for Adam and its variants (AMSgrad, AdamNC, etc.). In practice, these algorithms are used with a constant first-order moment parameter ${\beta }_1$ (typically between $0.9$ and $0.99$). In theory, regret guarantees for online convex optimization require a rapidly decaying ${\beta }_1\to 0$ schedule. We show that this is an artifact of the standard analysis and propose a novel framework that allows us to derive optimal, data-dependent regret bounds with a constant ${\beta }_1$, without further assumptions. We also demonstrate the flexibility of our analysis on a wide range of different algorithms and settings.

References in corpus (9)

• Adam: A Method for Stochastic Optimization
• On the Convergence of Adam and Beyond
• Adaptive Gradient Methods with Dynamic Bound of Learning Rate
• Closing the Generalization Gap of Adaptive Gradient Methods in Training Deep Neural Networks
• On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization
• Nostalgic Adam: Weighting more of the past gradients when designing the adaptive learning rate
• ZO-AdaMM: Zeroth-Order Adaptive Momentum Method for Black-Box Optimization
• On the Convergence of AdaBound and its Connection to SGD
• Convergence Analyses of Online ADAM Algorithm in Convex Setting and Two-Layer ReLU Neural Network

Cited by in corpus (1)

• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum