2019

Quasi-Newton Methods for Machine Learning: Forget the Past, Just Sample

Berahas, Albert S., Jahani, Majid, Richtárik, Peter et al.

Understand

We present two sampled quasi-Newton methods (sampled LBFGS and sampled LSR1) for solving empirical risk minimization problems that arise in machine learning.

Contrary to the classical variants of these methods that sequentially build Hessian or inverse Hessian approximations as the optimization progresses, our proposed methods sample points randomly around the current iterate at every iteration to produce these approximations.
As a result, the approximations constructed make use of more reliable (recent and local) information, and do not depend on past iterate information that could be significantly stale.
Our proposed algorithms are efficient in terms of accessed data points (epochs) and have enough concurrency to take advantage of parallel/distributed computing environments.

Built on

H. Robbins and S. Monro, A stochastic approximation method , The Annals of Mathematical Statistics (1951), pp. 400–407
1951
Earlier work this paper cites.
C.G. Broyden, Quasi-newton methods and their application to function minimisation , Mathematics of Computation 21 (1967), pp. 368–381
1967
Earlier work this paper cites.
R. Fletcher, A new approach to variable metric algorithms , The computer journal 13 (1970), pp. 317–322
1970
Earlier work this paper cites.
D. Goldfarb, A family of variable-metric methods derived by variational means , Mathematics of computation 24 (1970), pp. 23–26
1970
Earlier work this paper cites.
D.F. Shanno, Conditioning of quasi-newton methods for function minimization , Mathematics of computation 24 (1970), pp. 647–656
1970
Earlier work this paper cites.
M.J. Powell, Some global convergence properties of a variable metric algorithm for minimization without exact line searches , Nonlinear programming 9 (1976), pp. 53–72
1976
Earlier work this paper cites.
M.J. Powell, Algorithms for nonlinear constraints that use lagrangian functions , Mathematical programming 14 (1978), pp. 224–248
1978
Earlier work this paper cites.
J. Nocedal, Updating quasi-newton matrices with limited storage , Mathematics of computation 35 (1980), pp. 773–782
1980
Earlier work this paper cites.
D.C. Liu and J. Nocedal, On the limited memory bfgs method for large scale optimization , Mathematical programming 45 (1989), pp. 503–528
1989
Earlier work this paper cites.
A.R. Conn, N.I. Gould, and P.L. Toint, Convergence of quasi-newton matrices generated by the symmetric rank one update , Mathematical programming 50 (1991), pp. 177–195
1991
Earlier work this paper cites.
H.F. Khalfan, R.H. Byrd, and R.B. Schnabel, A theoretical and experimental study of the symmetric rank-one update , SIAM Journal on Optimization 3 (1993), pp. 1–24
1993
Earlier work this paper cites.
R.H. Byrd, J. Nocedal, and R.B. Schnabel, Representations of quasi-newton matrices and their use in limited memory methods , Mathematical Programming 63 (1994), pp. 129–156
1994
Earlier work this paper cites.
R.H. Byrd, H.F. Khalfan, and R.B. Schnabel, Analysis of a symmetric rank-one trust region method , SIAM Journal on Optimization 6 (1996), pp. 1025–1039
1996
Earlier work this paper cites.
X. Lu, A study of the limited memory SR1 method in practice , University of Colorado at Boulder, 1996
1996
Earlier work this paper cites.
Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, Gradient-based learning applied to document recognition , Proceedings of the IEEE 86 (1998), pp. 2278–2324
1998
Earlier work this paper cites.
E.G. Boman, Infeasibility and negative curvature in optimization , stanford university, 1999
1999
Earlier work this paper cites.
A.R. Conn, N.I. Gould, and P.L. Toint, Trust region methods , Vol. 1, Siam, 2000
2000
Earlier work this paper cites.
D.H. Li and M. Fukushima, A modified bfgs method and its global convergence in nonconvex minimization , Journal of Computational and Applied Mathematics 129 (2001), pp. 15–35
2001
Earlier work this paper cites.
D.H. Li and M. Fukushima, On the global convergence of the bfgs method for nonconvex unconstrained optimization problems , SIAM Journal on Optimization 11 (2001), pp. 1054–1064
2001
Earlier work this paper cites.
Y.H. Dai, Convergence properties of the bfgs algoritm , SIAM Journal on Optimization 13 (2002), pp. 693–701
2002
Earlier work this paper cites.
L. Bottou and Y.L. Cun, Large scale online learning , in Advances in neural information processing systems . 2004, pp. 217–224
2004
Earlier work this paper cites.

Similar

W.F. Mascarenhas, The bfgs method with exact line searches fails for non-convex objective functions , Mathematical Programming 99 (2004), pp. 49–61
2004
Cited alongside, same era.
J. Nocedal and S.J. Wright, Numerical Optimization , 2nd ed., Springer Series in Operations Research, Springer, 2006
2006
Cited alongside, same era.
N.N. Schraudolph, J. Yu, and S. Günter, A stochastic quasi-Newton method for online convex optimization , in Artificial Intelligence and Statistics . 2007, pp. 436–443
2007
Cited alongside, same era.
A. Krizhevsky and G. Hinton, Learning multiple layers of features from tiny images , Tech. Rep., 2009
2009
Cited alongside, same era.
J. Martens, Deep learning via Hessian-free optimization. , in ICML , Vol. 27. 2010, pp. 735–742
2010
Cited alongside, same era.
R.H. Byrd, G.M. Chin, W. Neveitt, and J. Nocedal, On the use of stochastic hessian information in optimization methods for machine learning , SIAM Journal on Optimization 21 (2011), pp. 977–995
2011
Cited alongside, same era.
C.C. Chang and C.J. Lin, Libsvm: a library for support vector machines , ACM transactions on intelligent systems and technology (TIST) 2 (2011), pp. 1–27
2011
Cited alongside, same era.
J. Duchi, E. Hazan, and Y. Singer, Adaptive subgradient methods for online learning and stochastic optimization , Journal of Machine Learning Research 12 (2011), pp. 2121–2159
2011
Cited alongside, same era.
R. Johnson and T. Zhang, Accelerating stochastic gradient descent using predictive variance reduction , in Advances in neural information processing systems . 2013, pp. 315–323
2013
Cited alongside, same era.
M. Takáč, A.S. Bijral, P. Richtárik, and N. Srebro, Mini-Batch Primal and Dual Methods for SVMs. , in International Conference on Machine Learning . 2013, pp. 1022–1030
2013
Cited alongside, same era.
A. Defazio, F. Bach, and S. Lacoste-Julien, SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives , in Advances in neural information processing systems . 2014, pp. 1646–1654
2014
Cited alongside, same era.
D.P. Kingma and J. Ba, Adam: A method for stochastic optimization , arXiv preprint arXiv:1412.6980 (2014)
Original
2014
Cited alongside, same era.

Then

N.S. Keskar, D. Mudigere, J. Nocedal, M. Smelyanskiy, and P.T.P. Tang, On large-batch training for deep learning: Generalization gap and sharp minima , arXiv preprint arXiv:1609.04836 (2016)
Original
2016
Later among the works it cites.
A. Mokhtari, H. Daneshmand, A. Lucchi, T. Hofmann, and A. Ribeiro, Adaptive newton method for empirical risk minimization to statistical accuracy , in Advances in Neural Information Processing Systems . 2016, pp. 4062–4070
2016
Later among the works it cites.
T. Akiba, S. Suzuki, and K. Fukuda, Extremely large minibatch sgd: Training resnet-50 on imagenet in 15 minutes , arXiv preprint arXiv:1711.04325 (2017)
Original
2017
Later among the works it cites.
J. Brust, J.B. Erway, and R.F. Marcia, On solving l-sr1 trust-region subproblems , Computational Optimization and Applications 66 (2017), pp. 245–266
2017
Later among the works it cites.
P. Goyal, P. Dollár, R. Girshick, P. Noordhuis, L. Wesolowski, A. Kyrola, A. Tulloch, Y. Jia, and K. He, Accurate, large minibatch sgd: training imagenet in 1 hour , arXiv preprint arXiv:1706.02677 (2017)
Original
2017
Later among the works it cites.
L.M. Nguyen, J. Liu, K. Scheinberg, and M. Takáč, SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient , in International Conference on Machine Learning . 2017, pp. 2613–2621
2017
Later among the works it cites.
M. Schmidt, N. Le Roux, and F. Bach, Minimizing finite sums with the stochastic average gradient , Mathematical Programming 162 (2017), pp. 83–112
2017
Later among the works it cites.
L. Bottou, F.E. Curtis, and J. Nocedal, Optimization methods for large-scale machine learning , Siam Review 60 (2018), pp. 223–311
2018
Later among the works it cites.
W. Gao and D. Goldfarb, Block bfgs methods , SIAM Journal on Optimization 28 (2018), pp. 1205–1231
2018
Later among the works it cites.
X. Jia, S. Song, W. He, Y. Wang, H. Rong, F. Zhou, L. Xie, Z. Guo, Y. Yang, L. Yu, et al. , Highly scalable deep learning training system with mixed-precision: Training imagenet in four minutes , arXiv preprint arXiv:1807.11205 (2018)
Original
2018
Later among the works it cites.
S.B. Kylasa, F. Roosta-Khorasani, M.W. Mahoney, and A. Grama, Gpu accelerated sub-sampled newtons method , arXiv preprint arXiv:1802.09113 (2018)
Original
2018
Later among the works it cites.
J. Liu, Y. Rong, M. Takáč, and J. Huang, On the acceleration of l-bfgs with second-order information and stochastic batches , arXiv preprint:1807.05328 (2018)
2018
Later among the works it cites.
F. Roosta-Khorasani and M.W. Mahoney, Sub-sampled newton methods , Mathematical Programming (2018)
2018
Later among the works it cites.
Y. You, Z. Zhang, C.J. Hsieh, J. Demmel, and K. Keutzer, Imagenet training in minutes , in Proceedings of the 47th International Conference on Parallel Processing . ACM, 2018, p. 1
2018
Later among the works it cites.
P. Xu, F. Roosta, and M.W. Mahoney, Newton-type methods for non-convex optimization under inexact hessian information , Mathematical Programming (2019), pp. 1–36
2019
Closest in time.
A.S. Berahas, R. Bollapragada, and J. Nocedal, An investigation of newton-sketch and subsampled newton methods , Optimization Methods and Software 35 (2020), pp. 661–680
2020
Closest in time.
A.S. Berahas and M. Takáč, A robust multi-batch l-bfgs method for machine learning , Optimization Methods and Software 35 (2020), pp. 191–219
2020
Closest in time.
M. Jahani, X. He, C. Ma, A. Mokhtari, D. Mudigere, A. Ribeiro, and M. Takác, Efficient distributed hessian free algorithm for large-scale empirical risk minimization via accumulating sample strategy , in International Conference on Artificial Intelligence and Statistics . PMLR, 2020, pp. 2634–2644
2020
Closest in time.
M. Jahani, M. Nazari, S. Rusakov, A.S. Berahas, and M. Takáč, Scaling up quasi-newton algorithms: Communication efficient distributed sr1 , in International Conference on Machine Learning, Optimization, and Data Science . Springer, 2020, pp. 41–54
2020
Closest in time.
P. Xu, F. Roosta, and M.W. Mahoney, Second-order optimization for non-convex machine learning: An empirical study , in Proceedings of the 2020 SIAM International Conference on Data Mining . SIAM, 2020, pp. 199–207
2020
Closest in time.
M. Jahani, M. Nazari, R. Tappenden, A.S. Berahas, and M. Takac, SONIA: A symmetric blockwise truncated optimization algorithm , in International Conference on Artificial Intelligence and Statistics . PMLR, 2021, pp. 487–495
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…