乾貨 —— Frank-Wolfe演算法

4 人贊了文章

這次讓我們來探討一個技術話題： Frank-Wolfe演算法。（大體內容是基於[Jaggi13]這篇論文，具體信息請參考備註）。

首先交代問題背景，Frank-Wolfe演算法屬於某種gradient decent演算法。這類演算法主要用於以下求極值問題（optimization problem）：

min_x L(x)

其中L稱為損失函數（loss function）或者目標函數（objective function）。如果L過於複雜，極值解 x^*=argmin_x L(x) 無法直接表達的時候，通過獲得導數?L(x)（gradient）相關信息而逼近極值點x^*。Frank-Wolfe 演算法則用於處理以下更特殊一點的情況：

min_(x∈C) L(x)

其中C是一個凸集（convex set）並且L是凸函數（convex function）（也有非convex版本的Frank-Wolfe，這次先不做討論）。

對於L被限制在一個凸集C（convex set）上取值這樣的問題，可以與Frank-Wolfe演算法作比較的同類演算法有proximal method 或者 projected gradient decent。 那麼Frank-Wolfe比同類演算法到底有什麼優勢呢？我們先來看下同類演算法。

如果沒有L必須在C上取值的限制，那麼通常的gradient decent演算法有如下形式：

x^(t+1)=x^t-α^t ?L(x^t ),t=0,1,2,?

即在每一個循環t中，我們只要通過計算?L(x^t )，取定步長α^t就能沿著梯度（gradient）向極值x^*逼近。現在L必須在C上取值，一般的同類演算法就會在循環中將到C的距離考慮進去。比如projected gradient decent就是將每次獲得的新的取值點x^(t+1)投影到C上，即

y^t=x^t-α^t?L(x^t )

x^(t+1)=argmin_(x∈C) ||y^t-x||2_2

而proximal method則是在L上增加一個到C距離的懲罰項，即

x^(t+1)=prox(x^t-α^t ?L(x^t ),γ^t)

其中prox()（proxy operator）的定義如下：

prox(x,γ)=argmin_u L(u)+1/2γ||u-x||2_2

還有的演算法則是直接先將導數空間投影到C上，再求新的取值點。總之這些演算法都涉及到二次方程求極值點的問題。Frank-Wolfe在這方面進行突破，只需要涉及到線性方程求極值點的問題即

s=argmin_(s∈C) ?s,?L(x^t)?

x^(t+1)=t/(t+2)*x^t+2/(t+2)*s

同時在L是凸函數（convex function）的條件下，其收斂速度（即所需循環個數）又和不加限制條件C的gradient decent演算法理論最優收斂速度同階(都是O(1/t))，所以理論上Frank-Wolfe是一種比較快速的演算法。

直覺上，求解線性問題應該比求解二次方程問題簡單一些，但也需要看具體的問題以及限制條件。因為我們是在一個凸集上找尋極值點，極值點可以被邊界上點或端點線性表示，所以在Frank-Wolfe演算法中每次求解的線性問題（求s的那一步）其實都是通過導數來找到一個較好的邊界點，並與之前找到的邊界點線性組合（求x^(t+1)的那一步）去逼近極值點。所以邊界點或端點好求將加快Frank-Wolfe的速度，反之則可能還不如其他同類演算法。 比如，如果凸集的端點是sparse的（向量只有少數非零分量），那麼每個循環的求解速度就快，同時如果極值點也是sparse的，那麼總循環個數也會比較少，同時運行需要的儲存也較少（只需存取非零項）。

另一方面，Frank-Wolfe 其實是一個1956年就已經提出的演算法，在過去數據集不大的情況下，該演算法並不突出。而如今因為大數據的緣故，往往總體維度高但有用的信息維度並不高（即sparse的情況），所以Frank-Wolfe演算法在最近幾年再次煥發第二春。

論文還給出了如何在不知道真實極值點x^*的情況下，如何估算誤差L(x^t )-L(x^*)。最後作者還列舉了一些演算法可以在此之上有較好表現的凸集C：Sparse Vectors, l_1 ball, Simplex, l_p ball, Structured Atomic Norms, Schatten Matrix Norms, Orthonormal Matrices and the Operator Norm Ball, Permutation Matrices, Rotation Matrices 和 Trace。

Reference

[Jaggi13] Martin Jaggi, Revisiting Frank-Wolfe: Projection-FreeSparse Convex Optimization, ICML, 2013.