Nesterovの加速法

同義語:Nesterovの加速勾配法Nesterov加速勾配法Nesterov's accelerated gradient methodNesterov accelerated gradientNesterov's accelerated gradient descent

概要

Nesterovの加速法(Nesterov's accelerated gradient method)とは、勾配が Lipschitz 連続な凸関数を最小化するため、勾配降下法の 1 歩に前回の動きの向きへの外挿を加えた反復法である。1 回に計算する勾配は 1 個のままで、$k$ 回目の誤差は初期点と最小点の距離の 2 乗に比例し $(k+1)^2$ に反比例する量以下になり、勾配降下法の $1/k$ から $1/k^2$ に改善する。強凸な関数では、誤差を一定の割合で減らす回数が条件数の平方根に比例する。勾配の張る空間に沿って点を動かす方法には、次元が十分大きいと $1/k^2$ より速くは誤差を減らせない関数があり、加速法は定数倍を除いて最適である。

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

前提知識: 勾配降下法, 凸関数, 凸最適化

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. 凸の場合の加速法:$k=0,1,2,\dots$ について $\theta_k:=\dfrac2{k+2}$ とし、
    $$ y_k:=(1-\theta_k)x_k+\theta_kz_k,\qquad x_{k+1}:=y_k-\frac1L\nabla f(y_k),\qquad z_{k+1}:=z_k-\frac1{\theta_kL}\nabla f(y_k) $$
    で点列を作る。
  2. 強凸の場合の加速法:$f$ が $m$ 強凸のとき、$\theta:=1/\sqrt\kappa=\sqrt{m/L}$ とし、
    $$ y_k:=\frac{x_k+\theta z_k}{1+\theta},\qquad x_{k+1}:=y_k-\frac1L\nabla f(y_k),\qquad z_{k+1}:=(1-\theta)z_k+\theta y_k-\frac\theta m\nabla f(y_k) $$
    で点列を作る。

どちらも 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. 凸の場合の加速法の点列は、$y_0=x_0$ と、$k\ge0$ について
    $$ x_{k+1}=y_k-\frac1L\nabla f(y_k),\qquad y_{k+1}=x_{k+1}+\frac k{k+3}(x_{k+1}-x_k) $$
    をみたす。また $x_{k+1}=(1-\theta_k)x_k+\theta_kz_{k+1}$ である。
  2. 強凸の場合の加速法の点列は、$y_0=x_0$ と
    $$ x_{k+1}=y_k-\frac1L\nabla f(y_k),\qquad y_{k+1}=x_{k+1}+\frac{\sqrt\kappa-1}{\sqrt\kappa+1}(x_{k+1}-x_k) $$
    をみたす。

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)である。

凸の場合の主定理

1 段の不等式

$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) $$
である。

凸性の 2 つの不等式を内分の重みで足す

凸最適化 の補題「凸関数は接平面より上にある」を点 $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 $$
である。

3 つの不等式を足して内分の定義で打ち消す

$\theta=1/\sqrt\kappa$、$y:=y_k$、$g:=\nabla f(y)$ とおく。次の 3 つを使う。

  • 降下補題:$f(x_{k+1})\le f(y)-\frac1{2L}\lvert g\rvert^2$。
  • 強凸性(点 $y$ から $x^*$ へ):$f^*\ge f(y)+g\cdot(x^*-y)+\frac m2\lvert x^*-y\rvert^2$。
  • 凸性(点 $y$ から $x_k$ へ):$f(x_k)\ge f(y)+g\cdot(x_k-y)$。
    $a:=z_k-x^*$、$b:=y-x^*$ とおくと $z_{k+1}-x^*=(1-\theta)a+\theta b-\frac\theta mg$ である。$\lvert\cdot\rvert^2$ の凸性 $\lvert(1-\theta)a+\theta b\rvert^2\le(1-\theta)\lvert a\rvert^2+\theta\lvert b\rvert^2$ と $\frac{\theta^2}{2m}=\frac1{2L}$ から
    $$ \frac m2\lvert z_{k+1}-x^*\rvert^2\le(1-\theta)\frac m2\lvert a\rvert^2+\theta\frac m2\lvert b\rvert^2-\theta\,g\cdot\bigl((1-\theta)a+\theta b\bigr)+\frac1{2L}\lvert g\rvert^2 $$
    である。これと降下補題を足すと $\lvert g\rvert^2$ の項が消え、
    $$ \Psi_{k+1}\le f(y)-f^*+(1-\theta)\frac m2\lvert a\rvert^2+\theta\frac m2\lvert b\rvert^2-\theta\,g\cdot\bigl((1-\theta)a+\theta b\bigr) $$
    となる。強凸性の不等式に $\theta$ を、凸性の不等式に $1-\theta$ を掛けて足すと
    $$ f(y)-\theta f^*-(1-\theta)f(x_k)\le g\cdot\bigl(\theta b+(1-\theta)(y-x_k)\bigr)-\theta\frac m2\lvert b\rvert^2 $$
    である。$f(y)-f^*=\bigl(f(y)-\theta f^*-(1-\theta)f(x_k)\bigr)+(1-\theta)\bigl(f(x_k)-f^*\bigr)$ に代入すると
    $$ \Psi_{k+1}\le(1-\theta)\Psi_k+g\cdot w,\qquad w:=\theta b+(1-\theta)(y-x_k)-\theta(1-\theta)a-\theta^2b $$
    となる。$w=(1-\theta)\bigl(\theta b+y-x_k-\theta a\bigr)=(1-\theta)\bigl((1+\theta)y-x_k-\theta z_k\bigr)$ で、$y$ の定義から $w=0$ である。よって $\Psi_{k+1}\le(1-\theta)\Psi_k$ である。
    $z_0=x_0$ と、降下補題を $x=x^*$($\nabla f(x^*)=0$)で使った $f(x_0)-f^*\le\frac L2\lvert x_0-x^*\rvert^2$ から $\Psi_0\le\frac{L+m}2\lvert x_0-x^*\rvert^2$ で、$f(x_k)-f^*\le\Psi_k$ である。$\square$

刻み幅 $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} $$
をみたす。

3 重対角行列の 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$ も定数倍を除いて改良できない。

例

細長い 2 次関数

$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アソシエイト)の紹介料で運営されています。 支援について / 寄付する