Acc-RSRN: Accelerated Randomized Subspace Regularized Newton

We propose Accelerated Randomized Subspace Regularized Newton (Acc-RSRN) for smooth, possibly nonconvex optimization, with improved local linear convergence rates. Our improvement over the prior work has two components: a sharp analysis of the randomized subspace iterations replaces the dependence on the full Hessian condition number with a smaller tail-averaged quantity which leverages the preconditioning effect of randomized subspaces, and Nesterov acceleration further reduces the dependence on this quantity from linear to square root. For an $n$-dimensional problem and subspace dimension proportional to $r$, the local iteration complexity improves from $\tilde{O}(n\kappa /r)$ in prior work to $\tilde{O}(n\sqrt{{\bar{\kappa }}_r}/r)$, where ${\bar{\kappa }}_r$ is the average of the Hessian's tail eigenvalues at the minimizer divided by its smallest eigenvalue. Our results support two different Hessian access models: Hessian-vector products via Gaussian sketching, and entry-wise access via ridge leverage score sampling. Experiments on kernel logistic regression and a CNN objective illustrate the benefits of acceleration in RSRN.