動機
經驗風險最小化指出目標,卻未說明如何到達。即使假設類的統計性質良好,計算問題仍可能十分龐大。對有限項損失的平均,可以每次遍歷全部觀察以計算完整梯度,也可以隨機選一個觀察來估計梯度。前者每步工作較多;後者引入需要長期控制的波動。比較算法時,必須問在甚麼條件及計算成本下,能得到甚麼保證。
目的地亦有不同含義。對可微凸函數,零梯度識別全域最小點;對非凸函數,小梯度可能只表示接近駐點,甚至位於極大點附近。另一方面,把訓練損失降至很低,不等於證明總體風險很小。最優化與泛化相關,但回答不同問題,以下會保持這個區分。
證明的核心是一個至比較點的平方距離。展開其變化會出現內積,而凸性把內積連到目標差距。光滑性則直接控制函數值的變化。這些恆等式說明了為何隨機方法需要平均,也說明無偏梯度的單步更新為何未必令損失下降。
定義
定義 2.1.1
(凸性與光滑性)
可微函數 為凸,若
若 且梯度滿足
便稱梯度為 -Lipschitz,或稱 為 -光滑。
凸性說明切平面在全域的位置;光滑性限制梯度變化速度,並不蘊涵凸性。若函數二次連續可微,一致的 Hessian 算子範數界足以保證光滑。對稱半正定矩陣 所定義的凸二次函數,可取正的 ;若全部曲率為零,任意正上界亦可。
確定性梯度下降是 ,其中 固定。對非空閉凸集 上的隨機方法,初始點 選為確定值。以 表示第 步前已知的全部隨機資訊, 對它可測。梯度估計器 須滿足
第二項界控制完整二階矩,並非只控制方差。投影更新為 ,其中 是 中與 歐幾里得(Euclid)距離最近的點。非空、閉及凸在有限維保證投影存在且唯一。若 且二階矩界沿迭代仍成立,便可省略投影。
若 ,每步重新均勻抽取指標 ,則 無偏。「隨機」一詞本身並不保證均勻或條件獨立。若抽樣概率是 ,正確無偏估計須改為 。
概念視角分析
投影步是線性模型加鄰近懲罰的最小點
配方可得
每一步只在由 控制的距離內信任抽樣梯度給出的線性模型,並保持可行。這樣寫時,步長是對靠近當前點的權重,這正是兩個證明都追蹤平方距離 的原因。
定理/命題
定理 2.1.2
(光滑下降與凸目標的速率)
設 在 可微且 -光滑。若 ,則
若 亦凸、在 取得最小值,且 ,則對 有
定理 2.1.3
(無偏且二階矩有界的投影 SGD)
設 在 可微且凸, 是它在 上的最小點,並滿足上述估計器條件。令 、。固定 時,
若 ,取 ,上界便是 。
第二個定理不需要光滑性,但其估計器假設比無偏更強,應在實際問題中核對。指定總步數 後,這個步長在同一次運行中保持不變;不能把它當作遞減步長的定理,也沒有因此證明每個迭代幾乎必然收斂。
證明思路
確定性證明以光滑性得到下降,以凸性得到差距。
證明
(下降不等式,再加望遠鏡式距離)
令 ,積分 的導數,並減去一次項:
代入 即得下降不等式。在非駐點, 保證嚴格下降。較窄的範圍 令距離證明更簡單。
凸性給 。與下降界合併,得
展開新的平方距離,右邊正是上述內積減去 。把 至 相加,距離項望遠鏡式消去。函數值單調下降,所以最後差距乘 不超過全部差距之和;再捨去非負的終點距離,便得確定性速率。
隨機證明不能依賴單調下降,所以只保留距離論證。
證明
(投影、條件化與平均)
投影亦保留所需的距離不等式。若 ,沿 至任意 的線段作最小化,得到 。展開距離便有 。令 ,得
給定 後,目前點及比較點已固定;條件無偏性把內積中的 換成真梯度。凸性提供目標差距,二階矩條件控制最後一項。取總期望並相加,得到
最後由凸性,。因此定理控制的平均明確包括 至 ,不能無聲改成最後迭代。
證明透視
每個估計器假設只進入一項
隨機證明完全沒有用到光滑性;唯一追蹤的量是 。投影一步需要 非空、閉且凸,並需要 :這樣 不會令任何點離 更遠,所以展開時可忽略投影。展開平方得到兩個隨機項。交叉項 由條件無偏性處理,這要求給定 時 已知;二次項 由二階矩界處理,這就是單有方差界不夠的原因。
凸性用了兩次:一次把 化成差距 ,另一次經 Jensen 不等式由差距的平均過渡到平均點的差距。關鍵一步是距離項可以望遠鏡式消去,而不需要 單調——雜訊步本來就沒有單調性。代價是結論關乎 ,而不是 。
沒有凸性時仍能說甚麼
若光滑函數有下界 ,在 下,下降不等式仍可相加為
這個結論沒有用凸性,只控制駐定程度,未控制全域最優差距。 在零點梯度為零,卻比全域最小值高一;它雖非整條實線上光滑有界曲率的例子,已顯示邏輯問題。全域光滑的例子是 :由零點開始便停在值為二的全域極大點。小梯度定理不能排除這種初始化。
反例模式
沒有凸性,差距速率便失效
聲稱:對有最小點 的 -光滑函數及 ,梯度下降滿足 。取 ,它有 ,故為 -光滑;取 、。由於 ,對每個 都有 ,且 。所聲稱的界是 ,當 時已小於 。下降不等式與梯度範數界在此仍然成立;只有差距速率需要凸性假設。
如何理解隨機界的兩項
固定步長時,距離項隨運行時間減少,二階矩項則隨步長增加。小步長減弱單次雜訊的作用,卻需要更多步才能離開初始點。指定總步數的選擇,是平衡這個上界的兩項,並非聲稱實際軌跡每步恰好遵從上界。
凸集亦保證平均點可行。若可行集是非凸離散集合,平均可行點可能不再可行;非凸投影也可能不唯一,且不滿足證明用的比較距離界。若不知道 ,可以用已知上界代替,例如有界可行集的直徑。所得保證可能保守,但常數的來歷清楚。
所有期望均同時涵蓋此前抽到的指標及目前的新雜訊。先給定歷史,再取總期望,並非形式上的多寫一步:它確保目前位置雖然隨機,對當步分析仍是已知量。若某抽樣規則使用歷史而改變各指標概率,就必須按真正的條件概率重新檢查無偏性及二階矩;不能繼續沿用均勻抽樣的計算。
例題詳解
例題 2.1.4
(曲率決定安全步長)
考慮 ,、。最小值為零,。取 ,誤差遞推矩陣是 ,故 、,函數值依次為 。第一座標改善較慢。若改取 ,第二誤差乘數變成 ,便會交替放大。負梯度方向正確,不代表任意位移長度都合適。
例題 2.1.5
(無偏不代表雜訊軌跡單調)
令 、,其中每步新雜訊獨立且等概率取 。記 、。固定 時,
展開平方後,交叉項的條件期望為零,便得遞推。在精確最小點,只要 ,下一步必定離開。取 ,極限均方誤差為 ,期望損失為 。這描述固定步長的最後迭代,並不違反隨總步數調小步長的平均迭代保證。
例題 2.1.6
(有限和的抽樣計算)
在某點,兩個分量梯度為 ,平均梯度為 。均勻抽樣的均值是 、方差是九。若第一項以概率 被抽中,仍直接用原分量梯度,均值卻變成 ,方向錯誤。重要性加權後,兩個可能值是 ,均值回到 ,方差則為 ,比九更大。恢復無偏不等於改善效率。在同一目前點平均 個獨立無偏梯度,雜訊方差除以 ;共同均值的平方範數並不因此除以 。
常見錯誤
常見錯誤
(把無偏隨機步當作下降步)
無偏只控制條件均值,單次估計未必接近真梯度,負估計方向亦未必下降;雜訊純量例子在精確最小點以概率一離開。條件化不可省略,因目前參數依賴以往的隨機指標。只在第一步無條件均值正確,並不保證後續無偏。
常見錯誤
(以方差界代替二階矩界)
SGD 定理要求完整二階矩界 。單有方差界仍容許非常大的確定性梯度,不能直接替代。若梯度範數不超過 、雜訊條件方差不超過 ,則 ,所以 足夠。緊緻可行集上連續且有界的分量梯度常能提供所需條件。
常見錯誤
(只按迭代次數比較兩種速率)
完整有限和梯度約需 次分量計算,單次 SGD 則只需一次。只比較迭代次數可能誤導;反過來,每步較便宜也不證明必定更快達到精度。幾何、方差、實作及所需精度都會影響結果。
總結
光滑性控制函數值變化,凸性把內積連到全域差距,條件無偏性則讓距離證明在期望下成立。平均及步長平衡處理隨機波動。這些都是最優化保證;所得預測器的泛化仍須另行分析。
練習
快速檢查
(求第一個二次例子對所有初始點收斂的精確固定步長區間,並說明最大邊界的情況。)
解答 · 答案
誤差乘數為 、,兩者絕對值均小於一等價於 。在 ,第二乘數為 ,非零誤差交替而不縮小。定理所用的 足以證明簡單速率,卻不是此二次函數的精確穩定區間。
快速檢查
(在 SGD 定理中取 、、,求建議步長及界。若期望差距須不超過 ,此界要求多少步?)
解答 · 答案
步長為 ,上界 亦為此值。由 得 。這裏使用的是初始距離及完整二階矩的界,不能把方差估計直接當作 。
快速檢查
(在雜訊純量例子中取 、、、。求 、 及期望目標值的極限。)
解答 · 答案
遞推是 ,且 ,故 、。極限為 ,期望目標值趨向 。初始期望損失是 ;這個雜訊水平令它上升至固定步長的雜訊下限。
快速檢查
(同一點的兩個獨立估計雜訊均值為零、方差為 ,求它們平均的方差。為甚麼不能直接把這個計算套用於相鄰兩步 SGD?)
解答 · 答案
獨立性令交叉協方差為零,故平均的方差是 。相鄰步的梯度在不同的隨機點計算,後一點依賴前一步的雜訊,並非同一固定點的兩個獨立估計,所以需要重新作條件分析。