Tracking a Small Set of Experts in Online Convex Optimization
This paper studies online convex optimization against comparators that switch $k$ times among only $m$ distinct points, generalizing the classic experts tracking problem to continuous domains. While discretizing the domain and applying the Bousquet–Warmuth long-term-memory algorithm yields information-theoretic regret $\widetilde O(md+k)$, this is computationally inefficient. The authors prove that, under the hypergraphic planted-clique conjecture, no polynomial-time algorithm can achieve $\widetilde O(k^a d^b)$ regret whenever the exponents violate $\theta a + b < \theta + 1/2$, establishing a fundamental computational barrier for exp-concave losses even when $m=2$.
The paper makes a compelling theoretical contribution by identifying a clean computational separation in tracking regret for online convex optimization. Its main result conditionally rules out efficient attainment of the information-theoretic rate for exp-concave losses, attributing hardness to the recurrence structure of the comparator rather than to switches alone. The reduction is technically sophisticated, the upper bounds are appropriately adapted from prior adaptive-regret machinery, and the landscape across convex, strongly convex, and exp-concave regimes is carefully charted.
The conceptual framing is sharp: the authors clearly explain why exp-concavity is the curvature regime where recurrence should help yet computationally cannot, and they derive efficient upper bounds cleanly by combining Follow-the-Leading-History with Online Newton Step or projected gradient descent. The hardness construction is elegant—rank-one quadratics on the Euclidean unit ball—making the planted-clique reduction both simple to state and amenable to concentration analysis.
The hardness result rests on the hypergraphic planted-clique conjecture holding for every fixed hyperedge order $r \geq 4$. This is a very strong average-case assumption, and while the authors use varying $r$ to sweep the full $(k,d)$ tradeoff, the lower bound would be more persuasive under a weaker or better-studied conjecture. There is also a non-trivial gap between the conditional lower bound of roughly $(k\sqrt{d})^{1-o(1)}$ and the best known efficient upper bound of $\widetilde O(dk)$, so the optimal polynomial-time rate for exp-concave tracking regret remains open.
The evidence is carefully structured. The authors summarize three curvature regimes and correctly note that convex and strongly convex settings already admit efficient, nearly optimal algorithms, whereas exp-concave losses sit in an intermediate spot where dimension-dependent static regret makes naive segment-wise relearning costly. Comparisons to prior tracking-expert and adaptive-regret literature are thorough and fair, though the paper would benefit from a sharper discussion of whether structural side information could bypass the hardness.
The upper-bound algorithms are oracle-efficient and built from standard components (Online Newton Step, online gradient descent, pruned FLH), so they are in principle reproducible, but the paper provides neither code nor explicit hyperparameter schedules. The lower-bound reduction is fully specified in the appendices, yet verifying the intricate concentration arguments and the averaging amplification step would require substantial implementation work. As a purely theoretical paper, the main barrier to reproduction is the reliance on an unproven average-case hardness conjecture rather than on omitted experimental details.
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.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.