# Sharp Oracle-Regret Tradeoffs for Projection-Free Online Convex Optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 15 references that are in the map.
- First posted on arXiv 23 Sep 2026.

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

- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [Faster Projection-free Online Learning](https://mlsanity.com/paper/2001.11568/) (2020)
- [Efficient Projection-Free Online Convex Optimization with Membership Oracle](https://mlsanity.com/paper/2111.05818/) (2021)
- [The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle](https://mlsanity.com/paper/1309.5550/) (2013)
- [New Projection-free Algorithms for Online Convex Optimization with Adaptive Regret Guarantees](https://mlsanity.com/paper/2202.04721/) (2022)
- [Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method](https://mlsanity.com/paper/2010.01848/) (2020)
- [Online Convex Optimization with a Separation Oracle](https://mlsanity.com/paper/2410.02476/) (2024)
- [Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization](https://mlsanity.com/paper/2501.18183/) (2025)
- [Optimized projection-free algorithms for online learning: construction and worst-case analysis](https://mlsanity.com/paper/2506.05855/) (2025)

## Abstract (arXiv)

We characterize the regret attainable in online convex optimization when access to the feasible set is limited to an exact linear optimization oracle. The learner is given an inscribed ball and a diameter bound and must remain feasible on every consistent instance. For convex G-Lipschitz losses, diameter at most D, a total allowance of Q oracle calls, and a strict limit of B calls per round, the dimension-free minimax expected regret is Theta(GDmax√ T,T/(1+minQ,BT)1/4). The lower bound applies to arbitrary randomized learners. Universal feasibility first forces each action into the hull of the supplied ball and the preceding oracle replies. A fixed-body construction then couples fresh phase directions to a shared simplex, making useful replies costly repeatedly even though all losses have a common minimizer. A counted approximate-gradient method with interleaved blocks attains the matching rate. Total-budget and strict per-round guarantees follow as special cases, including the T3/4 rate with one call per round and the quadratic total budget needed for √ T regret. For prescribed smoothness β, an analytic construction yields a curvature-dependent lower bound and identifies the threshold above which the general characterization remains sharp.