Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
We investigate the online convex optimization problem of competing with an adversary that selects a small subset of $m$ experts and can switch among them up to $k$ times. While an information-theoretic optimal algorithm exists with $\widetilde{O}(k\sqrt{d})$ regret, we prove that any polynomial-time algorithm suffers at least $(k\sqrt{d})^{1-o(1)}$ regret under the hypergraphic planted-clique conjecture, establishing a separation between achievable regret bounds. This implies that efficient algorithms for this continuous expert problem are fundamentally suboptimal compared to the theoretical best.
Efficiently tracking a small, switching subset of experts in continuous action spaces is provably harder than theoretically possible, with polynomial-time algorithms facing inherent regret limitations.
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 $\widetilde{O}(md+k)$, while the best known efficient algorithm for this problem has regret $\widetilde{O}(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.
DeepMind