## 2. 準備：勾配とは何か
多変数関数の微分については[多変数関数の微分と偏微分](/mathematics/calculus/multivariable-differentiation)で扱っており、全微分可能性は
で定義しました。ここではこの章で使う形に整理し直しておきます。鍵は「偏微分を並べたもの」ではなく「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}}.
$$
一意性と成分表示は定義からすぐに出ます。$\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 次近似の係数」という読み方を強調しておきます。
が言っているのは、$\boldsymbol{w}$ の近くでは
$$
f(\boldsymbol{w} + \boldsymbol{h}) \approx f(\boldsymbol{w}) + \langle \nabla f(\boldsymbol{w}), \boldsymbol{h}\rangle
$$
という**線形**の式で $f$ が近似でき、その誤差は $\|\boldsymbol{h}\|$ より速く $0$ に近づく、ということです。勾配降下法はこの近似式だけを頼りに次の一歩を決めます。
$\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$ の増加率」を表します。
$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$ とします。偏微分を成分ごとに計算するのではなく、
## 3. なぜ勾配が「最も急な坂」なのか
「勾配は最も急な坂の方向を指す」という言い方をよく聞きます。これは比喩ではなく、証明できる主張です。まず方向微分と勾配を結びつけます。
$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
$$
が成り立ちます。
によって、「どの向きに進むと $f$ が最も速く減るか」という問いは「単位ベクトル $\boldsymbol{u}$ のうち内積 $\langle \nabla f(\boldsymbol{w}), \boldsymbol{u}\rangle$ を最小にするのはどれか」という代数の問題に置き換わりました。この問題は完全に解けます。
$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})\|$ のときに限ります。
$\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})\|.
$$
の証明で使ったのはコーシー・シュワルツの不等式の等号条件そのものです（$\|\alpha\boldsymbol{u}+\boldsymbol{a}\|^2 \ge 0$ を展開する、という標準的な導出をその場で書き下しました）。つまり「勾配が最急降下方向である」ことの数学的な中身は、**内積が最大になるのはベクトルが平行なとき**という事実に尽きます。
$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$ であることは同値です。
$D_{\boldsymbol{u}}f(\boldsymbol{w}) = 0$ は「その向きに動いても $f$ が 1 次のオーダーでは変わらない」ということ、つまり等高線（等位集合）に沿って動くということです。
は、勾配が等高線と直交することを意味します。後で描く図では、この直交性が重要な役割を果たします。
「最も急」という言葉は、**どのノルムで歩幅を測るか**に依存しています。
## 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$ によらないとき、定数学習率であるといいます。
B["勾配 ∇f(w) を計算する"]
B --> C{"‖∇f(w)‖ は十分小さいか"}
C -- いいえ --> D["更新: w ← w − η ∇f(w)"]
D --> B
C -- はい --> E["w を近似解として出力して停止"]`} />
が保証しているのは「向きが正しい」ことだけで、$\eta$ をいくらにしてよいかは何も言っていません。方向微分は $t \to 0$ の極限の話なので、有限の $\eta$ で本当に値が下がるかは別問題です。ここを埋めるのが次の平滑性の仮定です。
$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$ が大きいと、少し動いただけで坂の向きが変わってしまいます。この直観を定量化するのが次の補題です。
$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
$$
が成り立ちます。
$\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 .
$$
微分積分学の基本定理（[積分の基本定理](/mathematics/calculus/integration-and-ftc)）を $\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 .
$$
被積分関数をコーシー・シュワルツの不等式で押さえ、続いて は「$f$ は 1 次近似より上には行かない、ただし高々 $\frac{L}{2}\|\boldsymbol{d}\|^2$ だけ」という主張です。テイラーの定理（[平均値の定理とテイラーの定理](/mathematics/calculus/mean-value-and-taylor)の
）の 2 次の剰余項を、2 階微分の存在を仮定せずに $L$ で押さえた形になっています。この上界を最小にするように 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$ です。
学習率の意味がはっきりしました。**$\eta$ は 1 次近似を信用する範囲を決める量**で、その安全圏の広さは平滑性定数 $L$ の逆数で測られます。$\eta \ge 2/L$ では
の右辺が $f(\boldsymbol{w})$ を超えてしまい、減少の保証が消えます。
$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$）。
## 5. 二次関数で見る収束の速さ
二次関数は、勾配降下法の挙動を完全に手計算で追える唯一の例です。しかも一般の $f$ も最小点の近くでは二次関数で近似されるので、ここで分かることは局所的な挙動の指針になります。
$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}.
$$
まず勾配を求めます。 の 2 は
と正確に整合します。二次関数 $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$ となり、収束の必要十分条件とぴたり一致します。降下補題の評価は二次関数に対しては無駄がない、ということです。
の 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 歩進めた軌跡です。
のとおり勾配は等高線に直交するので、細長い谷では勾配がほとんど「谷を横切る向き」を指し、「谷に沿って最小点へ向かう向き」の成分はごくわずかしか含みません。その結果、上下に激しく振動しながら少しずつ右から左へ進むことになります。
この例では $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 回の反復が必要です。
同じ $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$ です。
```python
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$ |
## 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]
$$
です。
上の $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}$ が取れます。
まずシグモイド関数の微分を確かめます。$\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}$ が大域最小の必要十分条件です（ の 2 と 3 を合わせると、ロジスティック回帰の学習は「凸で $L$-平滑な関数の最小化」という、
がそのまま使える設定だと分かります。しかも $L$ はデータから直接計算できます。手探りではなく、$\eta = 4N/\lambda_{\max}(X^{\mathsf{T}}X)$ から始めればよいのです。
手で最後まで追えるように、特徴量を 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$ なので、
## 7. 確率的勾配降下法：勾配を安く見積もる
の勾配の式をもう一度見てください。1 回の更新のために $N$ 個のサンプルすべてについて $p_i$ を計算し、$\boldsymbol{x}_i$ を足し合わせています。計算量は 1 反復あたり $O(Nn)$ です。$N = 10^{8}$ のデータで
の $O(1/T)$ を頼りに 1000 回反復しようとすれば、$10^{11}$ 回のオーダーの積和が必要になります。
ここで発想を変えます。$f$ は $N$ 個の関数の**平均**です。平均を正確に計算する代わりに、少数のサンプルで**推定**すればどうでしょうか。世論調査で全有権者に聞かずに 1000 人の標本で支持率を推定するのと同じ考え方です。
目的関数が $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$（かつ非復元抽出）が通常の勾配降下法にあたります。
この方法が意味を持つのは、次の二つの性質があるからです。
は「ミニバッチ勾配は平均としては正しく、誤差の大きさは $\sigma/\sqrt{B}$ 程度」と言っています。ここに大数の法則（[大数の法則と中心極限定理](/mathematics/probability/limit-theorems)）と同じ $1/\sqrt{B}$ が現れます。重要なのは、**$B$ を 4 倍にしても精度は 2 倍にしかならない**のに、計算コストは 4 倍かかるという非対称性です。
$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 歩しか進めません。
勾配の情報だけを使う手法はここで打ち止めではありません。過去の更新方向を慣性として足すモーメンタム法、座標ごとに学習率を調整する AdaGrad や Adam などは、いずれも
の一行を書き換えたものです。
で触れたとおり、これらは「どのノルムで最急降下を測るか」を暗黙に変えている、と解釈できます。次章の[ニューラルネットワークと逆伝播](/computer-science/math-for-ml/backpropagation)では、この $\nabla f(\boldsymbol{w})$ を数百万次元で**効率よく計算する**方法、すなわち連鎖律の巧妙な使い方を扱います。
## 8. 演習
$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$ を決定してください（直線探索）。
**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}.
$$
## 参考文献
- 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」。降下方向・直線探索・収束解析が体系的にまとまっています。全文が [著者のページ](https://web.stanford.edu/~boyd/cvxbook/) で公開されています。
- 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](https://doi.org/10.1214/aoms/1177729586) — 確率的近似法の原論文。
の学習率条件の出典です。
- L. Bottou, F. E. Curtis, J. Nocedal, "Optimization Methods for Large-Scale Machine Learning", *SIAM Review* 60 (2018), 223–311. [arXiv:1606.04838](https://arxiv.org/abs/1606.04838) — 大規模学習における確率的手法の総説。バッチサイズと収束の関係が丁寧に議論されています。
- I. Goodfellow, Y. Bengio, A. Courville, *Deep Learning*, MIT Press, 2016 — 第 4 章「Numerical Computation」、第 8 章「Optimization for Training Deep Models」。モーメンタムや Adam など実用的な改良の位置づけが分かります。全文が [公式サイト](https://www.deeplearningbook.org/) で公開されています。
## Appendix: ヘッセ行列の有界性から平滑性へ
**示したいこと。** 本文では
と
で「ヘッセ行列の作用素ノルムが $L$ 以下なら $L$-平滑」という事実を使いました。
は勾配のリプシッツ連続性で述べられているので、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}\|
$$
となり、
の条件が示せました。
**対称行列の作用素ノルムと固有値。** 本文では「対称半正定値行列 $H$ について $\|H\|_2 = \lambda_{\max}(H)$」という事実も使いました。これは[スペクトル定理](/mathematics/linear-algebra/spectral-theorem)から出ます。$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$ 級を仮定したくないのか。** 本文の
（降下補題）は $C^1$ 級と $L$-平滑性だけから証明しました。2 階微分の存在を仮定していないのは、機械学習でよく使う ReLU を含むネットワークのように、2 階微分が至るところでは存在しない関数を扱いたいからです。$L$-平滑性という条件は、そうした関数にも（区分的に）適用できる、より弱く扱いやすい仮定になっています。