The authors consider online convex optimization (OCO) with exp-concave losses on a continuous decision set in d dimensions.
Polynomial-time algorithms face fundamental limits in online convex optimization with switching experts
Under the hypergraphic planted-clique conjecture, the authors show that no efficient algorithm can achieve regret better than roughly k√d for tracking a small set of experts, even when only two distinct experts are used.
Big Tech
Angelos Assos · Anand Brahmbhatt · Elad Hazan
Princeton University · Google DeepMind Princeton
Research Digest··3 min read
Assos et al.
Why this paper
From Google DeepMind Princeton and Princeton University
In one line
Under the hypergraphic planted-clique conjecture, polynomial-time algorithms for online convex optimization incur at least (k sqrt(d))^{1-o(1)} regret when tracking few experts.
What we could check
- ·No code link found
- ·No weights link found
- ·No dataset link found
- ·No compute details found
- ✓Limitations stated by the authors (2 noted)
- ·No benchmark numbers found
Observed from the paper text and links we have. Absence here means we did not find it, not that it does not exist.
§