在线凸优化中追踪少量专家的计算困境

在线学习领域有一个经典问题：当预测器需要从一组专家中动态切换时，能否以低遗憾实现接近最优的预测？Freund早年提出，若允许比较器在m个专家中切换k次，是否存在高效算法与之竞争？对于离散专家集合，Bousquet和Warmuth在2020年给出了优雅解答——一个高效算法，其遗憾达到信息论下界。然而，当行动空间从离散变为连续的在线凸优化场景时，问题变得棘手。最近一项研究深入剖析了这一计算复杂性，揭示了信息论最优与多项式时间可达到的遗憾之间存在本质分离。

从离散专家到连续行动：问题迁移的挑战

在离散专家建议框架中，学习者每轮从m个专家中选择一个行动，并希望与事后最优的“切换k次”专家序列竞争。Bousquet-Warmuth算法通过精巧的组合结构，将遗憾控制在$\widetilde{O}(md+k)$，这与信息论下界匹配，且计算效率为多项式时间。

当行动空间变为连续凸集时，自然的思路是离散化行动空间，再套用离散算法。这样确实能得到$\widetilde{O}(md+k)$的遗憾，但离散化所需的网格点数量随维度d指数增长，导致算法在多项式时间内不可行。此前已知的最高效多项式时间算法遗憾为$\widetilde{O}(dk)$——远高于信息论极限。这留下一个悬念：是否存在更聪明的多项式时间算法能弥合差距？

在线凸优化（OCO） 是在线学习的一个核心子领域：每一轮学习者从某个凸集 $\mathcal{K} \subseteq \mathbb{R}^d$ 中选取决策 $w_t$，随后遭受凸损失函数 $f_t(w_t)$，目标是最小化累积遗憾 $\sum_t f_t(w_t) - \min_{w \in \mathcal{K}} \sum_t f_t(w)$。与离散专家框架中只能选择有限个候选动作不同，OCO 允许连续取值，梯度信息可用，这既带来了诸如在线梯度下降、跟随正则化领导者等成熟算法的便利，也引入了新的复杂性——学习者不仅要选点，还要应对非平稳环境。文章讨论的“追踪切换 $k$ 次的专家序列”正是非平稳 OCO 的一类典型设定：比较器可以在 $m$ 个基础专家轨迹间切换 $k$ 次，对应于环境具有分段平稳结构。

计算低效性是固有的：超图种植团猜想下的下界

新研究给出了否定答案。作者证明，在超图种植团猜想（hypergraphic planted-clique conjecture）成立的前提下，任何多项式时间算法都不可避免地承受至少$(k\sqrt{d})^{1-o(1)}$的遗憾。这意味着信息论最优遗憾$\widetilde{O}(md+k)$与多项式时间可达遗憾之间的鸿沟是计算复杂性所固有的，而非算法设计不足。

这一下界建立在对问题结构的深入分析上。超图种植团猜想是平均情形复杂性理论中的核心假设，常被用于证明某些统计估计与优化问题的计算下界。研究者将在线凸优化中的专家追踪问题归约到该猜想，从而确立了计算难解性。

超图种植团猜想（Hypergraphic Planted Clique Conjecture） 是平均情形复杂性理论中的核心假设之一。经典种植团问题指在一个随机图 $G(n, 1/2)$ 中隐藏一个大小为 $k$ 的团，要求高效算法找回该团；大量证据表明当 $k = o(\sqrt{n})$ 时该问题在多项式时间内不可解。超图版本将其推广到 $r$-均匀超图：在一个随机 $r$-均匀超图（每条 $r$-边独立以概率 $p$ 出现）中植入一个 $k$ 顶点团，即其中所有可能的 $r$-边都存在。此假设常被用作归约基准，用来证明统计估计、稀疏 PCA、张量分解等问题的计算下界。其逻辑是：若存在多项式时间算法打破某下界，则同样可以求解种植团问题，从而违背广泛接受的猜想。

信息论下界与计算下界的区别：信息论下界刻画的是在无计算资源限制、仅受数据量约束时任何算法（甚至指数时间）能达到的最优表现，本问题中对应 $\widetilde{O}(md+k)$。计算下界则进一步假设算法必须在多项式时间内运行，所得到的下界通常更大。两者之间若存在差距，便称为 信息论-计算间隙。这一概念在平均情形复杂性理论中已被广泛用于高维统计、矩阵恢复、社区检测等场景。文章所证的结果表明：在超图种植团猜想下，追踪切换专家的 OCO 问题同样存在本质间隙，即统计最优与计算可行之间的鸿沟并非算法设计缺陷，而是问题本身的计算硬度所致。

分离结果的意义与启示

该分离结果对在线学习理论有重要影响。它表明，即使在看似简单的连续凸优化设定中，追求与最佳切换策略竞争也可能面临计算壁垒。这提醒实践者：当维度d较大且切换次数k不可忽略时，依赖离散化或精确优化的方法可能并不现实，需要重新审视算法效率与遗憾的权衡。

此外，这一结论与近年来在线学习、在线凸优化中一系列计算下界工作相呼应，进一步印证了“统计最优未必计算可行”的普遍现象。对于设计实际算法而言，接受$\widetilde{O}(dk)$级别的遗憾或寻求额外结构假设，可能是更务实的方向。

关键要点

• 在线凸优化中，追踪切换k次的专家序列存在信息论与计算复杂性的分离。
• 离散化方法虽能达到$\widetilde{O}(md+k)$遗憾，但计算代价随维度指数增长。
• 在超图种植团猜想下，多项式时间算法遗憾下界为$(k\sqrt{d})^{1-o(1)}$，证明计算低效性固有。
• 已知高效算法遗憾$\widetilde{O}(dk)$，与信息论极限差距显著。
• 该结果为在线学习算法设计提供了理论边界，提示需权衡计算与统计效率。