cs.LGstat.ML

Oracle-Efficient Online Classification with Stochastic Inputs and Adversarial Outputs

📅 👥 2 authors arXiv:2609.33760v1

Authors

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.

Paper Information

arXiv ID:
2609.33760v1
Published:

Related Categories

cs.LGstat.ML