# A Stochastic Trust Region Method for Non-convex Minimization

arXiv: https://arxiv.org/abs/1903.01540 · HTML: https://mlsanity.com/paper/1903.01540/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Mar 2019.

## Built on by (most cited first, 4 of 4)

- [Two trust region type algorithms for solving nonconvex-strongly concave minimax problems](https://mlsanity.com/paper/2402.09807/) (2024)
- [On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum Optimization](https://mlsanity.com/paper/2103.05138/) (2021)
- [Faster Riemannian Newton-type Optimization by Subsampling and Cubic Regularization](https://mlsanity.com/paper/2302.11076/) (2023)
- [Stochastic Trust-Region Methods for Over-parameterized Models](https://mlsanity.com/paper/2604.14017/) (2026)

## Abstract (arXiv)

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 O(1/k2/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 (ε, √ε)-approximate local minimum within O(√n/ε1.5) stochastic Hessian oracle queries. This improves state-of-the-art result by O(n1/6). Experiments verify theoretical conclusions and the efficiency of STR.