AI RESEARCH
Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning
arXiv CS.LG
•
ArXi:2605.07155v1 Announce Type: new Agnostic online learning is classically solved via a reduction to the realizable setting, utilizing Littlestone's Standard Optimal Algorithm (SOA) as a base learner. However, the SOA is computationally intractable to execute even for a single round. To overcome this barrier, recent work in oracle-efficient online learning replaces the SOA with a realizable base learner that accesses the concept class exclusively through an offline empirical risk minimization (ERM) oracle.