papersSEP 10 04:00 UTC
Paper shows exponential deterministic–randomized gap in ERM-oracle complexity for thresholds
A new arXiv preprint addresses a question raised by Attias, Hanneke, and Ramaswami (NeurIPS 2025) about whether randomized learners can provably get by with fewer oracle calls than deterministic ones when a hypothesis class is accessible only through an oracle. Focusing on the instance they singled out, transductive online learning of thresholds over an unknown ordering, the authors establish an exponential separation between deterministic and randomized ERM-oracle complexity, showing randomization can reduce the required number of calls exponentially.