勾配降下法

同義語:最急降下法gradient descentgradient descent methodsteepest descent method

概要

勾配降下法(gradient descent)とは、微分可能な関数 $f$ の最小点を探すため、点 $x_k$ の勾配の逆の向きに進む更新 $x_{k+1}=x_k-s_k\nabla f(x_k)$ を繰り返す反復法で、最急降下法ともいう。$L$ 平滑な関数(勾配が定数 $L$ の Lipschitz 連続)では刻み幅 $1/L$ 以下で値が単調に減り、凸で最小点があれば誤差は $1/k$ の速さで減る。さらに $m$ 強凸なら誤差は等比数列で減るが、その速さは条件数 $L/m$ で決まり、等高線の細長い問題ではジグザグに進んで遅い。機械学習や最小二乗法など、変数の多い問題の最小化に使う。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 偏微分, 凸関数, 最適化

$f(x,y)=\frac12(x^2+10y^2)$ の最小点は見れば分かるが、変数が数千あり式が複雑な関数では、$\nabla f=0$ を閉じた形で解くことはできない。それでも、今いる点の勾配は計算できることが多い。勾配の逆の向きは、その点で値が最も急に減る向きである。そこで、この向きに少し進むことを繰り返す。これが 勾配降下法 である。
1 回の計算が勾配 1 個で済むので、Newton 系の方法の使えない大きな問題でも動く。その代わり、等高線が細長い問題では遅い。上の $f$ で $(10,1)$ から始めると、点は谷をジグザグに渡りながら進み、値が $10^{-6}$ を切るまでに 45 回かかる(ex-gd-zigzag)。
この記事では、刻み幅の決め方ごとの収束の評価を表にし、それらが正しいことを証明する。強凸な関数で速さを決めるのは、関数の条件数 $\kappa$ である。

定義と使える条件

以下、$\mathbb{R}^n$ の内積を $a\cdot b$、長さを $\lvert x\rvert=\sqrt{x\cdot x}$ と書く。微分可能な $f\colon\mathbb{R}^n\to\mathbb{R}$ の 勾配 は、偏微分係数を並べたベクトル $\nabla f(x)=(\partial_1f(x),\dots,\partial_nf(x))$ である。

勾配降下法

$f\colon\mathbb{R}^n\to\mathbb{R}$ を微分可能な関数とする。初期点 $x_0$ と正の数 $s_0,s_1,\dots$ をとり、
$$ x_{k+1}:=x_k-s_k\nabla f(x_k)\qquad(k=0,1,2,\dots) $$
で点列を作る方法を 勾配降下法(最急降下法)という。$s_k$ を 刻み幅 という。すべての $k$ で $s_k=s$ のとき固定刻みという。

文献によっては、「最急降下法」を下の完全直線探索を使う場合に限ることがある。また、積分の漸近評価にも同じ名の方法がある(漸近解析 の鞍点法)が、これは別のものである。最大化は $-f$ に当てはめる。

最も急な下りの向き

$f$ が点 $x$ で微分可能で $\nabla f(x)\ne0$ とする。長さ $1$ のベクトル $d$ のうち、方向微分係数 $\nabla f(x)\cdot d$ を最小にするものは $d=-\nabla f(x)/\lvert\nabla f(x)\rvert$ だけである。

Cauchy–Schwarzの不等式 より $\nabla f(x)\cdot d\ge-\lvert\nabla f(x)\rvert\lvert d\rvert=-\lvert\nabla f(x)\rvert$ で、等号は $d$ が $-\nabla f(x)$ の正の数倍のときに限る。$\square$

この向きに十分小さく進めば値が下がることは、最適化 の命題「降下方向」が述べている。問題は、どれだけ進んでよいかである。それを決めるのが次の 2 つの量である。

L 平滑と m 強凸

$f\colon\mathbb{R}^n\to\mathbb{R}$ を微分可能とする。

  1. $L>0$ について、すべての $x,y$ で $\lvert\nabla f(x)-\nabla f(y)\rvert\le L\lvert x-y\rvert$ のとき、$f$ は $L$ 平滑 であるという(勾配が Lipschitz連続)。
  2. $m>0$ について、すべての $x,y$ で
    $$ f(y)\ge f(x)+\nabla f(x)\cdot(y-x)+\frac m2\lvert y-x\rvert^2 $$
    のとき、$f$ は $m$ 強凸 であるという。
    $f$ が $L$ 平滑かつ $m$ 強凸のとき、$\kappa:=L/m$ を $f$ の 条件数 という。

$m$ 強凸な関数は凸である。$f$ が $C^2$ 級で、Hesse行列 の固有値がすべての点で $[m,L]$ に入るなら($m>0$)、$f$ は $L$ 平滑かつ $m$ 強凸である。実際、$\nabla f(y)-\nabla f(x)=\int_0^1\nabla^2f(x+t(y-x))(y-x)\,dt$ から前者が、Taylorの定理 から後者が従う。
2 次関数:$A$ を $n$ 次の実対称な 正定値行列、最小の固有値を $m$、最大の固有値を $L$ とする。$f(x)=\frac12x\cdot Ax-b\cdot x$ は $\nabla f(x)=Ax-b$、$\nabla^2f=A$ なので、$L$ 平滑かつ $m$ 強凸である。$\kappa$ は Euclid ノルムでの $A$ の 条件数 に等しい。最小点は $Ax^*=b$ の解である。
この記事の評価を使う条件をまとめる。

  • (i) $f$ は $\mathbb{R}^n$ 全体で微分可能で、勾配が計算できる。
  • (ii) $f$ は $L$ 平滑である。定数 $L$ を知らないときはバックトラック(prop-gd-backtracking)を使う。
  • (iii) 凸でなければ、言えるのは(下に有界のとき)勾配が $0$ に近づくことまでで、極限が最小点とは限らない。
  • (iv) 等比数列の速さの評価(thm-gd-strong)では $m$ 強凸性を使う。$m$ 強凸でないと遅くなることがある(反例の表の 6 行目)。

公式の表

$f^*:=\min f$ とし、$x^*$ は最小点とする。$f_{\inf}:=\inf f$ である。$\kappa=L/m$ とする。

関数の仮定刻み幅保証根拠
$L$ 平滑、下に有界固定 $0< s\le1/L$$\min_{j< k}\lvert\nabla f(x_j)\rvert^2\le\dfrac{2(f(x_0)-f_{\inf})}{sk}$thm-gd-stationary
$L$ 平滑、下に有界バックトラック同じ形($s$ を下限の刻み幅に、$2$ を $1/c$ に)prop-gd-backtracking
$L$ 平滑、凸、最小点あり固定 $0< s\le1/L$$f(x_k)-f^*\le\dfrac{\lvert x_0-x^*\rvert^2}{2sk}$thm-gd-convex
$L$ 平滑、$m$ 強凸固定 $0< s\le1/L$$\lvert x_k-x^*\rvert^2\le(1-ms)^k\lvert x_0-x^*\rvert^2$thm-gd-strong
2 次関数固定 $0< s< 2/L$$\lvert x_k-x^*\rvert\le\rho(s)^k\lvert x_0-x^*\rvert$prop-gd-quadratic
2 次関数固定 $s=\dfrac2{m+L}$上の式で $\rho=\dfrac{\kappa-1}{\kappa+1}$(これが最小)prop-gd-quadratic
2 次関数完全直線探索$f(x_{k+1})-f^*\le\Bigl(\dfrac{\kappa-1}{\kappa+1}\Bigr)^2(f(x_k)-f^*)$thm-gd-exact

ここで $\rho(s):=\max\{\lvert1-sm\rvert,\lvert1-sL\rvert\}$ である。

主定理と証明

1 回の更新でどれだけ下がるか

降下補題

$f$ が $L$ 平滑なら、すべての $x,y$ で
$$ f(y)\le f(x)+\nabla f(x)\cdot(y-x)+\frac L2\lvert y-x\rvert^2 $$
である。とくに $y=x-s\nabla f(x)$ とすると
$$ f(x-s\nabla f(x))\le f(x)-s\Bigl(1-\frac{Ls}2\Bigr)\lvert\nabla f(x)\rvert^2 $$
であり、$0< s\le1/L$ なら右辺は $f(x)-\frac s2\lvert\nabla f(x)\rvert^2$ 以下である。

$\varphi(t):=f(x+t(y-x))$ は $C^1$ 級で($\nabla f$ は連続である)、$\varphi'(t)=\nabla f(x+t(y-x))\cdot(y-x)$ である。よって
$$ f(y)-f(x)-\nabla f(x)\cdot(y-x)=\int_0^1\bigl(\nabla f(x+t(y-x))-\nabla f(x)\bigr)\cdot(y-x)\,dt $$
である。被積分関数は Cauchy–Schwarzの不等式 と $L$ 平滑性により $Lt\lvert y-x\rvert^2$ 以下なので、積分は $\frac L2\lvert y-x\rvert^2$ 以下である。後半は代入である。$0< s\le1/L$ なら $1-\frac{Ls}2\ge\frac12$ である。$\square$

$0< s< 2/L$ では $1-\frac{Ls}2$ は正なので、$\nabla f(x)\ne0$ なら値は下がる。保証される下げ幅 $s(1-\frac{Ls}2)$ が最大なのは $s=1/L$ である。

凸でない場合:勾配は 0 に近づく

勾配の減少

$f$ を $L$ 平滑で下に有界な関数とし、$0< s\le1/L$、$x_{k+1}=x_k-s\nabla f(x_k)$ とする。このとき $f(x_k)$ は単調非増加で、$k\ge1$ について
$$ \sum_{j=0}^{k-1}\lvert\nabla f(x_j)\rvert^2\le\frac{2(f(x_0)-f_{\inf})}s $$
である。とくに $\min_{j< k}\lvert\nabla f(x_j)\rvert^2\le\dfrac{2(f(x_0)-f_{\inf})}{sk}$ で、$\nabla f(x_k)\to0$ である。$(x_k)$ の集積点では勾配が $0$ である。

lem-gd-descent より $\frac s2\lvert\nabla f(x_j)\rvert^2\le f(x_j)-f(x_{j+1})$ である。右辺は $0$ 以上なので $f(x_k)$ は単調非増加である。$j=0,\dots,k-1$ で足すと、右辺の和は $f(x_0)-f(x_k)\le f(x_0)-f_{\inf}$ になる。和の最小の項は平均以下である。級数が収束するので一般項は $0$ に近づく。$\nabla f$ は連続なので、集積点でも勾配は $0$ である。$\square$

勾配が $0$ の点は最小点とは限らない(反例の表)。

凸な場合:誤差は $1/k$ で減る

凸の場合の評価

$f$ を $L$ 平滑な凸関数で、最小点 $x^*$ をもつものとする。$0< s\le1/L$、$x_{k+1}=x_k-s\nabla f(x_k)$ とすると、$k\ge1$ で
$$ f(x_k)-f(x^*)\le\frac{\lvert x_0-x^*\rvert^2}{2sk} $$
である。

$g_j:=\nabla f(x_j)$ とおく。lem-gd-descent より $f(x_{j+1})\le f(x_j)-\frac s2\lvert g_j\rvert^2$ である。凸性から、$f$ は接平面より上にあるので(凸最適化 の補題「凸関数は接平面より上にある」)、$f(x^*)\ge f(x_j)+g_j\cdot(x^*-x_j)$ である。この 2 つから
$$ f(x_{j+1})-f(x^*)\le g_j\cdot(x_j-x^*)-\frac s2\lvert g_j\rvert^2=\frac1{2s}\Bigl(\lvert x_j-x^*\rvert^2-\lvert x_j-x^*-sg_j\rvert^2\Bigr) $$
である。最後の式の 2 項目の中身は $x_{j+1}-x^*$ である。$j=0,\dots,k-1$ で足すと右辺は打ち消し合い、
$$ \sum_{j=1}^k\bigl(f(x_j)-f(x^*)\bigr)\le\frac1{2s}\bigl(\lvert x_0-x^*\rvert^2-\lvert x_k-x^*\rvert^2\bigr)\le\frac{\lvert x_0-x^*\rvert^2}{2s} $$
である。$f(x_j)$ は単調非増加なので(lem-gd-descent)、左辺は $k\bigl(f(x_k)-f(x^*)\bigr)$ 以上である。$\square$

強凸な場合:誤差は等比数列で減る

強凸の場合の 1 次収束

$f$ を $L$ 平滑かつ $m$ 強凸とする。このとき $m\le L$ で、$f$ の最小点 $x^*$ がただ 1 つ存在する。$0< s\le1/L$、$x_{k+1}=x_k-s\nabla f(x_k)$ とすると、すべての $k$ で次が成り立つ。

  1. $\lvert x_{k+1}-x^*\rvert^2\le(1-ms)\lvert x_k-x^*\rvert^2$。
  2. $f(x_{k+1})-f(x^*)\le(1-ms)\bigl(f(x_k)-f(x^*)\bigr)$。
    とくに $s=1/L$ なら、どちらも係数は $1-1/\kappa$ である。

$x\ne y$ について lem-gd-descent と強凸性の不等式を比べると $m\le L$ である。
最小点。 強凸性で $x=0$ とすると $f(y)\ge f(0)+\nabla f(0)\cdot y+\frac m2\lvert y\rvert^2\to\infty$($\lvert y\rvert\to\infty$)なので、最適化 の系「遠くで大きくなる関数」により最小点がある。最小点 $x^*$ では $\nabla f(x^*)=0$ なので、強凸性から $y\ne x^*$ で $f(y)>f(x^*)$ である。よって最小点は 1 つである。
1。 $e:=x_k-x^*$、$g:=\nabla f(x_k)$、$\delta:=f(x_k)-f(x^*)$ とおく。強凸性で $x=x_k$、$y=x^*$ とすると
$$ g\cdot e\ge\delta+\frac m2\lvert e\rvert^2 $$
である。lem-gd-descent と $f(x_{k+1})\ge f(x^*)$ から $\frac s2\lvert g\rvert^2\le f(x_k)-f(x_{k+1})\le\delta$ である。よって
$$ \lvert x_{k+1}-x^*\rvert^2=\lvert e\rvert^2-2sg\cdot e+s^2\lvert g\rvert^2\le\lvert e\rvert^2-2s\delta-ms\lvert e\rvert^2+2s\delta=(1-ms)\lvert e\rvert^2 $$
である。
2。 次の命題の不等式 $\lvert g\rvert^2\ge2m\delta$ を lem-gd-descent に入れると、$f(x_{k+1})-f(x^*)\le\delta-\frac s2\lvert g\rvert^2\le(1-ms)\delta$ である。$\square$

勾配の小ささから誤差が分かる

$f$ が $m$ 強凸で $x^*$ が最小点なら、すべての $x$ で
$$ f(x)-f(x^*)\le\frac{\lvert\nabla f(x)\rvert^2}{2m},\qquad\lvert x-x^*\rvert\le\frac{\lvert\nabla f(x)\rvert}m $$
である。

証明を開く

強凸性の不等式の右辺を $y$ について最小にする($y=x-\nabla f(x)/m$)と、すべての $y$ で $f(y)\ge f(x)-\lvert\nabla f(x)\rvert^2/(2m)$ である。$y=x^*$ とすると 1 つ目が出る。強凸性の不等式を $(x,x^*)$ と $(x^*,x)$ に使って足すと $\nabla f(x)\cdot(x-x^*)\ge m\lvert x-x^*\rvert^2$ である($\nabla f(x^*)=0$ を使う)。Cauchy–Schwarzの不等式 から 2 つ目が出る。$\square$

2 次関数:条件数がすべてを決める

2 次関数の固定刻み

$f(x)=\frac12x\cdot Ax-b\cdot x$($A$ は実対称な正定値行列)、最小の固有値を $m$、最大の固有値を $L$、$\rho(s)=\max\{\lvert1-sm\rvert,\lvert1-sL\rvert\}$ とする。$x_{k+1}=x_k-s\nabla f(x_k)$($s>0$)について、次が成り立つ。

  1. $\lvert x_k-x^*\rvert\le\rho(s)^k\lvert x_0-x^*\rvert$ である。
  2. $\rho(s)< 1$ となるのは $0< s< 2/L$ のときに限る。$s\ge2/L$ なら、$x_0-x^*$ が固有値 $L$ の固有ベクトルの成分をもつとき、$x_k$ は $x^*$ に収束しない。
  3. $\rho(s)$ を最小にする $s$ は $2/(m+L)$ で、そのとき $\rho=\dfrac{L-m}{L+m}=\dfrac{\kappa-1}{\kappa+1}$ である。

$\nabla f(x_k)=A(x_k-x^*)$ なので $x_{k+1}-x^*=(I-sA)(x_k-x^*)$ である。$A$ の固有値 $\lambda_i$ の正規直交な固有ベクトル $e_i$ で $x_0-x^*=\sum_ic_ie_i$ と書くと
$$ x_k-x^*=\sum_i(1-s\lambda_i)^kc_ie_i $$
である。$t\mapsto\lvert1-st\rvert$ は凸なので $[m,L]$ での最大値は端でとり、$\lvert1-s\lambda_i\rvert\le\rho(s)$ である。これで 1 が出る。
$\lvert1-sm\rvert< 1$ は $0< s< 2/m$、$\lvert1-sL\rvert< 1$ は $0< s< 2/L$ と同値で、$m\le L$ なので後者のほうが強い。$s\ge2/L$ なら固有値 $L$ の成分は $\lvert1-sL\rvert^k\ge1$ 倍のままで減らない。これが 2 である。
$s\le2/(m+L)$ では $\rho(s)=1-sm$ で減少し、$s\ge2/(m+L)$ では $\rho(s)=sL-1$ で増加する。これが 3 である。$\square$

$s=1/L$ の係数 $1-1/\kappa$ と最適な係数 $\frac{\kappa-1}{\kappa+1}\approx1-\frac2\kappa$ は同じ程度で、どちらも誤差を一定の割合で減らす回数が $\kappa$ に比例する。下の表は、$f(x_k)-f^*$ を $10^{-6}$ 倍にするのに $\bigl(\frac{\kappa-1}{\kappa+1}\bigr)^{2k}\le10^{-6}$ から必要な $k$ である。

$\kappa$$10$$100$$1000$
必要な回数$35$$346$$3454$

完全直線探索

各段で $s\mapsto f(x_k-s\nabla f(x_k))$($s\ge0$)を最小にする $s$ をとる方法を 完全直線探索 という。2 次関数なら、$r_k:=\nabla f(x_k)\ne0$ として
$$ s_k=\frac{r_k\cdot r_k}{r_k\cdot Ar_k} $$
である。$\frac d{ds}f(x_k-sr_k)=-r_k\cdot(r_k-sAr_k)$ が $0$ になる $s$ を解けばよい。さらに $r_{k+1}=r_k-s_kAr_k$ なので、この式は $r_{k+1}\cdot r_k=0$ を意味する。続く 2 回の進む向きは直交する。

Kantorovich の不等式

$A$ を $n$ 次の実対称な正定値行列、最小の固有値を $m$、最大の固有値を $L$ とする。すべての $v\ne0$ で
$$ \frac{(v\cdot Av)(v\cdot A^{-1}v)}{\lvert v\rvert^4}\le\frac{(m+L)^2}{4mL} $$
である。

固有値ごとの不等式を足す
証明を開く

$\lvert v\rvert=1$ としてよい。$t\in[m,L]$ なら $(t-m)(L-t)\ge0$ で、これを $t$ で割ると $t+\frac{mL}t\le m+L$ である。$A$ の固有値 $\lambda_i$ の正規直交な固有ベクトルで $v=\sum_ic_ie_i$ と書き、$t=\lambda_i$ の不等式に $c_i^2$ を掛けて足すと、$\sum_ic_i^2=1$ より $v\cdot Av+mL\,v\cdot A^{-1}v\le m+L$ である。相加平均と相乗平均の関係から $2\sqrt{mL(v\cdot Av)(v\cdot A^{-1}v)}\le m+L$ で、2 乗して整理すると結論である。$\square$

完全直線探索の収束

$f(x)=\frac12x\cdot Ax-b\cdot x$($A$ は実対称な正定値行列)を完全直線探索の勾配降下法で最小化すると、
$$ f(x_{k+1})-f(x^*)\le\Bigl(\frac{\kappa-1}{\kappa+1}\Bigr)^2\bigl(f(x_k)-f(x^*)\bigr) $$
である($r_k\ne0$ の段について。$r_k=0$ なら $x_k=x^*$ である)。

$r:=r_k$、$E(x):=f(x)-f(x^*)$ とおく。$r=A(x_k-x^*)$ なので $E(x_k)=\frac12(x_k-x^*)\cdot A(x_k-x^*)=\frac12r\cdot A^{-1}r$ である。また
$$ f(x_k-sr)=f(x_k)-s\,r\cdot r+\frac{s^2}2r\cdot Ar $$
に $s=s_k$ を入れると $E(x_{k+1})=E(x_k)-\dfrac{(r\cdot r)^2}{2r\cdot Ar}$ である。よって
$$ \frac{E(x_{k+1})}{E(x_k)}=1-\frac{(r\cdot r)^2}{(r\cdot Ar)(r\cdot A^{-1}r)}\le1-\frac{4mL}{(m+L)^2}=\Bigl(\frac{L-m}{L+m}\Bigr)^2 $$
である。不等号は lem-gd-kantorovich による。$\square$

一般の関数でも、$L$ 平滑かつ $m$ 強凸なら、完全直線探索の値の減りは 1 回の固定刻み $1/L$ の減り以上なので、thm-gd-strong の 2 と同じ係数 $1-1/\kappa$ の評価が成り立つ(BV04 §9.3.1、pp. 466–467 は Hesse 行列を仮定して同じ評価を述べる)。

計算の手順

  1. 関数と勾配を用意する:勾配の第 $i$ 成分の式を、差分 $(f(x+hu_i)-f(x-hu_i))/(2h)$($u_i$ は第 $i$ 座標の単位ベクトル)と数点で比べ、式の誤りを除く。
  2. 変数の尺度をそろえる:平均を引き、大きさをそろえる。$\kappa$ が小さくなることが多い(ex-gd-least-squares)。
  3. 刻み幅の決め方を選ぶ:下の表から選ぶ。
  4. 反復する:$x_{k+1}=x_k-s_k\nabla f(x_k)$ とする。
  5. 止める判定:許容誤差 $\varepsilon$ を決め、$\lvert\nabla f(x_k)\rvert\le\varepsilon$ で止める(prop-gd-stopping)。反復の上限 $k_{\max}$ も決めておく。
  6. 失敗を検出する:値が増えるなら $s$ が大きすぎる。上限に達したなら $\kappa$ が大きい疑いがある。準Newton法 などの別の方法を考える。凸でない問題では、結果は勾配が小さい点にすぎないので、初期点を替えて比べる。
    決め方やること要る情報向く場面
    固定 $s=1/L$そのまま反復する$L$$L$ が見積もれるとき
    固定 $s=2/(m+L)$そのまま反復する$m,L$固有値が分かる 2 次関数
    完全直線探索各段で 1 変数の最小化を解く2 次関数なら上の式1 変数の最小化が安いとき
    バックトラック下の手順関数の値$L$ が分からないとき

バックトラック(BV04 §9.2、pp. 464–466)。定数 $0< c< 1$、$0< \beta< 1$、$\bar s>0$ を決める($c=10^{-4}$、$\beta=\frac12$、$\bar s=1$ など)。各段で次を行う。

  1. $s\leftarrow\bar s$ とする。
  2. $f(x_k-s\nabla f(x_k))\le f(x_k)-cs\lvert\nabla f(x_k)\rvert^2$ なら、この $s$ を $s_k$ とする。
  3. そうでなければ $s\leftarrow\beta s$ として段 2 へ戻る。
バックトラックの正しさ

$f$ を $L$ 平滑とする。各段の手順は有限回で終わり、$s_k\ge s_{\min}:=\min\{\bar s,\ 2\beta(1-c)/L\}$ である。さらに $f$ が下に有界なら、すべての $k\ge1$ で
$$ \sum_{j=0}^{k-1}\lvert\nabla f(x_j)\rvert^2\le\frac{f(x_0)-f_{\inf}}{c\,s_{\min}} $$
である。

証明を開く

lem-gd-descent より、$s\le2(1-c)/L$ なら $1-\frac{Ls}2\ge c$ なので、段 2 の条件が成り立つ。$s$ は等比数列で小さくなるので手順は有限回で終わる。終わるときの $s_k$ は、$\bar s$ のままか、1 つ前の値 $s_k/\beta$ で条件が成り立たなかったかのどちらかである。後者なら $s_k/\beta>2(1-c)/L$ である。よって $s_k\ge s_{\min}$ である。段 2 の条件から $c\,s_{\min}\lvert\nabla f(x_j)\rvert^2\le f(x_j)-f(x_{j+1})$ で、足し合わせると結論である。$\square$

例題

固定刻みの比較

問い:$f(x,y)=\frac12(x^2+10y^2)$ を $(x_0,y_0)=(10,1)$ から、固定刻み $s=\frac1{10}$、$\frac2{11}$、$0.21$ で解く。
使う公式:prop-gd-quadratic。ここで $m=1$、$L=10$、$\kappa=10$、$f^*=0$ である。
答え:$s=\frac1{10}$ は $L$ の向きの成分を 1 回で消し、$\rho=0.9$。$s=\frac2{11}$ は $\rho=\frac9{11}\approx0.8182$ で最適。$s=0.21>2/L$ は $y$ が発散する。下の表は $f(x_k,y_k)\le10^{-6}$ となる最初の $k$ を含む。

途中の計算を開く

更新は $x_{k+1}=(1-s)x_k$、$y_{k+1}=(1-10s)y_k$ である。$s=\frac1{10}$ なら $y_1=0$、$x_k=10\cdot0.9^k$ で、$f(x_k,0)=50\cdot0.81^k$ である。$50\cdot0.81^k\le10^{-6}$ は $k\ge84.13$ と同値である。$s=\frac2{11}$ なら $x_k=10(\frac9{11})^k$、$y_k=(-\frac9{11})^k$ で、$f=55(\frac{81}{121})^k$ である。$55(\frac{81}{121})^k\le10^{-6}$ は $k\ge44.41$ と同値である。$s=0.21$ なら $y_{k+1}=-1.1y_k$ である。

$s$$(x_1,y_1)$$(x_2,y_2)$$f(x_{10},y_{10})$$f\le10^{-6}$ の最初の $k$
$0.1$$(9,\ 0)$$(8.1,\ 0)$$6.0788$$85$
$2/11$$(8.18182,\ -0.81818)$$(6.69421,\ 0.66942)$$0.99394$$45$
$0.21$$(7.9,\ -1.1)$$(6.241,\ 1.21)$$34.086$達しない($f$ は発散)
完全直線探索のジグザグ

問い:ex-gd-fixed の $f$ を同じ初期点から完全直線探索で解く。
使う公式:$s_k$ の式、thm-gd-exact。
答え:すべての $k$ で $s_k=\frac2{11}$ となり、$x_k=10(\frac9{11})^k$、$y_k=(-\frac9{11})^k$ である。$f$ は毎回ちょうど $(\frac9{11})^2\approx0.66942$ 倍になり、thm-gd-exact の評価は等号で成り立つ。$f\le10^{-6}$ となるのは $k=45$ である。

途中の計算を開く

一般に $f=\frac12(x^2+\kappa y^2)$ と $(x_0,y_0)=(\kappa,1)$ について、勾配は $r_0=(\kappa,\kappa)$ で、$s_0=\frac{2\kappa^2}{\kappa^2+\kappa^3}=\frac2{1+\kappa}$ である。すると $x_1=\kappa\frac{\kappa-1}{\kappa+1}$、$y_1=-\frac{\kappa-1}{\kappa+1}$ である。これは $(x_0,y_0)$ を $x$ 軸について折り返して $\frac{\kappa-1}{\kappa+1}$ 倍した点で、$y$ の符号を替えても $f$ は同じなので、同じ計算が繰り返される。$\kappa=10$ が問いの場合である。

この初期点は最悪の場合である。各段で最良の刻みを選んでも、$\kappa$ からくる遅さは消えない。図の左は ex-gd-fixed の 3 つの刻み幅の点の動きで、$s=\frac2{11}$ は完全直線探索と同じ点列である。
図: 左は等高線の上の点の動き。s=1/10 は 1 回で谷に降りてまっすぐ進み、s=2/11 はジグザグに進み、s=0.21 は谷を渡るたびに離れていく。右は値の減り方を片対数で示す 図: 左は等高線の上の点の動き。s=1/10 は 1 回で谷に降りてまっすぐ進み、s=2/11 はジグザグに進み、s=0.21 は谷を渡るたびに離れていく。右は値の減り方を片対数で示す

最小二乗の直線と変数の中心化

問い:点 $(t,b)=(0,1),(1,2),(2,2),(3,4)$ に当てはめる直線 $b\approx x_1+x_2t$ を、$f(x)=\frac12\lvert Ax-b\rvert^2$ の最小化で求める。$\lvert\nabla f\rvert\le10^{-6}$ まで、$x_0=0$、$s=2/(m+L)$ で解く。次に $t$ を $t-\frac32$ に替えて同じことをする。
使う公式:$\nabla f(x)=A^{\mathsf T}(Ax-b)$(最小二乗法)、prop-gd-quadratic。
答え:直線は $b=0.9+0.9t$、最小値は $0.35$ である。そのままでは $\kappa\approx14.13$ で $119$ 回かかる。中心化すると $A^{\mathsf T}A=\mathrm{diag}(4,5)$、$\kappa=1.25$ で $8$ 回で止まる。

途中の計算を開く

そのままでは $A^{\mathsf T}A=\begin{pmatrix}4&6\\6&14\end{pmatrix}$ で、固有値は $9\pm\sqrt{61}\approx1.18975,\ 16.81025$ である。$A^{\mathsf T}b=(9,18)$ なので、正規方程式の解は $x=(0.9,0.9)$ で、残差は $(0.1,0.2,-0.7,0.4)$ である。最小値は $\frac12\cdot0.7=0.35$ である。中心化すると $\rho=\frac{5-4}{5+4}=\frac19$ で、そのままの $\rho\approx0.8678$ より大幅に小さい。

凸でない関数とバックトラック

問い:$f(x,y)=(1-x)^2+100(y-x^2)^2$ を $(-1.2,1)$ から、$c=10^{-4}$、$\beta=\frac12$、$\bar s=1$ のバックトラックで解き、$\lvert\nabla f\rvert\le10^{-3}$ で止める。
使う公式:prop-gd-backtracking。
答え:$5231$ 回で $(0.99921,\ 0.99842)$、$f\approx6.25\times10^{-7}$ に達する(数値計算による値)。最小点は $(1,1)$ である。$k=1000$ では $(0.97278,\ 0.94602)$ で、$y=x^2$ に沿う細い谷をゆっくり進む。$c=\frac14$ に替えると $121$ 回で止まるので、回数は定数に大きく左右される。

確認を開く

$f\ge0$ で、$f=0$ は $x=1$、$y=x^2$ と同値なので、最小点は $(1,1)$ である。$(1,1)$ の Hesse 行列 $\begin{pmatrix}802&-400\\-400&200\end{pmatrix}$ の条件数は約 $2508$ である。この関数は $\mathbb{R}^2$ 全体では $L$ 平滑でないが、点列のとどまる水準集合はコンパクトで、その上では勾配が Lipschitz 連続である。同じ判定まで 準Newton法 の BFGS 法(Wolfe 条件の直線探索)では $31$ 回である。

使える条件と反例

各行は 1 つの条件だけを外している。

外す条件反例成り立たなくなること
$s< 2/L$$f(x)=x^2$($L=2$)、$s=\frac32$$x_k=(-2)^kx_0$ で発散する
$\mathbb{R}$ 全体での $L$ 平滑性$f(x)=x^4$、$s=0.1$、$x_0=3$$x_1=-7.8$、$x_2\approx182.02$ と発散する
微分可能性$f(x)=\lvert x\rvert$、$s=1$、$x_0=0.3$$0.3,-0.7,0.3,\dots$ と振動し、最小値に近づかない
凸性(thm-gd-convex)$f(x)=\cos x$、$s=1$、$x_0=0$勾配が $0$ なので動かず、最大点にとどまる
最小点の存在(thm-gd-convex)$f(x)=\log(1+e^{-x})$($L=\frac14$)、$s=4$$\nabla f(x_k)\to0$ だが $x_k\to\infty$ で、点列は収束しない
$m$ 強凸性(thm-gd-strong)下の $\tilde f$、$s=\frac1{12}$、$x_0=1$$x_{k+1}/x_k\to1$ で、等比数列の速さにならない

表の $\tilde f$ は、$\lvert x\rvert\le1$ で $\tilde f(x)=x^4$、$\lvert x\rvert>1$ で $\tilde f(x)=6x^2-8\lvert x\rvert+3$ とおいた関数である。

表の反例の確かめ
各行の確かめを開く

$x^4$:更新は $x_{k+1}=x_k(1-4sx_k^2)$ である。$x_k^2>\frac1{2s}$ なら $\lvert1-4sx_k^2\rvert>1$ なので、$\lvert x_k\rvert$ は増え続け、比も増えるので発散する。どの固定の $s>0$ についても、$x_0^2>\frac1{2s}$ の初期点は発散する。$f''$ が有界でないので $L$ 平滑でない。

$\lvert x\rvert$:$x\ne0$ で勾配は $\pm1$ なので、$x_{k+1}=x_k\mp1$ である。問いの初期点では $0$ に当たらず、$0.3$ と $-0.7$ を往復する。

$\log(1+e^{-x})$:$f'(x)=-\frac1{1+e^x}< 0$、$f''(x)=\frac{e^x}{(1+e^x)^2}\in(0,\frac14]$ なので、凸で $\frac14$ 平滑である。$f>0=\inf f$ で最小点はない。$x_k$ は増加し、有界なら極限で $f'=0$ となって矛盾するので、$x_k\to\infty$ である。

$\tilde f$:$x=\pm1$ で値と 2 階までの導関数がつながるので $C^2$ 級で、$0\le\tilde f''\le12$ である。よって $12$ 平滑で凸だが、$\tilde f''(0)=0$ なので強凸でない。$s=\frac1{12}$、$x_0=1$ の更新は $x_{k+1}=x_k-\frac13x_k^3$ で、$x_k$ は正のまま減少して $0$ に収束し、$x_{k+1}/x_k=1-\frac13x_k^2\to1$ である。$x_{k+1}^{-2}-x_k^{-2}\to\frac23$ なので $x_k^2k\to\frac32$、$\tilde f(x_k)k^2\to\frac94$ である。$k=100$ で $\tilde f(x_{100})\approx2.04\times10^{-4}$ で、thm-gd-convex の上界 $0.06$ の中にある。

よくある誤り

誤り正しくはなぜ
刻み幅は大きいほど速い$2/L$ 以上では 2 次関数でも収束しないprop-gd-quadratic
勾配の逆向きは最小点を指す等高線に垂直なだけで、一般には最小点を指さないex-gd-zigzag
勾配が $0$ になったので最小点である凸でなければ極大点や鞍点のこともある反例の表の 4 行目
完全直線探索ならジグザグしない続く 2 回の向きは必ず直交するex-gd-zigzag
勾配が小さいので解に近い誤差の上界は $\lvert\nabla f\rvert/m$ で、$m$ が小さいと遠いこともあるprop-gd-stopping
変数の尺度はそのままでよい尺度で $\kappa$ が変わるex-gd-least-squares

演習

最適な刻み幅

$A=\begin{pmatrix}2&1\\1&2\end{pmatrix}$、$b=(3,3)$、$f(x)=\frac12x\cdot Ax-b\cdot x$ とする。最適な固定刻み $s$ と $\rho$ を求め、$x_0=0$ から $x_1,x_2$ を計算せよ。

解答を開く

固有値は $1,3$ なので $s=\frac12$、$\rho=\frac12$ である。$x^*=(1,1)$ で、$x_1=(\frac32,\frac32)$、$x_2=(\frac34,\frac34)$ である。$x_0-x^*=(-1,-1)$ は固有値 $3$ の固有ベクトルなので、誤差は毎回 $1-3s=-\frac12$ 倍になる。$\square$

解までの距離の単調性

thm-gd-convex の仮定のもとで、$\lvert x_k-x^*\rvert$ が単調非増加であることを示せ。

解答を開く

thm-gd-convex の証明の不等式は $0\le f(x_{j+1})-f(x^*)\le\frac1{2s}(\lvert x_j-x^*\rvert^2-\lvert x_{j+1}-x^*\rvert^2)$ を与える。$\square$

補足

  • 連続時間の見方:$s\to0$ の極限は 常微分方程式 $x'(t)=-\nabla f(x(t))$(勾配流)で、勾配降下法はこれを刻み $s$ の陽的な差分で近似したものである。
  • 長さの測り方:「最も急な向き」は長さの測り方で変わる。Euclid の長さ以外での最急降下の向きは BV04 §9.4(pp. 475–476)にある。
  • 微分できない関数と標本の和:微分できない凸関数には勾配の代わりに 劣微分 の元を使う(劣勾配法)。目的関数が多数の標本の和のときは、1 回ごとに標本の一部の勾配だけを使う確率的な方法(確率的勾配降下法)がある(SSBD14 §14.2–14.3)。ニューラルネットワーク の学習では、その勾配を 誤差逆伝播法 で計算する。近接写像の反復は、Moreau包絡 に勾配降下法を当てたものと同じである。滑らかな項と微分できない凸の項の和には、勾配の段と近接写像の段を交互に行う 近接勾配法 を使う。
  • 連立 1 次方程式:2 次関数の最小化は $Ax=b$ を解くことと同じである。Saa03 §5.3.1 は同じ方法を最急降下法として扱う。この問題には $\sqrt\kappa$ で決まる速さの Krylov部分空間法 がある(定理「条件数による収束の上界」)。
  • Newton 系の方法:Newton法 は Hesse 行列で尺度を自動で直す方法と見なせる。2 階導関数が使えないときは 準Newton法 を使う。

関連項目

参考文献

[1]
Stephen Boyd, Lieven Vandenberghe, Convex Optimization, 1st ed., Cambridge University Press, 2004, §9.1.2(強凸性と (9.9)・(9.11)、pp. 459–460)、§9.2(完全直線探索とバックトラック、pp. 463–466)、§9.3(勾配降下法、p. 466)、§9.3.1(収束の解析、pp. 466–468)、§9.3.2(2 次関数の例、p. 469)、§9.4(最急降下法、pp. 475–476)
[2]
Yousef Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, 2003, §5.3.1 Steepest Descent(pp. 142–145、Lemma 5.8・Theorem 5.9)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する