math.OCOct 29, 2026

Stochastic and Noisy Oracles in Smooth Continuous Optimization

Authors: Albert S. Berahas, Liyuan Cao, Katya Scheinberg

Organizations: Department of Industrial and Operations Engineering, University of Michigan. · School of Mathematics, Nanjing University. · School of Industrial and Systems Engineering, Georgia Institute of Technology.

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.

Figures & tables

Appendix figures & tables18 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Wall-Clock Complexity for Zeroth-Order Optimization with Tunable Oracle Fidelity

    May 29, 2026Alexandra Suvorikova, Igor Pavlov, Artem Vasin +4Stochastic OptimizationOracle Complexity

  2. Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization

    Oct 1, 2026Jiayi Song, Zi XuMin-Max Optimization