mlsanityData to 7 Oct 2026

Efficient Second Order Online Learning by Sketching

arXiv 1602.02202 ↗First posted 6 Feb 2016cs.LGcited by 33

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 33 papers in the map (data through 7 Oct 2026). First posted on arXiv 6 Feb 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2019: 1; 2020: 0; 2021: 6; 2022: 5; 2023: 9; 2024: 4; 2025: 5; 2026: 3.

33 papers.

Sort:

By area:

  1. 2021MetaGrad: Adaptation using Multiple Learning Rates in Online Learningcited by 26
  2. 2021An Adaptive Stochastic Sequential Quadratic Programming with Differentiable Exact Augmented Lagrangianscited by 25
  3. 2023Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimizationcited by 22
  4. 2021Inequality Constrained Stochastic Nonlinear Optimization via Active-Set Sequential Quadratic Programmingcited by 16
  5. 2023Sketchy: Memory-efficient Adaptive Regularization with Frequent Directionscited by 16
  6. 2022Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergencecited by 14
  7. 2019Soft-Bayes: Prod for Mixtures of Experts with Log-Losscited by 10
  8. 2023Projection-free Online Exp-concave Optimizationcited by 10
  9. 2024Online Linear Regression in Dynamic Environments via Discountingcited by 10
  10. 2022Quasi-Newton Steps for Efficient Online Exp-Concave Optimizationcited by 9
  11. 2024Gradient descent with generalized Newton's methodcited by 9
  12. 2022Second Order Path Variationals in Non-Stationary Online Learningcited by 7
21 more
  1. 2023Delayed Bandits: When Do Intermediate Observations Help?cited by 7
  2. 2022Addressing modern and practical challenges in machine learning: A survey of online federated and transfer learningcited by 6
  3. 2023Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedbackcited by 6
  4. 2023Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketchingcited by 5
  5. 2021Dynamic Regret for Strongly Adaptive Methods and Optimality of Online KRRcited by 4
  6. 2026Simple Projection-Free Algorithm for Contextual Recommendation with Logarithmic Regret and Robustnesscited by 4
  7. 2023Sketch-and-Project Meets Newton Method: Global mathcal O(k-2) Convergence with Low-Rank Updatescited by 3
  8. 2024Revisiting Matrix Sketching in Linear Bandits: Achieving Sublinear Regret via Dyadic Block Sketchingcited by 3
  9. 2025Parameter-free Algorithms for the Stochastically Extended Adversarial Modelcited by 3
  10. 2022A Randomised Subspace Gauss-Newton Method for Nonlinear Least-Squarescited by 2
  11. 2025A Simple, Optimal and Efficient Algorithm for Online Exp-Concave Optimizationcited by 2
  12. 2021An Improved Frequent Directions Algorithm for Low-Rank Approximation via Block Krylov Iterationcited by 1
  13. 2025Subspace-based Approximate Hessian Method for Zeroth-Order Optimizationcited by 1
  14. 2021Discriminative Bayesian filtering lends momentum to the stochastic Newton method for minimizing log-convex functionscited by 0
  15. 2023Nearly Optimal Algorithms with Sublinear Computational Complexity for Online Kernel Regressioncited by 0
  16. 2023A Computationally Efficient Sparsified Online Newton Methodcited by 0
  17. 2024Fast Second-Order Online Kernel Learning through Incremental Matrix Sketching and Decompositioncited by 0
  18. 2025Online Statistical Inference of Constrained Stochastic Optimization via Random Scalingcited by 0
  19. 2025A Polynomial-time Algorithm for Online Sparse Linear Regression with Improved Regret Bound under Weaker Conditionscited by 0
  20. 2026Efficient Multinomial Logistic Bandit via Frequent Directionscited by 0
  21. 2026QueryMarket: Cost-Aware Online Active Learning in Data Marketscited by 0