Loading
Life sciences · Preprint
arXiv · September 9, 2026
Raises a question worth testing. It does not answer one.
This is a theoretical complexity paper establishing a provable separation between deterministic and randomized learners for transductive online threshold learning on unknown total orders. The work shows that randomization can reduce oracle calls exponentially (from linear to logarithmic) for certain oracle designs, but this separation is oracle-dependent and does not address clinical or biomedical applications.
Preprint.
For minimal-prefix and maximal-prefix oracle rules, deterministic learners require M + Q ≥ T − ε on some instance, whereas randomized learners achieve O(log T) expected calls and mistakes On explicit hard distribution under minimal-prefix rule, every learner has expected mistakes at least ((T+1−ε)·128^(−E[Q])−1)/2, requiring Ω(log T) expected calls for polylogarithmic mistakes For feasible-median ERM rule, deterministic learners achieve O(log T) calls and mistakes, avoiding the linear separation
Safety was not reported in the material analysed. Check the source before drawing any conclusion about harm.
The source did not state who this applies to in practice.
This is a theoretical computer science paper establishing complexity separations between deterministic and randomized learners using oracle queries; it advances our understanding of learning theory but does not address a clinical or biomedical question.
Quoted from the source exactly as published.
Graded across the dimensions that decide whether you should act, each from what the source actually supports. There is no single score, and where a dimension was not assessed it says so.
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.
Taken from the source record, never inferred. Follow any of these and new work involving them reaches your briefing.