# Tracking a Small Set of Experts in Online Convex Optimization

arXiv: https://arxiv.org/abs/2610.20416 · HTML: https://mlsanity.com/paper/2610.20416/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 25 references that are in the map.
- First posted on arXiv 14 Oct 2026.

## Builds on (most cited first, 10 of 10)

- [Strongly Adaptive Online Learning](https://mlsanity.com/paper/1502.07073/) (2015)
- [Tensor SVD: Statistical and Computational Limits](https://mlsanity.com/paper/1703.02724/) (2017)
- [Reducibility and Statistical-Computational Gaps from Secret Leakage](https://mlsanity.com/paper/2005.08099/) (2020)
- [Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limits](https://mlsanity.com/paper/2005.10743/) (2020)
- [Efficient tracking of a growing number of experts](https://mlsanity.com/paper/1708.09811/) (2017)
- [Equipping Experts/Bandits with Long-term Memory](https://mlsanity.com/paper/1905.12950/) (2019)
- [Open Problem: Average-Case Hardness of Hypergraphic Planted Clique Detection](https://mlsanity.com/paper/2009.05870/) (2020)
- [Online Convex Optimisation: The Optimal Switching Regret for all Segmentations Simultaneously](https://mlsanity.com/paper/2405.20824/) (2024)
- [Online Multitask Learning with Long-Term Memory](https://mlsanity.com/paper/2008.07055/) (2020)
- [Improved Regret Bounds for Tracking Experts with Memory](https://mlsanity.com/paper/2106.13021/) (2021)

## Abstract (arXiv)

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 widetildeO(md+k), while the best known efficient algorithm for this problem has regret widetildeO(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√ d)1-o(1) regret.