We present an oracle-optimal method for finite-sum monotone inclusions under mean-square Lipschitz continuity. Our switching regularization method finds a point y and a certificate g∈G(y) with (E∥F(y)+g∥2)1/2≤ε using O(n+nLR/ε) expected component evaluations and resolvent evaluations. It removes the additive nlogn cost of restarting a variance-reduced solver at every regularization stage by switching to a centered stochastic proximal iteration at regularization strength L/n. Carrying an operator estimate between the remaining stages limits their total cost to O(n). A matching Ω(n+nLR/ε) lower bound holds for randomized linear-span component-oracle algorithms with adaptive stopping and expected query budgets. Thus, for 0<ε≤LR/2, our method attains the optimal worst-case expected component complexity in this oracle model, up to universal constants.
We study nonconvex--strongly-convex bilevel optimization under a stochastic first-order oracle. We introduce MRT-FD, a single-loop first-order method that simultaneously tracks the upper-level variable, the lower-level solution, and the auxiliary response arising from implicit differentiation of the hyperobjective. MRT-FD performs one update of each variable per iteration and approximates the second-order derivative actions using order-p finite differences. For any fixed finite smoothness order p≥1 in the lower-level variable, MRT-FD finds an ε-stationary point using O(ε−4−2/p) stochastic gradient queries. We also prove a matching Ω(ε−4−2/p) oracle lower bound. The lower-bound construction starts from a hard nonconvex minimization chain with a stronger stochastic oracle, and lifts it to a bilevel problem through a sinusoidal coupling with a scalar lower-level variable. Consequently, the dependence on ε is optimal for every fixed finite p, closing the upper--lower complexity gap in this stochastic first-order oracle setting.
Optimistic matrix mirror-prox (OMMP) computes ε-approximate Nash equilibria in quantum zero-sum games with an O(1/ε) average-iterate guarantee [arXiv:2311.10859]. We investigate whether this dependence on accuracy is tight and whether geometric last-iterate convergence can be guaranteed. We study these questions through explicit games with one qubit per player. First, we prove an Ω(1/ε) lower bound for the uniform-average output that includes the maximally mixed initial state, independently of the regularizer and step size. Second, we construct a fixed game on which optimistic gradient descent-ascent (OGDA), initialized at the maximally mixed state, has last-iterate Frobenius distance to equilibrium Θ(1/t) and duality gap Θ(1/t3) for every sufficiently small fixed step size. A separate fixed game exhibits arbitrarily long delays in reducing the initial error by a constant factor across a family of initial states. Finally, we give a fixed game with a unique, strictly complementary equilibrium on which optimistic matrix multiplicative weights updates (OMMWU) converge only polynomially from the maximally mixed state for every fixed positive step size. The last-iterate Frobenius distance and quantum relative entropy from the equilibrium to the iterates decay as Θ(1/t), while the duality gap decays as Θ(1/t2).
Yiheng Su, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Pucheng Xiong
Department of Computer Sciences, University of Wisconsin-Madison
We prove nearly quadratic lower bounds for randomized algorithms for linear optimization and uniform sampling over convex bodies in the membership oracle model. For linear optimization, this matches the known nearly quadratic upper bound up to a polylog factor in the dimension. For uniform sampling, this improves on the previous linear lower bound. Our construction also implies the same lower bound for volume estimation.
We study the deterministic oracle complexity of finding approximate solutions to composite monotone inclusion problems, formed by the sum of a smooth single-valued monotone operator and a maximally monotone set-valued operator, under the tangent-residual criterion. We introduce the Anchored Extra-Proximal (AEP) framework, which combines an anchored extrapolation step with an inexact anchored proximal update satisfying a relative-error condition. The framework recovers the composite Fast Extragradient method in the first-order setting and yields natural second- and higher-order extensions by replacing the operator in the implicit update with its Taylor approximation at the extrapolated point. For every p≥2, assuming that the (p−1)th derivative of the single-valued operator is Lipschitz continuous, we combine this construction with a bisection line search to obtain a pth-order method that finds a point with tangent residual at most ε in O(ε−2/(3p−1)) oracle calls. This improves all prior upper bounds for pth-order methods: in particular, it improves the previous best-known O(ε−1/p) tangent-residual complexity as well as the classical O(ε−2/(p+1)) bound of higher-order hybrid proximal extragradient methods under the weaker duality-gap criterion. We complement this result with a worst-case lower bound of Ω(ε−2/(3p−1)) for every deterministic algorithm in the pth-order oracle model, without restricting the algorithm to tensor steps or any other prescribed update structure. Thus, the proposed method attains the optimal dependence on ε, up to logarithmic factors, for all p≥2.
We consider a standard convex composite optimization problem with either smooth or nonsmooth objective function, and under quadratic growth. In recent years, several works gave algorithms based on a \textit{weak proximal oracle} (WPO) that essentially match in oracle complexities proximal (sub)gradient methods relying on exact prox operations. Importantly, such WPOs, which relax the strong optimality condition of the standard prox operator, may admit much more efficient implementation in terms of runtime when optimal solutions have some sparse structure. A question remained if such WPO-based methods can be accelerated (in the sense of Nesterov's accelerated gradient). In this work we provide a negative answer by establishing lower bounds against both deterministic and randomized methods. Thus, while WPOs can substantially reduce the cost of individual oracle calls, this comes with an inherent loss in oracle complexity. We also provide a new upper-bound for WPO-based nonsmooth convex composite optimization, nearly matching the proximal subgradient method.
Dan Garber
Faculty of Data and Decision Sciences Technion - Israel Institute of Technology
We study the complexity of finding (δ,ε)-Goldstein stationary points of nonsmooth nonconvex Lipschitz functions. By now, it is known that randomized first-order algorithms can solve this task with a dimension-free oracle complexity [Zhang et al., 2020], whereas deterministic algorithms cannot, as their complexity must scale at least linearly with the dimension d [Jordan et al., 2023, Tian and So, 2024]. This leaves open whether deterministic algorithms can nevertheless solve the problem with oracle complexity polynomial in d. We answer this question negatively by proving a lower bound of order (1/ε)Ω(d) for deterministic algorithm, closing the exponential gap between the previously known lower and upper bounds and resolving an open problem posed by Jordan et al. [2023]. We further discuss several extensions and implications of this result to weaker stationarity notions, finding a descent direction and deterministic smoothing. Overall, our results establish an exponential computational advantage in nonsmooth nonconvex optimization offered by randomization.
Attias, Hanneke and Ramaswami (NeurIPS 2025) asked whether randomization provably reduces the oracle calls needed for online learning when the class is accessible only through an oracle. We study the instance they singled out: transductive online learning of thresholds on an unknown total order of T instances, with a consistency-type ERM oracle that returns a full concept consistent with a queried labeled set (or reports non-realizability). Our main result is a separation for a fixed natural oracle. When the oracle is the minimal-prefix rule (or the maximal-prefix rule), every deterministic learner makes M mistakes and Q calls with M+Q≥T−ε on some instance (ε∈{0,1}, according to whether the empty prefix is a concept), and the constant is exact; hence O(logT) mistakes cost T−ε−O(logT) calls, whereas that paper's randomized learner achieves O(logT) expected calls and mistakes under the same rule. The randomized order is optimal: on an explicit hard distribution under the minimal-prefix rule, every learner has expected mistakes at least ((T+1−ε)128−E[Q]−1)/2, so Ω(logT) expected calls are necessary for polylogarithmic mistakes. The separation is governed by the oracle's selection rule, not by the class alone: for a legal feasible-median ERM rule a deterministic learner achieves O(logT) calls and mistakes, while a global-median rule again forces linear total cost. The same linear bound holds when the oracle's answers are chosen adversarially and then frozen into a memoryless oracle. We add partial tradeoff results for fixed query budgets (the middle regime is open) and an interface contrast: with only a weak consistency oracle, returning a realizability bit, both deterministic and randomized learners need Θ(T) calls.
We study the oracle complexity of computing a point with small fixed-point residual ∥T(x)−x∥≤ε, for a general norm ∥⋅∥ and a self-map T of a compact convex set. We study this problem in the setting where T is nonexpansive with respect to the same norm ∥⋅∥ and accessed via an unbiased stochastic oracle with bounded variance σ2. We provide an algorithm that solves such instances for any norm with a weak Rademacher type q>1, with high probability. The algorithm is based on a recursive anchoring technique. For type-2 spaces, such as ℓp-spaces for p∈[2,∞], our algorithm attains stochastic oracle complexity O~(σ2ε−3+ε−1). We further prove a near-matching lower bound (i.e., matching up to poly-log factors) for such ℓ∞-norm instances in high dimensions. Our lower bound holds against any randomized algorithm that succeeds with constant probability. It further extends to settings with ``sparse'' noise, where variance measured with respect to any ℓp norm is of the same order, ruling out the possibility of improving oracle complexity as a function of ε by measuring variance in a non-matching ℓp norm.
Jelena Diakonikolas, Cristóbal Guzmán, David Martínez-Rubio
Department of Computer Sciences, University of Wisconsin-Madison · Institute for Mathematical and Computational Engineering, Faculty of Mathematics and School of Engineering, Pontificia Universidad Católica de Chile, Santiago, Chile · IMDEA Software Institute, Madrid, Spain
We prove two lower bounds for the first order oracle complexity of minimizing a d-dimensional 1-Lipschitz convex function over the unit ball with m bits of memory. We first show that any such (possibly randomized) algorithm must make Ω~(md2) oracle queries. For deterministic optimization algorithms, we show that Ω~(min{d1.6,m2/3d8/3}) queries are required. For all memory regimes of interest, these improves upon the previous best known lower bounds of Ω~(max{m4/3d8/3,m1/6d4/3}) and Ω~(m1/3d5/3) for randomized and deterministic algorithms respectively. Notably, due to existing upper bounds, our lower bound for deterministic algorithms is the first to show a sharp oracle complexity phase transition around m≈d2, where a polylogarithmic change in memory leads to a poly(d) change in the number of required oracle calls. Further, when the suboptimality is polynomially small in d, our lower bound randomized algorithms is the first to show that Ω~(d2) memory is necessary to nearly match the optimal query complexity among algorithms without memory constraints. Previously, such a result was only known for the regime where the suboptimality is quasipolynomially small in d.
Michael Menart, Aleksandar Nikolov, Ohad Shamir
Department of Computer Science, University of Toronto, Vector Institute · Department of Computer Science, University of Toronto · Weizmann Institute of Science and University of Toronto +1
The Stochastic-Oracle Turing Machine (SOTM) framework models AI-augmented computation as the interaction of a probabilistic Turing machine with an oracle whose responses are drawn from context-dependent distributions. This paper studies what an SOTM can achieve under two oracle-response schemes: in a cached-response oracle, each distinct query receives one response that is reused on later calls to the same query, while in a fresh-response oracle, each call returns an independent response. In both schemes, the SOTM first computes from its input and internal random source to generate its first query, then proceeds adaptively, computing from its query-response transcript (the record of queries issued and responses received) to generate each subsequent query or produce a final output. Cached responses impose two transcript-based ceilings on achievable performance: a correct-identification ceiling governed by the total variation distance between the transcript distributions induced by the hidden states of the oracle, and an output quality ceiling equal to the expected score of the best output the SOTM can compute from the transcript. Fresh responses can raise these ceilings by allowing repeated calls to accumulate independent evidence toward correct or high-quality outputs. In the binary single-informative-query case, the error probability decreases exponentially in the number of calls to the same query at the Chernoff rate. For output quality, query-count bounds characterize threshold stopping when the score function is incorporated as part of the SOTM, and majority-based amplification bounds characterize the binary candidate-output model when it is not. Together, the results identify how response reuse, transcript information, and access to the score function determine what an SOTM can compute and at what token cost.
Jie Wang
Richard A. Miner School of Computing and Information Sciences, University of Massachusetts, Lowell, MA 01854, USA.
The John ellipsoid of a symmetric polytope P={x∈Rd:∥Ax∥∞≤1}, A∈Rn×d, is computed by a long line of leverage-score algorithms, from Cohen, Cousins, Lee and Yang (COLT 2019) to its successors [WY24, CLS+25], all reaching a (1+ε)-approximation in Θ(ε−1log(n/d)) iterations. We separate this complexity into three costs the modern line conflates (certification, identification, and accuracy) and locate the historical ε−1 in the first alone. In the equivalent D-optimal-design form minp∈Δn−logdet(∑ipiaiai⊤), the leverage-score oracle is exactly the first-order oracle and the (1+ε)-John guarantee the Frank-Wolfe gap g(p)≤εd; through this dictionary the costs come apart. The ε−1 is a certification artifact: the uniform average of the iterates, the certificate used throughout the line, has gap exactly Θ(1/T), however cheap each iteration is made. Pointed instead at the last iterate the same oracle is fast: a warm-started accelerated method reaches the guarantee in C(A)+O(κlog(1/ε)) queries after an ε-independent setup C(A), and once the optimal face is identified the facial problem is an unconstrained self-concordant minimization whose Hessian the oracle recovers exactly, so damped Newton needs only O(loglog(1/ε)) steps, for a total of C(A)+O(d2loglog(1/ε)) queries. The accuracy dependence is thus doubly logarithmic after an ε-independent, condition-dependent setup; the open problem is the remaining identification cost (a condition-free bound on reaching the optimal face) and lower bounds. Accuracy is not the obstruction.
Xiaoyu Li, Junwei Yu, Jiaojiao Jiang +2
University of New South Wales · University of California, Berkeley · University of Sydney
Recent work on first-order optimizers for empirical risk minimization (ERM) has suggested that smoothness of ERM loss functions in the training data, rather than in the optimization parameters, can be leveraged to improve the oracle complexity of gradient descent (GD) methods. In this paper, we propose an inexact gradient method, piecewise polynomial interpolation-based gradient descent (PPI-GD), which approximates the full gradient in each iteration by querying the first-order oracle at equidistant points in the data domain to construct polynomial interpolants of the resulting gradient samples over appropriately sized patches of the data domain. We analyze the oracle complexity of PPI-GD for strongly convex and non-convex loss functions when the data space dimension is bounded by a polylogarithmic function of the number of training samples, and find it to outperform several GD variants in key regimes when the loss function is sufficiently smooth. Furthermore, our analysis extends several techniques from the error analysis of bicubic spline interpolants to the setting of d-variate tensor product polynomial interpolants which may be of independent interest in interpolation analysis.
Dongmin Lee, William Lu, Anuran Makur
Department of Computer Science, Purdue University, West Lafayette, IN 47907, USA · Department of Computer Science and the Elmore Family School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN 47907, USA
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(δ), and we minimize the total time Ttotal=∑k=1Nc(δ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.
Alexandra Suvorikova, Igor Pavlov, Artem Vasin +4
Weierstrass Institute for Applied Analysis and Stochastics, Berlin, Germany · Moscow Independent Research Institute of Artificial Intelligence, Moscow, Russia · MSU Institute for Artificial Intelligence, Moscow, Russia +3
We study the query complexity of obtaining a relative Fisher information guarantee for sampling from a log-smooth non-log-concave distribution; this is a sampling analog of finding an approximate stationary point in optimization. Our algorithm is based on the proximal sampler, which is an implicit discretization of the Langevin diffusion, and requires an implementation of the backward step known as the restricted Gaussian oracle (RGO). We show that by leveraging the recent results for log-concave sampling with high-accuracy guarantees in Rényi divergence, we can obtain an approximate RGO implementation that -- when used with the proximal sampler -- yields a complexity guarantee in relative Fisher information that inherits the same dimension dependence as log-concave sampling, and improves upon prior work for non-log-concave sampling. We also show a converse reduction that any improvement in the dimension dependence in relative Fisher information for non-log-concave sampling will yield an improved dimension dependence for high-accuracy log-concave sampling.
Sinho Chewi, Andre Wibisono
Yale University, Department of Statistics and Data Science. · Yale University, Department of Computer Science.
We study the query complexity of min-max optimization of a nonconvex-nonconcave function f over [0,1]d×[0,1]d. We show that, given oracle access to f and to its gradient ∇f, any algorithm that finds an ε-approximate stationary point must make a number of queries that is exponential in 1/ε or d.
Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1
Bocconi University · Politecnico di Milano · University of Oxford
Agnostic online learning is classically solved via a reduction to the realizable setting, utilizing Littlestone's Standard Optimal Algorithm (SOA) as a base learner. However, the SOA is computationally intractable to execute even for a single round. To overcome this barrier, recent work in oracle-efficient online learning replaces the SOA with a realizable base learner that accesses the concept class exclusively through an offline empirical risk minimization (ERM) oracle. While such agnostic learners achieve near-optimal expected regret, they suffer from a doubly-exponential oracle complexity of O(T2O(dLD)), where dLD is the Littlestone dimension and T is the number of rounds. In this work, we significantly improve this oracle complexity while relying on an even weaker primitive: a weak-consistency oracle, which merely decides whether a given labeled dataset is realizable. At the core of our approach is an adaptive and dynamic agnostic-to-realizable reduction that actively prunes non-realizable label sequences on the fly. By using the VC dimension (dVC) to bound the number of dynamically maintained active paths, our algorithm reduces the total query complexity down to O(TdVC+1) while perfectly preserving near-optimal expected regret. Crucially, this dynamic pruning also yields a memory reduction over the standard reduction. Furthermore, we formally quantify the regret--oracle complexity tradeoff, providing upper bounds that smoothly interpolate between restricted query budgets and attainable expected regret. We complement these with lower bounds proving that any learner restricted to Q=o(T) queries must suffer an expected regret of Ω(T/Q).
Idan Attias, Steve Hanneke, Arvind Ramaswami
Institute for Data, Econometrics, Algorithms, and Learning (IDEAL), hosted by UIC and TTIC · Department of Computer Science, Purdue University
The standard oracle model for matroid algorithms assumes that each independence query can be answered in constant time, regardless of the size of the queried set. While this abstraction has underpinned much of the theoretical progress in matroid optimization, it masks the true computational effort required by these algorithms. In particular, for natural and widely studied classes such as graphic matroids, even a single independence query can require work linear in the size of the set, making the constant-time assumption implausible. We address this gap by introducing a size-sensitive cost model where the cost of a query Q scales with ∣Q∣. Nearly linear-time oracle implementations exist for broad families of matroids, and this refined abstraction therefore captures the true cost of query evaluation while allowing for a more faithful comparison between general matroids and their natural special cases. Within this framework we study three fundamental algorithmic tasks: finding a basis of a matroid, approximating its rank, and approximating its partition size. We establish tight results, proving nearly matching upper and lower bounds that show the optimal query cost is (up to logarithmic factors) quadratic in the size of the matroid. On the algorithmic side, our upper bounds are realized by explicit procedures that construct the desired solution. On the complexity side, our lower bounds are unconditional and already hold even for weaker distinguishing formulations of the problems. Finally, for matroids with maximum circuit size at most c, we show that the quadratic barrier can be broken, providing an algorithm that calculates the maximum-weight basis with expected query cost O(n2−1/clogn).
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{α2d,log(1/α)d}) is necessary to achieve α excess risk on problems of dimension d when d≥1/α2. Upper bounds via DP-SGD show these results are tight when d>Ω~(1/α4). We further show our lower bound can be strengthened to Ω(min{mˉα2d,log(1/α)d}) for algorithms which use minibatches of size at most mˉ<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{α21,n}), where n 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{α2Γd,log(1/α)d}) oracle calls are needed. This result shows fundamental limitations of gradient quantization techniques in optimization.
Michael Menart, Aleksandar Nikolov
Department of Computer Science, University of Toronto, Vector Institute · Department of Computer Science, University of Toronto