Summary
This paper studies whether guessing randomly can reduce the number of questions an online learner must ask to identify patterns in ordered data. The authors show that if the learner is not allowed to use randomness, it will have to ask almost as many questions as there are data points, even when trying to make very few mistakes. However, if randomness is used intelligently, the learner can make very few mistakes while only asking a small number of questions. This difference depends on exactly how the learning oracle chooses consistent answers, highlighting that the learning process's details impact the value of randomness.
What this means in practice
- •For machine learning engineers: Design online classifiers that use randomness to reduce the number of expensive oracle calls in systems with unknown data order.
- •For data platform architects: Optimize query strategies in systems querying black-box models by selecting effective oracle response rules to minimize total query complexity.
A theory result. No direct application yet.
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.