Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update

Michał Dereziński, Jonathan Lacotte, Mert Pilanci +1

In second-order optimization, a potential bottleneck can be computing the Hessian matrix of the optimized function at every iteration. Randomized sketching has emerged as a powerfu…