
GB
Gon Buzaglo, Elad Hazan
· 1 min read
ResearcharXiv cs.LG
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{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.
Original source
This story was published by arXiv cs.LG and written by Gon Buzaglo, Elad Hazan. SyncAI.news shows a preview; the complete article is on the publisher's site.
Read the full story on arxiv.org


