# Online Improper Learning with an Approximation Oracle

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Apr 2018.

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

- [Multi-Receiver Online Bayesian Persuasion](https://mlsanity.com/paper/2106.06480/) (2021)
- [Boosting for Online Convex Optimization](https://mlsanity.com/paper/2102.09305/) (2021)
- [Minimizing Dynamic Regret on Geodesic Metric Spaces](https://mlsanity.com/paper/2302.08652/) (2023)
- [On Learning Verifiers and Implications to Chain-of-Thought Reasoning](https://mlsanity.com/paper/2505.22650/) (2025)
- [Online nonparametric regression with Sobolev kernels](https://mlsanity.com/paper/2102.03594/) (2021)
- [Simple Combinatorial Algorithms for Combinatorial Bandits: Corruptions and Approximations](https://mlsanity.com/paper/2106.06712/) (2021)
- [Oracle-Efficient Online Classification with Stochastic Inputs and Adversarial Outputs](https://mlsanity.com/paper/2609.33760/) (2026)
- [Efficient Online Learning for Dynamic k-Clustering](https://mlsanity.com/paper/2106.04336/) (2021)
- [Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets](https://mlsanity.com/paper/2107.00472/) (2021)
- [Tight Bounds for γ-Regret via the Decision-Estimation Coefficient](https://mlsanity.com/paper/2303.03327/) (2023)
- [Blackwell's Approachability with Approximation Algorithms](https://mlsanity.com/paper/2502.03919/) (2025)

## Abstract (arXiv)

We revisit the question of reducing online learning to approximate optimization of the offline problem. In this setting, we give two algorithms with near-optimal performance in the full information setting: they guarantee optimal regret and require only poly-logarithmically many calls to the approximation oracle per iteration. Furthermore, these algorithms apply to the more general improper learning problems. In the bandit setting, our algorithm also significantly improves the best previously known oracle complexity while maintaining the same regret.