確率的勾配降下法（かくりつてきこうばいこうかほう、英: stochastic gradient descent, SGD）は、連続最適化問題に対する勾配法の乱択アルゴリズム。バッチ学習である最急降下法をオンライン学習に改良したアルゴリズムである。目的関数が微分可能な和の形であることを必要とする。
背景

下記の和の形の目的関数を最小化する問題を扱う。 Q ( w ) = ∑ i = 1 n Q i ( w ) {\displaystyle Q(w)=\sum _{i=1}^{n}Q_{i}(w)}

パラメータ w ∗ {\displaystyle w^{*}} はQ(w) を最小化するように推定する。典型的には、 Q i {\displaystyle Q_{i}} は i 番目の訓練データ。

古典的な統計学において、和の最小化問題は、最小二乗問題や最尤推定問題などにあらわれる。一般的なケースでは、和を最小化する推定量はM推定量と呼ぶ。しかしながら、Thomas S. Fergusonの例[1]などで示されるように、いくつかの最尤推定の問題において、最小解ではなく局所解を要求するだけでも制限が厳しすぎると長い間認識され続けてきた。それゆえ、現代の統計理論家は最尤関数の停留点(微分がゼロになる点)を考慮する事が多くなった。

和の最小化問題は経験損失最小化（英語版）の問題にも現れる。 Q i ( w ) {\displaystyle Q_{i}(w)} の値が i 番目の訓練データであるならば、Q(w) が経験損失である。

上記の関数 Q を最小化する際、標準的な最急降下法（バッチ学習）では、下記の反復を繰り返す。 w := w − η ∇ Q ( w ) = w − η ∑ i = 1 n ∇ Q i ( w ) {\displaystyle w:=w-\eta \nabla Q(w)=w-\eta \sum _{i=1}^{n}\nabla Q_{i}(w)}

η {\displaystyle \eta } はステップサイズと呼ばれる。機械学習においては学習率（英語版）とも呼ばれる。

確率分布がパラメータが一つの指数型分布族などで、勾配の総和の計算が、小さな計算量で出来てしまう事もあるが、一つ一つの勾配を計算して総和を取らないといけない事も多い。そのような場合、和の全体ではなく、和の一部分だけを計算する事で、1回の反復の計算量を小さくする事ができる。これは大規模な機械学習の問題で効果的である[2]。
反復法

確率的勾配降下法（オンライン学習）では、Q(w) の勾配は、1つの訓練データから計算した勾配で近似する。

上記の更新を1つ1つの訓練データで行い、訓練データ集合を一周する。収束するまで訓練データ集合を何周もする。一周するたびに訓練データはランダムにシャッフルする。AdaGrad などの適応学習率のアルゴリズムを使用すると収束が速くなる。

擬似コードでは、確率的勾配降下法は下記になる。パラメータ w {\displaystyle w} と学習率 η {\displaystyle \eta } の初期値を選ぶwhile 収束するか所定の反復回数まで反復する do Q i {\displaystyle Q_{i}} （訓練データ）をランダムにシャッフルする for each i = 1, 2, ..., n do w := w − η ∇ Q i ( w ) {\displaystyle \!w:=w-\eta \nabla Q_{i}(w)}

全てではないが複数の訓練データで勾配を計算する方法をミニバッチと言う。この方法は、コンピュータのSIMDを有効活用でき計算を高速化できる。また、複数の訓練データを使うので収束がよりなめらかになる事もある。

確率的勾配降下法の収束性は凸最適化と確率近似の理論を使い解析されている。目的関数が凸関数もしくは疑似凸関数であり、学習率が適切な速度で減衰し、さらに、比較的緩い制約条件を付ければ、確率的勾配降下法はほとんど確実に最小解に収束する。目的関数が凸関数でない場合でも、ほとんど確実に局所解に収束する[3][4]。これは Robbins-Siegmund の定理による[5]。

Q i {\displaystyle Q_{i}} （訓練データ）がランダムにシャッフルされる事により、確率的に局所解にはまりにくくなる効果がある。
学習率の調整方法および変種

基本的な確率的勾配降下法に対して多くの改良が提案されている。特に、機械学習において、ステップサイズ（学習率）の調整は重要問題として認識されている。学習率を大きくしすぎると発散し、小さくしすぎると収束まで遅くなる。
確率的近似法

1951年に Herbert Robbins と Sutton Monro が発表[6]。学習率をイテレーション回数の逆数で減衰させる方法。Robbins-Monro法とも言われる。 η t = η 0 t {\displaystyle \eta _{t}={\frac {\eta _{0}}{t}}}
Nesterovの加速勾配降下法

1983年に Yurii Nesterov が発表[7]。 x 0 = w 0 x t = w t − 1 − η ∇ Q i ( w t − 1 ) w t = x t + t − 1 t + 2 ( x t − x t − 1 ) {\displaystyle {\begin{aligned}x_{0}&=w_{0}\\x_{t}&=w_{t-1}-\eta \nabla Q_{i}(w_{t-1})\\w_{t}&=x_{t}+{\frac {t-1}{t+2}}(x_{t}-x_{t-1})\end{aligned}}}