Online Adaptive Methods, Universality and Acceleration

By Kfir Yehuda Levy, Alp Yurtsever, Volkan Cevher. 2018

110 citations recorded by the source corpus.

We present a novel method for convex unconstrained optimization that, without any modifications ensures: (1) accelerated convergence rate for smooth objectives, (2) standard convergence rate in the general (non-smooth) setting, and (3) 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 [duchi2011adaptive,levy2017online], combined with an update that linearly couples two sequences, in the spirit of [AllenOrecchia2017]. An empirical examination of our method demonstrates its applicability to the above mentioned scenarios and corroborates our theoretical findings.

Subfields: Artificial Intelligence, Computational Mechanics, 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 Artificial Intelligence

In Computational Mechanics

In Management Science and Operations Research

In Optimization & Training

Citations in the corpus

Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution (2022, background): “Not only does SPS max not have this dimension dependency, which dates back to crucial arguments in the AdaGrad literature [11, 21], but also does not require bounded iterates.”
On the Convergence of Weighted AdaGrad with Momentum for Training Deep Neural Networks (2018, methodology): “In contrast with the traditional adaptive learning rate in AdaGrad [11], the adaptive learning rates in AdaHB and AdaNAG are estimated via a novel weighted gradient accumulation technique generalized from [23, 24] which can capture more information on the later generated gradients.”
Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Network (2019, unknown): “Many modiﬁcations to AdaGrad have been proposed, namely, RMSprop [Hinton et al., 2012], AdaDelta [Zeiler, 2012], Adam [Kingma and Ba, 2014], AdaFTRL[Orabona and P´al, 2015], SGD-BB[Tan et al., 2016], AdaBatch [D´efossez and Bach, 2017], signSGD [Bernstein et al., 2018], SC-Adagrad [Mukkamala and Hei”
On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes (2018, methodology): “Levy et al. (2018) propose an acceleration method with adaptive stepsizes which are also similar to our global ones, proving the ˜ O (1 /T 2 ) convergence in the deterministic smooth case and ˜ O (1 / √ T ) in both general deterministic case and stochastic smooth case, but requiring a…”
Linear Convergence of Adaptive Stochastic Gradient Descent (2019, methodology): “To put the theorem in context, we compare with the sub-linear convergence rate of AdaGrad-Norm (i.e., T = O 1 / 2 ) in [28, 24, 27, 29].”