Sketch-and-Project Meets Newton Method: Global O(k^{-2}) Convergence with Low-Rank Updates

May, 2023

Sketch-and-Project Meets Newton Method: Global $\mathcal O(k^{-2})$ Convergence with Low-Rank Updates

Slavomír Hanzely

TL;DR提出新的SGN方法，具有sketch-and-project、cubically regularized Newton以及damped Newton等特点，可用于基于自共轭函数的优化问题，同时具有较快的全局收敛速度。

Abstract

In this paper, we propose the first sketch-and-project newton method with fast $\mathcal O(k^{-2})$ global convergence rate for self-concordant f