世界是動態(tài)變化的。為了理解這個動態(tài)變化的世界并在其中運行，AI 模型必須具備在線學(xué)習(xí)能力。為此，該領(lǐng)域提出了一種新的性能指標 —— 適應(yīng)性遺憾值（adaptive regret），其定義為任意區(qū)間內(nèi)的最大靜態(tài)遺憾值。

在在線凸優(yōu)化（online convex optimization）的框架下，已有一些算法能夠有效地最小化自適應(yīng)遺憾值。然而，現(xiàn)有算法存在通用性不足的問題：它們通常只能處理某一類特定的凸函數(shù)，并且需要預(yù)先知道某些參數(shù)，這限制了它們在實際場景中的應(yīng)用。

為了解決這一局限，南京大學(xué)周志華團隊研究了具有雙重自適應(yīng)性（dual adaptivity）的通用算法。這類算法不僅能夠自動適應(yīng)函數(shù)的性質(zhì)（如凸、指數(shù)凹或強凸），還能夠適應(yīng)環(huán)境的變化（如靜態(tài)或動態(tài)環(huán)境）。

• 論文標題：Dual Adaptivity: Universal Algorithms for Minimizing the Adaptive Regret of Convex Functions
• 論文鏈接：https://arxiv.org/pdf/2508.00392

具體而言，該團隊提出了一種元-專家框架（meta-expert framework），用于構(gòu)建雙重自適應(yīng)算法。在該框架中，會動態(tài)地創(chuàng)建多個專家算法，并通過一個元算法進行集成。該元算法需滿足二階界限（second-order bound）的要求，以應(yīng)對未知的函數(shù)類型。

為了捕捉環(huán)境的變化，該團隊還進一步引入了「休眠專家（sleeping experts）」技術(shù)。在專家的構(gòu)建策略上，本文提出了兩種通用性實現(xiàn)方式：一是增加專家數(shù)量，二是提升專家能力。

理論分析表明，該方法能夠同時對多種類型的凸函數(shù)實現(xiàn)自適應(yīng)遺憾值最小化，且在不同輪次之間函數(shù)類型可變的情況下依然保持有效。

此外，該團隊還將元-專家框架成功擴展用于「在線復(fù)合優(yōu)化（online composite optimization）」，并提出了一種通用算法，用于最小化復(fù)合函數(shù)的自適應(yīng)遺憾值。

用于實現(xiàn)雙重自適應(yīng)性的元-專家框架

該團隊提出的元-專家框架包含三個關(guān)鍵組成部分：

• 專家算法：能夠最小化靜態(tài)遺憾值；
• 區(qū)間集合：每個區(qū)間關(guān)聯(lián)一個或多個專家，負責(zé)最小化該區(qū)間內(nèi)的遺憾；
• 元算法：在每一輪中組合當前活躍專家的預(yù)測結(jié)果。

受靜態(tài)遺憾值通用算法研究成果的啟發(fā)，該團隊選擇的元算法是 Adapt-ML-Prod，他們還將其擴展為了支持「休眠專家」的版本，即僅在特定時間段活躍的專家。

改進后的元算法達成了二階界限，能夠自適應(yīng)函數(shù)的特性，從而獲得較小的元遺憾值。

基于以往工作，他們采用幾何覆蓋（Geometric Covering, GC）區(qū)間來定義專家的生命周期。為了在這些區(qū)間上構(gòu)建專家，他們提出兩種策略：一種是增加專家數(shù)量，另一種是提升專家能力。下面將分別介紹基于這兩種策略的算法。

雙層通用算法（UMA2）

對于增加專家數(shù)量的策略，周志華團隊提出了一種用于最小化自適應(yīng)遺憾值的雙層通用算法（UMA2）。

相比現(xiàn)有的自適應(yīng)算法，UMA2 在每個區(qū)間上引入了更大規(guī)模的專家集合，以應(yīng)對函數(shù)類型及其相關(guān)參數(shù)不確定性的挑戰(zhàn)。這些專家的決策結(jié)果通過前述元算法進行聚合，從而構(gòu)成一個雙層結(jié)構(gòu)。

值得注意的是，盡管這里的元算法受到 Zhang et al. (2022) 的論文《A simple yet universal strategy for online convex optimization》啟發(fā)，但這兩項研究在專家的構(gòu)建方式上存在顯著差異。

具體來說，該團隊引入了由不同學(xué)習(xí)率參數(shù)化的替代損失函數(shù)（surrogate loss），讓每位專家分別最小化一個替代損失函數(shù)；而在 Zhang et al. 的方法中，每個專家則是直接優(yōu)化原始損失函數(shù)。

這一設(shè)計使這里新提出的方法無需進行多次梯度估計，并且避免了對參數(shù)有界性的假設(shè)。

該團隊也進行了理論分析，結(jié)果表明，UMA2 能夠有效最小化一般凸函數(shù)的自適應(yīng)遺憾值，并在可能的情況下自動利用函數(shù)的「易解性」。具體而言，UMA2 分別對以下三類函數(shù)達成如下的強自適應(yīng)遺憾值界限：

• 一般凸函數(shù)：
• α- 指數(shù)凹函數(shù)： 
• λ- 強凸函數(shù)： 

其中，d 表示問題的維度。上述界限均與當前最優(yōu)的自適應(yīng)遺憾值結(jié)果完全一致。

此外，UMA2 還能夠應(yīng)對函數(shù)類型在不同輪次之間發(fā)生變化的情況。例如，假設(shè)在區(qū)間 I_1 內(nèi)，在線函數(shù)為一般凸函數(shù)；在區(qū)間 I_2 中變?yōu)?α- 指數(shù)凹函數(shù)；最終在區(qū)間 I_3 中切換為 λ- 強凸函數(shù)。對于這樣的函數(shù)序列，UMA2 在各個區(qū)間中分別實現(xiàn)以下遺憾值界限：

• 在 I_1：
• 在 I_2：
• 在 I_3：

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

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

三層通用算法（UMA3）

對于第二種，即提升專家能力的策略，該團隊提出了一種三層通用算法（UMA3），同樣用于最小化自適應(yīng)遺憾值。與以往依賴專用專家的自適應(yīng)算法不同，UMA3 提升的是單個專家的能力，使其能夠處理更廣泛的凸函數(shù)類別。

具體而言，他們采用了現(xiàn)有的用于最小化靜態(tài)遺憾值的通用算法 Maler 作為專家算法。然后，使用與 UMA2 相同的元算法動態(tài)聚合專家決策。

由于 Maler 本身是一個雙層結(jié)構(gòu)，因此 UMA3 構(gòu)成了一個三層結(jié)構(gòu)。與 UMA2 不同的是，UMA3 將現(xiàn)有通用算法作為黑盒子子程序使用，從而簡化了算法設(shè)計與理論分析。

UMA3 達成的強自適應(yīng)遺憾值界限與 UMA2 相同，并同樣支持函數(shù)類型在不同輪次之間的切換。

算法 4: 最小化自適應(yīng)遺憾值的 UMA3

在線復(fù)合優(yōu)化（Online Composite Optimization）

該團隊還進一步研究了在線復(fù)合優(yōu)化問題，其中損失函數(shù)定義為

即由時間變化的函數(shù) f_t (?) 與固定的凸正則項 r (?) 組成。而該團隊的目標是設(shè)計一種通用算法，最小化復(fù)合函數(shù)形式的自適應(yīng)遺憾值：

一種直觀的做法是將復(fù)合函數(shù) F_t (w) 直接輸入 UMA2 或 UMA3。但這種方法難以對指數(shù)凹函數(shù)獲得緊致的自適應(yīng)遺憾界限，因為一個指數(shù)凹函數(shù)與一個凸正則項之和通常不再保持指數(shù)凹性質(zhì)。

為解決這一問題，他們?yōu)樵诰€復(fù)合優(yōu)化構(gòu)建了一個新的元-專家框架，并采用 Optimistic-Adapt-ML-Prod 作為元算法。借助《Universal online convex optimization meets second-order bounds》中提出的樂觀設(shè)定（optimism setting），該團隊證明該框架在時間變化的函數(shù)下能達成二階界限。

為了應(yīng)對多樣的函數(shù)類型，可以采用兩種方案：構(gòu)建大量專用專家，或構(gòu)建少量能力更強的專家。為簡化實現(xiàn)，該團隊的選擇是后者，使用復(fù)合函數(shù)的通用算法作為專家。

此外，由于之前的樂觀設(shè)定方法依賴于模量有界性的假設(shè)，因此該團隊提出了一種新的不依賴該假設(shè)的通用復(fù)合函數(shù)算法。在每個區(qū)間上部署一個專家后，新算法對三類復(fù)合函數(shù) f_t (?) 分別實現(xiàn)了以下強自適應(yīng)遺憾界限：

• 一般凸函數(shù)：
• α-指數(shù)凹函數(shù)： 
• λ-強凸函數(shù)： 

算法 5: 面向在線復(fù)合優(yōu)化的雙重自適應(yīng)元-專家框架

結(jié)論與未來工作

為實現(xiàn)對函數(shù)類型和環(huán)境變化的雙重自適應(yīng)，上述通用算法在最后一層需維護  個專家算法（其中 T 為在線學(xué)習(xí)的總輪數(shù)）。這意味著在每一輪中，算法需執(zhí)行 次對可行域的投影操作。然而，在實際應(yīng)用中，尤其當可行域復(fù)雜時，如此大量的投影會帶來較高的計算開銷。

值得注意的是，近年來的在線學(xué)習(xí)研究中，已有工作利用黑盒歸約技術(shù)（black-box reduction），成功將非平穩(wěn)在線凸優(yōu)化（non-stationary OCO）和通用在線凸優(yōu)化（universal OCO）中的投影次數(shù)從降至每輪 1 次。

未來的研究中，該團隊表示將探索能否將該技術(shù)應(yīng)用于該算法框架中，以進一步降低投影操作的復(fù)雜度，提升實際應(yīng)用的效率。

更多有關(guān)算法、引理和定理的證明請參閱原論文。