2020

A Second look at Exponential and Cosine Step Sizes: Simplicity, Adaptivity, and Performance

Li, Xiaoyu, Zhuang, Zhenxun, Orabona, Francesco

Understand

Stochastic Gradient Descent (SGD) is a popular tool in training large-scale machine learning models.

Its performance, however, is highly variable, depending crucially on the choice of the step sizes.
Accordingly, a variety of strategies for tuning the step sizes have been proposed, ranging from coordinate-wise approaches (a.k.a.
``adaptive'' step sizes) to sophisticated heuristics to change the step size in each iteration.

Built on

Bag of freebies for training object detection neural networks
Original
Zhang, Z., He, T., Zhang, H., Zhang, Z., Xie, J., and Li, M · 1902
Earlier work this paper cites.
A stochastic approximation method
Robbins, H. and Monro, S · 1951
Earlier work this paper cites.
A topological property of real analytic subsets (in french)
Łojasiewicz, S · 1963
Earlier work this paper cites.
Gradient methods for minimizing functionals
Polyak, B. T · 1963
Earlier work this paper cites.
On convergence rates of subgradient optimization methods
Goffin, J.-L · 1977
Earlier work this paper cites.
A method for unconstrained convex minimization problem with the rate of convergence O ⁡ ( 1 / k 2 ) O(1/k^{2})
Nesterov, Y · 1983
Earlier work this paper cites.
Neuro-Dynamic Programming
Bertsekas, D. P. and Tsitsiklis, J. N · 1996
Earlier work this paper cites.
Adaptive and self-confident on-line learning algorithms
Auer, P., Cesa-Bianchi, N., and Gentile, C · 2002
Earlier work this paper cites.
Introductory lectures on convex optimization: A basic course , volume 87
Nesterov, Y · 2004
Earlier work this paper cites.
Adaptive subgradient methods for online learning and stochastic optimization
Duchi, J., Hazan, E., and Singer, Y · 2010
Earlier work this paper cites.
Adaptive bound optimization for online convex optimization
McMahan, H. B. and Streeter, M. J · 2010
Earlier work this paper cites.
Non-asymptotic analysis of stochastic approximation algorithms for machine learning
Bach, F. and Moulines, E · 2011
Earlier work this paper cites.
Beyond the regret minimization barrier: an optimal algorithm for stochastic strongly-convex optimization
Hazan, E. and Kale, S · 2011
Earlier work this paper cites.
Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude
Tieleman, T. and Hinton, G · 2012
Earlier work this paper cites.
ADADELTA: an adaptive learning rate method
Original
Zeiler, M. D · 2012
Earlier work this paper cites.
Stochastic first- and zeroth-order methods for nonconvex stochastic programming
Ghadimi, S. and Lan, G · 2013
Earlier work this paper cites.
GloVe: Global vectors for word representation
Pennington, J., Socher, R., and Manning, C · 2014
Earlier work this paper cites.
TensorFlow: Large-scale machine learning on heterogeneous systems, 2015
Abadi, M., Agarwal, A., Barham, P., Brevdo, E., Chen, Z., Citro, C., Corrado, G. S., Davis, A., Dean, J., Devin, M., Ghemawat, S., Goodfellow, I., Harp, A., Irving, G., Isard, M., Jia, Y., Jozefowicz, R., Kaiser, L., Kudlur, M., Levenberg, J., Mané, D., Monga, R., Moore, S., Murray, D., Olah, C., Schuster, M., Shlens, J., Steiner, B., Sutskever, I., Talwar, K., Tucker, P., Vanhoucke, V., Vasudevan, V., Viégas, F., Vinyals, O., Warden, P., Wattenberg, M., Wicke, M., Yu, Y., and Zheng, X · 2015
Earlier work this paper cites.
Simple, efficient, and neural algorithms for sparse coding
Arora, S., Ge, R., Ma, T., and Moitra, A · 2015
Earlier work this paper cites.
A large annotated corpus for learning natural language inference
Bowman, S., Angeli, G., Potts, C., and Manning, C · 2015
Earlier work this paper cites.
Solving random quadratic systems of equations is nearly as easy as solving linear systems
Chen, Y. and Candes, E · 2015
Earlier work this paper cites.
Adam: A method for stochastic optimization
Kingma, D. P. and Ba, J · 2015
Earlier work this paper cites.
Deeply-supervised nets
Lee, C., Xie, S., Gallagher, P., Zhang, Z., and Tu, Z · 2015
Earlier work this paper cites.
Universal gradient methods for convex optimization problems
Nesterov, Y · 2015
Earlier work this paper cites.

Similar

Scale-free algorithms for online linear optimization
Orabona, F. and Pál, D · 2015
Cited alongside, same era.
Scale-free online learning
Orabona, F. and Pál, D · 2015
Cited alongside, same era.
Deep residual learning for image recognition
He, K., Zhang, X., Ren, S., and Sun, J · 2016
Cited alongside, same era.
Linear convergence of gradient and proximal-gradient methods under the Polyak-Łojasiewicz condition
Karimi, H., Nutini, J., and Schmidt, M · 2016
Cited alongside, same era.
Stochastic variance reduction for nonconvex optimization
Reddi, S. J., Hefny, A., Sra, S., Poczos, B., and Smola, A · 2016
Cited alongside, same era.
Guaranteed matrix completion via non-convex factorization
Sun, R. and Luo, Z · 2016
Cited alongside, same era.
Learning transferable architectures for scalable image recognition
Zoph, B., Vasudevan, V., Shlens, J., and Le, Q. V · 2016
Cited alongside, same era.
Supervised learning of universal sentence representations from natural language inference data
Conneau, A., Kiela, D., Schwenk, H., Barrault, L., and Bordes, A · 2017
Cited alongside, same era.
Shake-shake regularization of 3-branch residual networks
Gastaldi, X · 2017
Cited alongside, same era.
Densely connected convolutional networks
Huang, G., Liu, Z., Van Der Maaten, L., and Weinberger, K. Q · 2017
Cited alongside, same era.
How to escape saddle points efficiently
Jin, C., Ge, R., Netrapalli, P., Kakade, S., and Jordan, M. I · 2017
Cited alongside, same era.
Non-convex finite-sum optimization via SCSG methods
Lei, L., Ju, C., Chen, J., and Jordan, M. I · 2017
Cited alongside, same era.

Then

A universally optimal multistage accelerated stochastic gradient method
Aybat, N. S., Fallah, A., Gurbuzbalaban, M., and Ozdaglar, A · 2019
Later among the works it cites.
Deep Frank-Wolfe for neural network optimization
Berrada, L., Zisserman, A., and Kumar, M · 2019
Later among the works it cites.
Autoaugment: Learning augmentation strategies from data
Cubuk, E. D., Zoph, B., Mane, D., Vasudevan, V., and Le, Q. V · 2019
Later among the works it cites.
Stochastic algorithms with geometric step decay converge linearly on sharp functions
Original
Davis, D., Drusvyatskiy, D., and Charisopoulos, V · 2019
Later among the works it cites.
The step decay schedule: A near optimal, geometrically decaying learning rate procedure for least squares
Ge, R., Kakade, S. M., Kidambi, R., and Netrapalli, P · 2019
Later among the works it cites.
Stochastic gradient methods with layer-wise adaptive moments for training of deep networks
Original
Ginsburg, B., Castonguay, P., Hrinchuk, O., Kuchaiev, O., Lavrukhin, V., Leary, R., Li, J., Nguyen, H., Zhang, Y., and Cohen, J. M · 2019
Later among the works it cites.
Bag of tricks for image classification with convolutional neural networks
He, T., Zhang, Z., Zhang, H., Zhang, Z., Xie, J., and Li, M · 2019
Later among the works it cites.
A generic acceleration framework for stochastic composite optimization
Kulunchakov, A. and Mairal, J · 2019
Later among the works it cites.
Attention network robustification for person ReID
Original
Lawen, H., Ben-Cohen, A., Protter, M., Friedman, I., and Zelnik-Manor, L · 2019
Later among the works it cites.
On the convergence of stochastic gradient descent with adaptive stepsizes
Li, X. and Orabona, F · 2019
Later among the works it cites.
A modern introduction to online learning
Original
Orabona, F · 2019
Later among the works it cites.
Pytorch: An imperative style, high-performance deep learning library
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E., DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S · 2019
Later among the works it cites.
AdaGrad stepsizes: Sharp convergence over nonconvex landscapes
Ward, R., Wu, X., and Bottou, L · 2019
Later among the works it cites.
Stagewise training accelerates convergence of testing error over sgd
Yuan, Z., Yan, Y., Jin, R., and Yang, T · 2019
Later among the works it cites.
A simple framework for contrastive learning of visual representations
Chen, T., Kornblith, S., Norouzi, M., and Hinton, G · 2020
Closest in time.
Bootstrap your own latent - a new approach to self-supervised learning
Grill, J., Strub, F., Altché, F., Tallec, C., Richemond, P., Buchatskaya, E., Doersch, C., Avila P., B., Guo, Z., Gheshlaghi Azar, M., Piot, B., kavukcuoglu, K., Munos, R., and Valko, M · 2020
Closest in time.
Better theory for SGD in the nonconvex world
Original
Khaled, A. and Richtárik, P · 2020
Closest in time.
A high probability analysis of adaptive SGD with momentum
Li, X. and Orabona, F · 2020
Closest in time.
Page: A simple and optimal probabilistic gradient estimator for nonconvex optimization
Original
Li, Z., Bao, H., Zhang, X., and Richtárik, P · 2020
Closest in time.
AdaGrad stepsizes: Sharp convergence over nonconvex landscapes
Ward, R., Wu, X., and Bottou, L · 2020
Closest in time.
Graph structure of neural networks
You, J., Leskovec, J., He, K., and Xie, S · 2020
Closest in time.
Exploring self-attention for image recognition
Zhao, H., Jia, J., and Koltun, V · 2020
Closest in time.
From low probability to high confidence in stochastic convex optimization
Davis, D., Drusvyatskiy, D., Xiao, L., and Zhang, J · 2021
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…