動機
許多計算問題都化為最小化大量記錄的平均損失。參數向量描述模型或近似,每筆記錄貢獻一項損失。完整梯度可能要掃描全部數據,但粗略方向往往已足以作一次有用更新。小批次方法正是在方向準確度與取得方向的成本之間取捨。
這個取捨同時涉及數學與電腦。平均更多獨立抽取的梯度,可降低方差;但它也消耗更多記錄求值、可能需要更大的緩衝,並減少固定預算內可更新參數的次數。硬件處理中等大小矩陣,也可能比逐項小運算有效率。因此,最小或最大批次都不自動是最佳選擇。
必須先說清想改善甚麼。降低期望梯度平方、降低一步後目標值、每秒處理更多記錄,以及符合記憶體限制,是不同的結論。數據管線較快,不能證明優化較快;駐點界也不能證明非凸目標已達全域最小值。
定義
定義 3.1.1
(有限和目標與有放回小批次梯度)
參數 ,考慮有限和目標:
每個 皆可微。完整梯度在同一參數處求全部 項。大小為 的小批次梯度,從 獨立均勻地有放回抽取 ,並計算
此定義容許索引重複。無放回抽取子集是另一種設計,方差會有有限母體修正。把數據洗牌後依次使用又不同:給定前面抽到的記錄,同一輪後續索引不再是獨立均勻抽樣。使用證明前,不能只因都叫「小批次」便忽略差異。
定義 3.1.2
(-光滑)
採用歐氏(Euclidean)範數與內積。設常數 。若可微目標 對所有 都有 ,稱 為 -光滑。
沿線段積分梯度,並限制梯度變化,可得上二次模型:
光滑不等於凸。光滑函數仍可有多個局部極小值、鞍點,甚至沒有有限下界。後面的定理因此另外假設 是有限下界,而不把它混入光滑的定義。
定義 3.1.3
(隨機迭代與條件無偏)
隨機迭代為 ,固定步長 。令 包含初始狀態及第 步抽批次之前的全部隨機資訊,因此給定 時現時參數 已知。若每個 都有 ,稱梯度估計條件無偏。
這比含糊地說「整個過程平均方向正確」更精確,也正是下降論證所需的假設。
定理 / 命題
命題 3.1.4
(獨立小批次降低條件方差)
在固定參數處定義
上述有放回小批次滿足
若在固定 後重新獨立抽取批次,同樣恆等式在第 步條件成立。
此命題只以更新噪音衡量批次。實際上,同一個 還進入其他幾本賬。
概念視角算法
同一批次大小,不同的比較分母
從統計看,增大 降低每次更新的獨立梯度噪音。從算法預算看,每次參數移動耗用 次項求值。從系統看,它改變緩衝、矩陣運算效率及通訊頻率。比較方法前要選符合問題的分母:更新次數、記錄求值、經過時間或記憶體。只報告每次更新改善,會把取得該更新的成本隱藏起來。
第二個結果把方差恆等式變成關於多次更新的保證。
定理 3.1.5
(光滑隨機迭代的駐點界)
設 全域 -光滑,且有下界 。取確定的 、、。假設每步條件無偏,並有條件噪音界 ,相關期望有有限矩。則
結論限制平均期望梯度平方,並不斷言每次迭代改善、最後一次最好,或已到達全域極小值。
證明思路
證明
(獨立中心化抽樣的交叉項消失)
每個隨機項梯度的期望都是完整梯度。把 個向量中心化,展開總和的範數平方。獨立且均值為零,令交叉內積的期望消失;剩下 項共貢獻 ,再除以 ,即得第一個定理。此論證直接適用於向量,而不只是逐座標的說法。
證明
(條件期望下的一步下降,再望遠鏡相消)
對第二個定理,在光滑上界中代入 ,並給定 取期望。條件無偏處理線性項,中心二階矩恆等式則給出
因 ,梯度平方前的下降係數至少是 。再取期望,從零加到 ,目標值項望遠鏡相消。最後期望目標值不少於 ,移項便得所需界。參數依賴先前隨機性,所以必須用條件期望:新批次要在當前參數處仍然無偏。
證明透視
駐點界中每個假設的用處
光滑性只用一次,就是在 、 處的二次上界;它把隨機的一步化為含 的線性項與含 的二次項。關鍵一步是先對 取條件期望。在此條件下 固定,無偏性把線性項變成 ,噪音界則把二次項拆成 。步長限制 只用來令淨係數 至少為 ;換成其他固定比例只改變常數,但係數必須保持為正。望遠鏡求和消去所有中間目標值,下界 只用一次,控制最後一項。沒有 ,右邊會含 ,它可以無界增大。
固定正步長下,噪音項不會只因增加 而消失。減小步長可減噪音項,但在固定迭代預算下會放大暫態項。有正噪音時,平衡兩項建議步長尺度為 ,仍須受 限制,比例常數也依賴目標差距與方差。當常數未知,這個理論建議並不是可以直接使用的全知參數選擇。
若另行獨立均勻地從 選一個迭代索引,其期望梯度平方正好等於左邊。這給出平均界的明確輸出解釋。小梯度只是一次駐點判準;要換成函數值或全域最佳性保證,還需額外結構。
例題詳解
例題 3.1.6
(看得見梯度噪音的一維損失)
取 、。平均是 ,極小點為 ,光滑常數 。兩個項梯度是 、,均值為 ,相對均值偏差為 ,故任何位置都有 。
在 ,以步長 作完整梯度更新,得到 ,目標由 降至 。若只均勻抽一項,更新值為 或 ,各佔一半,目標分別為 、,期望為 。
批次大小 的更新噪音方差為 。因目標是二次函數,更新後期望恰為 ; 時為 。相同步長下,較大批次改善一步的期望,卻花更多項求值。在極小點,兩個項梯度仍是 :完整梯度為零,不代表隨機梯度也消失。
例題 3.1.7
(比較預算,而非只比較更新次數)
同一目標從 出發,初始差距為 ,可取 。設 、、,駐點界為 。暫態與噪音項分別為 、;此上界不必精確貼近真實表現。
若項求值預算固定為 , 可作四百次更新,相同步長下界為 。 只能作二十五次,界為 。這些特定選擇中,中等批次的上界較小,但比較的是上界,不是精確結果或普遍最佳批次。
代入 ,暫態項成為 ,隨 增大;噪音項卻隨 減少。改步長會改變比較。若硬件吞吐量依賴批次,固定時間預算又不同於固定項求值預算。
例題 3.1.8
(記憶體與透明的時間模型)
一百萬筆稠密特徵,各有一千維,以八位元組數值儲存。只保存特徵矩陣便需 位元組,即十進制八 GB。二百五十六筆的批次緩衝需 位元組;參數或累積梯度向量各需 。標籤、優化器狀態、臨時陣列及執行環境仍有額外開銷,以上不能當成總記憶體承諾。
作為示意而非測量,設一步成本 毫秒,分別代表固定開銷及逐筆工作。 與 的吞吐量約為每毫秒 與 筆;模型中隨批次增大,上限趨近每毫秒一百筆。這不代表無限大批次最好:緩衝繼續增大,同一記錄預算內參數移動的次數則減少。
同步數據平行時,每個節點可先累積長度 的梯度再通訊,而非傳送全部原始記錄。但拓樸、延遲及慢節點仍影響時間。所有節點的貢獻要在同一參數版本處計算,才符合上述簡單估計量;使用過時參數的梯度需要另一套分析。
常見錯誤
駐點定理的步長假設很容易被當成技術細節,其實不然。
反例模式
步長過大,即使沒有噪音也破壞上界
聲稱:駐點界對任何固定步長都成立。取 、,則 、、,迭代是確定性的。取 、,更新為 ,故 。 時左邊為 ,右邊卻是 。所聲稱的不等式不成立,迭代值更以 增長。修正後的敘述保留假設 ,它保證下降係數為正。
常見錯誤
(改變抽樣分佈卻不重新加權)
均勻抽樣也是估計量的一部分。若第 項以正概率 被抽取,直接使用其梯度,期望便是概率加權目標的梯度。要對原來均勻目標無偏,單樣本應改為 。但極小概率可帶來很大方差;無偏不等於有效率。概率為零的記錄更不能由此式恢復。
反例模式
互不相同的索引不會給出同一方差
錯誤說法:任意 個抽樣索引都給出小批次方差 。在第一個例題中,、。有放回且 時,方差是 ;例如概率為 的批次 給出 ,偏差為 。無放回時,大小為二的批次只有 ,所以 恰好成立,方差為 。修正後,對均勻抽取的 個不同索引,應使用有限母體公式 (),此處正好給出 。
常見錯誤
(把定理套用到已修改的迭代)
梯度截斷、動量、自適應縮放、無放回抽樣及非同步更新,都改變了被分析的迭代。它們可能有用,但此定理沒有自動涵蓋。檢查一個例子的目標是否下降,也不能證明整個隨機程序滿足條件無偏與噪音假設。
總結
獨立有放回小批次給出無偏梯度,其方差按 降低。光滑性、有限下界及條件噪音控制共同產生平均駐點界。較大批次以更多工作與記憶體換取每步較少噪音。有效的計算比較要先說明統計假設、輸出判準與資源預算。
練習
練習 3.1.9
(固定參數處,三個純量項梯度為 。求完整梯度、均勻單項梯度的方差,以及四次獨立有放回小批次平均的方差。)
基礎
解答 · 答案
完整梯度是 。偏差 的平方平均為 ,故單項方差為 。四個獨立抽樣的平均方差為 。這依賴有放回與獨立;從三筆記錄抽四個不同索引,並不是題設的程序。
練習 3.1.10
( 採用確定性完整梯度更新。找出對所有非零起點都嚴格減少目標的正步長範圍,並與定理的充分限制比較。)
基礎
解答 · 答案
更新為 ,非零起點的目標比為 。因此恰在 嚴格下降; 不變,更大則上升。定理採用較嚴格的充分範圍 ,以確保證明所用的下降係數。
練習 3.1.11
(駐點界中取 、、、、、。計算此界並指出暫態項與噪音項。結論是否保證全域最小值?)
核心
解答 · 答案
暫態項是 ,噪音項是 ,總界為 。步長滿足 。若其他假設也成立,結論限制平均期望梯度平方;沒有額外適當凸性等結構,小梯度不能證明全域最佳。
練習 3.1.12
(兩個項梯度為 與 ,抽樣概率為 與 。求不加權梯度的期望與對均勻目標的兩個重要性修正值,驗證無偏,並解釋為何兩個概率皆須為正。)
核心
解答 · 答案
均勻目標的梯度為 ,但不加權期望是 。修正值為 與 ,期望為 。若某項概率為零,它永不被觀測,且除以概率沒有定義;無法用此方案對其任意貢獻作無偏恢復。