2020

ADAHESSIAN: An Adaptive Second Order Optimizer for Machine Learning

Yao, Zhewei, Gholami, Amir, Shen, Sheng et al.

Understand

We introduce ADAHESSIAN, a second order stochastic optimization algorithm which dynamically incorporates the curvature of the loss function via ADAptive estimates of the HESSIAN.

Second order algorithms are among the most powerful optimization algorithms with superior convergence properties as compared to first order methods such as SGD and Adam.
The main disadvantage of traditional second order methods is their heavier per iteration computation and poor accuracy as compared to first order methods.
To address these, we incorporate several novel approaches in ADAHESSIAN, including: (i) a fast Hutchinson based method to approximate the curvature matrix with low computational overhead; (ii) a root-mean-square exponential moving average to smooth out variations of the Hessian diagonal across different iterations; and (iii) a block diagonal averaging to reduce the variance of Hessian diagonal elements.

Built on

Oversketched newton: Fast convex optimization for serverless systems
Original
Gupta, V.; Kadhe, S.; Courtade, T.; Mahoney, M. W.; and Ramchandran, K. 2019 · 1903
Earlier work this paper cites.
Deep learning recommendation model for personalization and recommendation systems
Original
Naumov, M.; Mudigere, D.; Shi, H.-J. M.; Huang, J.; Sundaraman, N.; Park, J.; Wang, X.; Gupta, U.; Wu, C.-J.; Azzolini, A. G.; et al. 2019 · 1906
Earlier work this paper cites.
Fast Evaluation and Approximation of the Gauss-Newton Hessian Matrix for the Multilayer Perceptron
Original
Chen, C.; Reiz, S.; Yu, C.; Bungartz, H.-J.; and Biros, G. 2019 · 1910
Earlier work this paper cites.
PyHessian: Neural Networks Through the Lens of the Hessian
Original
Yao, Z.; Gholami, A.; Keutzer, K.; and Mahoney, M. 2019a · 1912
Earlier work this paper cites.
Why ADAM Beats SGD for Attention Models
Original
Zhang, J.; Karimireddy, S. P.; Veit, A.; Kim, S.; Reddi, S. J.; Kumar, S.; and Sra, S. 2019 · 1912
Earlier work this paper cites.
A stochastic approximation method
Robbins, H.; and Monro, S. 1951 · 1951
Earlier work this paper cites.
Inexact Newton methods
Dembo, R. S.; Eisenstat, S. C.; and Steihaug, T. 1982 · 1982
Earlier work this paper cites.
A method for unconstrained convex minimization problem with the rate of convergence O (1/kˆ 2)
Nesterov, Y. 1983 · 1983
Earlier work this paper cites.
Optimal brain damage
LeCun, Y.; Denker, J. S.; and Solla, S. A. 1990 · 1990
Earlier work this paper cites.
Second order derivatives for network pruning: Optimal brain surgeon
Hassibi, B.; and Stork, D. G. 1993 · 1993
Earlier work this paper cites.
A limited memory algorithm for bound constrained optimization
Byrd, R. H.; Lu, P.; Nocedal, J.; and Zhu, C. 1995 · 1995
Earlier work this paper cites.
Trust region methods
Conn, A. R.; Gould, N. I.; and Toint, P. L. 2000 · 2000
Earlier work this paper cites.
BLEU: a method for automatic evaluation of machine translation
Papineni, K.; Roukos, S.; Ward, T.; and Zhu, W.-J. 2002 · 2002
Earlier work this paper cites.
Convex optimization
Boyd, S.; and Vandenberghe, L. 2004 · 2004
Earlier work this paper cites.
SqueezeBERT: What can computer vision teach NLP about efficient neural networks?
Original
Iandola, F. N.; Shaw, A. E.; Krishna, R.; and Keutzer, K. W. 2020 · 2006
Earlier work this paper cites.
An estimator for the diagonal of a matrix
Bekas, C.; Kokiopoulou, E.; and Saad, Y. 2007 · 2007
Earlier work this paper cites.
Imagenet: A large-scale hierarchical image database
Deng, J.; Dong, W.; Socher, R.; Li, L.-J.; Li, K.; and Fei-Fei, L. 2009 · 2009
Earlier work this paper cites.
Learning multiple layers of features from tiny images
Krizhevsky, A.; and Hinton, G. 2009 · 2009
Earlier work this paper cites.
BEAR: Sketching BFGS Algorithm for Ultra-High Dimensional Feature Selection in Sublinear Memory
Original
Aghazadeh, A.; Gupta, V.; DeWeese, A.; Koyluoglu, O. O.; and Ramchandran, K. 2020 · 2010
Earlier work this paper cites.
Adaptive bound optimization for online convex optimization
Original
McMahan, H. B.; and Streeter, M. 2010 · 2010
Earlier work this paper cites.
Adaptive subgradient methods for online learning and stochastic optimization
Duchi, J.; Hazan, E.; and Singer, Y. 2011 · 2011
Earlier work this paper cites.
Empirical evaluation and combination of advanced language modeling techniques
Mikolov, T.; Deoras, A.; Kombrink, S.; Burget, L.; and Černockỳ, J. 2011 · 2011
Earlier work this paper cites.

Similar

Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude
Tieleman, T.; and Hinton, G. 2012 · 2012
Cited alongside, same era.
Adadelta: an adaptive learning rate method
Original
Zeiler, M. D. 2012 · 2012
Cited alongside, same era.
No more pesky learning rates
Schaul, T.; Zhang, S.; and LeCun, Y. 2013 · 2013
Cited alongside, same era.
Escaping from saddle points—online stochastic gradient for tensor decomposition
Ge, R.; Huang, F.; Jin, C.; and Yuan, Y. 2015 · 2015
Cited alongside, same era.
Adam: A method for stochastic optimization
Kingma, D. P.; and Ba, J. 2015 · 2015
Cited alongside, same era.
Optimizing neural networks with Kronecker-factored approximate curvature
Martens, J.; and Grosse, R. 2015 · 2015
Cited alongside, same era.
Layer-specific adaptive learning rates for deep networks
Singh, B.; De, S.; Zhang, Y.; Goldstein, T.; and Taylor, G. 2015 · 2015
Cited alongside, same era.
Deep learning with elastic averaging SGD
Zhang, S.; Choromanska, A. E.; and LeCun, Y. 2015 · 2015
Cited alongside, same era.
Finding approximate local minima for nonconvex optimization in linear time
Original
Agarwal, N.; Allen-Zhu, Z.; Bullins, B.; Hazan, E.; and Ma, T. 2016 · 2016
Cited alongside, same era.
Second-order stochastic optimization in linear time
Agarwal, N.; Bullins, B.; and Hazan, E. 2016 · 2016
Cited alongside, same era.
Deep residual learning for image recognition
He, K.; Zhang, X.; Ren, S.; and Sun, J. 2016 · 2016
Cited alongside, same era.
SqueezeNet: AlexNet-level accuracy with 50x fewer parameters and< 0.5 MB model size
Original
Iandola, F. N.; Han, S.; Moskewicz, M. W.; Ashraf, K.; Dally, W. J.; and Keutzer, K. 2016 · 2016
Cited alongside, same era.

Then

Attention is all you need
Vaswani, A.; Shazeer, N.; Parmar, N.; Uszkoreit, J.; Jones, L.; Gomez, A. N.; Kaiser, Ł.; and Polosukhin, I. 2017 · 2017
Later among the works it cites.
Deep & cross network for ad click predictions
Wang, R.; Fu, B.; Fu, G.; and Wang, M. 2017 · 2017
Later among the works it cites.
Second-order optimization for non-convex machine learning: An empirical study
Original
Xu, P.; Roosta-Khorasan, F.; and Mahoney, M. W. 2017 · 2017
Later among the works it cites.
A progressive batching L-BFGS method for machine learning
Original
Bollapragada, R.; Mudigere, D.; Nocedal, J.; Shi, H.-J. M.; and Tang, P. T. P. 2018 · 2018
Later among the works it cites.
Optimization methods for large-scale machine learning
Bottou, L.; Curtis, F. E.; and Nocedal, J. 2018 · 2018
Later among the works it cites.
Accelerated methods for nonconvex optimization
Carmon, Y.; Duchi, J. C.; Hinder, O.; and Sidford, A. 2018 · 2018
Later among the works it cites.
Shampoo: Preconditioned stochastic tensor optimization
Original
Gupta, V.; Koren, T.; and Singer, Y. 2018 · 2018
Later among the works it cites.
Scaling Neural Machine Translation
Ott, M.; Edunov, S.; Grangier, D.; and Auli, M. 2018 · 2018
Later among the works it cites.
Sentence encoders on stilts: Supplementary training on intermediate labeled-data tasks
Original
Phang, J.; Févry, T.; and Bowman, S. R. 2018 · 2018
Later among the works it cites.
How does batch normalization help optimization?
Santurkar, S.; Tsipras, D.; Ilyas, A.; and Madry, A. 2018 · 2018
Later among the works it cites.
Adafactor: Adaptive Learning Rates with Sublinear Memory Cost
Shazeer, N.; and Stern, M. 2018 · 2018
Later among the works it cites.
Exact and inexact subsampled Newton methods for optimization
Bollapragada, R.; Byrd, R. H.; and Nocedal, J. 2019 · 2019
Later among the works it cites.
Entropy-sgd: Biasing gradient descent into wide valleys
Chaudhari, P.; Choromanska, A.; Soatto, S.; LeCun, Y.; Baldassi, C.; Borgs, C.; Chayes, J.; Sagun, L.; and Zecchina, R. 2019 · 2019
Later among the works it cites.
Transformer-XL: Attentive Language Models beyond a Fixed-Length Context
Dai, Z.; Yang, Z.; Yang, Y.; Carbonell, J. G.; Le, Q.; and Salakhutdinov, R. 2019 · 2019
Later among the works it cites.
Decoupled Weight Decay Regularization
Loshchilov, I.; and Hutter, F. 2019 · 2019
Later among the works it cites.
A tensorized transformer for language modeling
Ma, X.; Zhang, P.; Zhang, S.; Duan, N.; Hou, Y.; Zhou, M.; and Song, D. 2019 · 2019
Later among the works it cites.
fairseq: A Fast, Extensible Toolkit for Sequence Modeling
Ott, M.; Edunov, S.; Baevski, A.; Fan, A.; Gross, S.; Ng, N.; Grangier, D.; and Auli, M. 2019 · 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 · 2019
Later among the works it cites.
Learning Deep Transformer Models for Machine Translation
Wang, Q.; Li, B.; Xiao, T.; Zhu, J.; Li, C.; Wong, D. F.; and Chao, L. S. 2019 · 2019
Later among the works it cites.
Large batch optimization for deep learning: Training bert in 76 minutes
You, Y.; Li, J.; Reddi, S.; Hseu, J.; Kumar, S.; Bhojanapalli, S.; Song, X.; Demmel, J.; Keutzer, K.; and Hsieh, C.-J. 2019 · 2019
Later among the works it cites.
https://github.com/amirgholami/ADAHESSIAN.git
2020 · 2020
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…