Stochastic Second-order Methods for Non-convex Optimization with Inexact Hessian and Gradient
This work addresses the scalability issue of second-order optimization methods for machine learning practitioners, but it is incremental as it extends existing methods with stochastic approximations.
The paper tackles the high computational cost of exact gradient, Hessian, and function value computations in second-order methods for large-scale non-convex optimization, such as deep network training, by proposing stochastic trust region and cubic regularization methods with inexact computations. It shows that these methods achieve the same iteration complexity for ε-approximate second-order optimality as exact methods and perform well on convolutional neural networks.
Trust region and cubic regularization methods have demonstrated good performance in small scale non-convex optimization, showing the ability to escape from saddle points. Each iteration of these methods involves computation of gradient, Hessian and function value in order to obtain the search direction and adjust the radius or cubic regularization parameter. However, exactly computing those quantities are too expensive in large-scale problems such as training deep networks. In this paper, we study a family of stochastic trust region and cubic regularization methods when gradient, Hessian and function values are computed inexactly, and show the iteration complexity to achieve $ε$-approximate second-order optimality is in the same order with previous work for which gradient and function values are computed exactly. The mild conditions on inexactness can be achieved in finite-sum minimization using random sampling. We show the algorithm performs well on training convolutional neural networks compared with previous second-order methods.