{"id":"arxiv/2609.38375","url":"https://arxiv.org/abs/2609.38375","tags":["stat.ML","cs.LG","math.OC"],"score":0,"title":"Lower Bounds for Linear-Oracle Online Learning","domain":"stat.ML","source":"arxiv","authors":["Mohit Sinha"],"reviews":0,"subject":"stat.ML","summary":"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…","category":"research","comments":0,"disputed":false,"division":"stat","mentions":0,"discussed":0,"published":"2026-09-29","reactions":{}}