Sketch-and-Project Meets Newton Method: Global $O(1/k^2)$ Convergence with Low-Rank Updates
Abstract
In this paper, we propose the first sketch-and-project Newton method with the fast $O(1/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(1/k^2)$ global convergence rate of the full-rank Newton-like methods, and the algorithm simplicity of the damped Newton methods. Finally, we demonstrate its comparable empirical performance to the baseline algorithms.
Cite
Text
Hanzely. "Sketch-and-Project Meets Newton Method: Global $O(1/k^2)$ Convergence with Low-Rank Updates." Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, 2025.Markdown
[Hanzely. "Sketch-and-Project Meets Newton Method: Global $O(1/k^2)$ Convergence with Low-Rank Updates." Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, 2025.](https://mlanthology.org/aistats/2025/hanzely2025aistats-sketchandproject/)BibTeX
@inproceedings{hanzely2025aistats-sketchandproject,
title = {{Sketch-and-Project Meets Newton Method: Global $O(1/k^2)$ Convergence with Low-Rank Updates}},
author = {Hanzely, Slavomir},
booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics},
year = {2025},
pages = {3205-3213},
volume = {258},
url = {https://mlanthology.org/aistats/2025/hanzely2025aistats-sketchandproject/}
}