# Stochastic Optimization Using a Trust-Region Method and Random Models

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Apr 2015.

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

- [TREGO: a Trust-Region Framework for Efficient Global Optimization](https://mlsanity.com/paper/2101.06808/) (2021)
- [An Adaptive Stochastic Sequential Quadratic Programming with Differentiable Exact Augmented Lagrangians](https://mlsanity.com/paper/2102.05320/) (2021)
- [Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems](https://mlsanity.com/paper/2211.15943/) (2022)
- [Inequality Constrained Stochastic Nonlinear Optimization via Active-Set Sequential Quadratic Programming](https://mlsanity.com/paper/2109.11502/) (2021)
- [Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence](https://mlsanity.com/paper/2204.09266/) (2022)
- [Globally Convergent Multilevel Training of Deep Residual Networks](https://mlsanity.com/paper/2107.07572/) (2021)
- [A Sequential Quadratic Programming Method with High Probability Complexity Bounds for Nonlinear Equality Constrained Stochastic Optimization](https://mlsanity.com/paper/2301.00477/) (2023)
- [Direct-Search for a Class of Stochastic Min-Max Problems](https://mlsanity.com/paper/2102.11386/) (2021)
- [No-Regret Constrained Bayesian Optimization of Noisy and Expensive Hybrid Models using Differentiable Quantile Function Approximations](https://mlsanity.com/paper/2305.03824/) (2023)
- [Riemannian Natural Gradient Methods](https://mlsanity.com/paper/2207.07287/) (2022)
- [Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models](https://mlsanity.com/paper/2409.15734/) (2024)
- [Adaptive Sampling Quasi-Newton Methods for Zeroth-Order Stochastic Optimization](https://mlsanity.com/paper/2109.12213/) (2021)
- [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)
- [A Globally Convergent Evolutionary Strategy for Stochastic Constrained Optimization with Applications to Reinforcement Learning](https://mlsanity.com/paper/2202.10464/) (2022)
- [Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function](https://mlsanity.com/paper/2310.11866/) (2023)
- [Adaptive First- and Second-Order Algorithms for Large-Scale Machine Learning](https://mlsanity.com/paper/2111.14761/) (2021)
- [A Novel Fast Exact Subproblem Solver for Stochastic Quasi-Newton Cubic Regularized Optimization](https://mlsanity.com/paper/2204.09116/) (2022)
- [On the efficiency of Stochastic Quasi-Newton Methods for Deep Learning](https://mlsanity.com/paper/2205.09121/) (2022)
- [A randomized algorithm for nonconvex minimization with inexact evaluations and complexity guarantees](https://mlsanity.com/paper/2310.18841/) (2023)
- [Global Optimisation of Black-Box Functions with Generative Models in the Wasserstein Space](https://mlsanity.com/paper/2407.11917/) (2024)
- [A Trust-Region Algorithm for Noisy Equality Constrained Optimization](https://mlsanity.com/paper/2411.02665/) (2024)
- [Probabilistic Iterative Hard Thresholding for Sparse Learning](https://mlsanity.com/paper/2409.01413/) (2024)
- [Stochastic Trust-Region Methods for Over-parameterized Models](https://mlsanity.com/paper/2604.14017/) (2026)
- [The cost of useful natural gradient updates](https://mlsanity.com/paper/2609.33499/) (2026)
- [STREGO: A Scalable Implementation of a Trust-Region Framework for Noisy Bayesian Optimization](https://mlsanity.com/paper/2610.14338/) (2026)

## Abstract (arXiv)

In this paper, we propose and analyze a trust-region model-based algorithm for solving unconstrained stochastic optimization problems. Our framework utilizes random models of an objective function f(x), obtained from stochastic observations of the function or its gradient. Our method also utilizes estimates of function values to gauge progress that is being made. The convergence analysis relies on requirements that these models and these estimates are sufficiently accurate with sufficiently high, but fixed, probability. Beyond these conditions, no assumptions are made on how these models and estimates are generated. Under these general conditions we show an almost sure global convergence of the method to a first order stationary point. In the second part of the paper, we present examples of generating sufficiently accurate random models under biased or unbiased noise assumptions. Lastly, we present some computational results showing the benefits of the proposed method compared to existing approaches that are based on sample averaging or stochastic gradients.