動機
有限步數的界告訴我們:預先指定更新次數後,平均迭代點有多準確;但它本身沒有說明一條無限長的運行軌跡是否會停靠在最小點。要回答後者,我們需要控制所有未來更新累積的雜訊,而非只控制某一步的雜訊。遞減學習率提供一個折衷:步長之和必須無限,讓算法有足夠機會繼續修正初始誤差;步長平方之和則必須有限,以控制條件方差的累積。
以下結論是單一迭代序列以概率一收斂,與平均迭代點的期望界不同。我們在強凸及二階矩有界的條件下證明一個實用版本;這些是充分條件,不代表隨機梯度法只在此情況下才收斂。
定義
定義 23.1.1
(強凸性與投影隨機梯度格式)
設 是 的非空閉凸集。可微函數 稱為 -強凸,其中 ,若對所有 ,
令 是代表第 次更新前資訊的濾過,並令 對 可測。給定確定的正步長 ,投影更新與隨機梯度的條件為
其中 ,而 是 中最接近 的點。
這裏 在下一時刻可測。上界要求的是完整條件二階矩,而不只是 的方差。即使隨機步越出可行集,投影仍保證更新點可行。假設 在 上於 取得最小值;下面的引理說明強凸性令此點唯一。
定理/命題
第一個結果把強凸性化為收斂證明真正使用的不等式。最小點位於邊界、梯度不為零時,它仍然成立。
引理 23.1.2
(約束最小點處的強單調性)
設 在 上可微且 -強凸, 是 在 上的最小點。則 是唯一最小點,並且對每個 ,
主定理把這個不等式與步長序列的兩個條件結合起來。
定理 23.1.3
(個別迭代點的收斂)
在上述條件下,設 是確定的,並且
則 幾乎必然成立。例如,、 恰在 時同時符合兩個條件。
在無界區域上,完整二階矩有界並非自動成立:強凸二次函數的梯度便無界。我們可以在有界可行集上證明矩有界,或另用假設增長條件的定理。此外,幾乎必然收斂並不提供有限樣本置信區間,也不自動給出普遍收斂速度。
證明或證明思路
先證明引理,再證明定理。
證明
(最優性條件加上兩條強凸不等式)
對 及 , 的凸性給出 ,所以函數 在 取最小值,其右導數非負:
把強凸不等式由 到 寫一次、由 到 再寫一次,然後相加。函數值互相抵消,剩下
再加上最優性不等式便得引理。至於唯一性,由 到 的強凸不等式連同最優性條件給出:當 時,。
定理的證明把一切化為純量 。
證明
(一步不等式,再以超鞅預付未來雜訊)
若 且 ,沿 到 的線段最小化到 的距離,得 ;展開 便有 。取 、,
對 取條件期望。由於 對 可測,無偏性把內積中的 換成 ,而矩界控制最後一項。再用引理,並記 ,得到
定義確定的尾和 (因 ,它有限),以及
每個 非負且對 可測;它亦可積,因為 ,而 是常數。利用 ,
由非負超鞅收斂定理, 幾乎必然收斂至有限極限。 中最後一項和式單調不減,又不大於 ,所以收斂;特別地,幾乎必然有 。由於 , 也幾乎必然有有限極限 。若在某個結果上 ,則該處對所有足夠大的 有 ,而 會令 發散。故 幾乎必然成立。
證明透視
一次為所有未來雜訊留出預算
兩個步長條件在不同位置起作用。平方可和只用來令 有限並趨於零; 發散只在最後一行使用,用以排除正的極限。單靠一步不等式不能沿每條軌跡迭代,因為它只在條件期望下成立,而雜訊項 每一步都會出現。
關鍵一步是預付這些雜訊。把全部未來預算 加到 ,吸收每一步的 ;把累積進展 加進去,吸收 ,於是總和成為超鞅。這只因步長是確定的才成立:此時 是已知數, 是適應過程。強凸性經由引理提供進展項,而投影需要 閉且凸,並且 。
這裏使用的標準超鞅定理可由上穿不等式得到:非負超鞅的期望對時間一致有界,因此無限次穿越任何固定有理端點區間的概率為零;它的上、下極限必相同。我們將定理用於一維記帳過程,並沒有假設迭代點本身是超鞅。
例子
例題 23.1.4
(帶雜訊的二次函數化為樣本平均)
令 、、、,其中獨立的 以相同概率取 和 。取 ( 時為平凡資訊)及 。隨機梯度條件無偏、,而在 上 。未投影的遞推式 經歸納給出
右邊落在 ,所以投影從不改變它。其期望為零,且 :交叉項因獨立及中心化而消失。定理保證它幾乎必然收斂到零;二階矩公式則是不同運行之間的有限時間平均。
例題 23.1.5
(選取冪次步長)
若 ,由 級數判別法, 而 。其他假設也成立時便可使用定理。相反, 不符合平方可和條件, 不符合步長和無限的條件。充分條件失效本身不表示每個採用該步長的問題都發散。
例題 23.1.6
(經投影到達的邊界最小點)
令 、,使用精確梯度 ,並取 、。此時 ,在 上 ,約束最小點是 ,而 。第一步給出 ;此後 ,所以對每個 都有 。若不投影,同一遞推給出 ,之後 :它停在 以外的無約束最小點。在約束問題中,迭代點收斂,但梯度趨於 而非 。
常見錯誤
反例模式
步長總和有限可以令誤差停留
即使沒有雜訊,取 、、 及 ,便有 。迭代點收斂到嚴格為正的乘積 。事實上,對 有 ,所以其對數之和有限。每一步都降低目標值,但有限的總移動量不能保證到達最小點。
固定步長則有相反的困難。對沒有觸發投影的上述帶雜訊二次例子,固定 時,,其極限為 。這個雜訊底限說明固定步長的最後迭代點不一定以均方收斂。但它不表示所有固定步長問題都失敗:沒有雜訊時結論可以不同。
常見錯誤
(以為極限處梯度必為零)
定理說的是 ,其中 是 上的最小點。若 位於邊界, 未必為零;在邊界例子中它等於 。「隨機梯度足夠小便停止」這類停止規則因而可能永不觸發;證明使用的是引理中的不等式,而不是 。
常見錯誤
(把條件不等式誤讀為逐條軌跡遞減)
不等式 只在條件期望下成立。個別距離可以增大:在帶雜訊的二次例子中 ,但 給出 。因此證明需要超鞅論證,不能沿每條軌跡作確定性遞推。
總結
無限的步長總和提供持續修正;有限的平方和使累積誤差項可求和。條件無偏、完整二階矩有界和強凸性結合超鞅論證,得到各個投影迭代點的幾乎必然收斂。
練習
快速檢查
(對 ,求同時符合兩個步長條件的所有 。乘以 會改變答案嗎?)
解答 · 答案
級數判別法要求第一個和式發散,即 ;第二個和式收斂則要 。因此 。乘以有限正數不改變這兩項判斷。
快速檢查
(在帶雜訊的二次例子中,計算 和 。)
解答 · 答案
,故 。它等於一恰在三個符號均為 時發生,概率為 。
快速檢查
(令 且 。求其約束最小點,並以 對一般 驗證引理的不等式。)
解答 · 答案
最小點是 ,雖然 。對 ,。邊界最優性不等式提供額外的非負項 。
快速檢查
(對常見錯誤部分的固定步長二次遞推,由一維遞推式推導二階矩的極限。)
解答 · 答案
令 ,中心化與獨立性給出 。由 ,幾何係數小於一,其固定點為 。