SEP 9, 2026 · PREPRINT
An Exponential Deterministic--Randomized Gap in ERM-Oracle Complexity for Thresholds on an Unknown Order
arXiv
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.
Hypothesis-GeneratingXuan Li
Reported
Deterministic lower bound (minima…M + Q ≥ T − ε
Randomized upper bound (minimal-p…O(log T) expected calls and mistakes
Lower bound on expected mistakes…((T+1−ε)·128^(−E[Q])−1)/2