完整梯度加總每個訓練例子的貢獻;隨機梯度使用較小的隨機樣本,減少每次更新的工作量,同時引入噪音。我們量化這個噪音,並說明下降論證能及不能保證甚麼。
從有限和抽樣
定義 12.1.1
(小批量梯度與梯度方差)
令 ,其中 可微且 。在固定的當前點 ,獨立均勻地從 有放回抽取 ,其中整數 。對步長 ,定義
處的梯度方差為 。
索引在當前點固定後重新抽取;同一例子可以出現兩次。以下所有期望都以 為條件。
定理 12.1.2
(小批量梯度的無偏性與方差)
以 為條件,
因此 。
證明
(逐次抽樣中心化,再展開平方)
令 。因為 均勻,,所以 ;由 的定義,。又 ,均值的結論隨即成立。
展開 。當 ,兩次抽樣條件獨立,故 。於是期望為 ,再除以 便得 。
最後,。中間項因無偏性期望為零,由此得到 的公式。
證明透視
獨立性與有放回抽樣用在哪裏
證明靠三個要素。用完整梯度中心化,使每一項均值為零,這用到每個索引均勻。抽樣條件獨立,使所有交叉項消失,方差在乘以 之前就是 。有放回抽樣正好提供這種獨立性;若不放回,交叉項為負, 時方差要乘以 ,取 便恰好回到完整梯度。相反的極端是把同一索引重用 次, 只是一次抽樣,方差仍為 。因子 來自 份獨立的資訊,而不是單單來自取平均。
由光滑性得到期望下降界
定義 12.1.3
(梯度為 Lipschitz)
可微函數 的梯度是 -Lipschitz(其中 ),是指對所有 都有 。
命題 12.1.4
(小批量步的期望下降)
設 的梯度為 -Lipschitz, 為上述小批量步。對每個 ,
特別地,當 ,
證明
(二次上界,再取期望)
對任意兩點 與 ,沿線段應用微積分基本定理,
其中用了柯西–施瓦茨(Cauchy–Schwarz)不等式與 Lipschitz 條件。代入 ,得 。
以 為條件,,且 。取期望即得第一條不等式。當 ,,便得第二條。證明只用了無偏性與二階矩,不需要凸性。
證明透視
哪個假設控制哪一項
線性項需要無偏性:它把帶噪音的內積變成 。二次項才是噪音付出代價之處,因為 並非 的無偏估計,而是多出 。步長限制只用了一次,使 的係數至少為 ;若 ,該係數為負,即使 界也不保證下降。證明從未用到凸性,所以適用於非凸的 ;但也因此只能談梯度的大小,不能談到極小點的距離。
這只是上界,不保證每一步、甚至每一步的期望值都下降。在這些抽樣假設下,較大的批量減小所示方差項,但每次更新需計算更多分量梯度。
完整算一次更新
取 、、,及 。則 、,所以 。兩個分量梯度是 與 ,與 分別相差 和 ,故每個 均有 。
例題 12.1.5
(只抽一個例子的一步)
在 ,取 、,抽得的梯度是 或 ,各概率 。下一點分別是 或 ,因此
定理的第一條不等式,代入 、、,給出 ,與此二次例子完全吻合。簡化界是 ,雖較鬆仍然有效。
例題 12.1.6
(批量為二且出現重複抽樣)
仍取 、,但 。有序對 等可能。 與 各有概率 ,分別給出 與 ; 與 合共概率 ,兩者都給出 。下一點 為 、 或 ,對應目標值 、 與 。因此
的均值為 ,方差為 ,與定理一致。命題的第一條不等式給出 ,同樣精確吻合。要留意的邊界情形是:有放回時 仍然是隨機的,因為 這一對從未看到第二個例子。
反例模式
無偏梯度不一定使目標下降
有人或會認為,只要梯度估計無偏,就保證 。在同一例子的極小點 ,分量梯度為 和 。取 及任意 ,下一點以相等概率為 或 ,兩種情況下目標均由 上升至 。梯度估計無偏,但方差非零,而命題中的方差項正好出現:由於 ,界為 ,且恰好取等。無偏性只控制線性項;要論證下降,還必須控制噪音。
從單步到平均保證
命題 12.1.7
(平均梯度平方界)
設 的梯度為 -Lipschitz,且有下界 。使用固定 走 步,每一步在給定歷史後抽取大小為 的新獨立小批量,且每個迭代點都有 。則
證明
(把條件界逐步疊加)
在 處、以歷史為條件應用上一命題的第二條不等式,再用全期望性質取總期望,得 ;因為 而每一步只增加有限的量,所有期望都有限。移項並對 求和,函數值相消:
兩邊乘以 即得結論。
左邊是梯度範數平方的期望之平均,並非每個迭代點或到全域最優點距離的界。固定步長下第二項不一定隨 增長而消失。若要其他類型的保證,需要凸性、更強假設或不同步長安排;上述計算並未建立它們。
例題 12.1.8
(二次例子中的平均界)
沿用上面的例子,取 、、。此時 、、、,右邊為 。
現在精確計算左邊。令 。抽得的梯度是 ,其中 等可能,且與過去獨立,所以 。交叉項的期望為零,故 滿足 ,。解為 ;例如 、。對 的平均是 。 時為 , 時為 。
邊界情形是極限:當 ,真實平均趨向 而非零,而界趨向 。固定步長下,噪音下限是真實存在的,且與界的第二項同階,因此這類證明無法使它消失。
常見錯誤
常見錯誤
(梯度無偏,不代表平方範數無偏)
因為 ,容易誤寫 。正確的值是 。在例子的 ,,而抽得的梯度為 ,所以 。光滑性不等式的二次項看到的正是這個多出來的部分。
常見錯誤
(批量變四倍,誤差只減半,不是減為四分之一)
的方差是 ,所以 使方差除以四;但誤差 的典型大小是方差的平方根,只減為一半。把方差的因子當成誤差本身的因子,會高估每多計算一個梯度所換來的好處。
習題
快速檢查
(在例子的 , 是多少?)
算出兩個分量梯度及其平均。
解答 · 答案
在 處,分量梯度為 、,平均為 。偏差的平方都是 ,所以 ,與前面得到的常數 一致。
快速檢查
(獨立有放回抽樣時, 由 變成 , 如何變化?)
使用方差公式。
解答 · 答案
變為四分之一。因此 的均方根誤差只減為一半,而不是四分之一。
快速檢查
(若所有 相同, 是多少?下降界變成甚麼?)
比較每個分量梯度與 。
解答 · 答案
每個 都等於 ,所以對每個 都有 ,不論批量多大都有 。命題便給出確定性的下降 。
快速檢查
(平均梯度界是否保證最後一個迭代點有小梯度?)
留意左邊對甚麼取平均。
解答 · 答案
單憑此界不行;它限制的是所有迭代點的期望之平均。在 、 的二次例子中,即使 ,對每個 也都大於 ,所以最後一個迭代點的梯度在期望意義下同樣不小。