Sketch-and-Project Meets Newton Method: Global mathcal O(k-2) Convergence with Low-Rank Updates
Not on the map. Why?
Abstract (arXiv)
In this paper, we propose the first sketch-and-project Newton method with fast mathcal O(k-2) global convergence rate for self-concordant functions. Our method, SGN, can be viewed in three ways: i) as a sketch-and-project algorithm projecting updates of Newton method, ii) as a cubically regularized Newton ethod in sketched subspaces, and iii) as a damped Newton method in sketched subspaces. SGN inherits best of all three worlds: cheap iteration costs of sketch-and-project methods, state-of-the-art mathcal O(k-2) global convergence rate of full-rank Newton-like methods and the algorithm simplicity of damped Newton methods. Finally, we demonstrate its comparable empirical performance to baseline algorithms.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 13 of its 32 references that are in the map. First posted on arXiv 22 May 2023.
Builds on
13 of 32 references.
References · 13
- 2020Variance-Reduced Methods for Machine Learningcited by 79
- 2019RSN: Randomized Subspace Newtoncited by 34
- 2016Efficient Second Order Online Learning by Sketchingcited by 33
- 2018Global linear convergence of Newton's method without strong-convexity or Lipschitz gradientscited by 24
- 2021Regularized Newton Method with Global O(1/k2) Convergencecited by 22
- 2020Greedy Quasi-Newton Methods with Explicit Superlinear Convergencecited by 21
- 2020Stochastic Subspace Cubic Newton Methodcited by 21
- 2015SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimizationcited by 18
- 2021Gradient Regularization of Newton Method with Bregman Distancescited by 16
- 2018Randomized Block Cubic Newton Methodcited by 14
- 2020Curiosities and counterexamples in smooth convex optimizationcited by 7
- 2019Local convergence of tensor methodscited by 6
1 more
- 2020A new framework for the computation of Hessianscited by 2
Built on by
Citing papers per year: 2024: 2; 2025: 1.
3 papers.