A Stochastic Trust Region Method for Non-convex Minimization

Abstract

We target the problem of finding a local minimum in non-convex finite-sum minimization. Towards this goal, we first prove that the trust region method with inexact gradient and Hessian estimation can achieve a convergence rate of order $\mathcal{O}(1/k^{2/3})$ as long as those differential estimations are sufficiently accurate. Combining such result with a novel Hessian estimator, we propose the sample-efficient stochastic trust region (STR) algorithm which finds an $(\epsilon ,\sqrt{\epsilon })$-approximate local minimum within $\mathcal{O}(\sqrt{n}/{\epsilon }^{1.5})$ stochastic Hessian oracle queries. This improves state-of-the-art result by $\mathcal{O}(n^{1/6})$. Experiments verify theoretical conclusions and the efficiency of STR.

References in corpus (5)

• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
• Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
• Stochastic Variance-Reduced Cubic Regularized Newton Method
• Adaptive Stochastic Variance Reduction for Subsampled Newton Method with Cubic Regularization
• Sample Efficient Stochastic Variance-Reduced Cubic Regularization Method

Cited by in corpus (3)

• Sharp Analysis for Nonconvex SGD Escaping from Saddle Points
• Stochastic Recursive Variance-Reduced Cubic Regularization Methods
• On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum Optimization