An Exponential Deterministic--Randomized Gap in ERM-Oracle Complexity for Thresholds on an Unknown Order
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≥ T−ε on some instance (ε∈{0,1}, according to whether the empty prefix is a concept), and the constant is exact; hence O(log T) mistakes cost T−ε−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−ε) 128−𝔼[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.
Related
- Exponential Deterministic Query Complexity of Goldstein Stationarity
- Calibrated Multiaccuracy: Deterministic and Randomized Sample Complexity
- Deletion thresholds and exponential examples for complete sequences
- Weighted Laplacian Flow: A Deterministic Particle Flow with Exponential Convergence
- Greedy sign-based box splitting: exact solvable classes, sharp thresholds and order-oracle complexity
BibTeX
@misc{li2026exponential,
title = {{An Exponential Deterministic--Randomized Gap in ERM-Oracle Complexity for Thresholds on an Unknown Order}},
author = {Xuan Li},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.10196},
eprint = {2609.10196},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.10196},
}
RIS
TY - UNPB
TI - An Exponential Deterministic--Randomized Gap in ERM-Oracle Complexity for Thresholds on an Unknown Order
AU - Xuan Li
PY - 2026
DA - 2026/09/09
PB - arXiv
DO - 10.48550/arxiv.2609.10196
UR - https://arxiv.org/abs/2609.10196
AB - 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(log T) mistakes cost T−ε−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−ε) 128^−𝔼[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.
ER -