# Lower Bounds for Linear-Oracle Online Learning

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

## Key facts

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

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Faster Projection-free Online Learning](https://mlsanity.com/paper/2001.11568/) (2020)
- [Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methods](https://mlsanity.com/paper/1502.05666/) (2015)
- [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)
- [Revisiting Projection-free Online Learning: the Strongly Convex Case](https://mlsanity.com/paper/2010.07572/) (2020)
- [Projection-free Online Learning over Strongly Convex Sets](https://mlsanity.com/paper/2010.08177/) (2020)
- [Exploiting the Curvature of Feasible Sets for Faster Projection-Free Online Learning](https://mlsanity.com/paper/2205.11470/) (2022)
- [On the Iteration Complexity of Oblivious First-Order Optimization Algorithms](https://mlsanity.com/paper/1605.03529/) (2016)
- [Online Convex Optimization with a Separation Oracle](https://mlsanity.com/paper/2410.02476/) (2024)
- [On the oracle complexity of smooth strongly convex minimization](https://mlsanity.com/paper/2101.09740/) (2021)
- [The exact information-based complexity of smooth convex minimization](https://mlsanity.com/paper/1606.01424/) (2016)
- [Lower Bounds for Frank-Wolfe on Strongly Convex Sets](https://mlsanity.com/paper/2602.04378/) (2026)
- [Lower Bounds for Linear Minimization Oracle Methods Optimizing over Strongly Convex Sets](https://mlsanity.com/paper/2602.22608/) (2026)
- [Optimized projection-free algorithms for online learning: construction and worst-case analysis](https://mlsanity.com/paper/2506.05855/) (2025)
- [Curvature-Dependent Lower Bounds for Frank-Wolfe](https://mlsanity.com/paper/2605.10595/) (2026)

## Abstract (arXiv)

Can a constant number of linear minimizations per round improve on the T3/4 regret rate of online Frank-Wolfe on general convex sets? Weibel et al. conjectured that fixed-coefficient methods cannot. We prove their conjecture and extend the lower bound to every deterministic learner in an oracle-only model. The learner receives an initial feasible point and a diameter bound, and must remain feasible on every domain consistent with its oracle replies. For T rounds, at most b calls between decisions, diameter bound D, and gradient norm bound L, we construct an instance in dimension d=2b(T-1)+1 with regret at least 2-1/4LDb-1/4T3/4. The adversary fixes the domain, initial point, deterministic tie rule and linear losses before play. The vertices form a path on which every point available before a decision has zero current loss, while the final vertex has negative loss on every round. For constant b, the result matches the known upper rate for dimension-independent guarantees. For one-call fixed schedules with a nonzero coefficient on the newest gradient, a second construction gives regret at least 3LDT3/4/4 with unique minimizers at every issued query. Exact-arithmetic certificates for the tuned schedule of Weibel et al. closely match their finite-horizon numerical worst cases, with unique oracle replies.