確率的勾配法

確率的勾配降下法（Stochastic Gradient Descent, SGD）は、経験リスクが標本の和の形で表されるとき、各ステップで一標本またはミニバッチの損失の勾配を用いてパラメータを更新する最適化アルゴリズムである。全標本の勾配（バッチ勾配）を用いる勾配降下法に比べて一ステップあたりの計算量が $O(1/n)$ または $O(B/n)$（$B$：バッチサイズ）に削減され、大規模データへの適用を可能にする。確率的勾配は真の勾配の不偏推定量であり、この性質が収束保証の基礎となる。

つまり、確率的勾配降下法は、機械学習やディープラーニングのモデルを学習させる際、誤差を最小化するように「重み（パラメータ）」を効率よく調整する手法のことである。

通常の方法（バッチ学習）は、すべての学習データを使って計算してから重みを更新するが、SGDには以下の特徴がある。

1つ（または少数）のデータで更新: データを1つ選ぶたびに、その場で少しずつ重みを更新する
スピードが速い: データ全体を読み込まなくても更新が進むため、大規模なデータセットでも高速に学習できる
局所解を回避しやすい: 1つずつのデータに基づいて計算するため動きに「ノイズ（ランダムさ）」が混じる。これが逆に、最適解ではない「行き止まり（局所解）」から抜け出す助けになる

設定

パラメータ空間 $\Theta \subseteq \mathbb{R}^d$、損失関数 $\ell: \Theta \times \mathcal{X} \times \mathcal{Y} \to \mathbb{R}_+$、 i.i.d. 標本 $\mathcal{D}_n = \{(\boldsymbol{x}_i, y_i)\}_{i=1}^n$ に対して、経験リスク（有限和目的関数）を

\[ R_n(\boldsymbol{\theta}) = \frac{1}{n} \sum_{i=1}^n \ell(\boldsymbol{\theta}; \boldsymbol{x}_i, y_i)\]

と定義する。最小化問題 $\min_{\boldsymbol{\theta} \in \Theta} R_n(\boldsymbol{\theta})$ を考える。真のリスク（期待損失）は

\[ R(\boldsymbol{\theta}) = \mathbb{E}_{(\boldsymbol{x},y) \sim P}\bigl[\ell(\boldsymbol{\theta}; \boldsymbol{x}, y)\bigr]\]

であり、大数の法則より $R_n(\boldsymbol{\theta}) \to R(\boldsymbol{\theta})$（$n \to \infty$、各点）が成立する。学習の目標は $R_n$ の最小化を通じて $R$ を小さくすることにある。

SGD の更新則と不偏性

時刻 $t$ において添字 $i_t \sim \mathrm{Uniform}(\{1,\ldots,n\})$ を一様ランダムに選び、 SGD の更新則を

\[ \boldsymbol{\theta}^{(t+1)} = \boldsymbol{\theta}^{(t)} - \eta_t \nabla_{\boldsymbol{\theta}} \ell(\boldsymbol{\theta}^{(t)}; \boldsymbol{x}_{i_t}, y_{i_t})\]

と定義する（$\eta_t > 0$ は学習率）。確率的勾配の条件付き期待値は

\[ \mathbb{E}_{i_t}\bigl[ \nabla_{\boldsymbol{\theta}} \ell(\boldsymbol{\theta}^{(t)}; \boldsymbol{x}_{i_t}, y_{i_t}) \,\big|\, \boldsymbol{\theta}^{(t)} \bigr] = \nabla R_n(\boldsymbol{\theta}^{(t)})\]

が成立する。すなわち確率的勾配は真の勾配（経験リスクの勾配）の不偏推定量であり、この性質が SGD の収束解析の出発点となる。バッチ勾配降下法との違いは、各ステップで $O(n)$ ではなく $O(1)$ の勾配計算のみを要する点にある。

ミニバッチ SGD

サイズ $B$ のミニバッチ $\mathcal{B}_t \subseteq \{1,\ldots,n\}$（$|\mathcal{B}_t| = B$）をランダムに選ぶミニバッチ SGD の更新則は

\[ \boldsymbol{\theta}^{(t+1)} = \boldsymbol{\theta}^{(t)} - \frac{\eta_t}{B} \sum_{i \in \mathcal{B}_t} \nabla_{\boldsymbol{\theta}} \ell(\boldsymbol{\theta}^{(t)}; \boldsymbol{x}_i, y_i)\]

である。確率的勾配の分散は $\mathrm{Var}(\nabla \ell_i) / B$ に低減され、 $B=1$ が純粋な SGD、$B=n$ がバッチ勾配降下法に対応する。バッチサイズ $B$ の増加により勾配の分散が低減され収束が安定化するが、並列計算の効率と収束速度のトレードオフが存在する。現代の深層学習では $B = 32 \sim 512$ 程度が実用上広く用いられる。

収束速度解析

以下では確率的勾配の分散を $\mathbb{E}\bigl[\|\nabla \ell(\boldsymbol{\theta}; \boldsymbol{x}_i, y_i) - \nabla R_n(\boldsymbol{\theta})\|^2\bigr] \leq \sigma^2$ と仮定する。収束速度は目的関数の構造（凸性・強凸性・平滑性）に依存する。

凸・$L$-平滑の場合

$R_n$ が凸かつ $L$-平滑（$\nabla R_n$ が $L$-リプシッツ連続）のとき、学習率を $\eta_t = \eta / \sqrt{t}$（$\eta > 0$）と設定すると、 $T$ ステップ後の Cesàro 平均 $\bar{\boldsymbol{\theta}}_T = \frac{1}{T}\sum_{t=1}^T \boldsymbol{\theta}^{(t)}$ について

\[ \mathbb{E}\bigl[R_n(\bar{\boldsymbol{\theta}}_T)\bigr] - R_n(\boldsymbol{\theta}^*) \leq \frac{C}{\sqrt{T}} \left(\frac{\|\boldsymbol{\theta}^{(0)} - \boldsymbol{\theta}^*\|^2}{\eta} + \eta \sigma^2 \right) = O\!\left(\frac{1}{\sqrt{T}}\right)\]

が成立する（$C$ は定数、$\boldsymbol{\theta}^*$ は最適解）。この $O(1/\sqrt{T})$ の収束率は一次法の情報論的下限に一致し、最適である。

$\mu$-強凸・$L$-平滑の場合

$R_n$ が $\mu$-強凸（$\mu > 0$）かつ $L$-平滑のとき、学習率を $\eta_t = 2/(\mu(t + 1))$ と設定すると

\[ \mathbb{E}\bigl[\|\boldsymbol{\theta}^{(T)} - \boldsymbol{\theta}^*\|^2\bigr] \leq \frac{4L\sigma^2}{\mu^2 T} = O\!\left(\frac{1}{\mu T}\right)\]

が成立する。強凸の場合の $O(1/(\mu T))$ の収束率は凸の場合の $O(1/\sqrt{T})$ より速く、強凸定数 $\mu$ が大きいほど（条件数 $\kappa = L/\mu$ が小さいほど）高速に収束する。

非凸の場合

$R_n$ が非凸（深層ニューラルネットワーク等）のとき、大域最適解への収束は一般に保証されない。代わりに停留点（Stationary Point、$\nabla R_n(\boldsymbol{\theta}) = \boldsymbol{0}$）への収束を議論する。 $R_n$ が $L$-平滑のとき、学習率 $\eta_t = \eta$ （定数）のもとで

\[ \frac{1}{T}\sum_{t=1}^T \mathbb{E}\bigl[\|\nabla R_n(\boldsymbol{\theta}^{(t)})\|^2\bigr] \leq \frac{2(R_n(\boldsymbol{\theta}^{(0)}) - R_n^*)}{\eta T} + \eta L \sigma^2 = O\!\left(\frac{1}{\sqrt{T}}\right)\]

が成立する（右辺を $\eta \propto 1/\sqrt{T}$ で最適化）。すなわち平均勾配ノルムの二乗は $O(1/\sqrt{T})$ で零に収束し、近似停留点への収束が保証される。なお非凸問題では鞍点（Saddle Point）が存在する場合があるが、確率的勾配のノイズが鞍点からの脱出を助ける効果があることが経験的・理論的に示されている（ただし保証の強さはランドスケープの構造に依存する）。

収束速度まとめ

目的関数の性質	収束の意味	収束速度	最適学習率
凸・$L$-平滑	$\mathbb{E}[R_n(\bar{\boldsymbol{\theta}}_T)] - R_n^*$	$O(1/\sqrt{T})$	$\eta_t \propto 1/\sqrt{t}$
$\mu$-強凸・$L$-平滑	$\mathbb{E}[\\|\boldsymbol{\theta}^{(T)} - \boldsymbol{\theta}^*\\|^2]$	$O(1/(\mu T))$	$\eta_t = 2/(\mu(t+1))$
非凸・$L$-平滑	$\frac{1}{T}\sum_t \mathbb{E}[\\|\nabla R_n(\boldsymbol{\theta}^{(t)})\\|^2]$	$O(1/\sqrt{T})$	$\eta_t \propto 1/\sqrt{T}$（定数）

汎化誤差との関係

SGD が最小化するのは経験リスク $R_n(\boldsymbol{\theta})$ であるが、学習の真の目標は真のリスク $R(\boldsymbol{\theta})$ の最小化にある。 汎化ギャップ（Generalization Gap）を

\[ \mathrm{GenGap}(\boldsymbol{\theta}) = R(\boldsymbol{\theta}) - R_n(\boldsymbol{\theta})\]

と定義する。VC 次元 $h$ を持つ仮説空間において、確率 $1-\delta$ で

\[ R(\hat{\boldsymbol{\theta}}) \leq R_n(\hat{\boldsymbol{\theta}}) + \sqrt{\frac{h\left(\ln\dfrac{2n}{h} + 1\right) + \ln\dfrac{4}{\delta}}{n}}\]

が成立する（$h \leq n$ を仮定）。右辺第二項が複雑度ペナルティであり、 $h/n$ が大きいほど汎化ギャップの上界が大きくなる。 SGD はパラメータの軌跡を通じて暗黙の正則化（Implicit Regularization）効果を持つことが知られており、例えば線形モデルでは SGD の解が最小ノルム解 $\hat{\boldsymbol{\theta}} = X^\top(XX^\top)^{-1}\boldsymbol{y}$ に収束することが示されている。深層学習では SGD の暗黙の正則化が汎化性能に本質的に寄与すると考えられているが、その理論的解明は現在も進行中である。

正則化と SGD の統合

正則化付き目的関数

\[ F(\boldsymbol{\theta}) = R_n(\boldsymbol{\theta}) + \lambda \Omega(\boldsymbol{\theta})\]

を SGD で最小化する場合、$\Omega$ の微分可能性によって更新則が異なる。

$\Omega$ が微分可能（例：$\ell_2$ 正則化）の場合：

\[ \boldsymbol{\theta}^{(t+1)} = \boldsymbol{\theta}^{(t)} - \eta_t \bigl( \nabla_{\boldsymbol{\theta}} \ell(\boldsymbol{\theta}^{(t)}; \boldsymbol{x}_{i_t}, y_{i_t}) + \lambda \nabla \Omega(\boldsymbol{\theta}^{(t)}) \bigr)\]

$\ell_2$ 正則化（$\Omega = \|\boldsymbol{\theta}\|^2$）では $\nabla \Omega = 2\boldsymbol{\theta}$ であり、更新則は 重み減衰（Weight Decay） $\boldsymbol{\theta}^{(t+1)} = (1 - 2\lambda\eta_t)\boldsymbol{\theta}^{(t)} - \eta_t \nabla \ell_{i_t}(\boldsymbol{\theta}^{(t)})$ と等価となる。

$\Omega$ が非平滑（例：$\ell_1$ 正則化）の場合： $\Omega = \|\boldsymbol{\theta}\|_1$ は $\boldsymbol{\theta} = \boldsymbol{0}$ で微分不可能であるため、劣微分を用いた劣勾配法（Subgradient Method）または 近接確率的勾配法（Proximal SGD）を用いる：

\[ \boldsymbol{\theta}^{(t+1)} = \mathrm{prox}_{\eta_t \lambda \|\cdot\|_1}\!\left( \boldsymbol{\theta}^{(t)} - \eta_t \nabla \ell(\boldsymbol{\theta}^{(t)}; \boldsymbol{x}_{i_t}, y_{i_t}) \right)\]

近接写像 $\mathrm{prox}_{\eta\lambda\|\cdot\|_1}$ はソフト閾値処理 $[\mathcal{S}_{\eta\lambda}(\boldsymbol{v})]_j = \mathrm{sign}(v_j)\max(|v_j|-\eta\lambda, 0)$ として閉形式で計算でき、スパース解を誘導する。純粋な劣勾配法では $\Omega$ の劣勾配を加算するが、近接 SGD は反復ごとに近接写像を適用するため収束が速く、スパース性も強く誘導される。

分散低減法

SGD の $O(1/\sqrt{T})$ 収束率（凸の場合）はバッチ勾配降下法の $O(1/T)$（凸）や $O((1-\mu/L)^T)$（強凸）より遅い。この原因は確率的勾配の分散 $\sigma^2$ であり、 分散低減法はこの分散を漸近的にゼロに低減することでバッチ法と同等の収束速度を $O(1/n)$ の計算量で達成する。

SVRG（Stochastic Variance Reduced Gradient；Johnson–Zhang, 2013）： 外側ループで全勾配 $\nabla R_n(\tilde{\boldsymbol{\theta}})$ を計算し、内側ループで分散補正された確率的勾配 \[ \tilde{\boldsymbol{g}}_t = \nabla \ell(\boldsymbol{\theta}^{(t)}; \boldsymbol{x}_{i_t}, y_{i_t}) - \nabla \ell(\tilde{\boldsymbol{\theta}}; \boldsymbol{x}_{i_t}, y_{i_t}) + \nabla R_n(\tilde{\boldsymbol{\theta}}) \] を用いる。$\mathbb{E}[\tilde{\boldsymbol{g}}_t] = \nabla R_n(\boldsymbol{\theta}^{(t)})$ かつ $\boldsymbol{\theta}^{(t)} \approx \tilde{\boldsymbol{\theta}}$ のとき分散が $O(\|\boldsymbol{\theta}^{(t)} - \tilde{\boldsymbol{\theta}}\|^2)$ に収縮する。$\mu$-強凸・$L$-平滑のもとで線形収束 $O((1-\mu/(10L))^T)$ を達成する。
SAGA（Defazio et al., 2014）： 各標本の最新勾配をテーブルに記録し、分散補正項を構成する。 SVRG と異なり外側ループが不要でオンライン設定にも適用可能。 $\mu$-強凸のもとで線形収束を達成し、実装が単純である。
SAG（Schmidt et al., 2017）： SAGA の前身。有偏推定量を用いるが低メモリで動作する。

適応的学習率法

パラメータの各座標によって勾配の規模が大きく異なる場合、全座標に同一の学習率を用いる SGD は非効率になる。 適応的学習率法は座標ごとに学習率を調整する。

AdaGrad（Duchi et al., 2011）： 累積二乗勾配 $G_j^{(t)} = \sum_{s=1}^t (g_j^{(s)})^2$ を用いて \[ \theta_j^{(t+1)} = \theta_j^{(t)} - \frac{\eta}{\sqrt{G_j^{(t)} + \epsilon}} g_j^{(t)} \] 頻度の低い特徴に大きな学習率を割り当て、スパースな勾配に有効。 $G_j^{(t)}$ が単調増加するため学習率が消滅する問題がある。
RMSProp（Hinton, 2012）： 累積二乗勾配の指数移動平均 $v_j^{(t)} = \rho v_j^{(t-1)} + (1-\rho)(g_j^{(t)})^2$ を用いて学習率の消滅を緩和する。
Adam（Adaptive Moment Estimation；Kingma–Ba, 2015）： 勾配の一次・二次モーメントの指数移動平均をともに追跡する： \[ m_j^{(t)} = \beta_1 m_j^{(t-1)} + (1-\beta_1)g_j^{(t)}, \quad v_j^{(t)} = \beta_2 v_j^{(t-1)} + (1-\beta_2)(g_j^{(t)})^2 \] バイアス補正済み推定量 $\hat{m}_j^{(t)} = m_j^{(t)}/(1-\beta_1^t)$、 $\hat{v}_j^{(t)} = v_j^{(t)}/(1-\beta_2^t)$ を用いて更新する： \[ \theta_j^{(t+1)} = \theta_j^{(t)} - \frac{\eta}{\sqrt{\hat{v}_j^{(t)}} + \epsilon}\hat{m}_j^{(t)} \] 典型的には $\beta_1 = 0.9$、$\beta_2 = 0.999$、$\epsilon = 10^{-8}$ を用いる。深層学習の実践的標準手法として広く用いられるが、凸問題での収束保証は SGD より弱い場合がある（AMSGrad による修正版が提案されている）。

学習率スケジューリング

収束理論より、$\eta_t \to 0$ かつ $\sum_t \eta_t = \infty$、 $\sum_t \eta_t^2 < \infty$（Robbins–Monro 条件）を満たす学習率スケジュールのもとで、 SGD は凸問題において確率的に最適解に収束する。実践的に広く使われるスケジュールを示す。

ステップ減衰： 一定のエポック数ごとに学習率を定数倍（例：$0.1$ 倍）する。実装が単純で深層学習で広く用いられる。
指数減衰： $\eta_t = \eta_0 \cdot \gamma^t$（$\gamma \in (0,1)$）。強凸問題での線形収束と整合するが、長期的に学習率が消滅する。
多項式減衰（$1/\sqrt{t}$ または $1/t$）： 凸・強凸の収束保証と理論的に整合する。
ウォームアップ付きコサインアニーリング： 最初に学習率を漸増（ウォームアップ）した後にコサイン関数に従い減衰させる。 Transformer 系モデルの学習で標準的に用いられる。

まとめ

確率的勾配降下法は、有限和目的関数の確率的不偏勾配を用いることで $O(1)$ の計算量で各ステップの更新を実現する最適化アルゴリズムである。凸・$L$-平滑のもとで $O(1/\sqrt{T})$、$\mu$-強凸のもとで $O(1/(\mu T))$ の収束速度が理論的に保証され、いずれも一次法の情報論的下限と整合する。ミニバッチ化により分散を低減し、SVRG・SAGA 等の分散低減法は強凸のもとでバッチ法と同等の線形収束をサンプルあたり $O(1)$ の計算量で達成する。 AdaGrad・RMSProp・Adam 等の適応的手法は座標ごとの学習率調整により非等方な損失関数における収束を加速する。近接 SGD は $\ell_1$ 正則化との組み合わせによりスパース解を誘導し、学習率スケジューリングは理論的収束保証と実践的性能を橋渡しする。 SGD の暗黙の正則化効果は深層学習における汎化性能の理論的解明において中心的な未解決問題の一つであり、最適化・統計学・情報理論を横断する研究が続いている。

Mathematics is the language with which God has written the universe.

正則化とスパース推定線形モデルと一般化線形モデル回帰分析と正則化ロジスティック回帰指数型分布族