Algorithm matches best learner performance with fewer computations
Oracle-Efficient Online Classification with Stochastic Inputs and Adversarial Outputs
Machine Learning
Summary
The paper solves a problem in machine learning where data inputs are random but results to learn from can be tricky and changing. The authors show that a simple, efficient algorithm can perform nearly as well as the best possible expert predictions using only limited calculations each time it gets new data. Their method works even when there are infinitely many possible prediction rules, making it as easy to compute as standard learning methods. This answers a long-standing question about how computationally hard it is to learn well in this challenging setting.
What this means in practice
- •For online advertising teams: Improve ad selection systems that receive random user visits but adapt to changing feedback efficiently with limited computation.
- •For recommendation system engineers: Build recommendation engines that can quickly adapt to user feedback appearing in unpredictable ways without exhaustive rule checks.
A theory result. No direct application yet.
Authors
Gon Buzaglo, Elad Hazan
Abstract
We consider contextual binary prediction with i.i.d. contexts from an unknown distribution and adaptively chosen losses. We show that a simple Follow-the-Perturbed-Leader algorithm with Gaussian perturbation for each observed context achieves the optimal $\widetilde O(\sqrt{T\log N})$ expected regret for a class of $N$ experts, while requiring one optimization-oracle call per round and no explicit enumeration of the class. For an infinite hypothesis class $\mathcal H$, the algorithm attains $\widetilde O(\sqrt{T\operatorname{VC}(\mathcal H)})$ regret. This resolves an open problem posed by Lazaric and Munos (2012), showing that hybrid classification is computationally as easy as statistical learning.