Tracking a Small Set of Experts in Online Convex Optimization

For the fundamental problem of prediction from expert advice, Freund asked whether one could compete with a comparator that switches k times among only m experts. For a discrete set of experts, this problem was resolved by Bousquet and Warmuth (2020), who gave an efficient algorithm with optimal regret matching the information-theoretic limit. We study the analogous problem in online convex optimization, where the action space is continuous. An inefficient algorithm can be derived by discretizing the action space and applying the Bousquet--Warmuth algorithm, giving regret of (md+k), while the best known efficient algorithm for this problem has regret (dk). We show that this computational inefficiency is inherent, establishing a separation between the information-theoretic and polynomial-time regret achievable for this problem. Specifically, under the hypergraphic planted-clique conjecture, we show that for every polynomial-time algorithm there exist instances for which it incurs at least (k sqrt d) 1-o(1) regret.