Overview

Oracle complexity measures the number of calls an algorithm needs when it can access a problem only through responses such as gradients, stochastic samples, membership answers, or proximal updates. Researchers develop algorithms and matching lower bounds for settings including convex and nonconvex optimization, online learning, monotone inclusions, and sampling, using methods such as variance reduction, proximal iterations, and higher-order updates. A central finding is that query costs depend not only on accuracy and dimension, but also on randomness, memory, oracle fidelity, and the cost or strength of each response. For many settings upper and lower bounds now match, while gaps remain across oracle models and regimes, including how to trade query budgets against wall-clock cost or memory.

Latest papers

35 papers4 papers in the last four weeks, down 67% on the four weeks before. 0.0% of all new papers.

Apr 17, 2026

Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance

Analysis of Stochastic Gradient Descent (SGD) and its variants typically relies on the assumption of uniformly bounded variance, a condition that frequently fails in practical non-convex settings, such as neural network training, as well as in several elementary optimization settings. While several relaxations are explored in the literature, the Blum-Gladyshev (BG-0) condition, which permits the variance to grow quadratically with distance has recently been shown to be the weakest condition. However, the study of the oracle complexity of stochastic first-order non-convex optimization under BG-0 has remained underexplored. In this paper, we address this gap and establish information-theoretic lower bounds, proving that finding an εε-stationary point requires Ω(ε−6)Ω(ε^{-6}) stochastic BG-0 oracle queries for smooth functions and Ω(ε−4)Ω(ε^{-4}) queries under mean-square smoothness. These limits demonstrate an unavoidable degradation from classical bounded-variance complexities, i.e., Ω(ε−4)Ω(ε^{-4}) and Ω(ε−3)Ω(ε^{-3}) for smooth and mean-square smooth cases, respectively. To match these lower bounds, we consider Proximally Anchored STochastic Approximation (PASTA), a unified algorithmic framework that couples Halpern anchoring with Tikhonov regularization to dynamically mitigate the extra variance explosion term permitted by the BG-0 oracle. We prove that PASTA achieves minimax optimal complexities across numerous non-convex regimes, including standard smooth, mean-square smooth, weakly convex, star-convex, and Polyak-Lojasiewicz functions, entirely under an unbounded domain and unbounded stochastic gradients.
Apr 12, 2026

Turing or Cantor: That is the Question

Alan Turing is considered as a founder of current computer science together with Kurt Godel, Alonzo Church and John von Neumann. In this paper multiple new research results are presented. It is demonstrated that there would not be Alan Turing's achievements without earlier seminal contributions by Georg Cantor in the set theory and foundations of mathematics. It is proposed to introduce the measure of undecidability of problems unsolvable by Turing machines based on probability distribution of its input data, i.e., to provide the degree of unsolvabilty based on the number of undecidable instances of input data versus decidable ones. It is proposed as well to extend the Turing's work on infinite logics and Oracle machines to a whole class of super-Turing models of computation. Next, the three new complexity classes for TM undecidable problems have been defined: U-complete (Universal complete), D-complete (Diagonalization complete) and H-complete (Hypercomputation complete) classes. The above has never been defined explicitly before by other scientists, and has been inspired by Cook/Levin NP-complete class for intractable problems. Finally, an equivalent to famous P is not equal to NP unanswered question for NP-complete class, has been answered negatively for U-complete class of complexity for undecidable problems.
Mar 2, 2026

Mini-Batch Covariance, Diffusion Limits, and Oracle Complexity in Stochastic Gradient Descent: A Sampling-Design Perspective

Stochastic gradient descent (SGD) is central to simulation optimization, stochastic programming, and online M-estimation, where sampling effort is a decision variable. We study the mini-batch gradient noise as a sampling-design object. Under exchangeable fresh-sampling mini-batches, the conditional covariance given the de Finetti directing measure mu is b^{-1} G_mu(theta), and under identifiability the projected population object is b^{-1} G*(theta) -- projected Fisher information for correctly specified likelihoods, the sandwich partner of the Hessian otherwise. This identification fixes the noise matrix entering the diffusion analysis of constant-step SGD: the raw iterate path has a deterministic fluid limit, and the sqrt(b/eta)-scaled fluctuations satisfy a functional CLT with noise covariance G*; near a nondegenerate optimum the limit is Ornstein-Uhlenbeck, and its Lyapunov covariance scaled by eta/b matches the linearized discrete recursion at leading order. Under a curvature-noise compatibility condition mu_F > 0, we prove 1/N mean-square upper bounds and an i.i.d. parametric Fisher van Trees lower bound of the same rate order, with oracle-complexity guarantees depending on an effective dimension d_eff and condition number kappa_F. Numerical experiments verify the identification and confirm the Lyapunov predictions in direct SGD.
Nov 27, 2025

On the Condition Number Dependency in Bilevel Optimization

Bilevel optimization minimizes an objective function, defined by an upper-level problem whose feasible region is the solution of a lower-level problem. We study the oracle complexity of finding an εε-stationary point with first-order methods when the upper-level problem is nonconvex, and the lower-level problem is strongly convex. Recent works (Ji et al., ICML 2021; Arbel and Mairal, ICLR 2022; Chen et al., JMLR 2025) achieve a O~(κˉy4ε−2)\tilde{\mathcal{O}}(\bar κ_y^4 ε^{-2}) upper bound that is near-optimal in εε, which can be reduced to O~(κˉy7/2ε−2)\tilde{\mathcal{O}}(\bar κ_y^{7/2} ε^{-2}) by a naive application of Nesterov acceleration in the inner loop, where κˉy\bar κ_y is the global condition number. However, the optimal dependency on the condition number is unknown. In this work, we establish a new Ω(κy5/2ε−2)Ω(κ_y^{5/2} ε^{-2}) lower bound, where κy<κˉyκ_y < \bar κ_y is the lower-level condition number that is of the same order as κˉy\bar κ_y when the smoothness constants are O(1)\mathcal{O}(1). Our lower bound establishes the first provable gap in terms of condition number dependency between bilevel problems and minimax problems in this setup. Our lower bounds can be extended to various settings, including high-order smooth functions, stochastic oracles, and convex hyper-objectives: (1) For second-order and arbitrarily smooth problems, we show lower bounds of Ω(κy31/14ε−12/7)Ω({κ_y^{31/14}} ε^{-12/7}) and Ω(κy21/10ε−8/5)Ω(κ_y^{21/10} ε^{-8/5}), respectively. (2) For convex-strongly-convex problems, we improve the previously best lower bound (Ji and Liang, JMLR 2022) from Ω(κy/ε)Ω(κ_y /\sqrtε) to Ω(κy3/2/ε)Ω(κ_y^{3/2} / \sqrtε). (3) For smooth stochastic problems, we also show a lower bound of Ω(κy4ε−4)Ω(κ_y^4 ε^{-4}).
Nov 17, 2025

On the Gradient Complexity of Private Optimization with Private Oracles

We study the running time, in terms of first order oracle queries, of differentially private empirical/population risk minimization of Lipschitz convex losses. We first consider the setting where the loss is non-smooth and the optimizer interacts with a private proxy oracle, which sends only private messages about a minibatch of gradients. In this setting, we show that expected running time Ω(min⁡{dα2,dlog⁡(1/α)})Ω(\min\{\frac{\sqrt{d}}{α^2}, \frac{d}{\log(1/α)}\}) is necessary to achieve αα excess risk on problems of dimension dd when d≥1/α2d \geq 1/α^2. Upper bounds via DP-SGD show these results are tight when d>Ω~(1/α4)d>\tildeΩ(1/α^4). We further show our lower bound can be strengthened to Ω(min⁡{dmˉα2,dlog⁡(1/α)})Ω(\min\{\frac{d}{\bar{m}α^2}, \frac{d}{\log(1/α)} \}) for algorithms which use minibatches of size at most mˉ<d\bar{m} < \sqrt{d}. We next consider smooth losses, where we relax the private oracle assumption and give lower bounds under only the condition that the optimizer is private. Here, we lower bound the expected number of first order oracle calls by Ω~(dα+min⁡{1α2,n})\tildeΩ\big(\frac{\sqrt{d}}α + \min\{\frac{1}{α^2}, n\}\big), where nn is the size of the dataset. Modifications to existing algorithms show this bound is nearly tight. Compared to non-private lower bounds, our results show that differentially private optimizers pay a dimension dependent runtime penalty. Finally, as a natural extension of our proof technique, we show lower bounds in the non-smooth setting for optimizers interacting with information limited oracles. Specifically, if the proxy oracle transmits at most ΓΓ-bits of information about the gradients in the minibatch, then Ω(min⁡{dα2Γ,dlog⁡(1/α)})Ω\big(\min\{\frac{d}{α^2Γ}, \frac{d}{\log(1/α)}\}\big) oracle calls are needed. This result shows fundamental limitations of gradient quantization techniques in optimization.