Stochastic Newton and Quasi-Newton Methods for Large Linear Least-squares Problems
This work addresses computational efficiency for large-scale data problems in machine learning, but it is incremental as it builds on existing stochastic optimization methods.
The paper tackles large linear least-squares problems with computational burdens like memory limits or real-time data by proposing stochastic Newton and quasi-Newton methods, showing that stochastic Newton may not converge to the solution while providing theoretical consistency results and numerical examples.
We describe stochastic Newton and stochastic quasi-Newton approaches to efficiently solve large linear least-squares problems where the very large data sets present a significant computational burden (e.g., the size may exceed computer memory or data are collected in real-time). In our proposed framework, stochasticity is introduced in two different frameworks as a means to overcome these computational limitations, and probability distributions that can exploit structure and/or sparsity are considered. Theoretical results on consistency of the approximations for both the stochastic Newton and the stochastic quasi-Newton methods are provided. The results show, in particular, that stochastic Newton iterates, in contrast to stochastic quasi-Newton iterates, may not converge to the desired least-squares solution. Numerical examples, including an example from extreme learning machines, demonstrate the potential applications of these methods.