コンテンツにスキップ
Rikai

勾配降下法：勾配はなぜ「最も急な坂」なのか

情報科学機械学習の数学 第4章学部無料公開約 46 分2026-08-23

対象読者: 学部 1 年の多変数微分積分（偏微分・テイラー展開）と線形代数（固有値・対称行列）を学び、本テーマ第 1〜3 章の内容を読んだ人。最適化の専門知識は仮定しません。

前提となる記事:ロジスティック回帰：シグモイドと交差エントロピーを最尤推定から導く

生 Markdown

0. この記事の要点

Section titled “0. この記事の要点”

霧の中で山を下りるとき、見えるのは足もとの傾きだけです。それでも「いま一番急に下っている向きへ少し進む」ことを繰り返せば、谷底に近づけそうです。機械学習で損失を小さくする学習は、まさにこれをしています。この記事では、その向きがなぜ「一番急」と言えるのか、一歩をどれだけ大きくしてよいのか、データが多いときにどう安く計算するのかを、式と数値例で確かめます。読み終えると、学習率を決める理屈と、学習が遅くなる原因を自分で説明できるようになります。

  • 勾配 ∇f(w)\nabla f(\boldsymbol{w}) は「ff を 1 次で最もよく近似するときの係数ベクトル」です。この 1 次近似から、長さ 1 のベクトルのうち ff を最も速く減らす向きが −∇f(w)/∥∇f(w)∥-\nabla f(\boldsymbol{w})/\|\nabla f(\boldsymbol{w})\| であることが従います（定理 3.2）。証明の要はコーシー・シュワルツの不等式です。
  • 学習率 η\eta は「1 次近似をどこまで信用するか」を表す量です。勾配が LL-リプシッツ連続（勾配の変わる速さに上限 LL があること）なら 0<η<2/L0 < \eta < 2/L のとき必ず関数値が下がり、η=1/L\eta = 1/L なら TT 回の反復で min⁡k∥∇f(wk)∥2≤2L(f(w0)−f⋆)/T\min_k \|\nabla f(\boldsymbol{w}_k)\|^2 \le 2L\bigl(f(\boldsymbol{w}_0) - f_\star\bigr)/T が保証されます（定理 4.5）。
  • 二次関数では収束の速さがヘッセ行列の条件数 κ\kappa（最大固有値と最小固有値の比）だけで決まります。最良の学習率を選んでも 1 歩あたりの縮小率は (κ−1)/(κ+1)(\kappa-1)/(\kappa+1) にしかならず、細長い谷でジグザグが起きるのはこれが理由です（命題 5.1）。
  • ロジスティック回帰の損失は ∇f(w)=1NXT(p−y)\nabla f(\boldsymbol{w}) = \frac{1}{N}X^{\mathsf{T}}(\boldsymbol{p} - \boldsymbol{y}) という簡潔な勾配を持ち、ヘッセ行列は常に半正定値なので凸です（命題 6.1）。ここから L=λmax⁡(XTX)/(4N)L = \lambda_{\max}(X^{\mathsf{T}}X)/(4N) という学習率の具体的な目安が出ます。
  • 確率的勾配降下法は、この勾配を BB 個のサンプルだけで置き換える方法です。得られる推定量は不偏で、分散はちょうど 1/B1/B に比例して小さくなります（命題 7.2）。「安いが揺れる勾配」を大量に使うという発想が、大規模学習を成り立たせています。

1. 動機：解が閉じた式で書けないとき

Section titled “1. 動機：解が閉じた式で書けないとき”

線形回帰と最小二乗法では、二乗誤差 f(w)=12∥Xw−y∥2f(\boldsymbol{w}) = \frac{1}{2}\|X\boldsymbol{w} - \boldsymbol{y}\|^2 を最小にする w\boldsymbol{w} が、正規方程式（定理 3.3）［線形回帰と最小二乗法］ XTXw=XTyX^{\mathsf{T}}X\boldsymbol{w} = X^{\mathsf{T}}\boldsymbol{y} を解くだけで求まりました。XTXX^{\mathsf{T}}X が正則なら w⋆=(XTX)−1XTy\boldsymbol{w}_\star = (X^{\mathsf{T}}X)^{-1}X^{\mathsf{T}}\boldsymbol{y} と、答えが一本の式で書けます。これは幸運な例外です。

ロジスティック回帰では事情が変わります。負の対数尤度を最小にする条件は

∑i=1N(σ(⟨w,xi⟩)−yi)xi=0,σ(z)=11+e−z\sum_{i=1}^{N}\Bigl(\sigma(\langle \boldsymbol{w}, \boldsymbol{x}_i\rangle) - y_i\Bigr)\boldsymbol{x}_i = \boldsymbol{0}, \qquad \sigma(z) = \frac{1}{1 + e^{-z}}

でした（交差エントロピー誤差の勾配（定理 5.1）［ロジスティック回帰］）。左辺には未知数 w\boldsymbol{w} が指数関数の中に入っています。これは代数方程式ではなく超越方程式（指数関数のように、多項式では表せない関数を含む方程式）で、一般には w\boldsymbol{w} について解いた形に書き直せません。N=3N = 3 のような小さな例でも、一般にはデータごとに根号や対数を有限回組み合わせた式では書けません。

では諦めるのかというと、そうではありません。方針を変えます。一発で答えを当てるのをやめて、今いる点より少しだけ良い点へ動くことを繰り返すのです。この発想は 1847 年にコーシーが連立方程式の数値解法として書いた短い論文にすでに現れています。彼は「関数 uu を減らしたければ、uu の偏微分係数に比例した量だけ変数を動かせばよい」と述べました。これが勾配降下法です。

現代の深層学習でも、事情は本質的に同じです。ニューラルネットワークの損失関数は数百万個のパラメータについて非線形で、停留点の条件を解くことなど到底できません。できるのは「今の点での勾配を計算し、その逆向きに少し動く」ことだけです。したがってこの章の問いは次の二つに絞られます。

  1. なぜ勾配の逆向きなのか。他の向きではいけないのか。
  2. どれだけ動けばよいのか。動きすぎるとどうなるのか。

以下ではこの二つに、多変数関数のテイラー展開（定理 9.10［多変数関数の微分と偏微分］）を使って正面から答えます。

2. 準備：勾配とは何か

Section titled “2. 準備：勾配とは何か”

多変数関数の微分については多変数関数の微分と偏微分で扱っており、全微分可能性は 定義 4.1［多変数関数の微分と偏微分］ で定義しました。ここではこの章で使う形に整理し直しておきます。鍵は「偏微分を並べたもの」ではなく「1 次近似の係数」として勾配を捉えることです。

定義 2.1（全微分可能性と勾配）↗

U⊂RnU \subset \mathbb{R}^n を開集合、f:U→Rf : U \to \mathbb{R}、w∈U\boldsymbol{w} \in U とします。あるベクトル g∈Rn\boldsymbol{g} \in \mathbb{R}^n が存在して

f(w+h)=f(w)+⟨g,h⟩+r(h),lim⁡h→0r(h)∥h∥=0f(\boldsymbol{w} + \boldsymbol{h}) = f(\boldsymbol{w}) + \langle \boldsymbol{g}, \boldsymbol{h}\rangle + r(\boldsymbol{h}), \qquad \lim_{\boldsymbol{h}\to\boldsymbol{0}}\frac{r(\boldsymbol{h})}{\|\boldsymbol{h}\|} = 0

が成り立つとき、ff は w\boldsymbol{w} で全微分可能であるといい、g\boldsymbol{g} を ff の w\boldsymbol{w} における勾配と呼んで ∇f(w)\nabla f(\boldsymbol{w}) と書きます。ここで ⟨⋅,⋅⟩\langle \cdot,\cdot\rangle は Rn\mathbb{R}^n の標準内積、∥⋅∥\|\cdot\| はそれが定めるユークリッドノルムです。

このとき g\boldsymbol{g} は一意に定まり、その第 jj 成分は偏微分係数 ∂f/∂wj(w)\partial f/\partial w_j(\boldsymbol{w}) に一致します。すなわち

∇f(w)=(∂f∂w1(w), …, ∂f∂wn(w))T.\nabla f(\boldsymbol{w}) = \left(\frac{\partial f}{\partial w_1}(\boldsymbol{w}),\ \ldots,\ \frac{\partial f}{\partial w_n}(\boldsymbol{w})\right)^{\mathsf{T}}.

注意 2.2

一意性と成分表示は定義からすぐに出ます。h=tej\boldsymbol{h} = t\boldsymbol{e}_j（ej\boldsymbol{e}_j は第 jj 標準基底ベクトル、t≠0t \ne 0）と取ると

f(w+tej)−f(w)t=gj+r(tej)t\frac{f(\boldsymbol{w} + t\boldsymbol{e}_j) - f(\boldsymbol{w})}{t} = g_j + \frac{r(t\boldsymbol{e}_j)}{t}

であり、∣r(tej)/t∣=∣r(tej)∣/∥tej∥→0|r(t\boldsymbol{e}_j)/t| = |r(t\boldsymbol{e}_j)|/\|t\boldsymbol{e}_j\| \to 0（t→0t \to 0）ですから、左辺は t→0t\to 0 で gjg_j に収束します。左辺の極限は偏微分係数の定義そのものなので gj=∂f/∂wj(w)g_j = \partial f/\partial w_j(\boldsymbol{w}) です。これが各 jj について成り立つので g\boldsymbol{g} は一意です。

逆は成り立ちません。偏微分が全部存在しても全微分可能とは限らないので、以下では必要に応じて ff が C1C^1 級（偏導関数が存在して連続）であることを仮定します。C1C^1 級なら全微分可能です。

「1 次近似の係数」という読み方を強調しておきます。定義 2.1 が言っているのは、w\boldsymbol{w} の近くでは

f(w+h)≈f(w)+⟨∇f(w),h⟩f(\boldsymbol{w} + \boldsymbol{h}) \approx f(\boldsymbol{w}) + \langle \nabla f(\boldsymbol{w}), \boldsymbol{h}\rangle

という線形の式で ff が近似でき、その誤差は ∥h∥\|\boldsymbol{h}\| より速く 00 に近づく、ということです。勾配降下法はこの近似式だけを頼りに次の一歩を決めます。

定義 2.3（方向微分）↗

u∈Rn\boldsymbol{u} \in \mathbb{R}^n を ∥u∥=1\|\boldsymbol{u}\| = 1 なるベクトルとします。極限

Duf(w)=lim⁡t→0f(w+tu)−f(w)tD_{\boldsymbol{u}}f(\boldsymbol{w}) = \lim_{t \to 0}\frac{f(\boldsymbol{w} + t\boldsymbol{u}) - f(\boldsymbol{w})}{t}

が存在するとき、これを ff の w\boldsymbol{w} における u\boldsymbol{u} 方向の方向微分と呼びます。「u\boldsymbol{u} の向きに進んだときの ff の増加率」を表します。

例 2.4（二乗誤差の勾配を定義から求める）

X∈RN×nX \in \mathbb{R}^{N\times n}、y∈RN\boldsymbol{y}\in\mathbb{R}^N を定数として f(w)=12∥Xw−y∥2f(\boldsymbol{w}) = \frac{1}{2}\|X\boldsymbol{w} - \boldsymbol{y}\|^2 とします。偏微分を成分ごとに計算するのではなく、定義 2.1 の形に整理して勾配を読み取ります。

r=Xw−y\boldsymbol{r} = X\boldsymbol{w} - \boldsymbol{y} とおくと X(w+h)−y=r+XhX(\boldsymbol{w}+\boldsymbol{h}) - \boldsymbol{y} = \boldsymbol{r} + X\boldsymbol{h} ですから、ノルムの二乗を展開して

f(w+h)=12⟨r+Xh, r+Xh⟩=12∥r∥2+⟨r,Xh⟩+12∥Xh∥2=f(w)+⟨XTr, h⟩+12∥Xh∥2.\begin{aligned} f(\boldsymbol{w}+\boldsymbol{h}) &= \tfrac{1}{2}\langle \boldsymbol{r} + X\boldsymbol{h},\ \boldsymbol{r} + X\boldsymbol{h}\rangle \\ &= \tfrac{1}{2}\|\boldsymbol{r}\|^2 + \langle \boldsymbol{r}, X\boldsymbol{h}\rangle + \tfrac{1}{2}\|X\boldsymbol{h}\|^2 \\ &= f(\boldsymbol{w}) + \langle X^{\mathsf{T}}\boldsymbol{r},\ \boldsymbol{h}\rangle + \tfrac{1}{2}\|X\boldsymbol{h}\|^2. \end{aligned}

3 行目では内積の随伴の性質 ⟨a,Xh⟩=⟨XTa,h⟩\langle \boldsymbol{a}, X\boldsymbol{h}\rangle = \langle X^{\mathsf{T}}\boldsymbol{a}, \boldsymbol{h}\rangle を使いました（内積空間を参照）。最後の項は作用素ノルム ∥X∥2\|X\|_2 を使って 12∥Xh∥2≤12∥X∥22∥h∥2\frac{1}{2}\|X\boldsymbol{h}\|^2 \le \frac{1}{2}\|X\|_2^2\|\boldsymbol{h}\|^2 と評価できるので、

12∥Xh∥2∥h∥≤12∥X∥22 ∥h∥⟶0(h→0)\frac{\frac{1}{2}\|X\boldsymbol{h}\|^2}{\|\boldsymbol{h}\|} \le \frac{1}{2}\|X\|_2^2\,\|\boldsymbol{h}\| \longrightarrow 0 \quad (\boldsymbol{h}\to\boldsymbol{0})

となり、確かに o(∥h∥)o(\|\boldsymbol{h}\|) です。よって 定義 2.1 の g\boldsymbol{g} にあたるのは XTrX^{\mathsf{T}}\boldsymbol{r} で、

∇f(w)=XT(Xw−y)=XTXw−XTy.\nabla f(\boldsymbol{w}) = X^{\mathsf{T}}(X\boldsymbol{w} - \boldsymbol{y}) = X^{\mathsf{T}}X\boldsymbol{w} - X^{\mathsf{T}}\boldsymbol{y}.

これを 0\boldsymbol{0} とおいたものが正規方程式です。線形回帰が閉じた形で解けたのは、勾配が w\boldsymbol{w} の一次式だったからだ、と言い直せます。

3. なぜ勾配が「最も急な坂」なのか

Section titled “3. なぜ勾配が「最も急な坂」なのか”

「勾配は最も急な坂の方向を指す」という言い方をよく聞きます。これは比喩ではなく、証明できる主張です。まず方向微分と勾配を結びつけます。

命題 3.1（方向微分は勾配との内積）✓

ff が w\boldsymbol{w} で全微分可能なら、任意の単位ベクトル u\boldsymbol{u} について方向微分 Duf(w)D_{\boldsymbol{u}}f(\boldsymbol{w}) が存在して

Duf(w)=⟨∇f(w),u⟩D_{\boldsymbol{u}}f(\boldsymbol{w}) = \langle \nabla f(\boldsymbol{w}), \boldsymbol{u}\rangle

が成り立ちます。

証明（命題 3.1）

定義 2.1 の式で h=tu\boldsymbol{h} = t\boldsymbol{u}（t≠0t \ne 0）と取ります。すると

f(w+tu)−f(w)=⟨∇f(w),tu⟩+r(tu)=t ⟨∇f(w),u⟩+r(tu)f(\boldsymbol{w} + t\boldsymbol{u}) - f(\boldsymbol{w}) = \langle \nabla f(\boldsymbol{w}), t\boldsymbol{u}\rangle + r(t\boldsymbol{u}) = t\,\langle \nabla f(\boldsymbol{w}), \boldsymbol{u}\rangle + r(t\boldsymbol{u})

です（内積の双線形性を使いました）。両辺を tt で割ると

f(w+tu)−f(w)t=⟨∇f(w),u⟩+r(tu)t.\frac{f(\boldsymbol{w} + t\boldsymbol{u}) - f(\boldsymbol{w})}{t} = \langle \nabla f(\boldsymbol{w}), \boldsymbol{u}\rangle + \frac{r(t\boldsymbol{u})}{t}.

ここで ∥tu∥=∣t∣ ∥u∥=∣t∣\|t\boldsymbol{u}\| = |t|\,\|\boldsymbol{u}\| = |t| ですから

∣r(tu)t∣=∣r(tu)∣∥tu∥\left|\frac{r(t\boldsymbol{u})}{t}\right| = \frac{|r(t\boldsymbol{u})|}{\|t\boldsymbol{u}\|}

であり、定義 2.1 の剰余条件よりこれは t→0t \to 0 で 00 に収束します。したがって右辺は t→0t\to 0 で ⟨∇f(w),u⟩\langle \nabla f(\boldsymbol{w}), \boldsymbol{u}\rangle に収束し、左辺の極限すなわち Duf(w)D_{\boldsymbol{u}}f(\boldsymbol{w}) が存在してその値に等しくなります。

命題 3.1 によって、「どの向きに進むと ff が最も速く減るか」という問いは「単位ベクトル u\boldsymbol{u} のうち内積 ⟨∇f(w),u⟩\langle \nabla f(\boldsymbol{w}), \boldsymbol{u}\rangle を最小にするのはどれか」という代数の問題に置き換わりました。この問題は完全に解けます。

次の定理の証明は、0≤∥αu+a∥20 \le \|\alpha\boldsymbol{u}+\boldsymbol{a}\|^2 という「ノルムの二乗は負にならない」という事実から始まります。αu\alpha\boldsymbol{u} と a\boldsymbol{a} がちょうど逆向きのときだけこれが 00 になるので、内積の下限と、その下限が達成される向きが一度に分かります。

定理 3.2（最急降下方向）✓

ff は w\boldsymbol{w} で全微分可能で ∇f(w)≠0\nabla f(\boldsymbol{w}) \ne \boldsymbol{0} とします。u\boldsymbol{u} が Rn\mathbb{R}^n の単位ベクトル全体を動くとき、

Duf(w) ≥ −∥∇f(w)∥D_{\boldsymbol{u}}f(\boldsymbol{w}) \ \ge\ -\|\nabla f(\boldsymbol{w})\|

が常に成り立ち、等号が成立するのは

u=−∇f(w)∥∇f(w)∥\boldsymbol{u} = -\frac{\nabla f(\boldsymbol{w})}{\|\nabla f(\boldsymbol{w})\|}

のとき、かつそのときに限ります。すなわち ff を最も速く減少させる単位方向はただ一つ存在し、それは勾配の逆向きです。同様に Duf(w)≤∥∇f(w)∥D_{\boldsymbol{u}}f(\boldsymbol{w}) \le \|\nabla f(\boldsymbol{w})\| で、等号は u=∇f(w)/∥∇f(w)∥\boldsymbol{u} = \nabla f(\boldsymbol{w})/\|\nabla f(\boldsymbol{w})\| のときに限ります。

証明（定理 3.2）

a=∇f(w)\boldsymbol{a} = \nabla f(\boldsymbol{w})、α=∥a∥>0\alpha = \|\boldsymbol{a}\| > 0 と略記します。∥u∥=1\|\boldsymbol{u}\| = 1 なる任意の u\boldsymbol{u} に対し、ノルムの二乗は非負なので

0≤∥αu+a∥2=α2∥u∥2+2α⟨u,a⟩+∥a∥2=2α2+2α ⟨a,u⟩0 \le \bigl\| \alpha\boldsymbol{u} + \boldsymbol{a} \bigr\|^2 = \alpha^2\|\boldsymbol{u}\|^2 + 2\alpha\langle \boldsymbol{u}, \boldsymbol{a}\rangle + \|\boldsymbol{a}\|^2 = 2\alpha^2 + 2\alpha\,\langle \boldsymbol{a}, \boldsymbol{u}\rangle

が成り立ちます（∥u∥=1\|\boldsymbol{u}\|=1 と ∥a∥=α\|\boldsymbol{a}\|=\alpha を代入し、内積の対称性を使いました）。両辺を 2α>02\alpha > 0 で割って整理すると

⟨a,u⟩≥−α=−∥∇f(w)∥.\langle \boldsymbol{a}, \boldsymbol{u}\rangle \ge -\alpha = -\|\nabla f(\boldsymbol{w})\|.

命題 3.1 より左辺は Duf(w)D_{\boldsymbol{u}}f(\boldsymbol{w}) ですから、最初の不等式が示せました。

等号成立を調べます。上の計算で等号が成り立つのは ∥αu+a∥2=0\|\alpha\boldsymbol{u} + \boldsymbol{a}\|^2 = 0、すなわち αu+a=0\alpha\boldsymbol{u} + \boldsymbol{a} = \boldsymbol{0} のとき、かつそのときに限ります（ノルムが 00 になるのはゼロベクトルのときだけ）。これは u=−a/α\boldsymbol{u} = -\boldsymbol{a}/\alpha と同値です。逆にこの u\boldsymbol{u} は ∥u∥=∥a∥/α=1\|\boldsymbol{u}\| = \|\boldsymbol{a}\|/\alpha = 1 を満たす単位ベクトルで、

⟨a,−a/α⟩=−∥a∥2α=−α\langle \boldsymbol{a}, -\boldsymbol{a}/\alpha\rangle = -\frac{\|\boldsymbol{a}\|^2}{\alpha} = -\alpha

なので実際に等号を与えます。上界の主張は u\boldsymbol{u} を −u-\boldsymbol{u} に置き換えれば同じ議論で得られます。

定理 3.2 の証明で使ったのはコーシー・シュワルツの不等式の等号条件そのものです（∥αu+a∥2≥0\|\alpha\boldsymbol{u}+\boldsymbol{a}\|^2 \ge 0 を展開する、という標準的な導出をその場で書き下しました）。つまり「勾配が最急降下方向である」ことの数学的な中身は、内積が最大になるのはベクトルが平行なときという事実に尽きます。

系 3.3（勾配は等高線に直交する）✓

ff が w\boldsymbol{w} で全微分可能で ∇f(w)≠0\nabla f(\boldsymbol{w}) \ne \boldsymbol{0} とします。単位ベクトル u\boldsymbol{u} が ⟨∇f(w),u⟩=0\langle \nabla f(\boldsymbol{w}), \boldsymbol{u}\rangle = 0 を満たすこと、すなわち u⊥∇f(w)\boldsymbol{u} \perp \nabla f(\boldsymbol{w}) であることと、Duf(w)=0D_{\boldsymbol{u}}f(\boldsymbol{w}) = 0 であることは同値です。

証明（系 3.3）

命題 3.1 より Duf(w)=⟨∇f(w),u⟩D_{\boldsymbol{u}}f(\boldsymbol{w}) = \langle \nabla f(\boldsymbol{w}), \boldsymbol{u}\rangle なので、一方が 00 であることと他方が 00 であることは同じ主張です。

Duf(w)=0D_{\boldsymbol{u}}f(\boldsymbol{w}) = 0 は「その向きに動いても ff が 1 次のオーダーでは変わらない」ということ、つまり等高線（等位集合。ff の値が一定になる点の集まり）に沿って動くということです。系 3.3 は、勾配が等高線と直交することを意味します。後で描く図では、この直交性が重要な役割を果たします。

注意 3.4

「最も急」という言葉は、どのノルムで歩幅を測るかに依存しています。定理 3.2 はユークリッドノルム ∥u∥=1\|\boldsymbol{u}\| = 1 という制約のもとでの結論です。もし歩幅を別のノルム、たとえば正定値行列 MM による ∥u∥M=⟨u,Mu⟩\|\boldsymbol{u}\|_M = \sqrt{\langle \boldsymbol{u}, M\boldsymbol{u}\rangle} で測れば、同じ議論から最急降下方向は −M−1∇f(w)-M^{-1}\nabla f(\boldsymbol{w}) に比例する向きになります。

MM をヘッセ行列に取ればニュートン法、フィッシャー情報行列に取れば自然勾配法です。「勾配の逆向き」が特別なのは数学的な必然ではなく、パラメータ空間をユークリッド空間だと思うという（暗黙の）約束の結果である、と理解しておくと、後で出てくる各種の改良手法が見通しよくなります。

4. 学習率：1 歩の大きさをどう決めるか

Section titled “4. 学習率：1 歩の大きさをどう決めるか”

方向が決まったので、次は歩幅です。

定義 4.1（勾配降下法）↗

f:Rn→Rf : \mathbb{R}^n \to \mathbb{R} を C1C^1 級とし、初期値 w0∈Rn\boldsymbol{w}_0 \in \mathbb{R}^n と正の数列 (ηk)k≥0(\eta_k)_{k\ge 0} を与えます。

wk+1=wk−ηk∇f(wk)(k=0,1,2,…)\boldsymbol{w}_{k+1} = \boldsymbol{w}_k - \eta_k \nabla f(\boldsymbol{w}_k) \qquad (k = 0, 1, 2, \ldots)

で定まる点列 (wk)(\boldsymbol{w}_k) を求める手続きを勾配降下法（最急降下法）と呼び、ηk\eta_k を学習率（ステップ幅）と呼びます。ηk=η\eta_k = \eta が kk によらないとき、定数学習率であるといいます。

勾配降下法の 1 反復

定理 3.2 が保証しているのは「向きが正しい」ことだけで、η\eta をいくらにしてよいかは何も言っていません。方向微分は t→0t \to 0 の極限の話なので、有限の η\eta で本当に値が下がるかは別問題です。ここを埋めるのが次の平滑性の仮定です。

定義 4.2（L-平滑（勾配のリプシッツ連続性））↗

f:Rn→Rf : \mathbb{R}^n \to \mathbb{R} は C1C^1 級とします。定数 L>0L > 0 が存在して

∥∇f(u)−∇f(v)∥≤L ∥u−v∥(∀ u,v∈Rn)\|\nabla f(\boldsymbol{u}) - \nabla f(\boldsymbol{v})\| \le L\,\|\boldsymbol{u} - \boldsymbol{v}\| \qquad (\forall\, \boldsymbol{u}, \boldsymbol{v} \in \mathbb{R}^n)

が成り立つとき、ff は LL-平滑である（勾配が LL-リプシッツ連続である）といいます。

LL は「勾配がどれだけ急に変わりうるか」の上限です。LL が小さいほど勾配は安定していて、遠くまで 1 次近似が信用できます。逆に LL が大きいと、少し動いただけで坂の向きが変わってしまいます。この直観を定量化するのが次の補題です。

補題の証明の方針は次のとおりです。u\boldsymbol{u} から v\boldsymbol{v} へ直線で進む間の ff の変化を積分で表し、そこから 1 次近似の分を引きます。残るのは「進む途中で勾配が ∇f(u)\nabla f(\boldsymbol{u}) からどれだけずれたか」だけを含む積分で、LL-平滑性がそのずれの大きさを抑えます。

補題 4.3（降下補題）✓

f:Rn→Rf : \mathbb{R}^n \to \mathbb{R} が C1C^1 級かつ LL-平滑ならば、任意の u,v∈Rn\boldsymbol{u}, \boldsymbol{v} \in \mathbb{R}^n に対して

f(v)≤f(u)+⟨∇f(u), v−u⟩+L2∥v−u∥2f(\boldsymbol{v}) \le f(\boldsymbol{u}) + \langle \nabla f(\boldsymbol{u}),\ \boldsymbol{v} - \boldsymbol{u}\rangle + \frac{L}{2}\|\boldsymbol{v} - \boldsymbol{u}\|^2

が成り立ちます。

証明（補題 4.3）

d=v−u\boldsymbol{d} = \boldsymbol{v} - \boldsymbol{u} とおき、φ(t)=f(u+td)\varphi(t) = f(\boldsymbol{u} + t\boldsymbol{d})（t∈[0,1]t \in [0,1]）とします。ff が C1C^1 級で t↦u+tdt \mapsto \boldsymbol{u}+t\boldsymbol{d} が滑らかなので φ\varphi は [0,1][0,1] 上で C1C^1 級であり、連鎖律より

φ′(t)=⟨∇f(u+td), d⟩.\varphi'(t) = \langle \nabla f(\boldsymbol{u} + t\boldsymbol{d}),\ \boldsymbol{d}\rangle .

微分積分学の基本定理（積分の基本定理）を φ\varphi に適用すると

f(v)−f(u)=φ(1)−φ(0)=∫01⟨∇f(u+td), d⟩ dt.f(\boldsymbol{v}) - f(\boldsymbol{u}) = \varphi(1) - \varphi(0) = \int_0^1 \langle \nabla f(\boldsymbol{u} + t\boldsymbol{d}),\ \boldsymbol{d}\rangle \,dt .

ここから 1 次近似の分 ⟨∇f(u),d⟩=∫01⟨∇f(u),d⟩ dt\langle \nabla f(\boldsymbol{u}), \boldsymbol{d}\rangle = \int_0^1 \langle \nabla f(\boldsymbol{u}), \boldsymbol{d}\rangle\,dt を引くと

f(v)−f(u)−⟨∇f(u),d⟩=∫01⟨∇f(u+td)−∇f(u), d⟩ dt.f(\boldsymbol{v}) - f(\boldsymbol{u}) - \langle \nabla f(\boldsymbol{u}), \boldsymbol{d}\rangle = \int_0^1 \bigl\langle \nabla f(\boldsymbol{u} + t\boldsymbol{d}) - \nabla f(\boldsymbol{u}),\ \boldsymbol{d}\bigr\rangle\,dt .

被積分関数をコーシー・シュワルツの不等式で押さえ、続いて 定義 4.2 の LL-平滑性を u+td\boldsymbol{u}+t\boldsymbol{d} と u\boldsymbol{u} に適用します。∥(u+td)−u∥=t∥d∥\|(\boldsymbol{u}+t\boldsymbol{d}) - \boldsymbol{u}\| = t\|\boldsymbol{d}\|（t≥0t \ge 0）ですから

⟨∇f(u+td)−∇f(u), d⟩≤∥∇f(u+td)−∇f(u)∥ ∥d∥≤Lt∥d∥2.\bigl\langle \nabla f(\boldsymbol{u} + t\boldsymbol{d}) - \nabla f(\boldsymbol{u}),\ \boldsymbol{d}\bigr\rangle \le \bigl\|\nabla f(\boldsymbol{u} + t\boldsymbol{d}) - \nabla f(\boldsymbol{u})\bigr\|\,\|\boldsymbol{d}\| \le L t \|\boldsymbol{d}\|^2 .

これを積分すると

∫01Lt∥d∥2 dt=L∥d∥2∫01t dt=L2∥d∥2\int_0^1 L t\|\boldsymbol{d}\|^2\,dt = L\|\boldsymbol{d}\|^2 \int_0^1 t\,dt = \frac{L}{2}\|\boldsymbol{d}\|^2

となり、主張の不等式が得られます。

補題 4.3 は「ff は 1 次近似より上には行かない、ただし高々 L2∥d∥2\frac{L}{2}\|\boldsymbol{d}\|^2 だけ」という主張です。テイラーの定理（平均値の定理とテイラーの定理の 定理 5.3［平均値の定理とテイラーの定理］）の 2 次の剰余項を、2 階微分の存在を仮定せずに LL で押さえた形になっています。この上界を最小にするように 1 歩を決めれば、少なくともその上界の分だけは確実に値が下がります。

系 4.4（1 ステップの減少量）✓

ff が C1C^1 級かつ LL-平滑とし、w′=w−η∇f(w)\boldsymbol{w}' = \boldsymbol{w} - \eta\nabla f(\boldsymbol{w}) とします。このとき

f(w′)≤f(w)−η(1−Lη2)∥∇f(w)∥2f(\boldsymbol{w}') \le f(\boldsymbol{w}) - \eta\left(1 - \frac{L\eta}{2}\right)\bigl\|\nabla f(\boldsymbol{w})\bigr\|^2

が成り立ちます。とくに ∇f(w)≠0\nabla f(\boldsymbol{w}) \ne \boldsymbol{0} かつ 0<η<2/L0 < \eta < 2/L ならば f(w′)<f(w)f(\boldsymbol{w}') < f(\boldsymbol{w}) です。また右辺の減少量 η(1−Lη/2)∥∇f(w)∥2\eta(1 - L\eta/2)\|\nabla f(\boldsymbol{w})\|^2 は η=1/L\eta = 1/L のとき最大で、その値は 12L∥∇f(w)∥2\dfrac{1}{2L}\|\nabla f(\boldsymbol{w})\|^2 です。

証明（系 4.4）

補題 4.3 で u=w\boldsymbol{u} = \boldsymbol{w}、v=w′=w−η∇f(w)\boldsymbol{v} = \boldsymbol{w}' = \boldsymbol{w} - \eta\nabla f(\boldsymbol{w}) と取ります。v−u=−η∇f(w)\boldsymbol{v} - \boldsymbol{u} = -\eta\nabla f(\boldsymbol{w}) なので

⟨∇f(w),v−u⟩=−η∥∇f(w)∥2,L2∥v−u∥2=Lη22∥∇f(w)∥2\langle \nabla f(\boldsymbol{w}), \boldsymbol{v}-\boldsymbol{u}\rangle = -\eta\|\nabla f(\boldsymbol{w})\|^2, \qquad \frac{L}{2}\|\boldsymbol{v}-\boldsymbol{u}\|^2 = \frac{L\eta^2}{2}\|\nabla f(\boldsymbol{w})\|^2

であり、代入して ∥∇f(w)∥2\|\nabla f(\boldsymbol{w})\|^2 でくくれば主張の不等式になります。

η(1−Lη/2)>0\eta(1 - L\eta/2) > 0 となるのは η>0\eta > 0 かつ 1−Lη/2>01 - L\eta/2 > 0、すなわち 0<η<2/L0 < \eta < 2/L のときです。このとき ∥∇f(w)∥2>0\|\nabla f(\boldsymbol{w})\|^2 > 0 と合わせて右辺は f(w)f(\boldsymbol{w}) より真に小さくなります。

最後に ψ(η)=η−Lη2/2\psi(\eta) = \eta - L\eta^2/2 は上に凸な二次関数で、ψ′(η)=1−Lη=0\psi'(\eta) = 1 - L\eta = 0 より η=1/L\eta = 1/L で最大値 ψ(1/L)=1/L−1/(2L)=1/(2L)\psi(1/L) = 1/L - 1/(2L) = 1/(2L) を取ります。

学習率の意味がはっきりしました。η\eta は 1 次近似を信用する範囲を決める量で、その安全圏の広さは平滑性定数 LL の逆数で測られます。η≥2/L\eta \ge 2/L では 補題 4.3 の右辺が f(w)f(\boldsymbol{w}) を下回らなくなり、減少の保証が消えます。

放物線 f(w)=L2w2f(w) = \frac{L}{2}w^2（L=1L = 1）で w0=1.5w_0 = 1.5 から 10 歩進めると、学習率ごとの違いが見えます。η=2/L\eta = 2/L を境に、収束・往復・発散に分かれます。

放物線の上を点が動く 4 つの図。η = 0.3/L では最小点へゆっくり近づき、η = 1/L では一歩で最小点に着き、η = 2/L では左右の同じ高さを往復し続け、η = 2.2/L では往復しながら振れ幅が大きくなって発散する。
放物線の上での勾配降下法。η を 0.3/L、1/L、2/L、2.2/L にしたときの点の動き

次の定理の証明は、数え上げの議論です。η=1/L\eta = 1/L のとき、1 歩ごとに ff は少なくとも勾配の大きさの二乗に比例した分だけ下がります。ところが ff が下がれる総量は f(w0)−f⋆f(\boldsymbol{w}_0) - f_\star までなので、勾配が大きいままの歩数は多くありえません。1 歩ごとの減少量を足し合わせると途中の f(wk)f(\boldsymbol{w}_k) が打ち消し合い（望遠鏡和）、最初と最後の差だけが残ります。

定理 4.5（勾配降下法の停留点への収束）✓

f:Rn→Rf : \mathbb{R}^n \to \mathbb{R} は C1C^1 級かつ LL-平滑で、下に有界とし、f⋆=inf⁡wf(w)>−∞f_\star = \inf_{\boldsymbol{w}} f(\boldsymbol{w}) > -\infty とします。定数学習率 η=1/L\eta = 1/L の勾配降下法 wk+1=wk−1L∇f(wk)\boldsymbol{w}_{k+1} = \boldsymbol{w}_k - \frac{1}{L}\nabla f(\boldsymbol{w}_k) について、次が成り立ちます。

  1. 数列 (f(wk))k≥0\bigl(f(\boldsymbol{w}_k)\bigr)_{k\ge 0} は単調非増加で、ある極限値に収束します。
  2. 任意の T≥1T \ge 1 に対して min⁡0≤k≤T−1∥∇f(wk)∥2 ≤ 2L(f(w0)−f⋆)T.\min_{0 \le k \le T-1}\bigl\|\nabla f(\boldsymbol{w}_k)\bigr\|^2 \ \le\ \frac{2L\bigl(f(\boldsymbol{w}_0) - f_\star\bigr)}{T}.
  3. ∑k=0∞∥∇f(wk)∥2<∞\displaystyle\sum_{k=0}^{\infty}\bigl\|\nabla f(\boldsymbol{w}_k)\bigr\|^2 < \infty。とくに ∥∇f(wk)∥→0\|\nabla f(\boldsymbol{w}_k)\| \to 0（k→∞k \to \infty）。
証明（定理 4.5）

系 4.4 に η=1/L\eta = 1/L を代入すると、すべての kk について

f(wk+1)≤f(wk)−12L∥∇f(wk)∥2f(\boldsymbol{w}_{k+1}) \le f(\boldsymbol{w}_k) - \frac{1}{2L}\bigl\|\nabla f(\boldsymbol{w}_k)\bigr\|^2

を得ます。以下この不等式を「1 ステップ不等式」と呼びます。右辺の第 2 項は非正なので f(wk+1)≤f(wk)f(\boldsymbol{w}_{k+1}) \le f(\boldsymbol{w}_k)、すなわち単調非増加です。さらに f(wk)≥f⋆f(\boldsymbol{w}_k) \ge f_\star で下に有界なので、単調有界数列の収束定理により (f(wk))\bigl(f(\boldsymbol{w}_k)\bigr) は収束します。これが 1 です。

この 1 ステップ不等式を移項して k=0,1,…,T−1k = 0, 1, \ldots, T-1 で足し合わせます。右辺は望遠鏡和になり

12L∑k=0T−1∥∇f(wk)∥2 ≤ ∑k=0T−1(f(wk)−f(wk+1))=f(w0)−f(wT) ≤ f(w0)−f⋆\frac{1}{2L}\sum_{k=0}^{T-1}\bigl\|\nabla f(\boldsymbol{w}_k)\bigr\|^2 \ \le\ \sum_{k=0}^{T-1}\bigl(f(\boldsymbol{w}_k) - f(\boldsymbol{w}_{k+1})\bigr) = f(\boldsymbol{w}_0) - f(\boldsymbol{w}_T) \ \le\ f(\boldsymbol{w}_0) - f_\star

を得ます（最後の不等号は f(wT)≥f⋆f(\boldsymbol{w}_T) \ge f_\star）。TT 個の非負数の最小値は平均以下なので

min⁡0≤k≤T−1∥∇f(wk)∥2≤1T∑k=0T−1∥∇f(wk)∥2≤2L(f(w0)−f⋆)T\min_{0\le k\le T-1}\bigl\|\nabla f(\boldsymbol{w}_k)\bigr\|^2 \le \frac{1}{T}\sum_{k=0}^{T-1}\bigl\|\nabla f(\boldsymbol{w}_k)\bigr\|^2 \le \frac{2L\bigl(f(\boldsymbol{w}_0)-f_\star\bigr)}{T}

となり 2 が示せました。

3 も同じ不等式から出ます。上の評価は TT によらない上界 2L(f(w0)−f⋆)2L(f(\boldsymbol{w}_0)-f_\star) を部分和に与えているので、非負項からなる級数 ∑k∥∇f(wk)∥2\sum_k \|\nabla f(\boldsymbol{w}_k)\|^2 の部分和は単調増加かつ有界、よって収束します（級数と収束判定）。収束する級数の一般項は 00 に収束するので ∥∇f(wk)∥2→0\|\nabla f(\boldsymbol{w}_k)\|^2 \to 0、したがって ∥∇f(wk)∥→0\|\nabla f(\boldsymbol{w}_k)\| \to 0 です。

注意 4.6

定理 4.5 が言っているのは「勾配が 00 に近づく」ことだけで、wk\boldsymbol{w}_k が収束するとも、f(wk)→f⋆f(\boldsymbol{w}_k) \to f_\star となるとも言っていません。凸でない ff では、鞍点や局所最小点の近くで勾配が消えて止まりうるからです。ff が凸なら停留点は大域最小点なので、この差は消えます。

また、2 の O(1/T)O(1/T) という速さは「最悪の場合の保証」です。ff が強凸なら誤差は指数的に減り、逆に平坦な方向があると O(1/T)O(1/T) 程度まで落ちることもあります。次節でその両極端を二次関数の上で正確に見ます。

5. 二次関数で見る収束の速さ

Section titled “5. 二次関数で見る収束の速さ”

二次関数は、勾配降下法の挙動を完全に手計算で追える唯一の例です。しかも一般の ff も最小点の近くでは二次関数で近似されるので、ここで分かることは局所的な挙動の指針になります。

命題 5.1（二次関数に対する勾配降下法）✓

A∈Rn×nA \in \mathbb{R}^{n\times n} を対称正定値行列、b∈Rn\boldsymbol{b} \in \mathbb{R}^n とし、

f(w)=12⟨w,Aw⟩−⟨b,w⟩f(\boldsymbol{w}) = \tfrac{1}{2}\langle \boldsymbol{w}, A\boldsymbol{w}\rangle - \langle \boldsymbol{b}, \boldsymbol{w}\rangle

とします。AA の固有値を 0<λ1≤λ2≤⋯≤λn0 < \lambda_1 \le \lambda_2 \le \cdots \le \lambda_n、条件数を κ=λn/λ1\kappa = \lambda_n/\lambda_1、最小点を w⋆=A−1b\boldsymbol{w}_\star = A^{-1}\boldsymbol{b} とします。定数学習率 η>0\eta > 0 の勾配降下法 wk+1=wk−η∇f(wk)\boldsymbol{w}_{k+1} = \boldsymbol{w}_k - \eta\nabla f(\boldsymbol{w}_k) について次が成り立ちます。

  1. wk−w⋆=(I−ηA)k(w0−w⋆)\boldsymbol{w}_k - \boldsymbol{w}_\star = (I - \eta A)^k(\boldsymbol{w}_0 - \boldsymbol{w}_\star)。
  2. ρ(η)=max⁡(∣1−ηλ1∣, ∣1−ηλn∣)\rho(\eta) = \max\bigl(|1-\eta\lambda_1|,\ |1-\eta\lambda_n|\bigr) とおくと ∥wk−w⋆∥≤ρ(η)k∥w0−w⋆∥\|\boldsymbol{w}_k - \boldsymbol{w}_\star\| \le \rho(\eta)^k\|\boldsymbol{w}_0 - \boldsymbol{w}_\star\| であり、さらにすべての初期値 w0\boldsymbol{w}_0 について wk→w⋆\boldsymbol{w}_k \to \boldsymbol{w}_\star となるのは 0<η<2/λn0 < \eta < 2/\lambda_n のとき、かつそのときに限ります。
  3. ρ(η)\rho(\eta) を最小にする学習率は η⋆=2λ1+λn\eta_\star = \dfrac{2}{\lambda_1 + \lambda_n} で、そのときの値は
ρ(η⋆)=λn−λ1λn+λ1=κ−1κ+1.\rho(\eta_\star) = \frac{\lambda_n - \lambda_1}{\lambda_n + \lambda_1} = \frac{\kappa - 1}{\kappa + 1}.
証明（命題 5.1）

まず勾配を求めます。例 2.4 と同じ要領で f(w+h)f(\boldsymbol{w}+\boldsymbol{h}) を展開すると、AA が対称であることから

f(w+h)=f(w)+⟨Aw−b, h⟩+12⟨h,Ah⟩f(\boldsymbol{w}+\boldsymbol{h}) = f(\boldsymbol{w}) + \langle A\boldsymbol{w} - \boldsymbol{b},\ \boldsymbol{h}\rangle + \tfrac{1}{2}\langle \boldsymbol{h}, A\boldsymbol{h}\rangle

となり、最後の項は ∥h∥2\|\boldsymbol{h}\|^2 のオーダーなので o(∥h∥)o(\|\boldsymbol{h}\|) です。よって ∇f(w)=Aw−b\nabla f(\boldsymbol{w}) = A\boldsymbol{w} - \boldsymbol{b} で、これが 0\boldsymbol{0} になるのは AA が正則（正定値だから）なので w=A−1b=w⋆\boldsymbol{w} = A^{-1}\boldsymbol{b} = \boldsymbol{w}_\star のときに限ります。

1 の証明。 b=Aw⋆\boldsymbol{b} = A\boldsymbol{w}_\star を使うと ∇f(wk)=Awk−Aw⋆=A(wk−w⋆)\nabla f(\boldsymbol{w}_k) = A\boldsymbol{w}_k - A\boldsymbol{w}_\star = A(\boldsymbol{w}_k - \boldsymbol{w}_\star) です。誤差ベクトルを ek=wk−w⋆\boldsymbol{e}_k = \boldsymbol{w}_k - \boldsymbol{w}_\star とおくと

ek+1=wk−ηAek−w⋆=(I−ηA)ek\boldsymbol{e}_{k+1} = \boldsymbol{w}_k - \eta A\boldsymbol{e}_k - \boldsymbol{w}_\star = (I - \eta A)\boldsymbol{e}_k

なので、kk について繰り返せば ek=(I−ηA)ke0\boldsymbol{e}_k = (I-\eta A)^k\boldsymbol{e}_0 を得ます。

2 の証明。 AA は実対称なのでスペクトル定理（実対称行列の直交対角化（系 4.3）［スペクトル定理］）により、正規直交基底からなる固有ベクトル q1,…,qn\boldsymbol{q}_1,\ldots,\boldsymbol{q}_n（Aqi=λiqiA\boldsymbol{q}_i = \lambda_i\boldsymbol{q}_i）が取れます。I−ηAI - \eta A は同じ固有ベクトルを持ち、固有値は 1−ηλi1 - \eta\lambda_i です。e0=∑iciqi\boldsymbol{e}_0 = \sum_i c_i \boldsymbol{q}_i と展開すると

ek=∑i=1n(1−ηλi)kciqi,∥ek∥2=∑i=1n(1−ηλi)2kci2\boldsymbol{e}_k = \sum_{i=1}^{n} (1-\eta\lambda_i)^k c_i \boldsymbol{q}_i, \qquad \|\boldsymbol{e}_k\|^2 = \sum_{i=1}^{n}(1-\eta\lambda_i)^{2k}c_i^2

です（2 番目の等式は正規直交性から）。m(η)=max⁡i∣1−ηλi∣m(\eta) = \max_i |1-\eta\lambda_i| とおけば ∥ek∥2≤m(η)2k∑ici2=m(η)2k∥e0∥2\|\boldsymbol{e}_k\|^2 \le m(\eta)^{2k}\sum_i c_i^2 = m(\eta)^{2k}\|\boldsymbol{e}_0\|^2 です。

m(η)=ρ(η)m(\eta) = \rho(\eta) であること、つまり最大が両端の固有値で達成されることを見ます。λ↦∣1−ηλ∣\lambda \mapsto |1-\eta\lambda| は 1 次式の絶対値なので凸関数であり、凸関数の閉区間上での最大値は端点で取られます。λi\lambda_i はすべて [λ1,λn][\lambda_1, \lambda_n] に入っているので max⁡i∣1−ηλi∣=max⁡(∣1−ηλ1∣,∣1−ηλn∣)\max_i|1-\eta\lambda_i| = \max(|1-\eta\lambda_1|, |1-\eta\lambda_n|) です。

収束条件を示します。0<η<2/λn0 < \eta < 2/\lambda_n なら、各 ii について 0<ηλi≤ηλn<20 < \eta\lambda_i \le \eta\lambda_n < 2 ですから −1<1−ηλi<1-1 < 1-\eta\lambda_i < 1、すなわち ρ(η)<1\rho(\eta) < 1 となり ∥ek∥→0\|\boldsymbol{e}_k\| \to 0 です。逆に η≥2/λn\eta \ge 2/\lambda_n なら 1−ηλn≤−11 - \eta\lambda_n \le -1 なので、e0=qn\boldsymbol{e}_0 = \boldsymbol{q}_n（すなわち w0=w⋆+qn\boldsymbol{w}_0 = \boldsymbol{w}_\star + \boldsymbol{q}_n）と取ると ∥ek∥=∣1−ηλn∣k≥1\|\boldsymbol{e}_k\| = |1-\eta\lambda_n|^k \ge 1 となって 0\boldsymbol{0} に収束しません。

3 の証明。 η\eta を 00 から増やすとき、∣1−ηλ1∣|1-\eta\lambda_1| は η=1/λ1\eta = 1/\lambda_1 まで減ってから増え、∣1−ηλn∣|1-\eta\lambda_n| は η=1/λn≤1/λ1\eta = 1/\lambda_n \le 1/\lambda_1 まで減ってから増えます。ρ\rho が最小になるのは二つのグラフが交わる点で、そこでは 1−ηλ1>01-\eta\lambda_1 > 0 かつ 1−ηλn<01-\eta\lambda_n < 0 なので

1−ηλ1=−(1−ηλn)  ⟺  2=η(λ1+λn)  ⟺  η=2λ1+λn1 - \eta\lambda_1 = -(1-\eta\lambda_n) \iff 2 = \eta(\lambda_1+\lambda_n) \iff \eta = \frac{2}{\lambda_1+\lambda_n}

です。実際、η\eta がこの値より小さければ ρ(η)=1−ηλ1\rho(\eta) = 1-\eta\lambda_1 が η\eta について減少、大きければ ρ(η)=ηλn−1\rho(\eta) = \eta\lambda_n - 1 が増加するので、ここが最小点です。値は

ρ(η⋆)=1−2λ1λ1+λn=λn−λ1λn+λ1\rho(\eta_\star) = 1 - \frac{2\lambda_1}{\lambda_1+\lambda_n} = \frac{\lambda_n-\lambda_1}{\lambda_n+\lambda_1}

で、分子分母を λ1\lambda_1 で割れば (κ−1)/(κ+1)(\kappa-1)/(\kappa+1) になります。

命題 5.1 の 2 は 系 4.4 と正確に整合します。二次関数 ff の勾配は ∇f(u)−∇f(v)=A(u−v)\nabla f(\boldsymbol{u}) - \nabla f(\boldsymbol{v}) = A(\boldsymbol{u}-\boldsymbol{v}) なので、LL-平滑性の最小の定数は L=∥A∥2=λnL = \|A\|_2 = \lambda_n です。降下補題から出た安全圏 0<η<2/L0 < \eta < 2/L は、ここでは 0<η<2/λn0 < \eta < 2/\lambda_n となり、収束の必要十分条件とぴたり一致します。降下補題の評価は二次関数に対しては無駄がない、ということです。

命題 5.1 の 3 が伝えているのは深刻な事実です。誤差を ε\varepsilon 倍に減らすのに必要な反復回数はおよそ

k≈ln⁡(1/ε)ln⁡(1/ρ(η⋆))≈κ2ln⁡1εk \approx \frac{\ln(1/\varepsilon)}{\ln\bigl(1/\rho(\eta_\star)\bigr)} \approx \frac{\kappa}{2}\ln\frac{1}{\varepsilon}

です（κ\kappa が大きいとき ln⁡κ+1κ−1≈2/κ\ln\frac{\kappa+1}{\kappa-1} \approx 2/\kappa を使いました）。条件数に比例して遅くなるわけです。κ=104\kappa = 10^4 なら誤差を 1/10001/1000 にするだけで数万回の反復が要ります。

最小点最小点へ向かう向き出発点最初の 1 歩
細長い等高線の上でのジグザグ。勾配は等高線に直交するため、最小点の方向とは大きくずれる

図は f(w1,w2)=12(w12+25w22)f(w_1, w_2) = \frac{1}{2}(w_1^2 + 25 w_2^2)、すなわち A=diag(1,25)A = \mathrm{diag}(1, 25)、κ=25\kappa = 25 の場合に、w0=(5,1)T\boldsymbol{w}_0 = (5, 1)^{\mathsf{T}} から最適学習率 η⋆=2/26=1/13\eta_\star = 2/26 = 1/13 で 12 歩進めた軌跡です。系 3.3 のとおり勾配は等高線に直交するので、細長い谷では勾配がほとんど「谷を横切る向き」を指し、「谷に沿って最小点へ向かう向き」の成分はごくわずかしか含みません。その結果、上下に激しく振動しながら少しずつ右から左へ進むことになります。

この例では w1w_1 成分に 1−ηλ1=12/131-\eta\lambda_1 = 12/13、w2w_2 成分に 1−ηλn=−12/131-\eta\lambda_n = -12/13 が毎回掛かります。w2w_2 の符号が毎回反転するのがジグザグの正体で、絶対値はどちらも 12/13≈0.92312/13 \approx 0.923 ずつしか縮みません。ff の値は 1 歩ごとに (12/13)2=144/169≈0.852(12/13)^2 = 144/169 \approx 0.852 倍になるので、ff を 10−610^{-6} 倍にするには ln⁡(10−6)/ln⁡(144/169)≈86.3\ln(10^{-6})/\ln(144/169) \approx 86.3、つまり 87 回の反復が必要です。

例 5.2（学習率を上げすぎると何が起きるか）

同じ f(w1,w2)=12(w12+25w22)f(w_1,w_2) = \frac{1}{2}(w_1^2 + 25w_2^2) で、学習率を変えて 50 回反復したときの ff の値を比べます。L=λn=25L = \lambda_n = 25 なので、理論上の安全圏は 0<η<2/25=0.080 < \eta < 2/25 = 0.08 です。

import numpy as np


A = np.diag([1.0, 25.0])          # f(w) = (1/2) * w^T A w
grad = lambda w: A @ w


def run(eta, n_iter=50, w0=(5.0, 1.0)):
    w = np.array(w0, dtype=float)
    for _ in range(n_iter):
        w = w - eta * grad(w)
    return 0.5 * w @ (A @ w)


for eta in (0.04, 1 / 13, 0.08, 0.09):
    print(f"eta = {eta:.4f}   f(w_50) = {run(eta):.3e}")

出力はおよそ次のようになります。

学習率 η\eta位置づけ50 回後の ff
0.04=1/L0.04 = 1/L降下補題が勧める値2.11×10−12.11 \times 10^{-1}
1/13≈0.07691/13 \approx 0.0769命題 5.1 の最適値8.35×10−38.35 \times 10^{-3}
0.08=2/L0.08 = 2/L安全圏の境界1.25×1011.25 \times 10^{1}
0.090.09安全圏の外6.14×10106.14 \times 10^{10}

読み取れることが三つあります。第一に、η=1/L=0.04\eta = 1/L = 0.04 は確かに収束しますが最適値の 2 倍近く遅いということです。実際このとき 1−ηλn=01-\eta\lambda_n = 0 なので w2w_2 は 1 歩で消え、あとは w1w_1 が 0.960.96 倍ずつ縮むだけになります。0.9650≈0.1300.96^{50} \approx 0.130 です。第二に、境界値 η=2/L=0.08\eta = 2/L = 0.08 では 1−ηλn=−11-\eta\lambda_n = -1 となり、w2w_2 が ±1\pm 1 を永久に往復して ff が減らなくなります（ff は約 12.512.5 で停滞します）。第三に、η=0.09\eta = 0.09 では ∣1−ηλn∣=1.25>1|1-\eta\lambda_n| = 1.25 > 1 なので w2w_2 が 1.2550≈7.0×1041.25^{50} \approx 7.0\times 10^4 倍に発散します。

学習率を上げすぎた学習の損失が「途中から急上昇して NaN になる」典型的な失敗は、これと同じことが起きています。

6. ロジスティック回帰に適用する

Section titled “6. ロジスティック回帰に適用する”

道具が揃ったので、§1 で立ち往生した問題に戻ります。記号を決めます。xi∈Rn\boldsymbol{x}_i \in \mathbb{R}^n、yi∈{0,1}y_i \in \{0,1\}（i=1,…,Ni = 1,\ldots,N）を学習データ、X∈RN×nX \in \mathbb{R}^{N\times n} を第 ii 行が xiT\boldsymbol{x}_i^{\mathsf{T}} である計画行列、y=(y1,…,yN)T\boldsymbol{y} = (y_1,\ldots,y_N)^{\mathsf{T}} とします。シグモイド関数 σ(z)=1/(1+e−z)\sigma(z) = 1/(1+e^{-z}) を使って予測確率を pi(w)=σ(⟨w,xi⟩)p_i(\boldsymbol{w}) = \sigma(\langle \boldsymbol{w}, \boldsymbol{x}_i\rangle) と書き、p(w)=(p1,…,pN)T\boldsymbol{p}(\boldsymbol{w}) = (p_1,\ldots,p_N)^{\mathsf{T}} とします。最小化する目的関数は平均交差エントロピー誤差

f(w)=−1N∑i=1N[ yilog⁡pi(w)+(1−yi)log⁡(1−pi(w))]f(\boldsymbol{w}) = -\frac{1}{N}\sum_{i=1}^{N}\Bigl[\, y_i \log p_i(\boldsymbol{w}) + (1-y_i)\log\bigl(1 - p_i(\boldsymbol{w})\bigr) \Bigr]

です。

命題 6.1（ロジスティック損失の勾配・ヘッセ行列・平滑性）✓

上の ff について次が成り立ちます。

  1. ff は Rn\mathbb{R}^n 上で C∞C^\infty 級で、 ∇f(w)=1N∑i=1N(pi(w)−yi)xi=1NXT(p(w)−y).\nabla f(\boldsymbol{w}) = \frac{1}{N}\sum_{i=1}^{N}\bigl(p_i(\boldsymbol{w}) - y_i\bigr)\boldsymbol{x}_i = \frac{1}{N}X^{\mathsf{T}}\bigl(\boldsymbol{p}(\boldsymbol{w}) - \boldsymbol{y}\bigr).
  2. ヘッセ行列は S(w)=diag(p1(1−p1),…,pN(1−pN))S(\boldsymbol{w}) = \mathrm{diag}\bigl(p_1(1-p_1), \ldots, p_N(1-p_N)\bigr) を使って ∇2f(w)=1N∑i=1Npi(1−pi) xixiT=1NXTS(w)X\nabla^2 f(\boldsymbol{w}) = \frac{1}{N}\sum_{i=1}^{N} p_i(1-p_i)\,\boldsymbol{x}_i\boldsymbol{x}_i^{\mathsf{T}} = \frac{1}{N}X^{\mathsf{T}}S(\boldsymbol{w})X と書け、これは任意の w\boldsymbol{w} で半正定値です。したがって ff は凸関数で、停留点はすべて大域最小点です。
  3. ff は LL-平滑で、定数として L=λmax⁡(XTX)4NL = \dfrac{\lambda_{\max}(X^{\mathsf{T}}X)}{4N} が取れます。
証明（命題 6.1）

まずシグモイド関数の微分を確かめます。σ(z)=(1+e−z)−1\sigma(z) = (1+e^{-z})^{-1} を微分すると

σ′(z)=− (1+e−z)−2⋅(−e−z)=e−z(1+e−z)2=11+e−z⋅e−z1+e−z=σ(z)(1−σ(z))\sigma'(z) = -\,(1+e^{-z})^{-2}\cdot(-e^{-z}) = \frac{e^{-z}}{(1+e^{-z})^{2}} = \frac{1}{1+e^{-z}}\cdot\frac{e^{-z}}{1+e^{-z}} = \sigma(z)\bigl(1-\sigma(z)\bigr)

です（最後は 1−σ(z)=e−z/(1+e−z)1-\sigma(z) = e^{-z}/(1+e^{-z}) による）。σ\sigma は R\mathbb{R} 上で C∞C^\infty 級かつ 0<σ<10 < \sigma < 1 なので、log⁡\log との合成も定義域全体で C∞C^\infty 級です。

1 の証明。 1 サンプル分の損失を ℓ(z,y)=−ylog⁡σ(z)−(1−y)log⁡(1−σ(z))\ell(z, y) = -y\log\sigma(z) - (1-y)\log(1-\sigma(z)) とおき、zz で微分します。(log⁡σ)′=σ′/σ=1−σ\bigl(\log\sigma\bigr)' = \sigma'/\sigma = 1-\sigma、(log⁡(1−σ))′=−σ′/(1−σ)=−σ\bigl(\log(1-\sigma)\bigr)' = -\sigma'/(1-\sigma) = -\sigma ですから

∂ℓ∂z(z,y)=−y(1−σ(z))+(1−y)σ(z)=−y+yσ(z)+σ(z)−yσ(z)=σ(z)−y.\frac{\partial \ell}{\partial z}(z,y) = -y(1-\sigma(z)) + (1-y)\sigma(z) = -y + y\sigma(z) + \sigma(z) - y\sigma(z) = \sigma(z) - y .

途中の yσy\sigma が打ち消し合うのがロジスティック回帰の気持ちよさで、残るのは「予測確率と正解のずれ」だけです。zi(w)=⟨w,xi⟩z_i(\boldsymbol{w}) = \langle \boldsymbol{w}, \boldsymbol{x}_i\rangle は w\boldsymbol{w} の線形関数なので ∇wzi=xi\nabla_{\boldsymbol{w}} z_i = \boldsymbol{x}_i であり、連鎖律より

∇f(w)=1N∑i=1N∂ℓ∂z(zi,yi) ∇wzi=1N∑i=1N(pi−yi)xi.\nabla f(\boldsymbol{w}) = \frac{1}{N}\sum_{i=1}^{N}\frac{\partial \ell}{\partial z}(z_i, y_i)\,\nabla_{\boldsymbol{w}}z_i = \frac{1}{N}\sum_{i=1}^{N}\bigl(p_i - y_i\bigr)\boldsymbol{x}_i .

∑icixi=XTc\sum_i c_i\boldsymbol{x}_i = X^{\mathsf{T}}\boldsymbol{c} なので行列形も従います。

2 の証明。 1 をもう一度 w\boldsymbol{w} で微分します。pi=σ(zi)p_i = \sigma(z_i) を w\boldsymbol{w} で微分すると、上と同じ連鎖律で ∇wpi=σ′(zi)xi=pi(1−pi)xi\nabla_{\boldsymbol{w}} p_i = \sigma'(z_i)\boldsymbol{x}_i = p_i(1-p_i)\boldsymbol{x}_i です。∇f=1N∑i(pi−yi)xi\nabla f = \frac{1}{N}\sum_i (p_i-y_i)\boldsymbol{x}_i の各項をヤコビ行列にすると xi(∇wpi)T=pi(1−pi)xixiT\boldsymbol{x}_i\bigl(\nabla_{\boldsymbol{w}} p_i\bigr)^{\mathsf{T}} = p_i(1-p_i)\boldsymbol{x}_i\boldsymbol{x}_i^{\mathsf{T}} となり、主張の式を得ます。

半正定値性を確かめます。任意の v∈Rn\boldsymbol{v} \in \mathbb{R}^n に対し

⟨v, ∇2f(w)v⟩=1N∑i=1Npi(1−pi) ⟨xi,v⟩2 ≥ 0\bigl\langle \boldsymbol{v},\ \nabla^2 f(\boldsymbol{w})\boldsymbol{v}\bigr\rangle = \frac{1}{N}\sum_{i=1}^{N} p_i(1-p_i)\,\bigl\langle \boldsymbol{x}_i, \boldsymbol{v}\bigr\rangle^{2} \ \ge\ 0

です（vTxixiTv=⟨xi,v⟩2\boldsymbol{v}^{\mathsf{T}}\boldsymbol{x}_i\boldsymbol{x}_i^{\mathsf{T}}\boldsymbol{v} = \langle\boldsymbol{x}_i,\boldsymbol{v}\rangle^2 と、0<pi<10 < p_i < 1 より pi(1−pi)>0p_i(1-p_i) > 0 を使いました）。ヘッセ行列が至るところ半正定値な C2C^2 級関数は凸なので ff は凸で、凸関数では ∇f(w)=0\nabla f(\boldsymbol{w}) = \boldsymbol{0} が大域最小の必要十分条件です（凸関数では停留点と大域最小点が一致する（定理 4.2）［なぜ機械学習に数学が必要か］）。

3 の証明。 t∈(0,1)t \in (0,1) に対し t(1−t)=14−(t−12)2≤14t(1-t) = \frac{1}{4} - \bigl(t-\frac{1}{2}\bigr)^2 \le \frac{1}{4} です。これを上の二次形式に代入すると

⟨v,∇2f(w)v⟩≤14N∑i=1N⟨xi,v⟩2=14N∥Xv∥2=14N⟨v,XTXv⟩≤λmax⁡(XTX)4N∥v∥2\bigl\langle \boldsymbol{v}, \nabla^2 f(\boldsymbol{w})\boldsymbol{v}\bigr\rangle \le \frac{1}{4N}\sum_{i=1}^{N}\langle \boldsymbol{x}_i,\boldsymbol{v}\rangle^2 = \frac{1}{4N}\|X\boldsymbol{v}\|^2 = \frac{1}{4N}\bigl\langle \boldsymbol{v}, X^{\mathsf{T}}X\boldsymbol{v}\bigr\rangle \le \frac{\lambda_{\max}(X^{\mathsf{T}}X)}{4N}\|\boldsymbol{v}\|^2

となります。最後の不等号は、対称半正定値行列 XTXX^{\mathsf{T}}X のレイリー商が最大固有値で抑えられること（固有値と固有ベクトル）によります。∇2f(w)\nabla^2 f(\boldsymbol{w}) は対称なので、その作用素ノルムは固有値の絶対値の最大値に等しく、半正定値性と合わせて ∥∇2f(w)∥2≤λmax⁡(XTX)/(4N)\|\nabla^2 f(\boldsymbol{w})\|_2 \le \lambda_{\max}(X^{\mathsf{T}}X)/(4N) を得ます。これがすべての w\boldsymbol{w} で成り立つので、Appendix の評価より ∇f\nabla f は L=λmax⁡(XTX)/(4N)L = \lambda_{\max}(X^{\mathsf{T}}X)/(4N) でリプシッツ連続です。

命題 6.1 の 2 と 3 を合わせると、ロジスティック回帰の学習は「凸で LL-平滑な関数の最小化」という、定理 4.5 がそのまま使える設定だと分かります。しかも LL はデータから直接計算できます。手探りではなく、η=4N/λmax⁡(XTX)\eta = 4N/\lambda_{\max}(X^{\mathsf{T}}X) から始めればよいのです。

例 6.2（4 点のデータで 2 ステップ手計算する）

手で最後まで追えるように、特徴量を 1 次元（バイアス項なし）にします。データを

(x1,y1)=(−2,0),(x2,y2)=(−1,0),(x3,y3)=(1,1),(x4,y4)=(2,1)(x_1,y_1) = (-2, 0),\quad (x_2,y_2) = (-1, 0),\quad (x_3,y_3) = (1, 1),\quad (x_4,y_4) = (2, 1)

とします。N=4N = 4、∑ixi2=4+1+1+4=10\sum_i x_i^2 = 4+1+1+4 = 10 なので、命題 6.1 の 3 より

L=14N∑i=14xi2=1016=0.625,η=1L=1.6.L = \frac{1}{4N}\sum_{i=1}^{4}x_i^2 = \frac{10}{16} = 0.625, \qquad \eta = \frac{1}{L} = 1.6 .

初期値 w0=0w_0 = 0。 すべての ii で pi=σ(0)=0.5p_i = \sigma(0) = 0.5 です。損失は f(0)=−log⁡0.5=0.693147f(0) = -\log 0.5 = 0.693147。勾配は

∇f(0)=14[(0.5−0)(−2)+(0.5−0)(−1)+(0.5−1)(1)+(0.5−1)(2)]=−34=−0.75.\nabla f(0) = \frac{1}{4}\Bigl[(0.5-0)(-2) + (0.5-0)(-1) + (0.5-1)(1) + (0.5-1)(2)\Bigr] = \frac{-3}{4} = -0.75 .

負なので ww を増やす向きに進みます。w1=0−1.6×(−0.75)=1.2w_1 = 0 - 1.6\times(-0.75) = 1.2。

1 ステップ後。 zi=1.2xiz_i = 1.2x_i は −2.4, −1.2, 1.2, 2.4-2.4,\ -1.2,\ 1.2,\ 2.4 です。σ(2.4)=1/(1+e−2.4)=1/1.090718=0.916827\sigma(2.4) = 1/(1+e^{-2.4}) = 1/1.090718 = 0.916827、σ(1.2)=1/(1+e−1.2)=1/1.301194=0.768525\sigma(1.2) = 1/(1+e^{-1.2}) = 1/1.301194 = 0.768525 で、σ(−z)=1−σ(z)\sigma(-z) = 1-\sigma(z) より σ(−1.2)=0.231475\sigma(-1.2) = 0.231475、σ(−2.4)=0.083173\sigma(-2.4) = 0.083173 です。損失は −log⁡σ(z)=log⁡(1+e−z)-\log\sigma(z) = \log(1+e^{-z}) を使って

f(1.2)=14[log⁡(1+e−2.4)⋅2+log⁡(1+e−1.2)⋅2]=2(0.086836)+2(0.263282)4=0.175059.f(1.2) = \frac{1}{4}\Bigl[\log(1+e^{-2.4})\cdot 2 + \log(1+e^{-1.2})\cdot 2\Bigr] = \frac{2(0.086836) + 2(0.263282)}{4} = 0.175059 .

（4 点とも正しく分類されているので、各点の損失は log⁡(1+e−∣zi∣)\log(1+e^{-|z_i|}) の形になります。）勾配は

∇f(1.2)=14[(0.083173)(−2)+(0.231475)(−1)+(0.768525−1)(1)+(0.916827−1)(2)]=−0.7956424=−0.198911.\nabla f(1.2) = \frac{1}{4}\Bigl[(0.083173)(-2) + (0.231475)(-1) + (0.768525-1)(1) + (0.916827-1)(2)\Bigr] = \frac{-0.795642}{4} = -0.198911 .

よって w2=1.2+1.6×0.198911=1.518257w_2 = 1.2 + 1.6\times 0.198911 = 1.518257。

2 ステップ後。 zi=±1.518257, ±3.036514z_i = \pm 1.518257,\ \pm 3.036514 で、log⁡(1+e−1.518257)=0.198107\log(1+e^{-1.518257}) = 0.198107、log⁡(1+e−3.036514)=0.046885\log(1+e^{-3.036514}) = 0.046885 ですから

f(1.518257)=2(0.046885)+2(0.198107)4=0.122496.f(1.518257) = \frac{2(0.046885) + 2(0.198107)}{4} = 0.122496 .

損失は 0.693147→0.175059→0.1224960.693147 \to 0.175059 \to 0.122496 と単調に減っています。系 4.4 が保証したとおりです。

注意 6.3

例 6.2 のデータは w>0w > 0 ならどれも正しく分類される、いわゆる線形分離可能なデータです（線形分離可能なら最尤推定量は存在しない（定理 6.3）［ロジスティック回帰］）。この場合 w→+∞w \to +\infty で f(w)→0f(w) \to 0 となり、下限 f⋆=0f_\star = 0 は達成されません。最小点が存在しないので、勾配降下法は止まらずに ww が（対数程度の遅さで）発散し続けます。

定理 4.5 はこの状況でも正しく機能していることに注意してください。定理が主張するのは ∥∇f(wk)∥→0\|\nabla f(\boldsymbol{w}_k)\| \to 0 であって、wk\boldsymbol{w}_k が収束することではありませんでした。実務では f(w)+α2∥w∥2f(\boldsymbol{w}) + \frac{\alpha}{2}\|\boldsymbol{w}\|^2 のように正則化項を足して、最小点の存在を回復させます。この項はヘッセ行列に αI\alpha I を加えるので、ff は強凸になり、条件数も改善します。

7. 確率的勾配降下法：勾配を安く見積もる

Section titled “7. 確率的勾配降下法：勾配を安く見積もる”

命題 6.1 の勾配の式をもう一度見てください。1 回の更新のために NN 個のサンプルすべてについて pip_i を計算し、xi\boldsymbol{x}_i を足し合わせています。計算量は 1 反復あたり O(Nn)O(Nn) です。N=108N = 10^{8} のデータで 定理 4.5 の O(1/T)O(1/T) を頼りに 1000 回反復しようとすれば、101110^{11} 回のオーダーの積和が必要になります。

ここで発想を変えます。ff は NN 個の関数の平均です。平均を正確に計算する代わりに、少数のサンプルで推定すればどうでしょうか。世論調査で全有権者に聞かずに 1000 人の標本で支持率を推定するのと同じ考え方です。

定義 7.1（確率的勾配降下法とミニバッチ）↗

目的関数が C1C^1 級関数の平均

f(w)=1N∑i=1Nfi(w)f(\boldsymbol{w}) = \frac{1}{N}\sum_{i=1}^{N} f_i(\boldsymbol{w})

の形をしているとします。各反復 kk で添字 iki_k を {1,…,N}\{1,\ldots,N\} から一様ランダムに（毎回独立に）選び、

wk+1=wk−ηk∇fik(wk)\boldsymbol{w}_{k+1} = \boldsymbol{w}_k - \eta_k \nabla f_{i_k}(\boldsymbol{w}_k)

と更新する方法を確率的勾配降下法（SGD）と呼びます。より一般に、BB 個の添字 ik,1,…,ik,Bi_{k,1},\ldots,i_{k,B} を独立一様に選び、

gB(wk)=1B∑j=1B∇fik,j(wk),wk+1=wk−ηk gB(wk)\boldsymbol{g}_B(\boldsymbol{w}_k) = \frac{1}{B}\sum_{j=1}^{B}\nabla f_{i_{k,j}}(\boldsymbol{w}_k), \qquad \boldsymbol{w}_{k+1} = \boldsymbol{w}_k - \eta_k\,\boldsymbol{g}_B(\boldsymbol{w}_k)

とする方法をミニバッチ勾配降下法と呼び、BB をバッチサイズといいます。B=1B = 1 が SGD、B=NB = N（かつ非復元抽出）が通常の勾配降下法にあたります。

この方法が意味を持つのは、次の二つの性質があるからです。

命題 7.2（ミニバッチ勾配の不偏性と分散）✓

定義 7.1 の設定で、w∈Rn\boldsymbol{w} \in \mathbb{R}^n を（添字の選び方と独立に）固定し、添字 i1,…,iBi_1,\ldots,i_B は {1,…,N}\{1,\ldots,N\} 上の一様分布に独立に従うとします。

σ2(w)=1N∑i=1N∥∇fi(w)−∇f(w)∥2\sigma^2(\boldsymbol{w}) = \frac{1}{N}\sum_{i=1}^{N}\bigl\|\nabla f_i(\boldsymbol{w}) - \nabla f(\boldsymbol{w})\bigr\|^2

とおきます。このとき

  1. E[gB(w)]=∇f(w)\mathbb{E}\bigl[\boldsymbol{g}_B(\boldsymbol{w})\bigr] = \nabla f(\boldsymbol{w})（不偏性）、
  2. E[∥gB(w)−∇f(w)∥2]=σ2(w)B\mathbb{E}\bigl[\bigl\|\boldsymbol{g}_B(\boldsymbol{w}) - \nabla f(\boldsymbol{w})\bigr\|^2\bigr] = \dfrac{\sigma^2(\boldsymbol{w})}{B}

が成り立ちます。

証明（命題 7.2）

1 の証明。 添字 iji_j は一様分布なので、各 jj について期待値の定義（期待値（定義 4.1）［確率変数と期待値］）から

E[∇fij(w)]=∑i=1NPr⁡[ij=i] ∇fi(w)=∑i=1N1N∇fi(w)=∇f(w)\mathbb{E}\bigl[\nabla f_{i_j}(\boldsymbol{w})\bigr] = \sum_{i=1}^{N}\Pr[i_j = i]\,\nabla f_i(\boldsymbol{w}) = \sum_{i=1}^{N}\frac{1}{N}\nabla f_i(\boldsymbol{w}) = \nabla f(\boldsymbol{w})

です。期待値の線形性より

E[gB(w)]=1B∑j=1BE[∇fij(w)]=1B⋅B ∇f(w)=∇f(w).\mathbb{E}[\boldsymbol{g}_B(\boldsymbol{w})] = \frac{1}{B}\sum_{j=1}^{B}\mathbb{E}\bigl[\nabla f_{i_j}(\boldsymbol{w})\bigr] = \frac{1}{B}\cdot B\,\nabla f(\boldsymbol{w}) = \nabla f(\boldsymbol{w}).

2 の証明。 ξj=∇fij(w)−∇f(w)\boldsymbol{\xi}_j = \nabla f_{i_j}(\boldsymbol{w}) - \nabla f(\boldsymbol{w}) とおきます。1 より E[ξj]=0\mathbb{E}[\boldsymbol{\xi}_j] = \boldsymbol{0} で、i1,…,iBi_1,\ldots,i_B が独立なので ξ1,…,ξB\boldsymbol{\xi}_1,\ldots,\boldsymbol{\xi}_B も独立です。また

E[∥ξj∥2]=1N∑i=1N∥∇fi(w)−∇f(w)∥2=σ2(w)\mathbb{E}\bigl[\|\boldsymbol{\xi}_j\|^2\bigr] = \frac{1}{N}\sum_{i=1}^{N}\bigl\|\nabla f_i(\boldsymbol{w}) - \nabla f(\boldsymbol{w})\bigr\|^2 = \sigma^2(\boldsymbol{w})

です。gB(w)−∇f(w)=1B∑jξj\boldsymbol{g}_B(\boldsymbol{w}) - \nabla f(\boldsymbol{w}) = \frac{1}{B}\sum_j \boldsymbol{\xi}_j なので、ノルムの二乗を内積で展開して

E[∥1B∑j=1Bξj∥2]=1B2∑j=1B∑l=1BE[⟨ξj,ξl⟩]\mathbb{E}\left[\Bigl\|\frac{1}{B}\sum_{j=1}^{B}\boldsymbol{\xi}_j\Bigr\|^2\right] = \frac{1}{B^2}\sum_{j=1}^{B}\sum_{l=1}^{B}\mathbb{E}\bigl[\langle \boldsymbol{\xi}_j, \boldsymbol{\xi}_l\rangle\bigr]

を得ます。j≠lj \ne l の項では ξj\boldsymbol{\xi}_j と ξl\boldsymbol{\xi}_l が独立なので E[⟨ξj,ξl⟩]=⟨E[ξj],E[ξl]⟩=0\mathbb{E}[\langle \boldsymbol{\xi}_j,\boldsymbol{\xi}_l\rangle] = \langle \mathbb{E}[\boldsymbol{\xi}_j], \mathbb{E}[\boldsymbol{\xi}_l]\rangle = 0 です（成分ごとに独立確率変数の積の期待値が期待値の積になることを使い、E[ξj]=0\mathbb{E}[\boldsymbol{\xi}_j] = \boldsymbol{0} を代入しました）。残るのは j=lj = l の BB 項だけで、

1B2∑j=1BE[∥ξj∥2]=1B2⋅B σ2(w)=σ2(w)B\frac{1}{B^2}\sum_{j=1}^{B}\mathbb{E}\bigl[\|\boldsymbol{\xi}_j\|^2\bigr] = \frac{1}{B^2}\cdot B\,\sigma^2(\boldsymbol{w}) = \frac{\sigma^2(\boldsymbol{w})}{B}

となります。

命題 7.2 は「ミニバッチ勾配は平均としては正しく、誤差の大きさは σ/B\sigma/\sqrt{B} 程度」と言っています。ここに大数の法則（大数の法則と中心極限定理）と同じ 1/B1/\sqrt{B} が現れます。重要なのは、BB を 4 倍にしても精度は 2 倍にしかならないのに、計算コストは 4 倍かかるという非対称性です。

例 7.3（同じ計算予算で何歩進めるか）

N=106N = 10^6、勾配 1 サンプル分の計算コストを 1 単位とします。予算を 10710^7 単位とすると、

方法1 歩のコスト歩数勾配の誤差の目安
勾配降下法（B=NB = N）10610^6101000
ミニバッチ（B=100B = 100）10010010510^5σ/10\sigma/10
SGD（B=1B = 1）1110710^7σ\sigma

勾配降下法は誤差ゼロの方向に 10 歩しか進めません。命題 5.1 で見たように、条件数が 100 程度の問題では 10 歩ではほとんど何も起きません。一方 SGD は方向が毎回大きくぶれますが 10710^7 歩進めます。ぶれは平均すると打ち消し合うので、正味では圧倒的にこちらが先へ進みます。

実際に使われるのは中間の B=32B = 32 から 10241024 程度です。これは統計的な理由というより、行列積の形にまとめて GPU で並列計算するとき、BB をある程度大きくしないと演算器が遊んでしまうという計算機側の事情によります。

注意 7.4

SGD では定数学習率のままでは最小点に落ち着きません。命題 7.2 より勾配推定の分散は最小点の近くでも σ2/B\sigma^2/B だけ残るので、wk\boldsymbol{w}_k は最小点のまわりを半径 O(ησ)O(\eta\sigma) 程度でうろつき続けます。そこで学習率を徐々に下げます。ロビンスとモンローが 1951 年に与えた古典的な十分条件は

∑k=0∞ηk=∞,∑k=0∞ηk2<∞\sum_{k=0}^{\infty}\eta_k = \infty, \qquad \sum_{k=0}^{\infty}\eta_k^2 < \infty

の二つです。第 1 条件は「どんなに遠い初期値からでも最小点まで到達できるだけの総移動距離を確保する」ことを、第 2 条件は「揺らぎの累積効果を有限に抑える」ことを意味します。ηk=η0/(k+1)\eta_k = \eta_0/(k+1) が代表例です（演習 8.4）。深層学習では、この理論的な条件を厳密に満たすかどうかより、コサイン減衰や段階的減衰など経験的に良い挙動を示すスケジュールが好まれています。

なお実装上の SGD は、毎回独立に添字を引くのではなく、データをシャッフルして順に使い切る（エポック）方式が普通です。この場合は厳密には独立サンプリングではないため 命題 7.2 はそのままは適用できませんが、挙動はよく似ています。

勾配の情報だけを使う手法はここで打ち止めではありません。過去の更新方向を慣性として足すモーメンタム法、座標ごとに学習率を調整する AdaGrad や Adam などは、いずれも 定義 4.1 の一行を書き換えたものです。注意 3.4 で触れたとおり、これらは「どのノルムで最急降下を測るか」を暗黙に変えている、と解釈できます。次章のニューラルネットワークと逆伝播では、この ∇f(w)\nabla f(\boldsymbol{w}) を数百万次元で効率よく計算する方法、すなわち連鎖律の巧妙な使い方を扱います。

8. 演習

Section titled “8. 演習”

演習 8.2標準

f:Rn→Rf : \mathbb{R}^n\to\mathbb{R} を C1C^1 級かつ LL-平滑とします。

  1. ∇f(wk)≠0\nabla f(\boldsymbol{w}_k) \ne \boldsymbol{0} かつ 0<η<2/L0 < \eta < 2/L ならば f(wk+1)<f(wk)f(\boldsymbol{w}_{k+1}) < f(\boldsymbol{w}_k) であることを示してください。
  2. η=2/L\eta = 2/L のとき、この結論が成り立たない例を挙げてください。
解答

1. 系 4.4 がそのまま答えです。wk+1=wk−η∇f(wk)\boldsymbol{w}_{k+1} = \boldsymbol{w}_k - \eta\nabla f(\boldsymbol{w}_k) に対して

f(wk+1)≤f(wk)−η(1−Lη2)∥∇f(wk)∥2f(\boldsymbol{w}_{k+1}) \le f(\boldsymbol{w}_k) - \eta\Bigl(1 - \frac{L\eta}{2}\Bigr)\|\nabla f(\boldsymbol{w}_k)\|^2

であり、0<η<2/L0 < \eta < 2/L から η>0\eta > 0 かつ 1−Lη/2>01 - L\eta/2 > 0 なので係数 η(1−Lη/2)\eta(1-L\eta/2) は正、∥∇f(wk)∥2>0\|\nabla f(\boldsymbol{w}_k)\|^2 > 0 なので減少量は正です。

2. n=1n = 1、f(w)=L2w2f(w) = \frac{L}{2}w^2 とします。f′(w)=Lwf'(w) = Lw なので ∣f′(u)−f′(v)∣=L∣u−v∣|f'(u)-f'(v)| = L|u-v| となり、この ff はちょうど LL-平滑です。η=2/L\eta = 2/L とすると

wk+1=wk−2L⋅Lwk=−wkw_{k+1} = w_k - \frac{2}{L}\cdot L w_k = -w_k

なので、w0≠0w_0 \ne 0 から始めると wkw_k は w0w_0 と −w0-w_0 を永久に往復し、f(wk)=L2w02f(w_k) = \frac{L}{2}w_0^2 は一定です。勾配は 00 でないのに値が減りません。したがって 0<η<2/L0 < \eta < 2/L の上限は改善できません。これは 例 5.2 の η=0.08\eta = 0.08 の行で観察した現象そのものです。

演習 8.3標準

命題 6.1 の設定で、特徴ベクトルがすべて ∥xi∥≤R\|\boldsymbol{x}_i\| \le R を満たすとします。このとき ff は L=R2/4L = R^2/4 で LL-平滑であることを示してください。λmax⁡(XTX)\lambda_{\max}(X^{\mathsf{T}}X) を使う評価と比べて、どちらが常に良い（小さい）かも確認してください。

解答

命題 6.1 の 2 の二次形式に、pi(1−pi)≤1/4p_i(1-p_i)\le 1/4 とコーシー・シュワルツの不等式 ⟨xi,v⟩2≤∥xi∥2∥v∥2≤R2∥v∥2\langle \boldsymbol{x}_i,\boldsymbol{v}\rangle^2 \le \|\boldsymbol{x}_i\|^2\|\boldsymbol{v}\|^2 \le R^2\|\boldsymbol{v}\|^2 を代入します。

⟨v,∇2f(w)v⟩=1N∑i=1Npi(1−pi)⟨xi,v⟩2≤1N⋅N⋅14R2∥v∥2=R24∥v∥2.\bigl\langle \boldsymbol{v}, \nabla^2 f(\boldsymbol{w})\boldsymbol{v}\bigr\rangle = \frac{1}{N}\sum_{i=1}^{N}p_i(1-p_i)\langle \boldsymbol{x}_i,\boldsymbol{v}\rangle^2 \le \frac{1}{N}\cdot N\cdot \frac{1}{4}R^2\|\boldsymbol{v}\|^2 = \frac{R^2}{4}\|\boldsymbol{v}\|^2 .

半正定値対称行列の作用素ノルムはレイリー商の上限に等しいので ∥∇2f(w)∥2≤R2/4\|\nabla^2 f(\boldsymbol{w})\|_2 \le R^2/4 であり、Appendix の評価より ∇f\nabla f は R2/4R^2/4-リプシッツです。

比較のため λmax⁡(XTX)/(4N)\lambda_{\max}(X^{\mathsf{T}}X)/(4N) を見ます。XTX=∑ixixiTX^{\mathsf{T}}X = \sum_i \boldsymbol{x}_i\boldsymbol{x}_i^{\mathsf{T}} のトレースは ∑i∥xi∥2≤NR2\sum_i\|\boldsymbol{x}_i\|^2 \le NR^2 で、λmax⁡\lambda_{\max} はトレース以下（固有値がすべて非負だから）なので

λmax⁡(XTX)4N≤NR24N=R24\frac{\lambda_{\max}(X^{\mathsf{T}}X)}{4N} \le \frac{NR^2}{4N} = \frac{R^2}{4}

となり、この場合は固有値による評価のほうが常に良いことが分かります。等号は全サンプルが同じ 1 本の直線上に乗り、かつ ∥xi∥=R\|\boldsymbol{x}_i\| = R のときに達成されます。逆に特徴が多方向に散らばっていれば λmax⁡\lambda_{\max} は NR2NR^2 よりずっと小さくなり、より大きな学習率が許されます。ただし λmax⁡\lambda_{\max} の計算には O(Nn2)O(Nn^2) 程度の手間がかかるので、RR による評価は「安価だが保守的な代用品」として意味があります。

演習 8.4標準

注意 7.4 のロビンス・モンロー条件について答えてください。

  1. ηk=η0/(k+1)\eta_k = \eta_0/(k+1)（η0>0\eta_0 > 0）が二つの条件をともに満たすことを示してください。
  2. ηk=η0/k+1\eta_k = \eta_0/\sqrt{k+1} はどちらの条件を満たし、どちらを満たさないでしょうか。
  3. ηk=η0γk\eta_k = \eta_0 \gamma^k（0<γ<10 < \gamma < 1）はどうでしょうか。
解答

1. ∑k≥0η0/(k+1)=η0∑m≥11/m\sum_{k\ge 0}\eta_0/(k+1) = \eta_0\sum_{m\ge 1} 1/m は調和級数で発散するので第 1 条件を満たします。∑k≥0η02/(k+1)2=η02∑m≥11/m2=η02π2/6<∞\sum_{k\ge 0}\eta_0^2/(k+1)^2 = \eta_0^2\sum_{m\ge1}1/m^2 = \eta_0^2\pi^2/6 < \infty なので第 2 条件も満たします（級数と収束判定）。

2. ∑k≥0η0/k+1=η0∑m≥1m−1/2\sum_{k\ge0}\eta_0/\sqrt{k+1} = \eta_0\sum_{m\ge1}m^{-1/2} は pp 級数で p=1/2≤1p = 1/2 \le 1 なので発散し、第 1 条件は満たします。一方 ∑k≥0η02/(k+1)=η02∑m≥11/m\sum_{k\ge0}\eta_0^2/(k+1) = \eta_0^2\sum_{m\ge1}1/m は調和級数でやはり発散するので、第 2 条件は満たしません。したがってこのスケジュールでは、理論上は最小点への収束が保証されません。実際、減衰が遅すぎて揺らぎが残ります。

3. 等比級数なので ∑kη0γk=η0/(1−γ)<∞\sum_k \eta_0\gamma^k = \eta_0/(1-\gamma) < \infty、∑kη02γ2k=η02/(1−γ2)<∞\sum_k \eta_0^2\gamma^{2k} = \eta_0^2/(1-\gamma^2) < \infty です。第 2 条件は満たしますが第 1 条件を満たしません。総移動距離が有限なので、初期値が最小点から η0∑k∥∇fik∥\eta_0\sum_k\|\nabla f_{i_k}\| の上限より遠いと、そもそも届きません。学習率を指数的に速く下げすぎると「途中で凍りついて動かなくなる」のはこのためです。

参考文献

Section titled “参考文献”
  • A.-L. Cauchy, “Méthode générale pour la résolution des systèmes d’équations simultanées”, Comptes Rendus de l’Académie des Sciences 25 (1847), 536–538. — 勾配降下法の原論文。2 ページ半で、現代の教科書と同じ発想が述べられています。
  • S. Boyd, L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004 — 第 9 章「Unconstrained minimization」。降下方向・直線探索・収束解析が体系的にまとまっています。全文が 著者のページ で公開されています。
  • J. Nocedal, S. J. Wright, Numerical Optimization, 2nd ed., Springer, 2006 — 第 3 章「Line Search Methods」。ウルフ条件など、学習率を自動で決める古典的な方法が詳しく扱われています。
  • H. Robbins, S. Monro, “A Stochastic Approximation Method”, The Annals of Mathematical Statistics 22 (1951), 400–407. DOI: 10.1214/aoms/1177729586 — 確率的近似法の原論文。注意 7.4 の学習率条件の出典です。
  • L. Bottou, F. E. Curtis, J. Nocedal, “Optimization Methods for Large-Scale Machine Learning”, SIAM Review 60 (2018), 223–311. arXiv:1606.04838 — 大規模学習における確率的手法の総説。バッチサイズと収束の関係が丁寧に議論されています。
  • I. Goodfellow, Y. Bengio, A. Courville, Deep Learning, MIT Press, 2016 — 第 4 章「Numerical Computation」、第 8 章「Optimization for Training Deep Models」。モーメンタムや Adam など実用的な改良の位置づけが分かります。全文が 公式サイト で公開されています。

Appendix: ヘッセ行列の有界性から平滑性へ

Section titled “Appendix: ヘッセ行列の有界性から平滑性へ”

示したいこと。 本文では 命題 6.1 と 演習 8.3 で「ヘッセ行列の作用素ノルムが LL 以下なら LL-平滑」という事実を使いました。定義 4.2 は勾配のリプシッツ連続性で述べられているので、2 階微分の情報からそこへ渡る橋が要ります。それがこの補足です。主張は次のとおりです。f:Rn→Rf : \mathbb{R}^n\to\mathbb{R} が C2C^2 級で、ある L>0L > 0 についてすべての w\boldsymbol{w} で ∥∇2f(w)∥2≤L\|\nabla^2 f(\boldsymbol{w})\|_2 \le L が成り立つならば、ff は LL-平滑です。

証明。 u,v∈Rn\boldsymbol{u}, \boldsymbol{v} \in \mathbb{R}^n を任意に取り、d=v−u\boldsymbol{d} = \boldsymbol{v}-\boldsymbol{u}、ψ(t)=∇f(u+td)\boldsymbol{\psi}(t) = \nabla f(\boldsymbol{u} + t\boldsymbol{d})（t∈[0,1]t\in[0,1]）とおきます。ff が C2C^2 級なので ψ\boldsymbol{\psi} は C1C^1 級で、連鎖律より ψ′(t)=∇2f(u+td) d\boldsymbol{\psi}'(t) = \nabla^2 f(\boldsymbol{u}+t\boldsymbol{d})\,\boldsymbol{d} です。各成分に微分積分学の基本定理を適用してベクトルにまとめると

∇f(v)−∇f(u)=ψ(1)−ψ(0)=∫01∇2f(u+td) d dt\nabla f(\boldsymbol{v}) - \nabla f(\boldsymbol{u}) = \boldsymbol{\psi}(1) - \boldsymbol{\psi}(0) = \int_0^1 \nabla^2 f(\boldsymbol{u}+t\boldsymbol{d})\,\boldsymbol{d}\ dt

を得ます。ベクトル値積分に対する三角不等式 ∥∫01ϕ(t)dt∥≤∫01∥ϕ(t)∥dt\bigl\|\int_0^1 \boldsymbol{\phi}(t)dt\bigr\| \le \int_0^1\|\boldsymbol{\phi}(t)\|dt と、作用素ノルムの定義 ∥Hd∥≤∥H∥2∥d∥\|H\boldsymbol{d}\| \le \|H\|_2\|\boldsymbol{d}\| を順に使えば

∥∇f(v)−∇f(u)∥≤∫01∥∇2f(u+td) d∥ dt≤∫01L∥d∥ dt=L∥v−u∥\bigl\|\nabla f(\boldsymbol{v}) - \nabla f(\boldsymbol{u})\bigr\| \le \int_0^1 \bigl\|\nabla^2 f(\boldsymbol{u}+t\boldsymbol{d})\,\boldsymbol{d}\bigr\|\,dt \le \int_0^1 L\|\boldsymbol{d}\|\,dt = L\|\boldsymbol{v}-\boldsymbol{u}\|

となり、定義 4.2 の条件が示せました。

対称行列の作用素ノルムと固有値。 本文では「対称半正定値行列 HH について ∥H∥2=λmax⁡(H)\|H\|_2 = \lambda_{\max}(H)」という事実も使いました。これはスペクトル定理から出ます。HH を正規直交固有基底 q1,…,qn\boldsymbol{q}_1,\ldots,\boldsymbol{q}_n（固有値 μ1,…,μn\mu_1,\ldots,\mu_n）で表し、v=∑iciqi\boldsymbol{v} = \sum_i c_i\boldsymbol{q}_i と展開すると

∥Hv∥2=∥∑iμiciqi∥2=∑iμi2ci2≤(max⁡iμi2)∑ici2=(max⁡i∣μi∣)2∥v∥2\|H\boldsymbol{v}\|^2 = \Bigl\|\sum_i \mu_i c_i \boldsymbol{q}_i\Bigr\|^2 = \sum_i \mu_i^2 c_i^2 \le \bigl(\max_i \mu_i^2\bigr)\sum_i c_i^2 = \bigl(\max_i|\mu_i|\bigr)^2\|\boldsymbol{v}\|^2

であり、最大値を与える固有ベクトルで等号が成り立つので ∥H∥2=max⁡i∣μi∣\|H\|_2 = \max_i|\mu_i| です。半正定値なら固有値はすべて非負なので、これは λmax⁡(H)\lambda_{\max}(H) に一致します。

なぜ C2C^2 級を仮定したくないのか。 本文の 補題 4.3（降下補題）は C1C^1 級と LL-平滑性だけから証明しました。2 階微分の存在を仮定していないのは、機械学習でよく使う ReLU を含むネットワークのように、2 階微分が至るところでは存在しない関数を扱いたいからです。LL-平滑性という条件は、そうした関数にも（区分的に）適用できる、より弱く扱いやすい仮定になっています。

このテーマの 100 本ノック（50 問）

関連記事

執筆: Claude Code（Sonnet 5.5）・監査 3 回（Claude Code）・最終 2026-10-12

この記事の誤りを報告する ・運営: 夢現技研合同会社 ・料金 ・利用条件 ・特定商取引法に基づく表記

© 2026 夢現技研合同会社 ・コード例は MIT ライセンスです。