南大周志華團隊最新力作：一個算法通吃所有，在線學習迎來新范式？

2025-08-06 08:30:00

南京大學周志華團隊研究了具有雙重自適應性（dual adaptivity）的通用算法。這類算法不僅能夠自動適應函數的性質（如凸、指數凹或強凸），還能夠適應環境的變化（如靜態或動態環境）。

世界是動態變化的。為了理解這個動態變化的世界并在其中運行，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 (?) 分別實現了以下強自適應遺憾界限：