# First- and Second-Order High Probability Complexity Bounds for Trust-Region Methods with Noisy Oracles

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 May 2022.

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

- [A Sequential Quadratic Programming Method with High Probability Complexity Bounds for Nonlinear Equality Constrained Stochastic Optimization](https://mlsanity.com/paper/2301.00477/) (2023)
- [Analyzing Inexact Hypergradients for Bilevel Learning](https://mlsanity.com/paper/2301.04764/) (2023)
- [First and zeroth-order implementations of the regularized Newton method with lazy approximated Hessians](https://mlsanity.com/paper/2309.02412/) (2023)
- [Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models](https://mlsanity.com/paper/2409.15734/) (2024)
- [High Probability Complexity Bounds of Trust-Region Stochastic Sequential Quadratic Programming with Heavy-Tailed Noise](https://mlsanity.com/paper/2503.19091/) (2025)
- [Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function](https://mlsanity.com/paper/2310.11866/) (2023)
- [A Trust-Region Interior-Point Stochastic Sequential Quadratic Programming Method](https://mlsanity.com/paper/2603.10230/) (2026)
- [A Trust-Region Algorithm for Noisy Equality Constrained Optimization](https://mlsanity.com/paper/2411.02665/) (2024)

## Abstract (arXiv)

In this paper, we present convergence guarantees for a modified trust-region method designed for minimizing objective functions whose value and gradient and Hessian estimates are computed with noise. These estimates are produced by generic stochastic oracles, which are not assumed to be unbiased or consistent. We introduce these oracles and show that they are more general and have more relaxed assumptions than the stochastic oracles used in prior literature on stochastic trust-region methods. Our method utilizes a relaxed step acceptance criterion and a cautious trust-region radius updating strategy which allows us to derive exponentially decaying tail bounds on the iteration complexity for convergence to points that satisfy approximate first- and second-order optimality conditions. Finally, we present two sets of numerical results. We first explore the tightness of our theoretical results on an example with adversarial zeroth- and first-order oracles. We then investigate the performance of the modified trust-region algorithm on standard noisy derivative-free optimization problems.