Computational limits found for tracking few experts in convex optimization
Tracking a Small Set of Experts in Online Convex Optimization
Machine Learning
Summary
This paper studies how well an algorithm can follow the advice of a small number of experts when making decisions repeatedly, especially when decisions involve continuous choices. While it is possible in theory to do very well by looking at all possibilities, the authors show that any algorithm that runs efficiently on a computer cannot always achieve the best possible performance. They prove this limitation by connecting it to a famous hard problem in computer science about finding hidden groups in networks. This means there is a fundamental trade-off between how accurately we can track experts and how quickly we can compute.
What this means in practice
- •For online decision system designers: Avoid expecting efficient algorithms to match the ideal tracking error when switching among few continuous-action experts due to inherent computational hardness.
- •For algorithms engineers in continuous control: Recognize that improving regret guarantees for few-expert tracking under continuous actions may require exponential computation or relaxations of problem assumptions.
A theory result. No direct application yet.
Authors
Angelos Assos, Anand Brahmbhatt, Elad Hazan
Abstract
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.