Nesterovの加速法(Nesterov's accelerated gradient method)とは、勾配が Lipschitz 連続な凸関数を最小化するため、勾配降下法の 1 歩に前回の動きの向きへの外挿を加えた反復法である。1 回に計算する勾配は 1 個のままで、$k$ 回目の誤差は初期点と最小点の距離の 2 乗に比例し $(k+1)^2$ に反比例する量以下になり、勾配降下法の $1/k$ から $1/k^2$ に改善する。強凸な関数では、誤差を一定の割合で減らす回数が条件数の平方根に比例する。勾配の張る空間に沿って点を動かす方法には、次元が十分大きいと $1/k^2$ より速くは誤差を減らせない関数があり、加速法は定数倍を除いて最適である。
Nesterovの加速法(Nesterov's accelerated gradient method)は、勾配が Lipschitz 連続な凸関数を最小化する反復法で、勾配降下法 の 1 歩に「前回からの動きの向きへの外挿」を加えたものである。1 回の反復で計算する勾配は 1 個のままで、誤差の上界は勾配降下法の $O(1/k)$ から $O(1/k^2)$ に改善する。Nesterov が 1983 年に導入した Nes83。
改善の程度には限りがある。勾配の 1 次結合で点を動かす方法は、どれも $1/k^2$ より速くは誤差を減らせない関数がある(thm-nag-lower)。加速法はこの下界と定数倍の違いで一致し、この意味で最適な 1 次の方法である。
この記事では、方法を 3 つの点列で書き(def-nag-method)、運動量の形に書き直す(prop-nag-momentum)。1 段の不等式(lem-nag-step)から主定理 $f(x_k)-f^*\le\frac{2L\lvert x_0-x^*\rvert^2}{(k+1)^2}$(thm-nag-convex)を証明し、強凸の場合の等比数列の評価(thm-nag-strong)と下界(thm-nag-lower)を証明する。
$\mathbb R^n$ の内積を $a\cdot b$、長さを $\lvert x\rvert$ と書く。$L$ 平滑性、$m$ 強凸性、条件数 $\kappa=L/m$ は 勾配降下法 の定義「L 平滑と m 強凸」のとおりとする。$f$ が最小点をもつとき $f^*:=\min f$、最小点の 1 つを $x^*$ とする。
$f\colon\mathbb R^n\to\mathbb R$ を $L$ 平滑な関数、$x_0\in\mathbb R^n$ とし、$z_0:=x_0$ とおく。
どちらも 1 回の反復で勾配を $y_k$ で 1 回だけ計算する。$x_{k+1}$ は $y_k$ から刻み幅 $1/L$ の勾配降下法の 1 歩で、$z_k$ はそれより大きな刻み幅 $\frac1{\theta_kL}$ で勾配を積み上げる点列、$y_k$ は 2 つを内分した点である。凸の場合は $\theta_0=1$ なので $y_0=x_0$ で、$x_1$ は勾配降下法の 1 歩と同じ点である。
1:$g:=\nabla f(y_k)$ とおく。$x_{k+1}-(1-\theta_k)x_k=y_k-(1-\theta_k)x_k-\frac gL=\theta_kz_k-\frac gL=\theta_kz_{k+1}$ なので、後半が成り立ち、$z_{k+1}=x_k+\frac1{\theta_k}(x_{k+1}-x_k)$ である。これを $y_{k+1}$ の定義に入れると
$$
y_{k+1}=(1-\theta_{k+1})x_{k+1}+\theta_{k+1}x_k+\frac{\theta_{k+1}}{\theta_k}(x_{k+1}-x_k)=x_{k+1}+\theta_{k+1}\Bigl(\frac1{\theta_k}-1\Bigr)(x_{k+1}-x_k)
$$
で、$\theta_{k+1}\bigl(\frac1{\theta_k}-1\bigr)=\frac2{k+3}\cdot\frac k2=\frac k{k+3}$ である。
2:$\theta^2=m/L$ に注意する。$y_k$ の定義から $\theta z_k=(1+\theta)y_k-x_k$ なので
$$
\theta z_{k+1}=(1-\theta)\bigl((1+\theta)y_k-x_k\bigr)+\theta^2y_k-\frac{\theta^2}m g=y_k-\frac gL-(1-\theta)x_k=x_{k+1}-(1-\theta)x_k
$$
である。よって $y_{k+1}=\frac{x_{k+1}+\theta z_{k+1}}{1+\theta}=\frac{2x_{k+1}-(1-\theta)x_k}{1+\theta}=x_{k+1}+\frac{1-\theta}{1+\theta}(x_{k+1}-x_k)$ で、$\frac{1-\theta}{1+\theta}=\frac{\sqrt\kappa-1}{\sqrt\kappa+1}$ である。$\square$
運動量の形では、加速法は「前回の動き $x_{k+1}-x_k$ の向きに少し先まで進んだ点 $y_{k+1}$ で勾配を計算し、そこから勾配降下法の 1 歩を踏む」方法である。外挿の係数は凸の場合は $1$ に近づき、強凸の場合は一定である。凸の場合の外挿の係数を、列 $t_{k+1}=\frac{1+\sqrt{1+4t_k^2}}2$ から $\frac{t_k-1}{t_{k+1}}$ と定める版もよく使われ、同じ形の評価が成り立つ(Bub15 §3.7.2、pp. 293–294)。微分できない凸関数の項を足した問題への拡張は 近接勾配法 の加速版(FISTA、BT09)である。
$f$ を $L$ 平滑な凸関数、$x^*$ を最小点、$\theta\in(0,1]$ とする。$x,z\in\mathbb R^n$ について $y:=(1-\theta)x+\theta z$、$g:=\nabla f(y)$、$x^+:=y-\frac gL$、$z^+:=z-\frac g{\theta L}$ とおくと
$$
f(x^+)-f^*\le(1-\theta)\bigl(f(x)-f^*\bigr)+\frac{\theta^2L}2\bigl(\lvert z-x^*\rvert^2-\lvert z^+-x^*\rvert^2\bigr)
$$
である。
凸最適化 の補題「凸関数は接平面より上にある」を点 $y$ で $u=x$ と $u=x^*$ に使うと $f(y)\le f(u)+g\cdot(y-u)$ である。これに $1-\theta$ と $\theta$ を掛けて足すと、$y-(1-\theta)x=\theta z$ なので
$$
f(y)\le(1-\theta)f(x)+\theta f^*+\theta\,g\cdot(z-x^*)
$$
である。勾配降下法 の補題「降下補題」により $f(x^+)\le f(y)-\frac1{2L}\lvert g\rvert^2$ である。一方、$z^+-x^*=z-x^*-\frac g{\theta L}$ を展開すると
$$
\frac{\theta^2L}2\bigl(\lvert z-x^*\rvert^2-\lvert z^+-x^*\rvert^2\bigr)=\theta\,g\cdot(z-x^*)-\frac1{2L}\lvert g\rvert^2
$$
である。3 つを合わせて $f^*$ を引くと結論を得る。$\square$
この不等式は、$f(x)-f^*$ を $1-\theta$ 倍に縮める代わりに、$z$ と $x^*$ の距離の 2 乗の減り方に $\frac{\theta^2L}2$ の重みを付けて払う、という形をしている。$\theta$ を小さくすると払いは安くなるが縮み方も小さくなる。次の定理は $\theta_k=\frac2{k+2}$ がこの釣り合いをとることを示す。
$f$ を $L$ 平滑な凸関数で最小点 $x^*$ をもつものとし、$(x_k)$、$(z_k)$ を凸の場合の加速法の点列とする。$k\ge1$ について
$$
f(x_k)-f^*\le\frac{2L\lvert x_0-x^*\rvert^2}{(k+1)^2}
$$
であり、$\lvert z_k-x^*\rvert\le\lvert x_0-x^*\rvert$、$\lvert x_k-x^*\rvert\le\lvert x_0-x^*\rvert$ である。
$h_k:=f(x_k)-f^*\ge0$、$d_k:=\lvert z_k-x^*\rvert^2$、$R:=\lvert x_0-x^*\rvert$ とおく。lem-nag-step を $x=x_k$、$z=z_k$、$\theta=\theta_k$ に使い(このとき $x^+=x_{k+1}$、$z^+=z_{k+1}$ である)、$\theta_k^2$ で割ると
$$
\frac{h_{k+1}}{\theta_k^2}+\frac L2d_{k+1}\le\frac{1-\theta_k}{\theta_k^2}h_k+\frac L2d_k
$$
である。$k=0$ では $\theta_0=1$ なので右辺は $\frac L2d_0=\frac L2R^2$ である。$k\ge1$ では
$$
\frac{1-\theta_k}{\theta_k^2}=\frac{k(k+2)}4\le\frac{(k+1)^2}4=\frac1{\theta_{k-1}^2}
$$
と $h_k\ge0$ から、右辺は $\frac{h_k}{\theta_{k-1}^2}+\frac L2d_k$ 以下である。よって $\Phi_k:=\frac{h_k}{\theta_{k-1}^2}+\frac L2d_k$($k\ge1$)は増えず、$\Phi_1\le\frac L2R^2$ なので、すべての $k\ge1$ で $\Phi_k\le\frac L2R^2$ である。とくに
$$
h_k\le\theta_{k-1}^2\cdot\frac L2R^2=\frac4{(k+1)^2}\cdot\frac L2R^2=\frac{2LR^2}{(k+1)^2},\qquad d_k\le R^2
$$
である。最後に、prop-nag-momentum の 1 の後半により $x_{k+1}$ は $x_k$ と $z_{k+1}$ の内分点で、$x_1=z_1$ である。$\lvert\cdot-x^*\rvert$ は凸なので、帰納法により $\lvert x_k-x^*\rvert\le\max_{1\le j\le k}\lvert z_j-x^*\rvert\le R$ である。$\square$
同じ仮定での刻み幅 $1/L$ の勾配降下法の上界は $\frac{LR^2}{2k}$ である(勾配降下法 の定理「凸の場合の評価」)。誤差を $\varepsilon$ 以下にするのに必要な反復の回数は、勾配降下法の上界からは $\frac{LR^2}{2\varepsilon}$ 回、加速法の上界からは $\sqrt{2LR^2/\varepsilon}$ 回で、$\varepsilon$ が小さいほど差が開く。同じ形の評価は Bub15 Theorem 3.19(p. 294)にもある。
加速法の $f(x_k)$ は単調に減るとは限らない(ex-nag-quadratic)。上の証明で単調に減るのは $f(x_k)$ そのものではなく、距離の項を加えた $\Phi_k$ である。
$f$ を $L$ 平滑かつ $m$ 強凸、$x^*$ をその最小点、$\kappa=L/m$ とし、$(x_k)$、$(z_k)$ を強凸の場合の加速法の点列とする。$\Psi_k:=f(x_k)-f^*+\frac m2\lvert z_k-x^*\rvert^2$ とおくと、すべての $k$ で $\Psi_{k+1}\le\bigl(1-\frac1{\sqrt\kappa}\bigr)\Psi_k$ であり、
$$
f(x_k)-f^*\le\Bigl(1-\frac1{\sqrt\kappa}\Bigr)^k\frac{L+m}2\lvert x_0-x^*\rvert^2
$$
である。
$\theta=1/\sqrt\kappa$、$y:=y_k$、$g:=\nabla f(y)$ とおく。次の 3 つを使う。
刻み幅 $1/L$ の勾配降下法の係数は $1-\frac1\kappa$ である(勾配降下法 の定理「強凸の場合の 1 次収束」)。誤差を一定の割合で減らす回数は、勾配降下法では $\kappa$ に比例し、加速法では $\sqrt\kappa$ に比例する。$\kappa=10^4$ なら約 $100$ 倍の差である。同じ方法と $\frac{L+m}2\lvert x_0-x^*\rvert^2\exp\bigl(-\frac{k}{\sqrt\kappa}\bigr)$ の形の評価は Bub15 Theorem 3.18(p. 290)にある。上の証明は強凸性と凸性の 2 つの不等式の重みを $y$ の内分の比に合わせるもので、$\Psi_k$ の形は凸の場合の $\Phi_k$ と同じ役割をもつ。
勾配の情報だけを使う方法の速さの限界を述べる。次の条件を考える。
点 $w_0:=x_0,w_1,w_2,\dots$ で勾配を計算する方法が、すべての $j\ge1$ で
$$
w_j\in x_0+\operatorname{span}\{\nabla f(w_0),\dots,\nabla f(w_{j-1})\}
$$
をみたすとき、勾配の張る空間に沿う という。$k$ 回の勾配の計算のあとに出力できる点は $x_0+\operatorname{span}\{\nabla f(w_0),\dots,\nabla f(w_{k-1})\}$ の点とする。
勾配降下法と 2 つの加速法はこの条件をみたす。加速法では $w_j=y_j$ で、prop-nag-momentum から帰納的に $x_k,y_k$ は $x_0$ に $\nabla f(y_0),\dots,\nabla f(y_{k-1})$ の 1 次結合を足した点である。
$k\ge1$、$n\ge2k+1$、$L>0$、$x_0\in\mathbb R^n$ とする。$\mathbb R^n$ 上の $L$ 平滑な凸関数 $f$ で、次をみたすものがある:$x^*$ を $x_0$ に最も近い最小点とすると、勾配の張る空間に沿うどの方法についても、$k$ 回の勾配の計算のあとに出力できるどの点 $u$ も
$$
f(u)-f^*\ge\frac{3L\lvert x_0-x^*\rvert^2}{32(k+1)^2}
$$
をみたす。
平行移動して $x_0=0$ とする。$N:=2k+1$ とし、$p\le N$ について、$n$ 次の対称行列 $A_p$ を、左上の $p\times p$ 部分が対角成分 $2$、その隣が $-1$ の 3 重対角行列で、ほかの成分が $0$ のものとする。$e_1$ を第 1 座標の単位ベクトル、$V_p:=\{x\mid x_i=0\ (i>p)\}$ とし、
$$
f_p(x):=\frac L4\Bigl(\frac12x\cdot A_px-x_1\Bigr),\qquad f:=f_N
$$
とおく。$x\cdot A_px=x_1^2+\sum_{i=1}^{p-1}(x_i-x_{i+1})^2+x_p^2$ であり、$(s-t)^2\le2s^2+2t^2$ から $0\le x\cdot A_px\le4\lvert x\rvert^2$ である。$f$ の Hesse 行列 $\frac L4A_N$ は半正定値で固有値は $L$ 以下なので、$f$ は凸で、$\nabla f(y)-\nabla f(x)=\frac L4A_N(y-x)$ から $L$ 平滑である。
最小値:$V_p$ の上で $x\cdot A_px$ は $x\ne0$ なら正なので、$f_p$ の $V_p$ 上の最小点は $A_px=e_1$ の $V_p$ の解 $\bar x^{(p)}_i:=1-\frac i{p+1}$($i\le p$)である。実際、第 $i$ 行($2\le i\le p-1$)は 1 次式の 2 階差分で $0$、第 1 行は $2(1-\frac1{p+1})-(1-\frac2{p+1})=1$、第 $p$ 行は $-\frac2{p+1}+\frac2{p+1}=0$ である。$f_p$ は $V_p$ の外の座標によらないので、$f_p^*:=\min_{\mathbb R^n}f_p=f_p(\bar x^{(p)})=\frac L4\bigl(\frac12\bar x^{(p)}_1-\bar x^{(p)}_1\bigr)=-\frac L8\cdot\frac p{p+1}$ である。$f$ の最小点全体は $\bar x^{(N)}+\operatorname{span}\{e_{N+1},\dots,e_n\}$ なので、$0$ に最も近いものは $x^*=\bar x^{(N)}$ で、
$$
\lvert x^*\rvert^2=\sum_{i=1}^N\Bigl(\frac i{N+1}\Bigr)^2=\frac{N(2N+1)}{6(N+1)}\le\frac{N+1}3=\frac{2(k+1)}3
$$
である。
張る空間:$\nabla f(x)=\frac L4(A_Nx-e_1)$ で、$x\in V_j$($j< N$)なら $A_Nx\in V_{j+1}$ である。$\nabla f(w_0)=-\frac L4e_1\in V_1$ で、$\nabla f(w_0),\dots,\nabla f(w_{j-1})\in V_j$ なら $w_j\in V_j$、$\nabla f(w_j)\in V_{j+1}$ である。よって出力できる点 $u$ は $V_k$ に入る。
評価:$u\in V_k$ では $u_{k+1}=\dots=u_N=0$ なので $u\cdot A_Nu=u\cdot A_ku$、すなわち $f(u)=f_k(u)\ge f_k^*$ である。よって
$$
f(u)-f^*\ge f_k^*-f_N^*=\frac L8\Bigl(\frac{2k+1}{2k+2}-\frac k{k+1}\Bigr)=\frac L{16(k+1)}\ge\frac L{16(k+1)}\cdot\frac{3\lvert x^*\rvert^2}{2(k+1)}
$$
で、右辺は $\frac{3L\lvert x^*\rvert^2}{32(k+1)^2}$ である。$\square$
thm-nag-convex の上界 $\frac{2L\lvert x_0-x^*\rvert^2}{(k+1)^2}$ との比は $\frac{64}3$ で、$k$ にも次元にもよらない。加速法は、次元が反復の回数の 2 倍より大きい範囲で、勾配の張る空間に沿う方法の中で定数倍を除いて最適である。同じ構成は Bub15 Theorem 3.14(p. 282)にあり、そこでは添字の付け方が 1 つずれている。次元の条件は外せない:2 次関数なら 共役勾配法 は $n$ 回の勾配の計算で厳密な最小点に達する。強凸の場合にも、係数 $\bigl(\frac{\sqrt\kappa-1}{\sqrt\kappa+1}\bigr)^2$ の等比数列より速くは減らせない関数が無限次元の数列空間の上にあることが知られており(Bub15 Theorem 3.15、p. 283)、thm-nag-strong の $\sqrt\kappa$ も定数倍を除いて改良できない。
$f(x)=\frac12(x_1^2+100x_2^2)$ を $x_0=(1,1)$ から最小化する。$m=1$、$L=100$、$\kappa=100$、$f(x_0)=50.5$、$f^*=0$ である。$f(x_k)\le10^{-6}$ となる最初の $k$ は次のとおりである(数値計算による値)。
| 方法 | 最初の $k$ | $f(x_{10})$ |
|---|---|---|
| 勾配降下法(刻み幅 $1/L$) | $653$ | $0.40895$ |
| 凸の場合の加速法 | $101$ | $0.33917$ |
| 強凸の場合の加速法 | $84$ | $0.24315$ |
勾配降下法では $x_2$ の成分が 1 回で $0$ になり、残りは $f(x_k)=\frac12\cdot0.99^{2k}$ なので、回数は $0.99^{2k}\le2\times10^{-6}$ の最小の $k$、すなわち $653$ である。凸の場合の加速法の値は単調には減らない:$f(x_{38})\approx8.77\times10^{-6}$ のあと $f(x_{39})\approx2.08\times10^{-4}$ に増える。外挿の係数が $1$ に近づくにつれて、$x_1$ の方向の動きが行き過ぎて振動するからである。
各行は 1 つの条件だけを外している。
| 外す条件 | 反例 | 成り立たなくなる結論 |
|---|---|---|
| 刻み幅の $L$ が勾配の Lipschitz 定数以上であること | $f(x)=\frac12x^2$(真の値は $1$)に $L=\frac13$ として凸の場合の加速法、$x_0=1$ | thm-nag-convex の誤差の評価($x_k=1,-2,4,-11,34,\dots$ と発散する) |
| $f$ の凸性 | $f(x)=\cos x$($L=1$)、$x_0=0$ | thm-nag-convex の誤差の評価(勾配が $0$ なので動かず $f(x_k)-f^*=2$ のまま。$x_0$ から最も近い最小点までの距離は $\pi$) |
| $m$ が強凸性の定数以下であること | $f(x)=\frac{x^2}{200}$(真の値は $m=L=0.01$)に $L=1$、$m=\frac12$ として強凸の場合の加速法、$x_0=1$ | thm-nag-strong の等比数列の評価($k=5$ から上界を超え、$x_{k+1}/x_k\to0.988$ 程度でしか減らない) |
1 行目では、$L$ を小さく見積もると $y$ からの 1 歩が降下補題の範囲を出る。3 行目では $L$ を大きく見積もっても降下補題は成り立つが、強凸性の不等式が成り立たない $m$ を使っている。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する