Can I read Nys-Newton: Nystr\"om-Approximated Curvature for Stochastic Optimization on EtoBox?

Nys-Newton: Nystr\"om-Approximated Curvature for Stochastic Optimization by Singh, Dinesh; Tankaria, Hardik; Yamada, Makoto is a scholarly article available to read on EtoBox.

What is Nys-Newton: Nystr\"om-Approximated Curvature for Stochastic Optimization about?

Second-order optimization methods are among the most widely used optimization approaches for convex optimization problems, and have recently been used to optimize non-convex optimization problems such as deep learning models. The widely used second-order optimization methods such as quasi-Newton methods generally provide curvature information by approximating the Hessian using the secant equation. However, the secant equation becomes insipid in approximating the Newton step owing to its use of the first-order derivatives. In this study, we propose an approximate Newton sketch-based stochastic optimization algorithm for large-scale empirical risk minimization. Specifically, we compute a partial column Hessian of size ($d\times m$) with $m\ll d$ randomly selected variables, then use the \emph{Nystr\"om method} to better approximate the full Hessian matrix. To further reduce the computational complexity per iteration, we directly compute the update step ($\Delta\boldsymbol{w}$) without computing and storing the full Hessian or its inverse. We then integrate our approximated Hessian with stochastic gradient descent and stochastic variance-reduced gradient methods. The results of numeri

Author

Singh, Dinesh; Tankaria, Hardik; Yamada, Makoto

Published

2021

Language

EN