1樓:梁令
這些很大程度是為了證明演算法收斂性和收斂率而假設的。
乙個簡單的應用是,在這些條件下, accelerated proximal gradient (APG)等一階演算法可以有複雜度結果(O(1/k^2)).
當沒有這些條件時, 分析起來會很難,比如如果沒有這兩個條件,大家又轉頭去考慮類似自洽(self-concordant) 函式。
2樓:Xenophon Tony
-smooth中的 ,和 -strongly convex中的 這一對CP,如果函式是二次可微的,可以認為它們就等同於函式Hessian矩陣的最大和最小奇異值的上界和下界,也就可以被看作梯度的最大變化速度和最小變化速度。由於SGD實在是乙個短視的演算法,每一步雖然也是在求解二階近似,但都把Hessian暴力換成identity matrix了,這麼說就明白了,梯度的變化率範圍越小,在做GD step的時候越可控,由此反映在了GD的收斂效能上,具體可見這個答案~
什麼是ill-conditioning 對SGD有什麼影響?
3樓:Zeap
如果是L-Lipschitz的,就有了乙個二次函式的上界:
+ \frac\|x-x_0\|^2 \quad \forall x" eeimg="1"/>
如果是 -strongly convex的,就有了乙個二次函式的下界:
+ \frac\|x-x_0\|^2 \leqslant f(x) \quad \forall x" eeimg="1"/>
畫個示意圖,大概長這個樣子:
由於被迫長成乙個二次函式的樣子,於是很多演算法在 -strongly convex + L-Lipschiz下都有比較好的表現。
Zeap:非凸優化基石:Lipschitz Condition
潘潤琦:非凸優化的基石2:Regularity Condition
Zeap:當我們談論收斂速度時,我們都在談什麼?
Zeap:如何理解非凸優化極值條件: 梯度= 0 & 二階導》 0?
怎麼判斷乙個優化問題是凸優化還是非凸優化?
HarryYang 判斷乙個複雜的優化式是不是凸的說簡單也簡單,說難也難。簡單的是,統計裡面主要涉及各種範數損失 log exp 這些是不是凸的,如何組合是凸的,都很清楚。難的是,統計裡面絕大部分優化式是多元函式,太複雜了分析不出來Hessian矩陣或其期望Fisher資訊珍是不是正定的。此時統計裡...
為什麼在光滑凸優化研究中,Lipschitz gradient比strongly convex更普遍?
遠處群山 其實啊,在不同的領域裡,對Lipschitz continuity和strong convexity的看法也是大不同的。在優化理論的研究裡,大家希望不要做Lipschitz continuity和strong convexity假設,因為假設越多,侷限性就越大。我們肯定是希望盡量不要出現限...
傳統優化演算法與智慧型優化演算法與凸優化演算法如何界定其區別?都屬於最優化演算法嗎?
養生的控制人 個人理解 本質上都是求解最優化問題 乙個目標函式在給定區域內的最小值就是約束優化,不考慮給定區域就是無約束優化 傳統優化演算法可以理解為比較general的優化演算法但是針對不同問題可能並不適用,且考慮的最優只能是區域性最優 凸優化則是優化問題中的一種特殊情況,因為凸性可以保證全域性最...