Linear oracle calls cannot beat existing regret rates in online learning
Lower Bounds for Linear-Oracle Online Learning
Machine Learning
Summary
This paper studies how well certain online learning methods can do when they are allowed only a limited number of simple queries (linear minimizations) each step. These methods try to minimize their mistakes over time but often hit a certain speed limit. The authors prove that no method following fixed rules with only a few of these linear queries per step can get better than a known slower rate of learning, measured by something called "regret." They build specific examples that show this limit is real and tight, confirming previous guesses about these algorithms.
What this means in practice
- •For machine learning engineers: Designing online learning systems knowing that using only a few linear oracle calls per step cannot improve worst-case regret beyond known limits.
- •For algorithm designers: Avoiding attempts to improve online convex optimization regret by fixed-coefficient linear oracle methods with limited queries, saving effort on infeasible approaches.
A theory result. No direct application yet.
Authors
Mohit Sinha
Abstract
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/4}LDb^{-1/4}T^{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.