動機
基本隨機梯度在解附近仍可能有噪音。不同記錄各自偏好的參數不一樣,即使平均梯度為零,單項梯度也不消失。逐步減小步長能壓低噪音,卻也減慢移動。方差縮減採另一策略:偶爾算完整參考梯度,再用它修正便宜的抽樣方向。修正應保留期望,同時抵消參考點已能解釋的隨機變動。
本節推導一個完整快照方法及其凸性收斂證明,通常稱為 SVRG。名稱不是核心;估計量才是:在現時位置與固定快照,使用同一抽取項算梯度,相減後加完整快照梯度。兩次必須用同一索引;若獨立抽兩個索引,便改了噪音結構,不能套原來的抵消論證。
固定預條件器則改變哪些方向算長、哪些梯度算大。適當選擇可把拉長的二次問題調整得均衡;沒有依據的選擇也可使步長證明失效。因此我們同時交代單項光滑界及採用的幾何。
定義
定義 7.1.1
(平均強凸的有限和目標)
設 ,定義域為 。每項可微、凸,且梯度全域 Lipschitz,共同有效常數為 。另設 為 -強凸,,極小點為 。強凸的意思是
所以 ,且極小點唯一。每個單項凸是額外假設,不能只從平均強凸推出。
定義 7.1.2
(快照輪)
每輪固定快照 ,算 ,從 開始。內步重新獨立均勻抽取 ,然後
做 步後,下一快照取平均 。
輸出規則是證明的一部分;改用最後內步,需要另一論證。期望適當地給定快照及先前抽樣;在這些資訊固定後,新索引仍然均勻,才能使用條件無偏。
定理 / 命題
定理 7.1.3
(修正方向無偏且噪音消失)
固定 ,均勻抽 ,取 。則 ,且
當 ,方向恰為完整梯度,與索引無關;當兩者均為 ,方向為零,即使個別項梯度仍非零。
定理 7.1.4
(完整一輪的收縮)
在上述凸性假設下取 ,新快照為指定內步平均,則
尤其 、 給 。做 輪後,期望目標差不多於初始的 。它不斷言每一次實現的內步均單調改善。
上述整輪不等式其實在 都成立。要收縮則須 ;較嚴格的 令 ,所以可以透過足夠大的輪長度達到收縮。
證明思路
證明
(減去切平面與中心化)
對一項減去在 的切平面,得 。凸性使 是 的極小點,梯度仍為 -Lipschitz。使用光滑上界,沿負梯度走 ,得到 。對項取平均,再用 ,即有
把 寫成現時項梯度相對於 的差,減去快照同類差的中心化版本。兩向量之差的範數平方不多於兩者平方各乘二;中心化亦不增加二階矩。在 各使用前式,便得第一定理。直接取期望則得無偏。這裏限制的是二階矩,不要把它與精確噪音方差混稱。
證明透視
為甚麼先減去切平面
不等式 只關於所用函數的最小值,而一般而言 並非在 取最小值。減去切平面不改變梯度差 ;分項凸性正是在這裏使用,用來保證 是 的極小點。由於 ,各 的平均就是 ,所以界回到目標差距。第二個想法是把 拆成在 的部分和在 的中心化部分:初等不等式 加上中心化,便給出常數 。
證明
(整輪距離的伸縮求和)
收縮證明先展開更新後的距離平方:
條件無偏把中間項的 換成 ,凸性給出 ,二階矩界則控制最後一項。合起來得到
整輪加總並捨去非負最後距離。初始距離由強凸限制為初始目標差的 倍。凸性又使平均位置的目標不多於平均目標值,除以 即得 。代入指定參數,兩項各不多於四分之一。每輪先給定隨機快照再重用論證,便得到跨輪期望界。
證明透視
整輪證明中每項假設各用一次
每項假設都在一個可辨認的位置進入。給定過去後重新均勻抽取的索引,使交叉項 的期望變成 ,而 的凸性把它限制為 。單項凸與光滑只透過二階矩界進入,同時產生因子 及快照項 。強凸只用了一次,就是以 限制 ;這正是 第一項的來源。伸縮求和能夠閉合,是因為最後距離非負、可以捨去,而 的凸性把內步目標差的平均化為平均位置的目標差。最後內步沒有這樣的不等式,所以輸出規則屬於定理的一部分。
單項凸看似只是技術條件,因為沒有它程式照樣可以執行。下例顯示二階矩界本身會失效。
反例模式
一個凹單項足以破壞二階矩界
斷言:若平均 強凸且每項 -光滑,即使沒有單項凸,第一定理的界仍成立。取 、、、。兩項都是 -光滑,故 ; 是 -強凸,;但 是凹函數。在 、 時,方向 取值 或 ,故 。所聲稱的界是 ,反而較小。失效的一步是 :此處 ,在 左邊是 ,右邊是 。單靠光滑只得到 ,需要另外分析;恢復原界的正是單項凸這個假設。
例題詳解
例題 7.1.5
(可直接執行的有限和方法)
程式的第 項為對角二次函數 。平均 Hessian 是 ,所以 ;每項最大曲率至多十二,所以 。精確極小點為 。注意每次更新前先累積平均,與定理的輸出規則完全相同。
import math
import random
data = [([1.0, 4.0], [1.0, 0.0]),
([2.0, 8.0], [0.0, 1.0]),
([3.0, 12.0], [-1.0, -1.0])]
def gradient(i, x):
h, center = data[i]
return [hj * (xj - aj) for hj, xj, aj in zip(h, x, center)]
def objective(x):
return math.fsum(0.5 * math.fsum(hj * (xj - aj)**2
for hj, xj, aj in zip(h, x, center))
for h, center in data) / len(data)
def svrg(start, epochs=5, seed=5):
n, d = len(data), len(start)
L, mu = 12.0, 2.0
eta, steps = 1 / (10 * L), math.ceil(50 * L / mu)
rng = random.Random(seed)
snapshot = list(start)
history = [objective(snapshot)]
for _ in range(epochs):
full = [0.0] * d
for i in range(n):
gi = gradient(i, snapshot)
full = [a + b / n for a, b in zip(full, gi)]
x = list(snapshot)
average = [0.0] * d
for _ in range(steps):
average = [a + b / steps for a, b in zip(average, x)]
i = rng.randrange(n)
now, old = gradient(i, x), gradient(i, snapshot)
direction = [a - b + c for a, b, c in zip(now, old, full)]
x = [a - eta * b for a, b in zip(x, direction)]
snapshot = average
history.append(objective(snapshot))
return snapshot, history
answer, history = svrg([3.0, 3.0])
optimum = [-1/3, -1/6]
assert objective(answer) >= objective(optimum) - 1e-12
print([round(x, 6) for x in answer])
print([round(value - objective(optimum), 6) for value in history])
斷言只檢查精確極小值的下界,不是證明所有種子收斂。所示執行的最後位置約為 [-0.332576, -0.166667];包括起點的目標差約為 51.222222, 0.552737, 0.020938, 0.000538, 0.000022, 0.000001。這核查某個實作及種子,不能反過來估計普遍收縮率。理論使用理想獨立均勻索引,實際生成器提供可重做示範。程式從不以觀察到的下降代替對凸性及光滑性的核查。
例題 7.1.6
(抵消在極小點仍存在的噪音)
取 、,平均 的極小點是零,但兩項梯度在此為負一及正一。普通抽樣梯度仍有變動,修正後卻是 ,任何索引都等於完整梯度。這個特殊問題每處都精確抵消;若兩次抽不同索引,偏移量不再抵消,噪音便重新出現。
例題 7.1.7
(預條件器消除已知二次拉伸)
,普通下降步長一半,第二座標被乘負四十九,因而不穩定。取 ,用 ,同一步長使兩座標都減半,目標變成四分之一。此預條件器使用已知曲率資訊,不是任意目標都安全的裝飾。
第三例提示了固定預條件器作用的一般描述。
概念視角幾何
預條件就是座標變換
固定對稱正定 的意義很清楚:令 、。鏈式法則給變換梯度 ,在新座標用同一算法,恰為原座標的預條件更新。二次可微時,新 Hessian 是 。其上下界才是新光滑與強凸常數;只改善平均 Hessian,不自動限制每個抽樣項的上界。
距離證明也隨座標改變。新座標的距離平方 是原座標差向量的 -二次型,而不是原歐氏(Euclidean)距離;因此不能保留舊常數,卻把更新矩陣任意換掉。目標函數值仍對應同一位置,內步平均也因線性變換而相容,但解讀距離及步長時必須使用同一幾何。
拉伸例子的新 Hessian 是單位矩陣。一般問題建立或應用 可能很貴;對角近似便宜而省空間,稠密精確逆卻昂貴。比較時應包含前處理及每次應用成本,不能只報告迭代減少。若預條件器隨時間改變,亦不再是此處一個固定座標變換。
精度規劃與停止證書
若初始差至多 ,希望期望差不多於 ,指定參數下 輪足夠。配合每輪成本,項梯度次數為 級別,常數已由定理明示。初始界及曲率常數仍須證明;看短暫軌跡後挑樂觀數值,不能支持這個預算。
若完整梯度已可用,還有逐點的證書。
命題 7.1.8
(強凸下的梯度證書)
若 為 -強凸,極小點為 ,則對每一點 ,
證明
(最小化二次下界模型)
強凸在 給出:對每個 ,。右邊是 的二次函數,在 取最小值 。因此對每個 都有 ;取 即得結論。
所以快照完整梯度可在不知道精確極小值時,認證目標差已小。這是確定性不等式,亦適用於隨機產生的位置。把完整梯度換成單次噪音方向便失去證書;浮點下極小的計算梯度也須留意相消與精度,不能任意解釋到無限細容差。
常見錯誤
常見錯誤
(替換或移動快照梯度)
完整快照梯度是估計量的一部分,不能隨便換成噪音小批次還引用原條件公式。近似快照方法可能有用,但須新分析。輪內快照也須固定;每步改快照,已改變估計量及證明。
常見錯誤
(只計內步而不計完整掃描)
不快取的每輪需 次項梯度,額外工作向量為 ,不包括原數據。保存全部快照項梯度可減少重算,卻要 空間。效果取決於完整掃描、內步、記憶體及目標精度的平衡。定理提供保守而透明的充分預算,不是普遍最快的參數。
常見錯誤
(在強凸以外引用線性收斂率)
強凸屬指定目標及參數化的性質。過度參數化可能有多個解,神經網絡目標常非凸。迴圈仍可運行,但此全域線性收斂證明不能認證它。把實驗可行與定理涵蓋範圍分開,是正確使用方法的一部分。
總結
快照修正保留平均梯度,並在解附近抵消單項噪音。單項凸與光滑限制二階矩,平均強凸則給指定平均輸出的整輪收縮。固定預條件是座標變換,須重新核查常數。算法、輸出規則、假設及成本應放在同一論證中。
練習
快速檢查
(第二例取 、,分別計算兩個索引的修正方向,以及步長 的新位置。)
解答 · 答案
快照完整梯度為 。第一項修正為 ,第二項為 。新位置皆為 。同一索引的偏移量以相反符號出現,才有精確抵消。
快速檢查
(取 、、、。求定理中的收縮係數;多少輪足以使期望差上界至少縮小三十二倍?)
解答 · 答案
、。第一項是 ,第二項為 ,故 。五輪給出期望因子 ,並不保證每條個別軌跡恰好按此比率改善。
快速檢查
(對 及 ,求變換後的 Hessian,並從 以步長 比較普通及預條件梯度下降。)
解答 · 答案
。普通更新為 ,預條件後則是 ,兩座標減半、二次目標變為四分之一。原座標的步長對第二方向的曲率過大,導致劇烈放大。
快速檢查
(為何使用最後內步、在兩個單項梯度中獨立抽索引,或隨時改變的預條件器,都不能只引用本節整輪證明?各指出受影響的一步。)
解答 · 答案
證明用凸性把平均位置的目標限制於內步目標的平均,對最後一步沒有同一結論。同索引相減提供二階矩界所需的抵消,獨立索引改變了噪音計算。固定預條件器提供單一座標變換與一組常數,變動的幾何則需要新的控制。即使程式看來相似,每種修改仍要獨立的定理。