2020

Adam$^+$: A Stochastic Method with Adaptive Variance Reduction

Liu, Mingrui, Zhang, Wei, Orabona, Francesco et al.

Understand

Adam is a widely used stochastic optimization method for deep learning applications.

While practitioners prefer Adam because it requires less parameter tuning, its use is problematic from a theoretical point of view since it may not converge.
Variants of Adam have been proposed with provable convergence guarantee, but they tend not be competitive with Adam on the practical performance.
In this paper, we propose a new method named Adam$^+$ (pronounced as Adam-plus).

Built on

Long short-term memory
Sepp Hochreiter and Jürgen Schmidhuber · 1997
Earlier work this paper cites.
CIFAR-10 and CIFAR-100 datasets
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton · 2009
Earlier work this paper cites.
Adaptive bound optimization for online convex optimization
Original
H Brendan McMahan and Matthew Streeter · 2010
Earlier work this paper cites.
Adaptive subgradient methods for online learning and stochastic optimization
John Duchi, Elad Hazan, and Yoram Singer · 2011
Earlier work this paper cites.
Lecture 6.5-rmsprop, coursera: Neural networks for machine learning
Tijmen Tieleman and Geoffrey Hinton · 2012
Earlier work this paper cites.
Stochastic first-and zeroth-order methods for nonconvex stochastic programming
Saeed Ghadimi and Guanghui Lan · 2013
Earlier work this paper cites.
Accelerating stochastic gradient descent using predictive variance reduction
Rie Johnson and Tong Zhang · 2013
Earlier work this paper cites.
Adam: A method for stochastic optimization
Original
Diederik P Kingma and Jimmy Ba · 2014
Earlier work this paper cites.
Very deep convolutional networks for large-scale image recognition
Original
Karen Simonyan and Andrew Zisserman · 2014
Earlier work this paper cites.
Variance reduction for faster non-convex optimization
Zeyuan Allen-Zhu and Elad Hazan · 2016
Earlier work this paper cites.
Deep residual learning for image recognition
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun · 2016
Earlier work this paper cites.
The WikiText long term dependency language modeling dataset
Stephen Merity · 2016
Earlier work this paper cites.
Stochastic variance reduction for nonconvex optimization
Sashank J Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola · 2016
Earlier work this paper cites.
Finding approximate local minima faster than gradient descent
Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma · 2017
Earlier work this paper cites.

Similar

Accurate, large minibatch SGD: Training imagenet in 1 hour
Original
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He · 2017
Cited alongside, same era.
How to escape saddle points efficiently
Original
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan · 2017
Cited alongside, same era.
Non-convex finite-sum optimization via SCSG methods
Lihua Lei, Cheng Ju, Jianbo Chen, and Michael I Jordan · 2017
Cited alongside, same era.
Online to offline conversions, universality and adaptive minibatch sizes
Kfir Levy · 2017
Cited alongside, same era.
English conversational telephone speech recognition by humans and machines
George Saon, Gakuto Kurata, Tom Sercu, Kartik Audhkhasi, Samuel Thomas, Dimitrios Dimitriadis, Xiaodong Cui, Bhuvana Ramabhadran, Michael Picheny, Lynn-Li Lim, Bergul Roomi, and Phil Hall · 2017
Cited alongside, same era.
Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions
Mengdi Wang, Ethan X Fang, and Han Liu · 2017
Cited alongside, same era.
The marginal value of adaptive gradient methods in machine learning
Ashia C Wilson, Rebecca Roelofs, Mitchell Stern, Nati Srebro, and Benjamin Recht · 2017
Cited alongside, same era.
Scaling SGD batch size to 32k for imagenet training
Original
Yang You, Igor Gitman, and Boris Ginsburg · 2017
Cited alongside, same era.
Accelerated methods for nonconvex optimization
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford · 2018
Cited alongside, same era.
Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang · 2018
Cited alongside, same era.
Stochastic nested variance reduction for nonconvex optimization
Dongruo Zhou, Pan Xu, and Quanquan Gu · 2018
Cited alongside, same era.
Lower bounds for non-convex stochastic optimization
Original
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Woodworth · 2019
Cited alongside, same era.

Then

Momentum-based variance reduction in non-convex SGD
Ashok Cutkosky and Francesco Orabona · 2019
Later among the works it cites.
Sharp analysis for nonconvex SGD escaping from saddle points
Original
Cong Fang, Zhouchen Lin, and Tong Zhang · 2019
Later among the works it cites.
On the convergence of stochastic gradient descent with adaptive stepsizes
Xiaoyu Li and Francesco Orabona · 2019
Later among the works it cites.
On the variance of the adaptive learning rate and beyond
Original
Liyuan Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han · 2019
Later among the works it cites.
Adaptive gradient methods with dynamic bound of learning rate
Original
Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun · 2019
Later among the works it cites.
On the convergence of Adam and beyond
Original
Sashank J Reddi, Satyen Kale, and Sanjiv Kumar · 2019
Later among the works it cites.
SpiderBoost and momentum: Faster variance reduction algorithms
Zhe Wang, Kaiyi Ji, Yi Zhou, Yingbin Liang, and Vahid Tarokh · 2019
Later among the works it cites.
AdaGrad stepsizes: Sharp convergence over nonconvex landscapes
Rachel Ward, Xiaoxia Wu, and Leon Bottou · 2019
Later among the works it cites.
Large batch optimization for deep learning: Training BERT in 76 minutes
Original
Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh · 2019
Later among the works it cites.
Distributed deep learning strategies for automatic speech recognition
Wei Zhang, Xiaodong Cui, Ulrich Finkler, Brian Kingsbury, George Saon, David Kung, and Michael Picheny · 2019
Later among the works it cites.
Momentum improves normalized SGD
Original
Ashok Cutkosky and Harsh Mehta · 2020
Closest in time.
ProxSARAH: An efficient algorithmic framework for stochastic composite nonconvex optimization
Nhan H Pham, Lam M Nguyen, Dzung T Phan, and Quoc Tran-Dinh · 2020
Closest in time.
On complexity of finding stationary points of nonsmooth nonconvex functions
Original
Jingzhao Zhang, Hongzhou Lin, Suvrit Sra, and Ali Jadbabaie · 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…