# Global convergence rate analysis of unconstrained optimization methods based on probabilistic models

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 May 2015.

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

- [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)
- [Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods](https://mlsanity.com/paper/2302.11962/) (2023)
- [Enhancing Efficiency of Safe Reinforcement Learning via Sample Manipulation](https://mlsanity.com/paper/2405.20860/) (2024)
- [A Sequential Quadratic Programming Method with High Probability Complexity Bounds for Nonlinear Equality Constrained Stochastic Optimization](https://mlsanity.com/paper/2301.00477/) (2023)
- [AdAdaGrad: Adaptive Batch Size Schemes for Adaptive Gradient Methods](https://mlsanity.com/paper/2402.11215/) (2024)
- [Global optimization using random embeddings](https://mlsanity.com/paper/2107.12102/) (2021)
- [Improving Stochastic Cubic Newton with Momentum](https://mlsanity.com/paper/2410.19644/) (2024)
- [Adaptive Sampling Quasi-Newton Methods for Zeroth-Order Stochastic Optimization](https://mlsanity.com/paper/2109.12213/) (2021)
- [AdaBatchGrad: Combining Adaptive Batch Size and Adaptive Step Size](https://mlsanity.com/paper/2402.05264/) (2024)
- [The Stochastic Conjugate Subgradient Algorithm For Kernel Support Vector Machines](https://mlsanity.com/paper/2407.21091/) (2024)
- [Gradient-Normalized Smoothness for Optimization with Approximate Hessians](https://mlsanity.com/paper/2506.13710/) (2025)
- [Recursive Bound-Constrained AdaGrad with Applications to Multilevel and Domain Decomposition Minimization](https://mlsanity.com/paper/2507.11513/) (2025)
- [A Randomised Subspace Gauss-Newton Method for Nonlinear Least-Squares](https://mlsanity.com/paper/2211.05727/) (2022)
- [Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function](https://mlsanity.com/paper/2310.11866/) (2023)
- [Adaptive Backtracking Line Search](https://mlsanity.com/paper/2408.13150/) (2024)
- [A Retrospective Approximation Approach for Smooth Stochastic Optimization](https://mlsanity.com/paper/2103.04392/) (2021)
- [Scaling the Wild: Decentralizing Hogwild!-style Shared-memory SGD](https://mlsanity.com/paper/2203.06638/) (2022)
- [Augmented Newton Method for Optimization: Global Linear Rate and Momentum Interpretation](https://mlsanity.com/paper/2205.11033/) (2022)
- [Stochastic Ratios Tracking Algorithm for Large Scale Machine Learning Problems](https://mlsanity.com/paper/2305.09978/) (2023)
- [A randomized algorithm for nonconvex minimization with inexact evaluations and complexity guarantees](https://mlsanity.com/paper/2310.18841/) (2023)
- [On the equivalence of different adaptive batch size selection strategies for stochastic gradient descent methods](https://mlsanity.com/paper/2109.10933/) (2021)
- [Painless Federated Learning: An Interplay of Line-Search and Extrapolation](https://mlsanity.com/paper/2408.17145/) (2024)
- [Probabilistic Iterative Hard Thresholding for Sparse Learning](https://mlsanity.com/paper/2409.01413/) (2024)
- [Stochastic Subspace Descent Accelerated via Bi-fidelity Line Search](https://mlsanity.com/paper/2505.00162/) (2025)
- [A Structured Tour of Optimization with Finite Differences](https://mlsanity.com/paper/2505.19720/) (2025)
- [Stochastic Trust-Region Methods for Over-parameterized Models](https://mlsanity.com/paper/2604.14017/) (2026)

## Abstract (arXiv)

We present global convergence rates for a line-search method which is based on random first-order models and directions whose quality is ensured only with certain probability. We show that in terms of the order of the accuracy, the evaluation complexity of such a method is the same as its counterparts that use deterministic accurate models; the use of probabilistic models only increases the complexity by a constant, which depends on the probability of the models being good. We particularize and improve these results in the convex and strongly convex case. We also analyze a probabilistic cubic regularization variant that allows approximate probabilistic second-order models and show improved complexity bounds compared to probabilistic first-order methods; again, as a function of the accuracy, the probabilistic cubic regularization bounds are of the same (optimal) order as for the deterministic case.