Sharp Oracle-Regret Tradeoffs for Projection-Free Online Convex Optimization

We characterize the regret attainable in online convex optimization when access to the feasible set is limited to an exact linear optimization oracle. The learner is given an inscribed ball and a diameter bound and must remain feasible on every consistent instance.