An Ω(T3/4) lower bound for projection-free online learning with linear minimization oracles
Abstract
This work considers projection-free online learning algorithms with linear minimization oracles for handling the decision set. For Online Frank--Wolfe (OFW), regret upper bounds were already known for specific OFW tunings [Hazan and Kale, 2012, Hazan, 2016] which scaled as T3/4 (where T is the horizon length). However, it remained an open question whether the regret of all OFW tunings scaled as T3/4. We answer that question, proving a universal worst-case regret lower bound Ω(T3/4 m−1/4) for any projection-free algorithm that makes at most m linear minimization oracle calls per round. The analysis suggests an extended OFW to resort to multiple linear optimizations per round, for which we prove a regret upper bound O(max { T3/4 m−1/4, √T }).
Related
- Optimizing the Preconditioner: A Black-box Online-to-Nonconvex Conversion with Static Regret Minimization Oracles
- Meta-LinEXP3: Online-within-Online Learning for Adversarial Linear Contextual Bandits
- Lower Bounds for Linear-Oracle Online Learning
- Tensor nuclear norm minimization with linear constraints
- On the Optimal Linear Minimization Oracle Complexity of Active-Hull Methods for Minimizing Convex Hölder Smooth Functions
BibTeX
@misc{weibel2026ωt34,
title = {{An $Ω(T^3/4)$ lower bound for projection-free online learning with linear minimization oracles}},
author = {Julien Weibel and Pierre Gaillard and Wouter Koolen and Adrien Taylor},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.37845},
eprint = {2610.37845},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.37845},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - An Ω(T^3/4) lower bound for projection-free online learning with linear minimization oracles
AU - Julien Weibel
AU - Pierre Gaillard
AU - Wouter Koolen
AU - Adrien Taylor
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2610.37845
UR - https://arxiv.org/abs/2610.37845
AB - This work considers projection-free online learning algorithms with linear minimization oracles for handling the decision set. For Online Frank--Wolfe (OFW), regret upper bounds were already known for specific OFW tunings [Hazan and Kale, 2012, Hazan, 2016] which scaled as T^3/4 (where T is the horizon length). However, it remained an open question whether the regret of all OFW tunings scaled as T^3/4. We answer that question, proving a universal worst-case regret lower bound Ω(T^3/4 m^−1/4) for any projection-free algorithm that makes at most m linear minimization oracle calls per round. The analysis suggests an extended OFW to resort to multiple linear optimizations per round, for which we prove a regret upper bound O(max { T^3/4 m^−1/4, √T }).
ER -