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

0. この記事の要点

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

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

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

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

$$\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}}$$

でした（交差エントロピー誤差の勾配（Theorem 5.1）［Logistic Regression］）。左辺には未知数 $\boldsymbol{w}$ が指数関数の中に入っています。これは代数方程式ではなく超越方程式で、一般には $\boldsymbol{w}$ について解いた形に書き直せません。$N = 3$ のような小さな例でも、根号や対数を有限回組み合わせた式にはなりません。

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

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

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

以下ではこの二つに、多変数関数のテイラー展開を使って正面から答えます。

Note

この章では最小化する関数を一貫して $f : \mathbb{R}^n \to \mathbb{R}$ と書き、変数を $\boldsymbol{w}$（重み）と書きます。$f$ の最小値（正確には下限）を $f_\star$、最小点を $\boldsymbol{w}_\star$ と書きます。

2. 準備：勾配とは何か

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

Definition 2.1（全微分可能性と勾配）

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

$$f(\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$$

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

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

$$\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}}.$$

Remark 2.2

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

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

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

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

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

$$f(\boldsymbol{w} + \boldsymbol{h}) \approx f(\boldsymbol{w}) + \langle \nabla f(\boldsymbol{w}), \boldsymbol{h}\rangle$$

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

Definition 2.3（方向微分）

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

$$D_{\boldsymbol{u}}f(\boldsymbol{w}) = \lim_{t \to 0}\frac{f(\boldsymbol{w} + t\boldsymbol{u}) - f(\boldsymbol{w})}{t}$$

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

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

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

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

$$\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 行目では内積の随伴の性質 $\langle \boldsymbol{a}, X\boldsymbol{h}\rangle = \langle X^{\mathsf{T}}\boldsymbol{a}, \boldsymbol{h}\rangle$ を使いました（内積空間を参照）。最後の項は作用素ノルム $\|X\|_2$ を使って $\frac{1}{2}\|X\boldsymbol{h}\|^2 \le \frac{1}{2}\|X\|_2^2\|\boldsymbol{h}\|^2$ と評価できるので、

$$\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(\|\boldsymbol{h}\|)$ です。よって Definition 2.1 の $\boldsymbol{g}$ にあたるのは $X^{\mathsf{T}}\boldsymbol{r}$ で、

$$\nabla f(\boldsymbol{w}) = X^{\mathsf{T}}(X\boldsymbol{w} - \boldsymbol{y}) = X^{\mathsf{T}}X\boldsymbol{w} - X^{\mathsf{T}}\boldsymbol{y}.$$

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

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

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

Proposition 3.1（方向微分は勾配との内積）

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

$$D_{\boldsymbol{u}}f(\boldsymbol{w}) = \langle \nabla f(\boldsymbol{w}), \boldsymbol{u}\rangle$$

が成り立ちます。

Proof（Proposition 3.1）

Definition 2.1 の式で $\boldsymbol{h} = t\boldsymbol{u}$（$t \ne 0$）と取ります。すると

$$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})$$

です（内積の双線形性を使いました）。両辺を $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}.$$

ここで $\|t\boldsymbol{u}\| = |t|\,\|\boldsymbol{u}\| = |t|$ ですから

$$\left|\frac{r(t\boldsymbol{u})}{t}\right| = \frac{|r(t\boldsymbol{u})|}{\|t\boldsymbol{u}\|}$$

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

∎

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

Theorem 3.2（最急降下方向）

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

$$D_{\boldsymbol{u}}f(\boldsymbol{w}) \ \ge\ -\|\nabla f(\boldsymbol{w})\|$$

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

$$\boldsymbol{u} = -\frac{\nabla f(\boldsymbol{w})}{\|\nabla f(\boldsymbol{w})\|}$$

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

Proof（Theorem 3.2）

$\boldsymbol{a} = \nabla f(\boldsymbol{w})$、$\alpha = \|\boldsymbol{a}\| > 0$ と略記します。$\|\boldsymbol{u}\| = 1$ なる任意の $\boldsymbol{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$$

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

$$\langle \boldsymbol{a}, \boldsymbol{u}\rangle \ge -\alpha = -\|\nabla f(\boldsymbol{w})\|.$$

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

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

$$\langle \boldsymbol{a}, -\boldsymbol{a}/\alpha\rangle = -\frac{\|\boldsymbol{a}\|^2}{\alpha} = -\alpha$$

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

∎

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

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

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

Proof（Corollary 3.3）

Proposition 3.1 より $D_{\boldsymbol{u}}f(\boldsymbol{w}) = \langle \nabla f(\boldsymbol{w}), \boldsymbol{u}\rangle$ なので、一方が $0$ であることと他方が $0$ であることは同じ主張です。

∎

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

Remark 3.4

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

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

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

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

Definition 4.1（勾配降下法）

$f : \mathbb{R}^n \to \mathbb{R}$ を $C^1$ 級とし、初期値 $\boldsymbol{w}_0 \in \mathbb{R}^n$ と正の数列 $(\eta_k)_{k\ge 0}$ を与えます。

$$\boldsymbol{w}_{k+1} = \boldsymbol{w}_k - \eta_k \nabla f(\boldsymbol{w}_k) \qquad (k = 0, 1, 2, \ldots)$$

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

flowchart TD
A["初期値 w と学習率 η を決める"] --> B["勾配 ∇f(w) を計算する"]
B --> C{"‖∇f(w)‖ は十分小さいか"}
C -- いいえ --> D["更新: w ← w − η ∇f(w)"]
D --> B
C -- はい --> E["w を近似解として出力して停止"]

勾配降下法の 1 反復

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

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

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

$$\|\nabla f(\boldsymbol{u}) - \nabla f(\boldsymbol{v})\| \le L\,\|\boldsymbol{u} - \boldsymbol{v}\| \qquad (\forall\, \boldsymbol{u}, \boldsymbol{v} \in \mathbb{R}^n)$$

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

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

Lemma 4.3（降下補題）

$f : \mathbb{R}^n \to \mathbb{R}$ が $C^1$ 級かつ $L$-平滑ならば、任意の $\boldsymbol{u}, \boldsymbol{v} \in \mathbb{R}^n$ に対して

$$f(\boldsymbol{v}) \le f(\boldsymbol{u}) + \langle \nabla f(\boldsymbol{u}),\ \boldsymbol{v} - \boldsymbol{u}\rangle + \frac{L}{2}\|\boldsymbol{v} - \boldsymbol{u}\|^2$$

が成り立ちます。

Proof（Lemma 4.3）

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

$$\varphi'(t) = \langle \nabla f(\boldsymbol{u} + t\boldsymbol{d}),\ \boldsymbol{d}\rangle .$$

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

$$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 次近似の分 $\langle \nabla f(\boldsymbol{u}), \boldsymbol{d}\rangle = \int_0^1 \langle \nabla f(\boldsymbol{u}), \boldsymbol{d}\rangle\,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 .$$

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

$$\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 .$$

これを積分すると

$$\int_0^1 L t\|\boldsymbol{d}\|^2\,dt = L\|\boldsymbol{d}\|^2 \int_0^1 t\,dt = \frac{L}{2}\|\boldsymbol{d}\|^2$$

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

∎

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

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

$f$ が $C^1$ 級かつ $L$-平滑とし、$\boldsymbol{w}' = \boldsymbol{w} - \eta\nabla f(\boldsymbol{w})$ とします。このとき

$$f(\boldsymbol{w}') \le f(\boldsymbol{w}) - \eta\left(1 - \frac{L\eta}{2}\right)\bigl\|\nabla f(\boldsymbol{w})\bigr\|^2$$

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

Proof（Corollary 4.4）

Lemma 4.3 で $\boldsymbol{u} = \boldsymbol{w}$、$\boldsymbol{v} = \boldsymbol{w}' = \boldsymbol{w} - \eta\nabla f(\boldsymbol{w})$ と取ります。$\boldsymbol{v} - \boldsymbol{u} = -\eta\nabla f(\boldsymbol{w})$ なので

$$\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$$

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

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

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

∎

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

Theorem 4.5（勾配降下法の停留点への収束）

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

1. 数列 $\bigl(f(\boldsymbol{w}_k)\bigr)_{k\ge 0}$ は単調非増加で、ある極限値に収束します。
2. 任意の $T \ge 1$ に対して

$$\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. $\displaystyle\sum_{k=0}^{\infty}\bigl\|\nabla f(\boldsymbol{w}_k)\bigr\|^2 < \infty$。とくに $\|\nabla f(\boldsymbol{w}_k)\| \to 0$（$k \to \infty$）。

Proof（Theorem 4.5）

Corollary 4.4 に $\eta = 1/L$ を代入すると、すべての $k$ について

$$f(\boldsymbol{w}_{k+1}) \le f(\boldsymbol{w}_k) - \frac{1}{2L}\bigl\|\nabla f(\boldsymbol{w}_k)\bigr\|^2$$

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

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

$$\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(\boldsymbol{w}_T) \ge f_\star$）。$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 も同じ不等式から出ます。上の評価は $T$ によらない上界 $2L(f(\boldsymbol{w}_0)-f_\star)$ を部分和に与えているので、非負項からなる級数 $\sum_k \|\nabla f(\boldsymbol{w}_k)\|^2$ の部分和は単調増加かつ有界、よって収束します（級数と収束判定）。収束する級数の一般項は $0$ に収束するので $\|\nabla f(\boldsymbol{w}_k)\|^2 \to 0$、したがって $\|\nabla f(\boldsymbol{w}_k)\| \to 0$ です。

∎

Remark 4.6

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

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

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

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

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

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

$$f(\boldsymbol{w}) = \tfrac{1}{2}\langle \boldsymbol{w}, A\boldsymbol{w}\rangle - \langle \boldsymbol{b}, \boldsymbol{w}\rangle$$

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

1. $\boldsymbol{w}_k - \boldsymbol{w}_\star = (I - \eta A)^k(\boldsymbol{w}_0 - \boldsymbol{w}_\star)$。
2. $\rho(\eta) = \max\bigl(|1-\eta\lambda_1|,\ |1-\eta\lambda_n|\bigr)$ とおくと $\|\boldsymbol{w}_k - \boldsymbol{w}_\star\| \le \rho(\eta)^k\|\boldsymbol{w}_0 - \boldsymbol{w}_\star\|$ であり、さらにすべての初期値 $\boldsymbol{w}_0$ について $\boldsymbol{w}_k \to \boldsymbol{w}_\star$ となるのは $0 < \eta < 2/\lambda_n$ のとき、かつそのときに限ります。
3. $\rho(\eta)$ を最小にする学習率は $\eta_\star = \dfrac{2}{\lambda_1 + \lambda_n}$ で、そのときの値は

$$\rho(\eta_\star) = \frac{\lambda_n - \lambda_1}{\lambda_n + \lambda_1} = \frac{\kappa - 1}{\kappa + 1}.$$

Proof（Proposition 5.1）

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

$$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$$

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

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

$$\boldsymbol{e}_{k+1} = \boldsymbol{w}_k - \eta A\boldsymbol{e}_k - \boldsymbol{w}_\star = (I - \eta A)\boldsymbol{e}_k$$

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

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

$$\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(\eta) = \max_i |1-\eta\lambda_i|$ とおけば $\|\boldsymbol{e}_k\|^2 \le m(\eta)^{2k}\sum_i c_i^2 = m(\eta)^{2k}\|\boldsymbol{e}_0\|^2$ です。

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

収束条件を示します。$0 < \eta < 2/\lambda_n$ なら、各 $i$ について $0 < \eta\lambda_i \le \eta\lambda_n < 2$ ですから $-1 < 1-\eta\lambda_i < 1$、すなわち $\rho(\eta) < 1$ となり $\|\boldsymbol{e}_k\| \to 0$ です。逆に $\eta \ge 2/\lambda_n$ なら $1 - \eta\lambda_n \le -1$ なので、$\boldsymbol{e}_0 = \boldsymbol{q}_n$（すなわち $\boldsymbol{w}_0 = \boldsymbol{w}_\star + \boldsymbol{q}_n$）と取ると $\|\boldsymbol{e}_k\| = |1-\eta\lambda_n|^k \ge 1$ となって $\boldsymbol{0}$ に収束しません。

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

$$1 - \eta\lambda_1 = -(1-\eta\lambda_n) \iff 2 = \eta(\lambda_1+\lambda_n) \iff \eta = \frac{2}{\lambda_1+\lambda_n}$$

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

$$\rho(\eta_\star) = 1 - \frac{2\lambda_1}{\lambda_1+\lambda_n} = \frac{\lambda_n-\lambda_1}{\lambda_n+\lambda_1}$$

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

∎

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

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

$$k \approx \frac{\ln(1/\varepsilon)}{\ln\bigl(1/\rho(\eta_\star)\bigr)} \approx \frac{\kappa}{2}\ln\frac{1}{\varepsilon}$$

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

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

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

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

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

同じ $f(w_1,w_2) = \frac{1}{2}(w_1^2 + 25w_2^2)$ で、学習率を変えて 50 回反復したときの $f$ の値を比べます。$L = \lambda_n = 25$ なので、理論上の安全圏は $0 < \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 回後の $f$
$0.04 = 1/L$	降下補題が勧める値	$2.11 \times 10^{-1}$
$1/13 \approx 0.0769$	Proposition 5.1 の最適値	$8.36 \times 10^{-3}$
$0.08 = 2/L$	安全圏の境界	$1.25 \times 10^{1}$
$0.09$	安全圏の外	$6.14 \times 10^{10}$

読み取れることが三つあります。第一に、$\eta = 1/L = 0.04$ は確かに収束しますが最適値の 2 倍近く遅いということです。実際このとき $1-\eta\lambda_n = 0$ なので $w_2$ は 1 歩で消え、あとは $w_1$ が $0.96$ 倍ずつ縮むだけになります。$0.96^{50} \approx 0.130$ です。第二に、境界値 $\eta = 2/L = 0.08$ では $1-\eta\lambda_n = -1$ となり、$w_2$ が $\pm 1$ を永久に往復して $f$ が減らなくなります（$f$ は約 $12.5$ で停滞します）。第三に、$\eta = 0.09$ では $|1-\eta\lambda_n| = 1.25 > 1$ なので $w_2$ が $1.25^{50} \approx 7.0\times 10^4$ 倍に発散します。

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

Tip

実務では $L$ が分からないことがほとんどです。そのときは学習率を対数スケールで（$10^{-1}, 10^{-2}, 10^{-3}, \ldots$ のように）振って、損失が発散しない最大の値の 3 分の 1 程度を選ぶ、という探し方が実用的だと思います。Example 5.2 の表が示すとおり、安全圏の上限ぎりぎりは性能が最良でも安定でもありません。

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

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

$$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]$$

です。

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

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

1. $f$ は $\mathbb{R}^n$ 上で $C^\infty$ 級で、

$$\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(\boldsymbol{w}) = \mathrm{diag}\bigl(p_1(1-p_1), \ldots, p_N(1-p_N)\bigr)$ を使って

$$\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$$

と書け、これは任意の $\boldsymbol{w}$ で半正定値です。したがって $f$ は凸関数で、停留点はすべて大域最小点です。 3. $f$ は $L$-平滑で、定数として $L = \dfrac{\lambda_{\max}(X^{\mathsf{T}}X)}{4N}$ が取れます。

Proof（Proposition 6.1）

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

$$\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-\sigma(z) = e^{-z}/(1+e^{-z})$ による）。$\sigma$ は $\mathbb{R}$ 上で $C^\infty$ 級かつ $0 < \sigma < 1$ なので、$\log$ との合成も定義域全体で $C^\infty$ 級です。

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

$$\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\sigma$ が打ち消し合うのがロジスティック回帰の気持ちよさで、残るのは「予測確率と正解のずれ」だけです。$z_i(\boldsymbol{w}) = \langle \boldsymbol{w}, \boldsymbol{x}_i\rangle$ は $\boldsymbol{w}$ の線形関数なので $\nabla_{\boldsymbol{w}} z_i = \boldsymbol{x}_i$ であり、連鎖律より

$$\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 .$$

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

2 の証明。 1 をもう一度 $\boldsymbol{w}$ で微分します。$p_i = \sigma(z_i)$ を $\boldsymbol{w}$ で微分すると、上と同じ連鎖律で $\nabla_{\boldsymbol{w}} p_i = \sigma'(z_i)\boldsymbol{x}_i = p_i(1-p_i)\boldsymbol{x}_i$ です。$\nabla f = \frac{1}{N}\sum_i (p_i-y_i)\boldsymbol{x}_i$ の各項をヤコビ行列にすると $\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}}$ となり、主張の式を得ます。

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

$$\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$$

です（$\boldsymbol{v}^{\mathsf{T}}\boldsymbol{x}_i\boldsymbol{x}_i^{\mathsf{T}}\boldsymbol{v} = \langle\boldsymbol{x}_i,\boldsymbol{v}\rangle^2$ と、$0 < p_i < 1$ より $p_i(1-p_i) > 0$ を使いました）。ヘッセ行列が至るところ半正定値な $C^2$ 級関数は凸なので $f$ は凸で、凸関数では $\nabla f(\boldsymbol{w}) = \boldsymbol{0}$ が大域最小の必要十分条件です（凸関数では停留点と大域最小点が一致する（Theorem 4.2）［Why Machine Learning Needs Mathematics］）。

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

$$\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$$

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

∎

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

Example 6.2（4 点のデータで 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 = 4$、$\sum_i x_i^2 = 4+1+1+4 = 10$ なので、Proposition 6.1 の 3 より

$$L = \frac{1}{4N}\sum_{i=1}^{4}x_i^2 = \frac{10}{16} = 0.625, \qquad \eta = \frac{1}{L} = 1.6 .$$

初期値 $w_0 = 0$。 すべての $i$ で $p_i = \sigma(0) = 0.5$ です。損失は $f(0) = -\log 0.5 = 0.693147$。勾配は

$$\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 .$$

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

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

$$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^{-|z_i|})$ の形になります。）勾配は

$$\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 .$$

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

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

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

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

Remark 6.3

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

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

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

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

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

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

目的関数が $C^1$ 級関数の平均

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

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

$$\boldsymbol{w}_{k+1} = \boldsymbol{w}_k - \eta_k \nabla f_{i_k}(\boldsymbol{w}_k)$$

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

$$\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)$$

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

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

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

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

$$\sigma^2(\boldsymbol{w}) = \frac{1}{N}\sum_{i=1}^{N}\bigl\|\nabla f_i(\boldsymbol{w}) - \nabla f(\boldsymbol{w})\bigr\|^2$$

とおきます。このとき

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

が成り立ちます。

Proof（Proposition 7.2）

1 の証明。 添字 $i_j$ は一様分布なので、各 $j$ について期待値の定義（期待値（Definition 4.1）［Random Variables and Expectation］）から

$$\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})$$

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

$$\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 の証明。 $\boldsymbol{\xi}_j = \nabla f_{i_j}(\boldsymbol{w}) - \nabla f(\boldsymbol{w})$ とおきます。1 より $\mathbb{E}[\boldsymbol{\xi}_j] = \boldsymbol{0}$ で、$i_1,\ldots,i_B$ が独立なので $\boldsymbol{\xi}_1,\ldots,\boldsymbol{\xi}_B$ も独立です。また

$$\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})$$

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

$$\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 \ne l$ の項では $\boldsymbol{\xi}_j$ と $\boldsymbol{\xi}_l$ が独立なので $\mathbb{E}[\langle \boldsymbol{\xi}_j,\boldsymbol{\xi}_l\rangle] = \langle \mathbb{E}[\boldsymbol{\xi}_j], \mathbb{E}[\boldsymbol{\xi}_l]\rangle = 0$ です（成分ごとに独立確率変数の積の期待値が期待値の積になることを使い、$\mathbb{E}[\boldsymbol{\xi}_j] = \boldsymbol{0}$ を代入しました）。残るのは $j = l$ の $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}$$

となります。

∎

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

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

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

方法	1 歩のコスト	歩数	勾配の相対誤差の目安
勾配降下法（$B = N$）	$10^6$	$10$	$0$
ミニバッチ（$B = 100$）	$100$	$10^5$	$\sigma/10$
SGD（$B = 1$）	$1$	$10^7$	$\sigma$

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

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

Remark 7.4

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

$$\sum_{k=0}^{\infty}\eta_k = \infty, \qquad \sum_{k=0}^{\infty}\eta_k^2 < \infty$$

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

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

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

8. 演習

Exercise 8.1易

$f(w_1, w_2) = w_1^2 + w_1w_2 + w_2^2$ とし、点 $\boldsymbol{w} = (1,2)^{\mathsf{T}}$ を考えます。

1. $\nabla f(\boldsymbol{w})$ を求め、最急降下方向（単位ベクトル）とそのときの方向微分の値を答えてください。
2. $\boldsymbol{w}$ から最急降下方向に $\eta\|\nabla f(\boldsymbol{w})\|$ だけ進んだ点、すなわち $\boldsymbol{w} - \eta\nabla f(\boldsymbol{w})$ における $f$ の値を $\eta$ の関数として求め、それを最小にする $\eta$ を決定してください（直線探索）。

Solution

1. 偏微分すると $\partial f/\partial w_1 = 2w_1 + w_2$、$\partial f/\partial w_2 = w_1 + 2w_2$ なので

$$\nabla f(1,2) = (2\cdot 1 + 2,\ 1 + 2\cdot 2)^{\mathsf{T}} = (4, 5)^{\mathsf{T}}, \qquad \|\nabla f(1,2)\| = \sqrt{16+25} = \sqrt{41}.$$

Theorem 3.2 より最急降下方向は $-\nabla f/\|\nabla f\| = -(4,5)^{\mathsf{T}}/\sqrt{41}$ で、そのときの方向微分は $-\sqrt{41} \approx -6.403$ です。

2. $u = 1-4\eta$、$v = 2-5\eta$ とおいて代入します。

$$\begin{aligned} u^2 &= 1 - 8\eta + 16\eta^2, \\ uv &= (1-4\eta)(2-5\eta) = 2 - 13\eta + 20\eta^2, \\ v^2 &= 4 - 20\eta + 25\eta^2 \end{aligned}$$

なので

$$g(\eta) = f(1-4\eta,\ 2-5\eta) = u^2 + uv + v^2 = 7 - 41\eta + 61\eta^2 .$$

$\eta = 0$ で $g(0) = 7 = f(1,2)$ となり検算が合います。$g'(\eta) = -41 + 122\eta = 0$ より $\eta = 41/122 \approx 0.336$ で、$g$ は下に凸なのでここが最小です。最小値は

$$g\!\left(\frac{41}{122}\right) = 7 - \frac{41^2}{122} + \frac{61\cdot 41^2}{122^2} = 7 - \frac{1681}{122} + \frac{1681}{244} = 7 - \frac{1681}{244} = \frac{27}{244} \approx 0.1107 .$$

参考までに、$f(\boldsymbol{w}) = \frac{1}{2}\langle \boldsymbol{w}, A\boldsymbol{w}\rangle$（$A = \begin{pmatrix}2 & 1\\ 1 & 2\end{pmatrix}$）と書けるので、Proposition 5.1 の固有値は $\lambda_1 = 1$、$\lambda_2 = 3$、最適な定数学習率は $\eta_\star = 2/(1+3) = 0.5$ です。1 歩だけの最適値 $41/122$ とは一致しません。直線探索は「その 1 歩」を最良にするだけで、長い目で見た最良とは限らない、という点に注意してください。

Exercise 8.2標準

$f : \mathbb{R}^n\to\mathbb{R}$ を $C^1$ 級かつ $L$-平滑とします。

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

Solution

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

$$f(\boldsymbol{w}_{k+1}) \le f(\boldsymbol{w}_k) - \eta\Bigl(1 - \frac{L\eta}{2}\Bigr)\|\nabla f(\boldsymbol{w}_k)\|^2$$

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

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

$$w_{k+1} = w_k - \frac{2}{L}\cdot L w_k = -w_k$$

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

Exercise 8.3標準

Proposition 6.1 の設定で、特徴ベクトルがすべて $\|\boldsymbol{x}_i\| \le R$ を満たすとします。このとき $f$ は $L = R^2/4$ で $L$-平滑であることを示してください。$\lambda_{\max}(X^{\mathsf{T}}X)$ を使う評価と比べて、どちらが良い（小さい）とは限らないことも確認してください。

Solution

Proposition 6.1 の 2 の二次形式に、$p_i(1-p_i)\le 1/4$ とコーシー・シュワルツの不等式 $\langle \boldsymbol{x}_i,\boldsymbol{v}\rangle^2 \le \|\boldsymbol{x}_i\|^2\|\boldsymbol{v}\|^2 \le R^2\|\boldsymbol{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 .$$

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

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

$$\frac{\lambda_{\max}(X^{\mathsf{T}}X)}{4N} \le \frac{NR^2}{4N} = \frac{R^2}{4}$$

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

Exercise 8.4標準

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

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

Solution

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

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

参考文献

• 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 — 確率的近似法の原論文。Remark 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: ヘッセ行列の有界性から平滑性へ

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

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

$$\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$$

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

$$\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}\|$$

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

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

$$\|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|\mu_i|$ です。半正定値なら固有値はすべて非負なので、これは $\lambda_{\max}(H)$ に一致します。

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