# Convergence of trust-region methods based on probabilistic models

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Apr 2013.

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

- [An Adaptive Stochastic Sequential Quadratic Programming with Differentiable Exact Augmented Lagrangians](https://mlsanity.com/paper/2102.05320/) (2021)
- [Inequality Constrained Stochastic Nonlinear Optimization via Active-Set Sequential Quadratic Programming](https://mlsanity.com/paper/2109.11502/) (2021)
- [SketchySGD: Reliable Stochastic Optimization via Randomized Curvature Estimates](https://mlsanity.com/paper/2211.08597/) (2022)
- [A Sequential Quadratic Programming Method with High Probability Complexity Bounds for Nonlinear Equality Constrained Stochastic Optimization](https://mlsanity.com/paper/2301.00477/) (2023)
- [Global optimization using random embeddings](https://mlsanity.com/paper/2107.12102/) (2021)
- [Minibatch Stochastic Three Points Method for Unconstrained Smooth Minimization](https://mlsanity.com/paper/2209.07883/) (2022)
- [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)
- [The Stochastic Conjugate Subgradient Algorithm For Kernel Support Vector Machines](https://mlsanity.com/paper/2407.21091/) (2024)
- [Probabilistic Iterative Hard Thresholding for Sparse Learning](https://mlsanity.com/paper/2409.01413/) (2024)

## Abstract (arXiv)

In this paper we consider the use of probabilistic or random models within a classical trust-region framework for optimization of deterministic smooth general nonlinear functions. Our method and setting differs from many stochastic optimization approaches in two principal ways. Firstly, we assume that the value of the function itself can be computed without noise, in other words, that the function is deterministic. Secondly, we use random models of higher quality than those produced by usual stochastic gradient methods. In particular, a first order model based on random approximation of the gradient is required to provide sufficient quality of approximation with probability greater than or equal to 1/2. This is in contrast with stochastic gradient approaches, where the model is assumed to be "correct" only in expectation. As a result of this particular setting, we are able to prove convergence, with probability one, of a trust-region method which is almost identical to the classical method. Hence we show that a standard optimization framework can be used in cases when models are random and may or may not provide good approximations, as long as "good" models are more likely than "bad" models. Our results are based on the use of properties of martingales. Our motivation comes from using random sample sets and interpolation models in derivative-free optimization. However, our framework is general and can be applied with any source of uncertainty in the model. We discuss various applications for our methods in the paper.