Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning
arXiv:2605.07155v1 Announce Type: new
Abstract: 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 i…