Second-Order Stochastic Optimization for Machine Learning in Linear Time
arXiv:1602.03943
Abstract
First-order stochastic methods are the state-of-the-art in large-scale machine learning optimization owing to efficient per-iteration complexity. Second-order methods, while able to provide faster convergence, have been much less explored due to the high cost of computing the second-order information. In this paper we develop second-order stochastic methods for optimization problems in machine learning that match the per-iteration cost of gradient based methods, and in certain settings improve upon the overall running time over popular first-order methods. Furthermore, our algorithm has the desirable property of being implementable in time linear in the sparsity of the input data.
References in corpus (7)
- SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
- A Linearly-Convergent Stochastic L-BFGS Algorithm
- Fast and Simple PCA via Convex Optimization
- Efficient Second Order Online Learning by Sketching
- Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence
- Finding Approximate Local Minima Faster than Gradient Descent
- Approximate Newton Methods
Cited by in corpus (17)
- Sub-sampled Newton Methods with Non-uniform Sampling
- Training Data Influence Analysis and Estimation: A Survey
- Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
- Shampoo: Preconditioned Stochastic Tensor Optimization
- A Selective Review on Statistical Methods for Massive Data Computation: Distributed Computing, Subsampling, and Minibatch Techniques
- Efficient Regret Minimization in Non-Convex Games
- Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients
- Estimation of discrete choice models with hybrid stochastic adaptive batch size algorithms
- Estimating the Spectral Density of Large Implicit Matrices
- Improved Optimization of Finite Sums with Minibatch Stochastic Variance Reduced Proximal Iterations
- Stochastic Second-Order Optimization via von Neumann Series
- True Asymptotic Natural Gradient Optimization
- Tricks from Deep Learning
- Lower Bounds for Higher-Order Convex Optimization
- Revisiting Sub-sampled Newton Methods
- Variance-Reduced Stochastic Optimization for Efficient Inference of Hidden Markov Models
- Unbiased Estimation of the Hessian for Partially Observed Diffusions