Efficient Second Order Online Learning by Sketching
arXiv:1602.02202
Abstract
We propose Sketched Online Newton (SON), an online second order learning algorithm that enjoys substantially improved regret guarantees for ill-conditioned data. SON is an enhanced version of the Online Newton Step, which, via sketching techniques enjoys a running time linear in the dimension and sketch size. We further develop sparse forms of the sketching methods (such as Oja's rule), making the computation linear in the sparsity of features. Together, the algorithm eliminates all computational obstacles in previous second order online learning approaches.
References in corpus (7)
- A Linearly-Convergent Stochastic L-BFGS Algorithm
- Global Convergence of Online Limited Memory BFGS
- Convergence rates of sub-sampled Newton methods
- Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence
- Rivalry of Two Families of Algorithms for Memory-Restricted Streaming PCA
- Faster SGD Using Sketched Conditioning
- Scale-Free Algorithms for Online Linear Optimization
Cited by in corpus (16)
- Online Learning: A Comprehensive Survey
- Second-Order Stochastic Optimization for Machine Learning in Linear Time
- MetaGrad: Multiple Learning Rates in Online Learning
- Robust Frequent Directions with Application in Online Learning
- Making Online Sketching Hashing Even Faster
- MetaGrad: Adaptation using Multiple Learning Rates in Online Learning
- Deep Online Convex Optimization with Gated Games
- An Efficient, Sparsity-Preserving, Online Algorithm for Low-Rank Approximation
- RSN: Randomized Subspace Newton
- Revisiting Co-Occurring Directions: Sharper Analysis and Efficient Algorithm for Sparse Matrices
- Uniform regret bounds over for the sequential linear regression problem with the square loss
- An Improved Frequent Directions Algorithm for Low-Rank Approximation via Block Krylov Iteration
- Discriminative Bayesian filtering lends momentum to the stochastic Newton method for minimizing log-convex functions
- Optimal Sketching Bounds for Exp-concave Stochastic Minimization
- Dynamic Regret for Strongly Adaptive Methods and Optimality of Online KRR
- Stochastic Multi-armed Bandits in Constant Space