Stochastic Quasi-Newton Methods
- 28 September 2020
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in Proceedings of the IEEE
- Vol. 108 (11) , 1906-1922
Abstract
Large-scale data science trains models for data sets containing massive numbers of samples. Training is often formulated as the solution of empirical risk minimization problems that are optimization programs whose complexity scales with the number of elements in the data set. Stochastic optimization methods overcome this challenge, but they come with their own set of limitations. This article discusses recent developments to accelerate the convergence of stochastic optimization through the exploitation of second-order information. This is achieved with stochastic variants of quasi-Newton methods that approximate the curvature of the objective function using stochastic gradient information. The reasons for why this leads to faster convergence are discussed along with the introduction of an incremental method that exploits memory to achieve a superlinear convergence rate. This is the best-known convergence rate for a stochastic optimization method. Stochastic quasi-Newton methods are applied to several problems, including prediction of the click-through rate of an advertisement displayed in response to a specific search engine query by a specific visitor. Experimental evaluations showcase reductions in overall computation time relative to stochastic gradient descent algorithms.Keywords
Funding Information
- National Science Foundation (CCF-2007668)
- NSF HDR TRIPODS (#1934960)
This publication has 41 references indexed in Scilit:
- Pegasos: primal estimated sub-gradient solver for SVMMathematical Programming, 2010
- On superlinear convergence of quasi-Newton methods for nonsmooth equationsOperations Research Letters, 1997
- A Modified BFGS Algorithm for Unconstrained OptimizationIMA Journal of Numerical Analysis, 1991
- Updating Quasi-Newton Matrices with Limited StorageMathematics of Computation, 1980
- On the Global Convergence of Broyden's MethodMathematics of Computation, 1976
- A characterization of superlinear convergence and its application to quasi-Newton methodsMathematics of Computation, 1974
- On the Local and Superlinear Convergence of Quasi-Newton MethodsIMA Journal of Applied Mathematics, 1973
- The Convergence of Single-Rank Quasi-Newton MethodsMathematics of Computation, 1970
- A new approach to variable metric algorithmsThe Computer Journal, 1970
- Conditioning of quasi-Newton methods for function minimizationMathematics of Computation, 1970