# The Computational Power of Optimization in Online Learning

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Apr 2015.

## Built on by (most cited first, 30 of 39)

- [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)
- [Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization](https://mlsanity.com/paper/2102.11050/) (2021)
- [Oracle Efficient Online Multicalibration and Omniprediction](https://mlsanity.com/paper/2307.08999/) (2023)
- [Oracle-Efficient Online Learning for Beyond Worst-Case Adversaries](https://mlsanity.com/paper/2202.08549/) (2022)
- [Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Bandits](https://mlsanity.com/paper/2309.00814/) (2023)
- [Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games](https://mlsanity.com/paper/2111.08911/) (2021)
- [Online Prediction in Sub-linear Space](https://mlsanity.com/paper/2207.07974/) (2022)
- [Near Optimal Memory-Regret Tradeoff for Online Learning](https://mlsanity.com/paper/2303.01673/) (2023)
- [The Sample Complexity of Approximate Rejection Sampling with Applications to Smoothed Online Learning](https://mlsanity.com/paper/2302.04658/) (2023)
- [On the Performance of Empirical Risk Minimization with Smoothed Data](https://mlsanity.com/paper/2402.14987/) (2024)
- [Boosting for Online Convex Optimization](https://mlsanity.com/paper/2102.09305/) (2021)
- [Online Learning and Solving Infinite Games with an ERM Oracle](https://mlsanity.com/paper/2307.01689/) (2023)
- [Efficient and Near-Optimal Smoothed Online Learning for Generalized Linear Functions](https://mlsanity.com/paper/2205.13056/) (2022)
- [Smoothed Online Learning for Prediction in Piecewise Affine Systems](https://mlsanity.com/paper/2301.11187/) (2023)
- [Group-wise oracle-efficient algorithms for online multi-group learning](https://mlsanity.com/paper/2406.05287/) (2024)
- [Adaptive Oracle-Efficient Online Learning](https://mlsanity.com/paper/2210.09385/) (2022)
- [Playing Large Games with Oracles and AI Debate](https://mlsanity.com/paper/2312.04792/) (2023)
- [Oracle-Efficient Differentially Private Learning with Public Data](https://mlsanity.com/paper/2402.09483/) (2024)
- [Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning](https://mlsanity.com/paper/2404.03774/) (2024)
- [On Efficient Online Imitation Learning via Classification](https://mlsanity.com/paper/2209.12868/) (2022)
- [Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Making](https://mlsanity.com/paper/2302.05430/) (2023)
- [Oracle-efficient Hybrid Learning with Constrained Adversaries](https://mlsanity.com/paper/2603.04546/) (2026)
- [Oracle-Efficient Online Classification with Stochastic Inputs and Adversarial Outputs](https://mlsanity.com/paper/2609.33760/) (2026)
- [Reusing Combinatorial Structure: Faster Iterative Projections over Submodular Base Polytopes](https://mlsanity.com/paper/2106.11943/) (2021)
- [Towards Characterizing the First-order Query Complexity of Learning (Approximate) Nash Equilibria in Zero-sum Matrix Games](https://mlsanity.com/paper/2304.12768/) (2023)
- [An Improved Relaxation for Oracle-Efficient Adversarial Contextual Bandits](https://mlsanity.com/paper/2310.19025/) (2023)
- [Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning](https://mlsanity.com/paper/2506.00135/) (2025)
- [Efficient Online Learning for Dynamic k-Clustering](https://mlsanity.com/paper/2106.04336/) (2021)
- [Learning to Play General-Sum Games Against Multiple Boundedly Rational Agents](https://mlsanity.com/paper/2106.05492/) (2021)

## Abstract (arXiv)

We consider the fundamental problem of prediction with expert advice where the experts are "optimizable": there is a black-box optimization oracle that can be used to compute, in constant time, the leading expert in retrospect at any point in time. In this setting, we give a novel online algorithm that attains vanishing regret with respect to N experts in total widetildeO(√N) computation time. We also give a lower bound showing that this running time cannot be improved (up to log factors) in the oracle model, thereby exhibiting a quadratic speedup as compared to the standard, oracle-free setting where the required time for vanishing regret is widetildeTheta(N). These results demonstrate an exponential gap between the power of optimization in online learning and its power in statistical learning: in the latter, an optimization oracle---i.e., an efficient empirical risk minimizer---allows to learn a finite hypothesis class of size N in time O(logN). We also study the implications of our results to learning in repeated zero-sum games, in a setting where the players have access to oracles that compute, in constant time, their best-response to any mixed strategy of their opponent. We show that the runtime required for approximating the minimax value of the game in this setting is widetildeTheta(√N), yielding again a quadratic improvement upon the oracle-free setting, where widetildeTheta(N) is known to be tight.