Adaptive Bound Optimization for Online Convex Optimization

By H. Brendan McMahan, Matthew J. Streeter. 2010

431 citations recorded by the source corpus.

We introduce a new online convex optimization algorithm that adaptively chooses its regularization function based on the loss functions observed so far. This is in contrast to previous algorithms that use a fixed regularization function such as L2-squared, and modify it only via a single time-dependent parameter. Our algorithm’s regret bounds are worst-case optimal, and for certain realistic classes of loss functions they are much better than existing bounds. These bounds are problem-dependent, which means they can exploit the structure of the actual problem instance. Critically, however, our algorithm does not need to know this structure in advance. Rather, we prove competitive guarantees that show the algorithm provides a bound within a constant factor of the best possible bound (of a certain functional form) in hindsight.

Subfields: Computational Mechanics, Computer Networks and Communications, Management Science and Operations Research, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Networks and Communications

In Management Science and Operations Research

In Optimization & Training

Citations in the corpus

Memory-Efficient Adaptive Optimization for Large-Scale Learning (2019, background): “Adaptive learning rates in online and stochastic optimization date back at least to [5] and were popularized in [11, 16], the former of which introduced the well-known Adagrad algorithm.”
On the Convergence of Adam and Beyond (2018, methodology): “The ﬁrst popular algorithm in this line of research is A DAGRAD (Duchi et al., 2011; McMahan & Streeter, 2010), which can achieve signiﬁcantly better performance compared to vanilla S GD when the gradients are sparse, or in general small.”
Practical and Private (Deep) Learning without Sampling or Shuffling (2021, methodology): “DP-FTRL algorithm: We provide DP-FTRL, a differentially private variant of the Follow-the-regularized-leader (FTRL) algorithm [32, 46, 49, 64] for online convex optimization (OCO).”
Adaptive Federated Optimization (2020, methodology): “…learning community because they can reduce the need to tune the learning rates and often exhibit strong empirical performance especially in presence of heavy-tail noise distributions of stochastic gradients (Reddi et al., 2019; McMahan and Streeter, 2010; Duchi et al., 2011; Zhang et al., 2019).”
Is Local SGD Better than Minibatch SGD? (2020, methodology): “Some important non-examples, however, are adaptive gradient methods like AdaGrad (McMahan and Streeter, 2010; Duchi et al., 2011)—these have linear updates, but the linear functions are data-dependent.”
Local AdaAlter: Communication-Efficient Stochastic Gradient Descent with Adaptive Learning Rates (2019, background): “Examples include AdaGrad (McMahan and Streeter, 2010; Duchi et al., 2011), RMSProp (Tieleman and Hinton, 2012), AdaDelta (Zeiler, 2012), and Adam (Kingma and Ba, 2014).”
Adaptive Gradient-Based Meta-Learning Methods (2019, background): “Nevertheless, our approach does strongly rely on online learning through the study of data-dependent regret-upperbounds, which has a long history of use in deriving adaptive single-task methods [40, 21]; however, in meta-learning there is typically not enough data to adapt to without considering mul”
The Marginal Value of Adaptive Gradient Methods in Machine Learning (2017, background): “An increasing share of deep learning researchers are training their models with adaptive gradient methods [3, 12] due to their rapid training time [6].”
Introduction to Online Convex Optimization (2016, methodology): “The AdaGrad algorithm was introduced in (38; 37), its diagonal version was also discovered in parallel in (75).”
Adaptive Gradient Methods with Dynamic Bound of Learning Rate (2019, neutral): “Lemma 1 (Mcmahan & Streeter (2010)) .”
A reliable effective terascale linear learning system (2011, methodology): “We start with each node making one online pass over its local data according to adaptive gradient updates (Duchi et al., 2010b; McMahan and Streeter, 2010) modiﬁed for loss non-linearity (Karampatziakis and Langford, 2011).”
AdaGrad stepsizes: Sharp convergence over nonconvex landscapes, from any initialization (2018, methodology): “2 Previous work AdaGrad, first introduced independently by [6] and [15], is a state-of-the-art first order method which is already used widely used in practice in stochastic gradient setting for its robustness to the choice of stepsize.”
Ad click prediction: a view from the trenches (2013, background): “A more theoretical treatment for FTRLProximal appears in [26].”
AdaBelief Optimizer: Adapting Stepsizes by the Belief in Observed Gradients (2020, background): “[59] H Brendan McMahan and Matthew Streeter, “Adaptive bound optimization for online convex optimization,” arXiv preprint arXiv:1002.”
Adaptive Methods for Nonconvex Optimization (2018, methodology): “Note that the update looks very similar to ADAGRAD except for the use of sign(vt−1 − g2t ) in YOGI.”
Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Network (2019, methodology): “To solve this problem, adaptive methods [Duchi et al., 2011, McMahan and Streeter, 2010] are proposed so that they can change the learning rate on-the-ﬂy according to gradient information received along the way.”
Sequential convergence of AdaGrad algorithm for smooth convex optimization (2020, methodology): “We will focus on AdaGrad algorithm [12], which was initially developed in an online learning context, see also [18].”