南大周志華團隊提出用於動態系統的自適應學習Ader

選自arXiv

作者：Lijun Zhang、Shiyin Lu、Zhi-Hua Zhou

機器之心編譯

參與：Panda

近日改名為 NeurIPS 的原 NIPS 會議將於當地時間 12 月 2-8 日在加拿大蒙特利爾舉辦。周志華領導的南京大學計算機軟體新技術國家重點實驗室有多篇論文入選，比如機器之心之前介紹的《NIPS 2018 | 南大周志華等人提出無組織惡意攻擊檢測演算法 UMA》，今天介紹的這篇論文則提出了一種可用於動態環境的自適應在線學習方法。

引言

在線凸優化（OCO）已經成為了一種用於建模各種真實世界問題的常用學習框架，比如在線路由、搜索引擎的廣告選擇和垃圾信息過濾 [Hazan, 2016]。OCO 的協議如下：在第 t 次迭代，在線學習器從凸集 X 選擇 x_t。在學習器確認這個選擇之後，會揭示出一個凸成本函數。然後，學習器會遭受一個即時的損失，其目標是最小化在 T 次迭代上的累積損失。OCO 的標準性能度量是後悔值（regret）：

這是學習器的累積損失減去事後選擇的最佳恆定點。

後悔值的概念已經得到過廣泛的研究，現在也有很多用於最小化後悔值的演算法和理論 [Shalev-Shwartz et al., 2007, Hazan et al., 2007, Srebro et al., 2010, Duchi et al., 2011, Shalev-Shwartz, 2011, Zhang et al., 2013]。但是，當環境會變化時，傳統的後悔值不再是合適的度量，因為它是將學習器與一個靜態點進行比較。為了解決這一局限性，在線學習領域的一些近期進展引入了一種增強的度量——動態後悔值，這方面多年來得到了相當多的研究關注 [Hall and Willett, 2013, Jadbabaie et al., 2015, Mokhtari et al., 2016, Yang et al., 2016, Zhang et al., 2017]。

文獻中的動態後悔值有兩種形式。Zinkevich [2003] 提出的是一種通用形式，即比較學習器的累積損失與任意比較器（comparator）的序列：

其中 u_1...u_T ∈ X。而大多數有關動態後悔值的已有研究則不同於 (2) 的定義，而是有限定的形式，其中比較器的序列由在線函數的局部最小化器構成 [Besbes et al., 2015]，即：

其中

是在域 X 上的最小化器。注意，儘管，但並不意味著

更強，因為對於

的

的上界可能非常寬鬆。

(2) 中的通用型動態後悔值包含 (1) 中的靜態後悔值以及 (3) 中的有限定的動態後悔值特例。因此，最小化通用動態後悔值可以自動適應環境的本質——不管是靜態的還是動態的。相對而言，受限的動態後悔值太過悲觀，無法適用於靜態問題。比如，對於靜態機器學習問題而言，這是無意義的；在這樣的問題中 f_t 是從同一分布中獨立採樣的。由於採樣所造成的隨機擾動，預期損失的局部最小化器可能會與全局最小化器有顯著的差異。在這個案例中，最小化 (3) 會導致過擬合。

因為通用動態後悔值很靈活，所以也是本論文關注的重點。限定通用動態後悔值的範圍是非常有難度的，因為我們需要普適地保證其對任何比較器序列而言都成立。通過比較，在限定受限動態後悔值的範圍時，我們僅需要關注局部最小化器。到目前為止，我們對通用動態後悔值的了解還很有限。Zinkevich [2003] 給出了一個結果，其證明在線梯度下降（OGD）能實現以下的動態後悔值範圍。

其中 P_T 在 (5) 中定義，是 u_1...u_T 的路徑長度。

但是，(4) 中對 P_T 的線性依賴太過寬鬆，而且在上界和本論文確立的

下界之間存在很大的範圍。為了解決這一限制，我們提出了一種全新的在線方法，即用於動態環境的

自適應學習（Ader），其獲得的動態後悔值為

。Ader 遵循帶有專家建議的學習框架 [Cesa-Bianchi and Lugosi, 2006]，而且受到了 MetaGrad 中維持多個學習率的策略的啟發 [van Erven and Koolen, 2016]。其基本思想是並行地運行多個 OGD 演算法，其中每個演算法都有不同的步長，這些步長對特定的路徑長度而言是最優的；並將它們與一個專家跟蹤演算法結合到一起。儘管基礎版的 Ader 在每一輪中都需要查詢梯度次，但我們還開發了一個改進版，其基於替代損失（surrogate loss）並將梯度評估的次數降為了 1。最後，我們還將 Ader 進行了延展，可用於給出了動態模型的序列的情況；並且當比較器序列緊密遵循這些動態模型時能獲得更嚴格的範圍。

本論文的貢獻總結如下：

我們首次為 (2) 中的通用後悔值範圍確立了下界，即

我們為最小化通用動態後悔值開發了一系列全新方法，並證明了一個最優的

上界。

相比於 (3) 中已有的受限動態後悔值研究工作，我們的結果是普適的，也就是說後悔值範圍適用於任意比較器序列。

我們的結果也能自適應，因為其上界取決於比較器序列的路徑長度，所以當比較器變化緩慢時它會自動變小。

論文：動態環境中的自適應在線學習（Adaptive Online Learning in Dynamic Environments）

論文地址：https://arxiv.org/pdf/1810.10815.pdf

在這篇論文中，我們研究了動態環境中的在線凸優化，目標是針對任意比較器序列限定動態後悔值的範圍。已有的研究已經表明在線梯度下降具有

的動態後悔值，其中 T 是迭代次數，P_T 是比較器序列的路徑長度。但是，這個結果並不令人滿意，因為離本論文確立的

下界存在較大差距。為了解決這一限制，我們開發了一種全新的在線方法，即用於動態環境的自適應學習（Ader），其能得到最優的

動態後悔值。其基本思想是維持一組專家，其中每個專家都為特定的路徑長度求取一個最優動態後悔值，然後使用一個專家跟蹤演算法將它們組合起來。此外，我們還基於替代損失提出了一種改進版 Ader，使用這種方法，每一輪的梯度評估次數將從 O(log T ) 降至 1。最後，我們還將 Ader 延展到了可使用動態模型的序列來特徵化比較器的案例上。

本文為機器之心編譯，轉載請聯繫本公眾號獲得授權。

------------------------------------------------

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！