Lower Bounds for Linear-Oracle Online Learning
Abstract
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.
Related
- Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets
- Feature Priming in Online Linear Regression: Sparse-Regret Lower Bounds and Tight Coordinatewise Rates
- An Ω(T3/4) lower bound for projection-free online learning with linear minimization oracles
- A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model
- Oracle-Efficient and Parameter-Free Agnostic Smoothed Online Learning
BibTeX
@misc{sinha2026lower,
title = {{Lower Bounds for Linear-Oracle Online Learning}},
author = {Mohit Sinha},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.38375},
eprint = {2609.38375},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.38375},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Lower Bounds for Linear-Oracle Online Learning
AU - Mohit Sinha
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.38375
UR - https://arxiv.org/abs/2609.38375
AB - Can a constant number of linear minimizations per round improve on the T^3/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/4T^3/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 3LDT^3/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.
ER -