在线凸优化中追踪少量专家的遗憾界与计算复杂度研究

研究针对连续动作空间在线凸优化中追踪仅在 $m$ 个专家间切换 $k$ 次的比较基准问题，证明了信息论最优与多项式时间可达遗憾界之间的计算复杂度分离。虽然离散化动作空间可实现 $\widetilde{O}(md+k)$ 的非高效算法，但在超图植入团猜想下，任意多项式时间算法的遗憾界至少为 $(k\sqrt d)^{1-o(1)}$。