Stochastic Second-Order Optimization via von Neumann Series
arXiv:1612.04694
Abstract
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.
References in corpus (4)
- SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
- SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization
- Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence
- Coordinate Descent with Arbitrary Sampling II: Expected Separable Overapproximation