確率的勾配降下法

データの一部だけで勾配を推定して更新する手法。SGD。

$$x_{k+1}=x_k-\eta \nabla f_{i_k}(x_k)$$

$f_{i_k}$ は無作為に選んだ 1 標本（またはミニバッチ）に対する損失。

なぜ一部で済ませるのか#

機械学習の目的関数は $f(x)=\frac{1}{m}{\sum }_{i=1}^m{f}_i(x)$ という平均の形。 全データで勾配を計算すると 1 回の更新に $𝒪(m)$ かかる。 標本を 1 つ選べば、その勾配は真の勾配の不偏推定量になる。

$$𝔼[\nabla f_i(x)]=\nabla f(x)$$

同じ計算量でずっと多く更新できるので、全体としては速い。 $m$ が数百万のとき、この差は決定的。

起源#

Robbins と Monro が 1951 年に提案した確率的近似が源流。 ノイズのある観測から根を求める枠組みで、 収束のためのステップサイズ条件を与えた。

$$\sum _k{\eta }_k=\infty ,\sum _k{\eta }_k^2<\infty$$

前者は「どこへでも到達できる」、後者は「ノイズが均される」ことを保証する。 ${\eta }_k={\eta }_0/k$ がこれを満たす代表例。 SPSA のゲイン列も同じ枠組みにある。

ノイズの役割#

推定した勾配のばらつきは欠点だけではない。 鞍点や浅い局所解から揺らぎによって抜け出せることがあり、 非凸な深層学習では有利に働くと考えられている。

参考文献#

• Herbert Robbins, Sutton Monro. A Stochastic Approximation Method. The Annals of Mathematical Statistics 22(3), 1951. https://doi.org/10.1214/aoms/1177729586
• Léon Bottou, Frank E. Curtis, Jorge Nocedal. Optimization Methods for Large-Scale Machine Learning. SIAM Review 60(2), 2018. https://doi.org/10.1137/16M1080173
• Ian Goodfellow, Yoshua Bengio, Aaron Courville. Deep Learning, Chapter 8. MIT Press, 2016. https://www.deeplearningbook.org/