An $\Omega (T^{3/4})$ lower bound for projection-free online learning with linear minimization oracles

Julien Weibel, Pierre Gaillard, Wouter Koolen +1

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 we…