Oracle-Efficient Online Classification with Stochastic Inputs and Adversarial Outputs
Abstract
We consider 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 using a Gaussian perturbation for each observed context achieves Õ(√(Tlog N)) 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 ℋ, the same algorithm achieves Õ(√(TVC(ℋ))) regret. This resolves an open problem posed by Lazaric and Munos (2012), showing that hybrid classification is computationally as easy as statistical learning. As an application, we reduce the problem of contextual bandits with K actions to classification through uniform exploration, achieving Õ(K2/3T2/3(log N)1/3) regret. This matches the best known dependence on the horizon while removing the context-distribution access required by prior oracle-efficient methods.
Related
- Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps
- Adaptivity, Anchoring, and the Exact Oracle Complexity of Stochastic Fixed-Point Iterations
- Oracle-Efficient and Parameter-Free Agnostic Smoothed Online Learning
- Deep operator learning for efficient sampling from invariant measures of stochastic differential equations
- A Unified Efficient Gradient-Based Heuristic For Box-Constrained Expectation-Related and Risk-Averse Stochastic Optimization Problems
BibTeX
@misc{buzaglo2026oracleefficient,
title = {{Oracle-Efficient Online Classification with Stochastic Inputs and Adversarial Outputs}},
author = {Gon Buzaglo and Elad Hazan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.33760},
eprint = {2609.33760},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.33760},
}
RIS
TY - UNPB
TI - Oracle-Efficient Online Classification with Stochastic Inputs and Adversarial Outputs
AU - Gon Buzaglo
AU - Elad Hazan
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2609.33760
UR - https://arxiv.org/abs/2609.33760
AB - We consider 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 using a Gaussian perturbation for each observed context achieves Õ(√(Tlog N)) 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 ℋ, the same algorithm achieves Õ(√(TVC(ℋ))) regret. This resolves an open problem posed by Lazaric and Munos (2012), showing that hybrid classification is computationally as easy as statistical learning. As an application, we reduce the problem of contextual bandits with K actions to classification through uniform exploration, achieving Õ(K^2/3T^2/3(log N)^1/3) regret. This matches the best known dependence on the horizon while removing the context-distribution access required by prior oracle-efficient methods.
ER -