Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 6 min ago
PreprintCC BY 4.0arXiv

Tracking a Small Set of Experts in Online Convex Optimization

  • Angelos Assos
  • Anand Brahmbhatt
  • Elad Hazan
Open at sourcePDFDOICite

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

Related

  1. Minimax Alternating Regret for the Experts Problem and Online Convex Optimization
    Mengxiao Zhang
    arXivPreprintarXiv licenceFull textStatisticsarXiv
  2. Private Online Prediction from Experts with Small Losses
    Bo Li, Peng Ye
    arXivPreprintCC BY 4.0Full textStatisticsarXiv
  3. Gradient-Only Online Convex Optimization with a Single Quadratic Leader
    Kamiar Asgari
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  4. Online Inverse Integer Linear Optimization via Small-Gradient Skipping: Constant Regret and Finite Mistakes
    Akira Kitaoka
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  5. Online Learning with LLM Experts from Limited Feedback
    Wang Wei, Soumyabrata Pal, Koyel Mukherjee +4
    arXivPreprintCC BY 4.0Full textStatisticsarXiv

Cite

BibTeXRIS
BibTeX
@misc{assos2026tracking,
  title = {{Tracking a Small Set of Experts in Online Convex Optimization}},
  author = {Angelos Assos and Anand Brahmbhatt and Elad Hazan},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.20416},
  eprint = {2610.20416},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.20416},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Tracking a Small Set of Experts in Online Convex Optimization
AU  - Angelos Assos
AU  - Anand Brahmbhatt
AU  - Elad Hazan
PY  - 2026
DA  - 2026/10/14
PB  - arXiv
DO  - 10.48550/arxiv.2610.20416
UR  - https://arxiv.org/abs/2610.20416
AB  - 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 Õ(md+k), while the best known efficient algorithm for this problem has regret Õ(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.
ER  -