Search papers, labs, and topics across Lattice.
Addressing an open problem on the oracle complexity of online learning, this work analyzes transductive learning of thresholds over an unknown total order of $T$ instances given access to an Empirical Risk Minimization (ERM) concept oracle. Resolving the deterministic-versus-randomized query efficiency question is critical for establishing tight computational limits for black-box learning reductions. The authors prove an exponential gap under natural prefix-selection rules, showing deterministic learners require $M+Q \ge T - \varepsilon$ (forcing $\Omega(T)$ calls for $O(\log T)$ mistakes) while randomized learners require merely $O(\log T)$ calls and mistakes, though this separation collapses or persists depending entirely on the oracle's internal tie-breaking rule.
Randomization slashes ERM-oracle query complexity from linear down to logarithmic for online threshold learning, revealing that an oracle's internal tie-breaking rule can single-handedly trigger an exponential computational gap.
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.
