Sketch-and-Project Meets Newton Method: Global $\mathcal O(k^{-2})$ Convergence with Low-Rank Updates
This work addresses the need for efficient optimization algorithms in machine learning by combining cheap iterations with state-of-the-art convergence rates, though it is incremental in building upon existing sketch-and-project and Newton methods.
The paper tackles the problem of achieving fast global convergence for Newton-like methods on self-concordant functions by proposing SGN, a sketch-and-project Newton method that attains an O(k^{-2}) convergence rate with low-rank updates, as demonstrated empirically against baseline algorithms.
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.