動機
隨機梯度的計算可以比完整梯度便宜,但隨機性也改變了收斂保證的內容。某一步可能令目標值上升;最後迭代仍可能波動,而適當平均卻已有小期望差距。要理解定理,必須說明每步之前知道甚麼、最後平均甚麼,以及假設控制的是雜訊方差,還是整個梯度的二階矩。
基本凸證明觀察至最優點的平方距離。投影維持可行性,並改善比較距離;凸性再把梯度內積連到目標差距。強凸性額外提供一個距離項,讓證明不必沿用普通凸情況的粗界。恰當的遞減步長與遞增權重會令這些額外項精確相消。
以下把相消完整推導出來,而非只列出更快速率。這解釋了後期點為何有較大權重,以及初始距離項為何可以消失。結論控制固定目標的期望最優化誤差,不自行處理泛化、有偏抽樣或某一條實現軌跡的誤差。
定義
定義 18.1.1
(歷史、無偏與兩種矩界)
設 非空、閉且凸, 在包含它的開鄰域可微且凸,並在 上於 取得最小值。選確定的 。濾過 表示第 步前的歷史, 對它可測;估計器 對 可測,並滿足
另假設沿迭代有完整條件二階矩界 。若 上梯度範數不超過 ,則 足夠。
置中雜訊 的條件均值為零,所以展開平方時交叉項消失。但方差界本身未控制均值梯度,不能直接當作完整二階矩。整個歐幾里得(Euclid)空間上的全域強凸函數不可能同時有全域有界梯度;有界可行集常令假設相容。更一般地,定理只需完整矩界沿實際迭代成立。
更新為 ,其中步長確定且正,投影指歐幾里得最近點。非負確定權重 的加權平均是 ,總權重須正。因 凸,此平均仍可行。
下面較快的速率還需要一個假設:可行集上一致的曲率下界。
定義 18.1.2
( 上的強凸性)
設 。若
便稱 在 上為 -強凸。
最優點可以在邊界,普通梯度未必要零;以下沒有把它當作無約束駐點。
定理/命題
定理 18.1.3
(完整二階矩下的凸平均界)
在上述條件下,記 ,用固定步長 及 ,則
若 ,取 得 。確定的變步長則給
定理 18.1.4
(沒有無故對數項的強凸速率)
若再有 -強凸性,取 ,使用另一個平均
則
強凸平均使用遞增指標權重,不是遞減步長權重。不能把它代入第一個定理便宣稱已證第二個。證明須先用強凸距離項,再選相匹配的加權求和。本節未要求光滑常數,也未斷言幾乎必然收斂。
證明思路
證明
(投影距離遞推與凸平均)
令 。從 指向任意 的線段可行,在最近點微分平方距離便得 。展開 即有 。取 ,每次實現都滿足
取條件期望。給定 後目前位移已知,無偏性可把內積中的 換成 。凸性令內積不小於 。再取總期望,令 、,得到
先不要除以變步長,直接相加,距離便精確消去。捨去非負終點項,再用凸性得 ,即得變步長公式。步長相同時便是普通平均公式,最小化兩項上界給所述步長。若 或 為零,須直接處理退化情況,不能把零代進要求正值的步長。
證明中有三個不同層次:先對每次實現的投影建立確定不等式,再給定目前歷史平均新雜訊,最後對整段歷史取總期望。若一開始就把目前點當成固定非隨機數,會漏掉它與以往抽樣的依賴;若只取無條件平均,又不足以移除內積中的相關項。明確的濾過正是令每一步合法的依據。
證明
(強凸下的加權相消)
把強凸不等式用於 、。整理後,梯度內積的下界增加 ;與前面相同的條件期望步驟給出
代入 ,再除以 :
乘以 。 的正係數為 ,剛好等於前一指標留下的負係數;在 時初始正係數為零。相加剩下
除以權重總和 ,再對相應平均用凸性,便得所述速率。
證明透視
加權相消中每個假設在哪裏起作用
對 可測只用了一次:它讓位移移出條件期望,無偏性才可從內積中移除雜訊。雜訊並沒有從 中消失;正是這一項需要完整矩 ,而非方差 。投影在取期望之前逐次實現地使用,所以毋須投影與估計器獨立。
不明顯的一步是步長與權重的配對。強凸性令除法後 的係數變成 ,權重 再令它等於前一指標以負號留下的 。求和能收口,是因為首個係數 ,所以 從不出現(但矩常數 仍取決於迭代可到達的位置);最後一項 非正,可以捨去。
權重亦決定雜訊總量。若用相等權重,距離係數的符號仍然正確,但雜訊貢獻 ,它像 般增長;除以 後得到 階的界。權重 把每個雜訊項變成 ,對數便消失。
輸出規則與速率的意思
實作必須真的計算定理指定的平均。遞增權重只需儲存加權和與總權重,不必保留整條軌跡;若改用最後一點,數學物件已改變。別的假設可能支援最後迭代定理,但本證明未給出它。
同一最優化結果可用於經驗目標,也可用於能抽取無偏梯度的總體期望。前者若逐筆循環數據,下一分量梯度未必在給定歷史下等於完整經驗梯度;後者則須新樣本相對目前歷史保持適當獨立。兩種用法不能只因公式相似便省略抽樣檢查。
矩常數是證明沿途統一使用的上界,未必等於解附近的二階矩。遞減雜訊或局部估計可以支持更佳分析,但尚未分析前,不能用某次觀察到的小梯度取代統一常數。
由目標差距控制距離
概念視角幾何
目標準確度與位置
在受約束最小點,沿可行線段微分給 。把強凸性用在該點,便得差距至少 。所以強凸加權輸出的期望平方距離至多 。這仍只適用指定輸出,不是靠聲稱邊界梯度為零而得。
步長需要有效的正曲率下界。若只有較小的已認證下界,可在步長與證明一起代入,得到較弱但有效保證。單點曲率、尤其有雜訊的 Hessian 估計,不會自行證明整個可行集強凸。這些常數反映已知的目標資訊,並非算法自動知道的量。二次增長也證唯一性:另一最小點若差距零,距離亦零;存在性則仍是獨立假設。
反例模式
步長安排需要真實的曲率常數
聲稱:對任何凸函數 ,只要取某個 並用步長 ,就有強凸速率。取 上的 ,精確梯度 (故 ),,。步長為 ,故 ,。當 ,加權輸出為 ,這也是其差距;聲稱的界卻是 。線性函數對任何 都不是 -強凸;修正是使用有效的下界 ,否則只有凸情形的定理適用。
例題詳解
例題 18.1.5
(投影與邊界最優點)
令 、、、、步長 ,此處 。有 ;兩項平均使用 ,所以為 。界為 。最優點零的導數是一,不應用無約束零梯度測試。第二步原候選點為負,投影把它修正為可行點。
例題 18.1.6
(強凸而有雜訊的均值問題)
等概率取負一及三,令 、。最優點一、強凸參數一,差距為 。新樣本梯度 的雜訊方差四,均值梯度範數至多二,故 足夠。從負一出發,抽到三及負一,步長一及 ,給 。兩項加權輸出為 ,此實現的差距是 ;定理控制所有抽樣的期望,不是每條實現。若 ,保證期望差距至多 。
例題 18.1.7
(方差不是完整矩)
對實線上的 ,估計器為 ,獨立置中雜訊方差一。在 ,條件方差是一,完整二階矩卻是 。把 寫成一便丟掉均值梯度。若可行集為 ,可用 。解附近收集的小雜訊估計不能自動認證之前全部更新的矩界。
常見錯誤
反例模式
無條件置中不足以控制歷史內積
目前點 等概率為正一或負一,目標恆為零,估計器卻回傳 。無條件均值零,與真梯度期望一樣;但給定目前歷史,其均值是 ,且 。距離證明所需的是實際目前點的條件無偏,而非整體平均巧合為零。
強凸不令每次有雜訊更新都下降;凸性本身亦未建立可用的統一矩常數,各條件都有不同作用。最後,以估計器調用次數計的速率不等於實際時間速率,尤其不同方法的單次調用成本不同時。
常見錯誤
(報告最後一點或錯誤的平均)
強凸定理控制的是 ,其權重像 般增長。改報 、普通平均 或步長加權平均 (權重像 般遞減)都改變了所討論的對象,本證明對它們都不適用。步長加權平均只是凸定理的正確輸出。
常見錯誤
(把雜訊方差當作矩常數)
遞推的平方項是 。以 代替 便丟掉 ,而它在遠離最優點時很大,正如方差例子所示。應使用 ,其中梯度界 須在迭代可到達的範圍內成立。
總結
投影控制實現距離,條件無偏處理一次雜訊項,完整二階矩控制平方餘項。普通凸性給步長加權界;強凸性則支持另一種精確相消,得到遞增權重輸出的 期望差距。
練習
快速檢查
(變步長證明為何應先求和再除以步長?用 及 寫出以 加權的界。)
解答 · 答案
未除步長時,距離項是 ,精確相消;若先除以不同步長,相鄰係數便不同,須另作分析。直接得到 ,輸出按步長加權。
快速檢查
(取 、,列出步長及正規化的強凸平均權重,並指出在 相消的係數。)
解答 · 答案
步長為 ,即 ;正規化輸出權重為 ,即 。在 , 的加權負係數為 , 的正係數為 ,恰好消去。輸出含 ,不含 。
快速檢查
(條件雜訊方差至多九,均值梯度範數至多四。求足夠的 ,以及 、 時的最佳凸界。)
解答 · 答案
條件置中給 ,即 。步長為 ,最佳期望界為 。這可以保守,並不表示實際誤差就是一。
快速檢查
(在 上最小化 ,驗證邊界最優點與證明使用的強凸內積不等式相容。)
解答 · 答案
最優點為零,導數為一。可行 的差距為 ,而 。因 ,這正好等於差距加 ,即證明所用的強不等式,完全不要求受約束最優點的梯度消失。