347. Sketch-and-Project Meets Newton Method: Global O(1/k^2) Convergence with Low-Rank Updates
Invited abstract in session WF-5: Randomized optimization algorithms part 2/2, stream Randomized optimization algorithms.
Wednesday, 16:20 - 18:00Room: M:N
Authors (first author is the speaker)
| 1. | SlavomÃr Hanzely
|
| Machine Learning, MBZUAI |
Abstract
In this paper, we propose the first sketch-and-project Newton method with 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 Newton method, ii) as a cubically regularized Newton method 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 O(1/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.
Keywords
- Analysis and engineering of optimization algorithms
- Complexity and efficiency of optimization algorithms
Status: accepted
Back to the list of papers