Research PapersNo Access

Stochastic sub-sampled Newton method with variance reduction

Zhijian Luo

http://orcid.org/0000-0002-8670-5786

College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, P. R. China

E-mail Address: luozhijian@zju.edu.cn

Search for more papers by this author

and

Yuntao Qian

College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, P. R. China

E-mail Address: ytqian@zju.edu.cn

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S0219691319500413Cited by:1 (Source: Crossref)

Abstract

Stochastic optimization on large-scale machine learning problems has been developed dramatically since stochastic gradient methods with variance reduction technique were introduced. Several stochastic second-order methods, which approximate curvature information by the Hessian in stochastic setting, have been proposed for improvements. In this paper, we introduce a Stochastic Sub-Sampled Newton method with Variance Reduction (S2NMVR), which incorporates the sub-sampled Newton method and stochastic variance-reduced gradient. For many machine learning problems, the linear time Hessian-vector production provides evidence to the computational efficiency of S2NMVR. We then develop two variations of S2NMVR that preserve the estimation of Hessian inverse and decrease the computational cost of Hessian-vector product for nonlinear problems.

Keywords:

AMSC: 62H35, 68T01

References

1. N. Agarwal, B. Bullins and E. Hazan , Second-order stochastic optimization for machine learning in linear time, J. Mach. Learn. Res. 18(116) (2017) 1–40. Google Scholar
2. A. Astorino, A. Fuduli and M. Gaudioso , Nonlinear programming for classification problems in machine learning, AIP Conf. Proc. 1776(1) (2016) 040004. Google Scholar
3. L. Bottou, F. E. Curtis and J. Nocedal , Optimization methods for large-scale machine learning, SIAM Rev. 60(2) (2018) 223–311. Web of Science, Google Scholar
4. G. Bouchard, T. Trouillon, J. Perez and A. Gaidon, Online learning to sample, preprint (2015), arXiv:1506.09016. Google Scholar
5. 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 J. Optim. 21(3) (2011) 977–995. Web of Science, Google Scholar
6. R. H. Byrd, S. L. Hansen, J. Nocedal and Y. Singer , A stochastic quasi-newton method for large-scale optimization, SIAM J. Optim. 26(2) (2015) 1008–1031. Web of Science, Google Scholar
7. A. Defazio, F. Bach and S. Lacostejulien , SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives, in Proc. Neural Inf. Process. Syst. (2014), pp. 1646–1654. Google Scholar
8. A. Defazio et al., Finito: A faster, permutable incremental gradient method for big data problems, in Proc. ACM Int. Conf. Machine Learning (Beijing, China, 2014), pp. 1125–1133. Google Scholar
9. J. Duchi, E. Hazan and Y. Singer , Adaptive subgradient methods for online learning and stochastic optimization, J. Mach. Learn. Res. 12(7) (2011) 257–269. Google Scholar
10. R. Johnson and T. Zhang , Accelerating stochastic gradient descent using predictive variance reduction, Proc. Neural Inf. Process. Syst. (2013), pp. 315–323. Google Scholar
11. R. Kiros, Training neural networks with stochastic hessian-free optimization, preprint (2013), arXiv:1301.3641. Google Scholar
12. R. Kolte, M. Erdogdu and A. Ozgür , Accelerating SVRG via second-order information, in NIPS Workshop on Optimization for Machine Learning (2015). Google Scholar
13. J. Konečnỳ and P. Richtárik , Semi-stochastic gradient descent methods, Front. Appl. Math. Stat. 3 (2017) 9. Google Scholar
14. A. Lucchi, B. Mcwilliams and T. Hofmann, A variance reduced stochastic newton method, preprint (2015), arXiv:1503.08316. Google Scholar
15. L. Luo, Z. Chen, Z. Zhang and W. J. Li, Variance-reduced second-order methods, preprint (2016), arXiv:1602.00223. Google Scholar
16. J. Mairal , Incremental majorization-minimization optimization with application to large-scale machine learning, SIAM J. Optim. 25(2) (2014) 829–855. Web of Science, Google Scholar
17. J. Martens , Deep learning via Hessian-free optimization, in Proc. ACM Int. Conf. Machine Learning (Haifa, Israel, 2010), pp. 735–742. Google Scholar
18. J. Martens, New insights and perspectives on the natural gradient method, preprint (2014), arXiv:1412.1193. Google Scholar
19. J. Martens and I. Sutskever , Learning recurrent neural networks with Hessian-free optimization, Proc. ACM Int. Conf. Machine Learning (Bellevue, Washington, USA, 2011), pp. 1033–1040. Google Scholar
20. P. Moritz, R. Nishihara and M. I. Jordan , A linearly-convergent stochastic l-BFGS algorithm, in Proc. Int. Conf. Artificial Intelligence and Statistics (Cadiz, Spain, 2016), pp. 249–258. Google Scholar
21. Y. Nesterov , Efficiency of coordinate descent methods on huge-scale optimization problems, SIAM J. Optim. 22(2) (2012) 341–362. Web of Science, Google Scholar
22. Y. Ollivier, Riemannian metrics for neural networks i: Feedforward networks, preprint (2013), arXiv:1303.0818. Google Scholar
23. H. Robbins and S. Monro , A stochastic approximation method, Ann. Math. Stat. 22(3) (1951) 400–407. Web of Science, Google Scholar
24. N. L. Roux, M. Schmidt and F. R. Bach , A stochastic gradient method with an exponential convergence rate for finite training sets, Proc. Neural Inf. Process. Syst. (Lake Tahoe, Nevada, USA, 2012), pp. 2663–2671. Google Scholar
25. C. D. Sa, C. Re and K. Olukotun , Global convergence of stochastic gradient descent for some non-convex matrix problems, in Proc. ACM Int. Conf. Machine Learning (Lille, France, 2015), pp. 2332–2341. Google Scholar
26. M. Schmidt, N. L. Roux and F. Bach , Minimizing finite sums with the stochastic average gradient, Math. Program. 26(5) (2013) 405–11. Google Scholar
27. N. N. Schraudolph, J. Yu and S. Gunter , A stochastic quasi-newton method for online convex optimization, J. Mach. Learn. Res. 2 (2007) 436–443. Google Scholar
28. S. Shalevshwartz and T. Zhang , Proximal stochastic dual coordinate ascent, Mathematics (2012). Google Scholar
29. D. P. Woodruff , Sketching as a tool for numerical linear algebra, Found. Trends Theor. Comput. Sci. 10 (2014) 1–157. Google Scholar
30. L. Xiao and T. Zhang , A proximal stochastic gradient method with progressive variance reduction, SIAM J. Optim. 24(4) (2014) 2057–2075. Web of Science, Google Scholar