南大周志华团队最新力作：一个算法通吃所有，在线学习迎来新范式？

摘要：世界是动态变化的。为了理解这个动态变化的世界并在其中运行，AI 模型必须具备在线学习能力。为此，该领域提出了一种新的性能指标 —— 适应性遗憾值（adaptive regret），其定义为任意区间内的最大静态遗憾值。

编辑：冷猫、Panda

世界是动态变化的。为了理解这个动态变化的世界并在其中运行，AI 模型必须具备在线学习能力。为此，该领域提出了一种新的性能指标 —— 适应性遗憾值（adaptive regret），其定义为任意区间内的最大静态遗憾值。

在在线凸优化（online convex optimization）的框架下，已有一些算法能够有效地最小化自适应遗憾值。然而，现有算法存在通用性不足的问题：它们通常只能处理某一类特定的凸函数，并且需要预先知道某些参数，这限制了它们在实际场景中的应用。

为了解决这一局限，南京大学周志华团队研究了具有双重自适应性（dual adaptivity）的通用算法。这类算法不仅能够自动适应函数的性质（如凸、指数凹或强凸），还能够适应环境的变化（如静态或动态环境）。

论文标题：Dual Adaptivity: Universal Algorithms for Minimizing the Adaptive Regret of Convex Functions论文链接：https://arxiv.org/pdf/2508.00392

具体而言，该团队提出了一种元-专家框架（meta-expert framework），用于构建双重自适应算法。在该框架中，会动态地创建多个专家算法，并通过一个元算法进行集成。该元算法需满足二阶界限（second-order bound）的要求，以应对未知的函数类型。

为了捕捉环境的变化，该团队还进一步引入了「休眠专家（sleeping experts）」技术。在专家的构建策略上，本文提出了两种通用性实现方式：一是增加专家数量，二是提升专家能力。

理论分析表明，该方法能够同时对多种类型的凸函数实现自适应遗憾值最小化，且在不同轮次之间函数类型可变的情况下依然保持有效。

此外，该团队还将元-专家框架成功扩展用于「在线复合优化（online composite optimization）」，并提出了一种通用算法，用于最小化复合函数的自适应遗憾值。

用于实现双重自适应性的元-专家框架

该团队提出的元-专家框架包含三个关键组成部分：

专家算法：能够最小化静态遗憾值；区间集合：每个区间关联一个或多个专家，负责最小化该区间内的遗憾；元算法：在每一轮中组合当前活跃专家的预测结果。

受静态遗憾值通用算法研究成果的启发，该团队选择的元算法是 Adapt-ML-Prod，他们还将其扩展为了支持「休眠专家」的版本，即仅在特定时间段活跃的专家。

改进后的元算法达成了二阶界限，能够自适应函数的特性，从而获得较小的元遗憾值。

基于以往工作，他们采用几何覆盖（Geometric Covering, GC）区间来定义专家的生命周期。为了在这些区间上构建专家，他们提出两种策略：一种是增加专家数量，另一种是提升专家能力。下面将分别介绍基于这两种策略的算法。

双层通用算法（UMA2）

对于增加专家数量的策略，周志华团队提出了一种用于最小化自适应遗憾值的双层通用算法（UMA2）。

相比现有的自适应算法，UMA2 在每个区间上引入了更大规模的专家集合，以应对函数类型及其相关参数不确定性的挑战。这些专家的决策结果通过前述元算法进行聚合，从而构成一个双层结构。

值得注意的是，尽管这里的元算法受到 Zhang et al. (2022) 的论文《A simple yet universal strategy for online convex optimization》启发，但这两项研究在专家的构建方式上存在显著差异。

具体来说，该团队引入了由不同学习率参数化的替代损失函数（surrogate loss），让每位专家分别最小化一个替代损失函数；而在 Zhang et al. 的方法中，每个专家则是直接优化原始损失函数。

这一设计使这里新提出的方法无需进行多次梯度估计，并且避免了对参数有界性的假设。

该团队也进行了理论分析，结果表明，UMA2 能够有效最小化一般凸函数的自适应遗憾值，并在可能的情况下自动利用函数的「易解性」。具体而言，UMA2 分别对以下三类函数达成如下的强自适应遗憾值界限：

一般凸函数：

α- 指数凹函数：

λ- 强凸函数：

其中，d 表示问题的维度。上述界限均与当前最优的自适应遗憾值结果完全一致。

此外，UMA2 还能够应对函数类型在不同轮次之间发生变化的情况。例如，假设在区间 I_1 内，在线函数为一般凸函数；在区间 I_2 中变为 α- 指数凹函数；最终在区间 I_3 中切换为 λ- 强凸函数。对于这样的函数序列，UMA2 在各个区间中分别实现以下遗憾值界限：

在 I_1：

在 I_2：

在 I_3：

算法 2: 基于原始损失的 UMA2

算法 3: 基于替代损失的 UMA2

三层通用算法（UMA3）

对于第二种，即提升专家能力的策略，该团队提出了一种三层通用算法（UMA3），同样用于最小化自适应遗憾值。与以往依赖专用专家的自适应算法不同，UMA3 提升的是单个专家的能力，使其能够处理更广泛的凸函数类别。

具体而言，他们采用了现有的用于最小化静态遗憾值的通用算法 Maler 作为专家算法。然后，使用与 UMA2 相同的元算法动态聚合专家决策。

由于 Maler 本身是一个双层结构，因此 UMA3 构成了一个三层结构。与 UMA2 不同的是，UMA3 将现有通用算法作为黑盒子子程序使用，从而简化了算法设计与理论分析。

UMA3 达成的强自适应遗憾值界限与 UMA2 相同，并同样支持函数类型在不同轮次之间的切换。

算法 4: 最小化自适应遗憾值的 UMA3

在线复合优化（Online Composite Optimization）

该团队还进一步研究了在线复合优化问题，其中损失函数定义为

即由时间变化的函数 f_t (・) 与固定的凸正则项 r (・) 组成。而该团队的目标是设计一种通用算法，最小化复合函数形式的自适应遗憾值：

一种直观的做法是将复合函数 F_t (w) 直接输入 UMA2 或 UMA3。但这种方法难以对指数凹函数获得紧致的自适应遗憾界限，因为一个指数凹函数与一个凸正则项之和通常不再保持指数凹性质。

为解决这一问题，他们为在线复合优化构建了一个新的元-专家框架，并采用 Optimistic-Adapt-ML-Prod 作为元算法。借助《Universal online convex optimization meets second-order bounds》中提出的乐观设定（optimism setting），该团队证明该框架在时间变化的函数下能达成二阶界限。

为了应对多样的函数类型，可以采用两种方案：构建大量专用专家，或构建少量能力更强的专家。为简化实现，该团队的选择是后者，使用复合函数的通用算法作为专家。

此外，由于之前的乐观设定方法依赖于模量有界性的假设，因此该团队提出了一种新的不依赖该假设的通用复合函数算法。在每个区间上部署一个专家后，新算法对三类复合函数 f_t (・) 分别实现了以下强自适应遗憾界限：

一般凸函数：