Stochastic Second-Order Optimization via von Neumann Series
Provides a simpler analysis and improved performance over LISSA for large-scale linear models, but is incremental in nature.
The authors propose a stochastic second-order optimization algorithm using von Neumann series, achieving linear and conditional quadratic convergence for strongly-convex smooth functions. In experiments, it matches L-BFGS performance and outperforms LISSA on quadratic objectives.
A stochastic iterative algorithm approximating second-order information using von Neumann series is discussed. We present convergence guarantees for strongly-convex and smooth functions. Our analysis is much simpler in contrast to a similar algorithm and its analysis, LISSA. The algorithm is primarily suitable for training large scale linear models, where the number of data points is very large. Two novel analyses, one showing space independent linear convergence, and one showing conditional quadratic convergence are discussed. In numerical experiments, the behavior of the error is similar to the second-order algorithm L-BFGS, and improves the performance of LISSA for quadratic objective function.