Oracle-Efficient Online Classification with Stochastic Inputs and Adversarial Outputs

arXiv:2609.33760v1 Announce Type: new 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{Tlog 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{Toperatorname{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.

Source: arXiv cs.LG | 2026-09-29