在线凸优化中追踪少量专家：多项式时间算法存在固有计算下界

针对在线凸优化中追踪在 m 个专家间切换 k 次的比较器问题，研究证明信息论最优遗憾与多项式时间可达遗憾之间存在本质分离。在超图植入团猜想下，任何多项式时间算法在最坏情况下至少产生 (k√d)^{1-o(1)} 的遗憾，而离散化方法可达 Õ(md+k)、已知最优高效算法为 Õ(dk)。