Sketch-and-Project Meets Newton Method: Global O(k-2) Convergence with Low-Rank Updates
Hanzely, Slavomir
Hanzely, Slavomir
Author
Supervisor
Department
Machine Learning
Embargo End Date
Type
Conference proceeding
Date
2025
License
Language
English
Collections
Research Projects
Organizational Units
Journal Issue
Abstract
In this paper, we propose the first sketch-and-project Newton method with the fast 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 the Newton method, ii) as a cubically regularized Newton method in the sketched subspaces, and iii) as a damped Newton method in the sketched subspaces. SGN inherits the best of all three worlds: the cheap iteration costs of the sketch-and-project methods, the state-of-the-art O(k-2) global convergence rate of the full-rank Newton-like methods, and the algorithm simplicity of the damped Newton methods. Finally, we empirically show SGN performs on par with baseline algorithms.
Citation
S. Hanzely, “Sketch-and-Project Meets Newton Method: Global O(k⁻²) Convergence with Low-Rank Updates,” in Proc. 28th Int. Conf. Artif. Intell. Stat. (AISTATS 2025), vol. 258, Proc. Mach. Learn. Res., Mai Khao, Thailand, May 3–5, 2025, pp. 3205–3213
Source
Proceedings of Machine Learning Research
Conference
28th International Conference on Artificial Intelligence and Statistics, AISTATS 2025
Keywords
Convergence Rates, Damped Newton's Methods, Global Conver-gence, Newton Like Methods, Newton's Methods, Project Methods, Regularized Newton Method, Self-concordant Functions, State Of The Art, Newton-raphson Method
Subjects
Source
28th International Conference on Artificial Intelligence and Statistics, AISTATS 2025
Publisher
ML Research Press