An Exponential Deterministic--Randomized Gap in ERM-Oracle Complexity for Thresholds on an Unknown Order

Xuan Li

cs.LGSep 9, 2026

An Exponential Deterministic--Randomized Gap in ERM-Oracle Complexity for Thresholds on an Unknown Order

Authors: Xuan Li

Abstract

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\ge T-\varepsilon$ on some instance ( $\varepsilon\in\{0,1\}$ , according to whether the empty prefix is a concept), and the constant is exact; hence $O(\log T)$ mistakes cost $T-\varepsilon-O(\log T)$ calls, whereas that paper's randomized learner achieves $O(\log T)$ 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-\varepsilon)\,128^{-\mathbb{E}[Q]}-1)/2$ , so $Ω(\log T)$ 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(\log T)$ 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.

Explore similar work

May 8, 2026cs.LG

Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning

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\big(T^{2^{O(d_\mathrm{LD})}}\big)

, where

d_\mathrm{LD}

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 (

d_\mathrm{VC}

) to bound the number of dynamically maintained active paths, our algorithm reduces the total query complexity down to

O(T^{d_\mathrm{VC}+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(\sqrt{T})

queries must suffer an expected regret of

Ω(T/Q)

Idan Attias, Steve Hanneke, Arvind Ramaswami

Learning-Augmented Algorithms Regret

Ask PDF

Nov 17, 2025cs.LG

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\{\frac{\sqrt{d}}{α^2}, \frac{d}{\log(1/α)}\})

is necessary to achieve

α

excess risk on problems of dimension

d

when

d \geq 1/α^2

. Upper bounds via DP-SGD show these results are tight when

d>\tildeΩ(1/α^4)

. We further show our lower bound can be strengthened to

Ω(\min\{\frac{d}{\bar{m}α^2}, \frac{d}{\log(1/α)} \})

for algorithms which use minibatches of size at most

\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

\tildeΩ\big(\frac{\sqrt{d}}α + \min\{\frac{1}{α^2}, n\}\big)

, 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

Ω\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.

Michael Menart, Aleksandar Nikolov

Differential Privacy Stochastic Gradient Descent Gradient Concentration Optimizer Design Oracles Prompt Optimization

Ask PDF

Jul 21, 2026cs.DS

Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory

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

\tildeΩ(\frac{d^2}{\sqrt{m}})

oracle queries. For deterministic optimization algorithms, we show that

\tildeΩ(\min\{d^{1.6},\frac{d^{8/3}}{m^{2/3}}\})

queries are required. For all memory regimes of interest, these improves upon the previous best known lower bounds of

\tildeΩ(\max\{\frac{d^{8/3}}{m^{4/3}},\frac{d^{4/3}}{m^{1/6}}\})

and

\tildeΩ(\frac{d^{5/3}}{m^{1/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\approx d^2

, where a polylogarithmic change in memory leads to a

\mathsf{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

\tildeΩ(d^2)

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

Convex Optimization Lower Bounds

Ask PDF