Stochastic Block BFGS: Squeezing More Curvature out of Data
arXiv:1603.09649
Abstract
We propose a novel limited-memory stochastic block BFGS update for incorporating enriched curvature information in stochastic approximation methods. In our method, the estimate of the inverse Hessian matrix that is maintained by it, is updated at each iteration using a sketch of the Hessian, i.e., a randomly generated compressed form of the Hessian. We propose several sketching strategies, present a new quasi-Newton method that uses stochastic block BFGS updates combined with the variance reduction approach SVRG to compute batch stochastic gradients, and prove linear convergence of the resulting method. Numerical tests on large-scale logistic regression problems reveal that our method is more robust and substantially outperforms current state-of-the-art methods.
arXiv comment22 pages, 6 figures, 1 table, 3 algorithms
References in corpus (12)
- SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
- Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
- RES: Regularized Stochastic BFGS Algorithm
- A Linearly-Convergent Stochastic L-BFGS Algorithm
- Global Convergence of Online Limited Memory BFGS
- Convergence rates of sub-sampled Newton methods
- Sub-Sampled Newton Methods I: Globally Convergent Algorithms
- Stochastic Dual Ascent for Solving Linear Systems
- SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization
- Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares
- Randomized Quasi-Newton Updates are Linearly Convergent Matrix Inversion Algorithms
- Action constrained quasi-Newton methods