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

May 29, 2026

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

Zeroth-order (black-box) optimization is applied when gradients are unavailable and objective evaluations rely on expensive simulations. In many such applications, the oracle fidelity is tunable: higher-accuracy queries reduce noise but incur higher computational costs. To capture this trade-off, we study an accuracy-aware wall-clock model where each query with fidelity δδ has a cost c(δ)c(δ), and we minimize the total time Ttotal=∑k=1Nc(δk)T_{\mathrm{total}} = \sum_{k=1}^{N} c(δ_k), subject to a target accuracy constraint. We show how the choice of oracle type, noise model, and optimization scheme induces explicit wall-clock-optimal choices for the algorithmic parameters. For instance, we demonstrate that accelerated methods can be wall-clock inferior to non-accelerated schemes. Furthermore, we characterize the conditions under which a constant fidelity strategy is optimal in the Big-O sense. Our framework provides a unified methodology to translate convergence guarantees into practical fidelity and batching recommendations.
Oct 4, 2026

Optimal Oracle Complexity for Finite-Sum Monotone Inclusions

We present an oracle-optimal method for finite-sum monotone inclusions under mean-square Lipschitz continuity. Our switching regularization method finds a point yy and a certificate g∈G(y)g\in G(y) with (E∥F(y)+g∥2)1/2≤ε(\mathbb{E}\|F(y)+g\|^2)^{1/2}\le\varepsilon using O(n+nLR/ε)\mathcal{O}(n+\sqrt{n}LR/\varepsilon) expected component evaluations and resolvent evaluations. It removes the additive nlog⁡nn\log n cost of restarting a variance-reduced solver at every regularization stage by switching to a centered stochastic proximal iteration at regularization strength L/nL/\sqrt{n}. Carrying an operator estimate between the remaining stages limits their total cost to O(n)\mathcal{O}(n). A matching Ω(n+nLR/ε)Ω(n+\sqrt{n}LR/\varepsilon) lower bound holds for randomized linear-span component-oracle algorithms with adaptive stopping and expected query budgets. Thus, for 0<ε≤LR/20<\varepsilon\le LR/2, our method attains the optimal worst-case expected component complexity in this oracle model, up to universal constants.
Oct 1, 2026

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

We establish complexity lower bounds for stochastic first-order algorithms in nonconvex--concave minimax optimization, allowing algorithms to use variance reduction. Our main contribution is a lower bound for a zero-respecting algorithm class that permits variance reduction, extending beyond the algorithmic restrictions imposed by some existing lower bounds. We consider objectives with an LL-Lipschitz continuous joint gradient, a compact convex dual domain of Euclidean radius at most DYD_Y, and a primal value function, defined by maximizing the objective over the dual variable, with initial suboptimality at most ΔΔ. The target accuracy ε\varepsilon is measured by the gradient norm of the Moreau envelope of the constrained primal value function with parameter 1/(2L)1/(2L). Under an unbiased stochastic first-order oracle with variance at most σ2σ^2 and mean-squared smoothness, we prove the lower bound Ω ⁣(L2DYΔε−3+L3DY2Δσ2ε−6)Ω\!\left(L^2D_YΔ\varepsilon^{-3}+L^3D_Y^2Δσ^2\varepsilon^{-6}\right). This result quantifies the dependence on accuracy, dual-domain radius, and oracle noise even when variance reduction is allowed. We also establish complementary lower bounds for nonconvex--strongly-concave minimax optimization. With dual strong-concavity parameter μ>0μ>0 and condition number κ:=L/μκ:=L/μ, we obtain Ω ⁣(LΔκ ε−2+LΔκσ2ε−4)Ω\!\left(LΔ\sqrtκ\,\varepsilon^{-2}+LΔκσ^2\varepsilon^{-4}\right) under the bounded-variance oracle model. Under the additional mean-squared smoothness condition with constant Lˉ\bar L, we obtain Ω ⁣(LΔκ ε−2+ΔLˉσκ3/2ε−3)Ω\!\left(LΔ\sqrtκ\,\varepsilon^{-2}+Δ\bar Lσκ^{3/2}\varepsilon^{-3}\right). Together, these results identify complexity barriers across the concave and strongly concave regimes, with the main nonconvex--concave bound remaining valid for algorithms that use variance reduction.