Stochastic and Noisy Oracles in Smooth Continuous Optimization
Abstract
We review models of inexact computational oracles in smooth continuous optimization and their implications for the convergence, computational complexity, and attainable accuracy of optimization algorithms. We adopt a framework in which zeroth-,first-, and second-order oracles are characterized by quantitative error bounds and may accept additional control parameters that influence both their accuracy and computational cost. We introduce deterministic and stochastic oracle models and illustrate their properties through a variety of examples, including finite-difference approximations, stochastic gradients, and randomized derivative estimators. Particular attention is given to the distinction between absolute and relative errors, bias and variance, and stochastic function evaluations with independent or coupled randomness. A central theme of the review is the use of common analytical tools to recover and compare convergence and complexity guarantees under different oracle models. For deterministic and stochastic first-order methods, we show how a general descent inequality leads to complexity bounds under various assumptions on the objective function and all proposed oracle models. In the stochastic setting, we develop bounds on expected stopping times and the accuracy that can be guaranteed under different oracle conditions. We also examine the total computational complexity of algorithms relying on specific oracle constructions and briefly review models of inexact second- order information and their use in optimization algorithms.
Related
- An Ω(κy8ε−6) Lower Bound for Stochastic NC-SC Bilevel Optimization with First-order Oracles
- Optimal Stochastic Bilevel Optimization with First-Order Oracles
- When is a better LLM worth paying for? Stochastic Optimization with Switching Mixed-Fidelity Oracles
- On the Complexity of Finding Stationary Points in Stochastic (L0, L1)-Smooth Nonconvex Optimization
- Random Reshuffling for Smooth Convex Optimization: Dominates Stochastic Gradient Descent
BibTeX
@misc{berahas2026stochastic,
title = {{Stochastic and Noisy Oracles in Smooth Continuous Optimization}},
author = {Albert S. Berahas and Liyuan Cao and Katya Scheinberg},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.41086},
eprint = {2610.41086},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.41086},
}
RIS
TY - UNPB
TI - Stochastic and Noisy Oracles in Smooth Continuous Optimization
AU - Albert S. Berahas
AU - Liyuan Cao
AU - Katya Scheinberg
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.41086
UR - https://arxiv.org/abs/2610.41086
AB - We review models of inexact computational oracles in smooth continuous optimization and their implications for the convergence, computational complexity, and attainable accuracy of optimization algorithms. We adopt a framework in which zeroth-,first-, and second-order oracles are characterized by quantitative error bounds and may accept additional control parameters that influence both their accuracy and computational cost. We introduce deterministic and stochastic oracle models and illustrate their properties through a variety of examples, including finite-difference approximations, stochastic gradients, and randomized derivative estimators. Particular attention is given to the distinction between absolute and relative errors, bias and variance, and stochastic function evaluations with independent or coupled randomness. A central theme of the review is the use of common analytical tools to recover and compare convergence and complexity guarantees under different oracle models. For deterministic and stochastic first-order methods, we show how a general descent inequality leads to complexity bounds under various assumptions on the objective function and all proposed oracle models. In the stochastic setting, we develop bounds on expected stopping times and the accuracy that can be guaranteed under different oracle conditions. We also examine the total computational complexity of algorithms relying on specific oracle constructions and briefly review models of inexact second- order information and their use in optimization algorithms.
ER -