A Stochastic Trust Region Method for Non-convex Minimization
This addresses optimization challenges in machine learning for non-convex problems, offering a sample-efficient method with theoretical guarantees.
The paper tackles the problem of finding local minima in non-convex finite-sum minimization by proposing a stochastic trust region algorithm that achieves an $(\\epsilon, \\sqrt{\\epsilon})$-approximate local minimum within $\\mathcal{O}({\\sqrt{n}}/{\\epsilon^{1.5}})$ stochastic Hessian oracle queries, improving the state-of-the-art by $\\mathcal{O}(n^{1/6})$.
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 $(ε, \sqrtε)$-approximate local minimum within $\mathcal{O}({\sqrt{n}}/{ε^{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.