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

arXiv: https://arxiv.org/abs/2609.10196 · HTML: https://mlsanity.com/paper/2609.10196/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 12 references that are in the map.
- First posted on arXiv 9 Sep 2026.

## Builds on (most cited first, 4 of 4)

- [A Trichotomy for Transductive Online Learning](https://mlsanity.com/paper/2311.06428/) (2023)
- [Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning](https://mlsanity.com/paper/2506.00135/) (2025)
- [Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning](https://mlsanity.com/paper/2605.07155/) (2026)
- [Sorting from Counterexamples](https://mlsanity.com/paper/2608.21579/) (2026)

## Abstract (arXiv)

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-varepsilon on some instance (varepsilon∈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^-mathbbE[Q]-1)/2, so Omega(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 Theta(T) calls.