# Oracle-Efficient Online Classification with Stochastic Inputs and Adversarial Outputs

arXiv: https://arxiv.org/abs/2609.33760 · HTML: https://mlsanity.com/paper/2609.33760/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 57 references that are in the map.
- First posted on arXiv 27 Sep 2026.

## Builds on (most cited first, 23 of 23)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective](https://mlsanity.com/paper/2010.03104/) (2020)
- [A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free](https://mlsanity.com/paper/1902.00980/) (2019)
- [Efficient Contextual Bandits in Non-stationary Worlds](https://mlsanity.com/paper/1708.01799/) (2017)
- [Smoothed Analysis with Adaptive Adversaries](https://mlsanity.com/paper/2102.08446/) (2021)
- [Smoothed Online Learning is as Easy as Statistical Learning](https://mlsanity.com/paper/2202.04690/) (2022)
- [Smoothed Analysis of Online and Differentially Private Learning](https://mlsanity.com/paper/2006.10129/) (2020)
- [The Computational Power of Optimization in Online Learning](https://mlsanity.com/paper/1504.02089/) (2015)
- [Efficient Algorithms for Adversarial Contextual Learning](https://mlsanity.com/paper/1602.02454/) (2016)
- [Oracle-Efficient Online Learning and Auction Design](https://mlsanity.com/paper/1611.01688/) (2016)
- [Learning in Non-convex Games with an Optimization Oracle](https://mlsanity.com/paper/1810.07362/) (2018)
- [BISTRO: An Efficient Relaxation-Based Method for Contextual Bandits](https://mlsanity.com/paper/1602.02196/) (2016)
- [Improved Regret Bounds for Oracle-Based Adversarial Contextual Bandits](https://mlsanity.com/paper/1606.00313/) (2016)
- [On the Performance of Empirical Risk Minimization with Smoothed Data](https://mlsanity.com/paper/2402.14987/) (2024)
- [Expected Worst Case Regret via Stochastic Sequential Covering](https://mlsanity.com/paper/2209.04417/) (2022)
- [A Compression Technique for Analyzing Disagreement-Based Active Learning](https://mlsanity.com/paper/1404.1504/) (2014)
- [Online Improper Learning with an Approximation Oracle](https://mlsanity.com/paper/1804.07837/) (2018)
- [Boosting for Online Convex Optimization](https://mlsanity.com/paper/2102.09305/) (2021)
- [Oracle-Efficient Hybrid Online Learning with Unknown Distribution](https://mlsanity.com/paper/2401.15520/) (2024)
- [Oracle-efficient Hybrid Learning with Constrained Adversaries](https://mlsanity.com/paper/2603.04546/) (2026)
- [An Improved Relaxation for Oracle-Efficient Adversarial Contextual Bandits](https://mlsanity.com/paper/2310.19025/) (2023)
- [Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness](https://mlsanity.com/paper/2602.20585/) (2026)

## Built on by (most cited first, 3 of 3)

- [Oracle-Efficient and Parameter-Free Agnostic Smoothed Online Learning](https://mlsanity.com/paper/2610.10499/) (2026)
- [Sample-Optimal Multi-Group Learning with an ERM Oracle](https://mlsanity.com/paper/2610.15916/) (2026)
- [Follow the Perturbed Leader for Linear Bandits: √T Regret over General Convex Sets](https://mlsanity.com/paper/2610.17818/) (2026)

## Abstract (arXiv)

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 widetilde O(√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 mathcal H, the same algorithm achieves widetilde O(√ToperatornameVC(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. As an application, we reduce the problem of contextual bandits with K actions to classification through uniform exploration, achieving widetilde O(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.