Combining Stochastic Adaptive Cubic Regularization with Negative Curvature for Nonconvex Optimization

We focus on minimizing nonconvex finite-sum functions that typically arise in\nmachine learning problems. In an attempt to solve this problem, the adaptive\ncubic regularized Newton method has shown its strong global convergence\nguarantees and ability to escape from strict saddle points. This method uses a\ntrust region-like scheme to determine if an iteration is successful or not, and\nupdates only when it is successful. In this paper, we suggest an algorithm\ncombining negative curvature with the adaptive cubic regularized Newton method\nto update even at unsuccessful iterations. We call this new method Stochastic\nAdaptive cubic regularization with Negative Curvature (SANC). Unlike the\nprevious method, in order to attain stochastic gradient and Hessian estimators,\nthe SANC algorithm uses independent sets of data points of consistent size over\nall iterations. It makes the SANC algorithm more practical to apply for solving\nlarge-scale machine learning problems. To the best of our knowledge, this is\nthe first approach that combines the negative curvature method with the\nadaptive cubic regularized Newton method. Finally, we provide experimental\nresults including neural networks problems supporting the efficiency of our\nmethod.\n