近接勾配法

同義語:proximal gradient methodforward-backward splitting

概要

近接勾配法(proximal gradient method)とは、微分できる関数 $f$ と、微分できなくてもよい凸関数 $g$ の和の最小点を探すため、$f$ の勾配の逆向きに進んでから $g$ の近接写像をとる操作を繰り返す反復法である。$g$ が絶対値の和なら近接写像は軟しきい値になり、LASSO のような疎な解を求める問題に使う。$f$ が凸で勾配が定数 $L$ の Lipschitz 連続、$g$ が凸で下半連続、最小点があり刻み幅が $1/L$ 以下なら、目的関数の誤差は反復回数に反比例して減り、$f$ が強凸なら最小点までの距離が等比数列の速さで減る。慣性の項を加えた加速版では誤差が反復回数の 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}} $$

前提知識: 勾配降下法, Moreau–吉田正則化, 凸関数

最小二乗の誤差に絶対値の和の罰金を足した
$$ F(x)=\frac12\|Ax-b\|^2+\mu\sum_{j=1}^n|x_j| $$
の最小化(LASSO)では、罰金の項が原点を含む座標軸の上で微分できないので、勾配降下法 はそのままでは使えない。しかし罰金の項だけなら、「$|u|$ の値と、$u$ が点 $v$ から離れることへの罰金 $\frac1{2\lambda}(u-v)^2$ の和」の最小点は閉じた形で書ける。$v$ を $0$ の方向に $\lambda$ だけ縮め、$|v|\le\lambda$ なら $0$ にした値(軟しきい値)である。
近接勾配法 は、目的関数を「微分できる項 $f$」と「微分できないが近接写像が計算できる項 $g$」の和 $F=f+g$ に分け、$f$ については勾配の向きに進み、$g$ については近接写像をとる、という 2 段の操作を繰り返す反復法である。$g=0$ なら勾配降下法、$g$ が閉凸集合の指示関数なら、勾配の向きに進んでから集合に射影する射影勾配法になる。
この記事では、$f$ が凸で勾配が Lipschitz 連続、$g$ が凸で下半連続なとき、刻み幅 $\lambda\le1/L$ の近接勾配法の誤差が $1/k$ の速さで減ること(主定理)、$f$ が強凸なら等比数列の速さで減ること、慣性の項を加えた加速版(FISTA)では $1/k^2$ の速さになることを証明する。

定義と使える条件

$\|\cdot\|$ は $\mathbb{R}^n$ の Euclid ノルム、$a\cdot b$ は内積とする。関数 $g\colon\mathbb{R}^n\to(-\infty,+\infty]$ は $+\infty$ の値を許す。$g$ が凸で下半連続で、$+\infty$ でない値を少なくとも 1 点でとるとき、閉真凸関数 という。集合 $C$ の指示関数 $I_C$ を、$C$ 上で $0$、外で $+\infty$ と定める。

近接写像

$g$ を閉真凸関数、$\lambda>0$ とする。$v\in\mathbb{R}^n$ に対し
$$ \operatorname{prox}_{\lambda g}(v):=\operatorname*{arg\,min}_{u\in\mathbb{R}^n}\Bigl(g(u)+\frac1{2\lambda}\|u-v\|^2\Bigr) $$
を $g$ の 近接写像 という。

右辺の最小点がただ 1 つ存在することは Moreau–吉田正則化 の定義「Moreau–吉田正則化と近接写像」の後で示されている(同記事の $J_\lambda$ が $\operatorname{prox}_{\lambda g}$ である)。同記事の定理「近接写像の特徴づけ」により、$p=\operatorname{prox}_{\lambda g}(v)$ であることと
$$ g(u)\ge g(p)+\frac{v-p}\lambda\cdot(u-p)\qquad(u\in\mathbb{R}^n) $$
が成り立つこと(以下、この不等式を近接写像の不等式と呼ぶ。$\frac{v-p}\lambda$ が $g$ の $p$ での 劣微分 に属すること)は同値である。

近接勾配法と加速版

$f\colon\mathbb{R}^n\to\mathbb{R}$ を微分可能、$g$ を閉真凸関数、$F:=f+g$ とする。初期点 $x_0$ と刻み幅 $\lambda>0$ について
$$ x_{k+1}:=\operatorname{prox}_{\lambda g}\bigl(x_k-\lambda\nabla f(x_k)\bigr)\qquad(k=0,1,2,\dots) $$
で点列を作る方法を 近接勾配法(proximal gradient method)という。また、$y_1:=x_0$、$t_1:=1$ とし、$k=1,2,\dots$ について
$$ x_k:=\operatorname{prox}_{\lambda g}\bigl(y_k-\lambda\nabla f(y_k)\bigr),\quad t_{k+1}:=\frac{1+\sqrt{1+4t_k^2}}2,\quad y_{k+1}:=x_k+\frac{t_k-1}{t_{k+1}}(x_k-x_{k-1}) $$
で点列を作る方法を 加速近接勾配法(FISTA)という。

$g=\mu\|\cdot\|_1$ の場合の近接勾配法は ISTA(iterative shrinkage-thresholding algorithm)とも呼ばれ、FISTA はその加速版の名である。$y_2$ の式で $x_1-x_0$ に掛かる係数は $t_1-1=0$ なので、$y_2=x_1$ である。
$L$ 平滑性と $m$ 強凸性は 勾配降下法 の定義「L 平滑と m 強凸」のとおりとする。この記事の評価を使う条件をまとめる。

  1. $f$ の凸性:$f$ は $\mathbb{R}^n$ 上の凸関数(等比数列の評価では $m$ 強凸)。
  2. $L$ 平滑:$\|\nabla f(x)-\nabla f(y)\|\le L\|x-y\|$(すべての $x,y$)。
  3. $g$ が閉真凸:とくに下半連続であること。
  4. 最小点:$F(x^*)=\min F$ となる $x^*$ がある。$F^*:=F(x^*)$、$R:=\|x_0-x^*\|$ とおく。
  5. 刻み幅:$0<\lambda\le1/L$。
    条件 1・2 は $f$ だけに課し、$g$ には微分可能性も連続性も求めない。$g$ に要るのは近接写像が計算できることである。

公式の表

近接写像の例($\lambda>0$):

$g$$\operatorname{prox}_{\lambda g}(v)$根拠
$0$$v$定義
$I_C$($C$ は空でない閉凸集合)$C$ への射影 $P_C(v)$定義(最も近い点)
$I_{[a,b]}$(箱 $\prod_j[a_j,b_j]$)成分ごとに $\min\{\max\{v_j,a_j\},b_j\}$成分に分かれる
$\mu\|u\|_1=\mu\sum_j\lvert u_j\rvert$成分ごとに $\operatorname{sign}(v_j)\max\{\lvert v_j\rvert-\lambda\mu,0\}$prop-pg-soft
$\frac\alpha2\|u\|^2$($\alpha\ge0$)$\dfrac{v}{1+\lambda\alpha}$微分して $0$ とおく

収束の評価($\lambda\le1/L$):

方法仮定評価根拠
近接勾配法条件 1〜5$F(x_k)-F^*\le\dfrac{R^2}{2\lambda k}$、$F(x_k)$ は単調に減るthm-pg-rate
近接勾配法$f$ が $m$ 強凸$\|x_k-x^*\|^2\le(1-\lambda m)^kR^2$thm-pg-rate
加速版条件 1〜5$F(x_k)-F^*\le\dfrac{2R^2}{\lambda(k+1)^2}$(単調とは限らない)thm-pg-fista

主定理と証明

1 回の更新の基本不等式

基本不等式

$f$ を凸かつ $L$ 平滑、$g$ を閉真凸関数、$0<\lambda\le1/L$ とする。$y\in\mathbb{R}^n$ について $p:=\operatorname{prox}_{\lambda g}(y-\lambda\nabla f(y))$ とおくと、すべての $x\in\mathbb{R}^n$ で
$$ F(x)-F(p)\ge\frac1{2\lambda}\bigl(\|p-x\|^2-\|y-x\|^2\bigr) $$
が成り立つ。さらに $f$ が $m$ 強凸なら、右辺に $\frac m2\|x-y\|^2$ を加えた不等式が成り立つ。

3 つの不等式を足す

$F(x)=+\infty$ なら明らかなので、$g(x)<+\infty$ とする。次の 3 つを使う。

  • 凸最適化 の補題「凸関数は接平面より上にある」:$f(x)\ge f(y)+\nabla f(y)\cdot(x-y)$。強凸なら右辺に $\frac m2\|x-y\|^2$ が加わる(強凸性の定義そのもの)。
  • 勾配降下法 の補題「降下補題」と $L\le1/\lambda$:$f(p)\le f(y)+\nabla f(y)\cdot(p-y)+\frac1{2\lambda}\|p-y\|^2$。
  • 近接写像の不等式を $v=y-\lambda\nabla f(y)$ に使う:$\frac{v-p}\lambda=\frac{y-p}\lambda-\nabla f(y)$ なので $g(x)\ge g(p)+\bigl(\frac{y-p}\lambda-\nabla f(y)\bigr)\cdot(x-p)$。
    1 つ目と 3 つ目を足し、2 つ目を引くと、$\nabla f(y)$ を含む項は $\nabla f(y)\cdot\bigl((x-y)-(p-y)-(x-p)\bigr)=0$ と消えて
    $$ F(x)-F(p)\ge\frac1\lambda(y-p)\cdot(x-p)-\frac1{2\lambda}\|p-y\|^2 $$
    となる。$a:=y-p$、$b:=x-p$ とおくと $2a\cdot b=\|a\|^2+\|b\|^2-\|a-b\|^2$ で、$a-b=y-x$ なので、右辺は $\frac1{2\lambda}\bigl(\|x-p\|^2-\|x-y\|^2\bigr)$ に等しい。強凸のときは 1 つ目の不等式の余分の項がそのまま残る。$\square$

この証明で $L\le1/\lambda$ を使ったのは 2 つ目の不等式だけである。$L$ を知らなくても、各回でこの不等式が成り立つまで $\lambda$ を小さくすれば(節「計算の手順」)、以下の評価は $\lambda$ をそれまでに使った最小の刻み幅に置きかえて成り立つ(刻み幅は縮めるだけで大きくしない)。

不動点と最小点

条件 1〜3 と $0<\lambda\le1/L$ のもとで、$x^*$ が $F$ の最小点であることと、$x^*=\operatorname{prox}_{\lambda g}\bigl(x^*-\lambda\nabla f(x^*)\bigr)$ であることは同値である。

$x^*$ が不動点なら、lem-pg-key を $y=x^*$(このとき $p=x^*$)で使うと、すべての $x$ で $F(x)-F(x^*)\ge\frac1{2\lambda}\bigl(\|x^*-x\|^2-\|x^*-x\|^2\bigr)=0$ である。逆に $x^*$ が最小点なら、$y=x=x^*$ とおいて $0\ge F(x^*)-F(p)\ge\frac1{2\lambda}\|p-x^*\|^2$ を得るので $p=x^*$ である。$\square$

不動点の条件は、近接写像の不等式により $-\nabla f(x^*)$ が $g$ の $x^*$ での劣微分に属すること、すなわち $0\in\nabla f(x^*)+\partial g(x^*)$ と同じである。この形の最適性条件は LASSO の解の性質の出発点になる。

主定理:$1/k$ の速さ

近接勾配法の収束率

条件 1〜5 を仮定し、$x_k$ を近接勾配法の点列とする。

  1. $F(x_{k+1})\le F(x_k)-\frac1{2\lambda}\|x_{k+1}-x_k\|^2$ であり、$\|x_{k+1}-x^*\|\le\|x_k-x^*\|$ である。
  2. $k\ge1$ について $F(x_k)-F^*\le\dfrac{\|x_0-x^*\|^2}{2\lambda k}$。
  3. $f$ が $m$ 強凸なら $\|x_k-x^*\|^2\le(1-\lambda m)^k\|x_0-x^*\|^2$。
基本不等式を 2 通りの点で使う

lem-pg-key を $y=x_j$ で使う。このとき $p=x_{j+1}$ である。
1:$x=x_j$ とおくと $F(x_j)-F(x_{j+1})\ge\frac1{2\lambda}\|x_{j+1}-x_j\|^2\ge0$ である。$x=x^*$ とおくと
$$ F(x_{j+1})-F^*\le\frac1{2\lambda}\bigl(\|x_j-x^*\|^2-\|x_{j+1}-x^*\|^2\bigr) $$
で、左辺は $0$ 以上なので $\|x_{j+1}-x^*\|\le\|x_j-x^*\|$ である。
2:この不等式を $j=0,1,\dots,k-1$ について足すと、右辺は差の和なので
$$ \sum_{j=1}^k\bigl(F(x_j)-F^*\bigr)\le\frac1{2\lambda}\bigl(\|x_0-x^*\|^2-\|x_k-x^*\|^2\bigr)\le\frac{\|x_0-x^*\|^2}{2\lambda} $$
である。1 により $F(x_j)$ は $j$ について減少するので、左辺は $k\bigl(F(x_k)-F^*\bigr)$ 以上である。両辺を $k$ で割ればよい。
3:強凸の場合の lem-pg-key を $y=x_j$、$x=x^*$ で使うと
$$ 0\ge F^*-F(x_{j+1})\ge\frac1{2\lambda}\bigl(\|x_{j+1}-x^*\|^2-\|x_j-x^*\|^2\bigr)+\frac m2\|x_j-x^*\|^2 $$
であり、$\|x_{j+1}-x^*\|^2\le(1-\lambda m)\|x_j-x^*\|^2$ を得る。$m\le L\le1/\lambda$(勾配降下法 の降下補題と強凸性の不等式を同じ 2 点 $x\ne y$ で比べると $m\le L$)なので $0\le1-\lambda m<1$ で、これを繰り返せばよい。$\square$

$g=0$ のとき、評価 2 は 勾配降下法 の定理「凸の場合の評価」と同じ形で、近接写像を挟んでも勾配降下法と同じ速さが保たれることを示している。$g$ がどれほど複雑でも、その複雑さは近接写像の計算に閉じ込められ、反復の回数の評価には現れない。

加速版:$1/k^2$ の速さ

加速版の収束率

条件 1〜5 を仮定し、$x_k$ を加速近接勾配法の点列とする。$k\ge1$ について
$$ F(x_k)-F^*\le\frac{2\|x_0-x^*\|^2}{\lambda(k+1)^2}. $$

重みつきの量が増えないことを示す
証明を開く

$v_k:=F(x_k)-F^*$、$u_k:=t_kx_k-(t_k-1)x_{k-1}-x^*$ とおく($u_1=x_1-x^*$)。lem-pg-key を $y=y_{k+1}$(このとき $p=x_{k+1}$)で、$x=x_k$ と $x=x^*$ に使うと$$v_k-v_{k+1}\ge\tfrac1{2\lambda}\bigl(\|x_{k+1}-x_k\|^2-\|y_{k+1}-x_k\|^2\bigr),\qquad -v_{k+1}\ge\tfrac1{2\lambda}\bigl(\|x_{k+1}-x^*\|^2-\|y_{k+1}-x^*\|^2\bigr)$$である。$t:=t_{k+1}\ge1$ とし、1 つ目を $t-1$ 倍して 2 つ目と足す。$\|p-z\|^2-\|y-z\|^2=\|p-y\|^2+2(p-y)\cdot(y-z)$ を使うと、右辺の括弧は $t\|x_{k+1}-y_{k+1}\|^2+2(x_{k+1}-y_{k+1})\cdot w$、$w:=ty_{k+1}-(t-1)x_k-x^*$ になる。全体を $t$ 倍すると、$\|a+w\|^2-\|w\|^2=\|a\|^2+2a\cdot w$($a:=t(x_{k+1}-y_{k+1})$)により$$t(t-1)v_k-t^2v_{k+1}\ge\tfrac1{2\lambda}\bigl(\|tx_{k+1}-(t-1)x_k-x^*\|^2-\|w\|^2\bigr)$$である。$t_{k+1}$ の定義は $t_{k+1}^2-t_{k+1}=t_k^2$ と同じである。また $y_{k+1}$ の定義から $t_{k+1}y_{k+1}=t_{k+1}x_k+(t_k-1)(x_k-x_{k-1})$ なので $w=u_k$ であり、$tx_{k+1}-(t-1)x_k-x^*=u_{k+1}$ である。よって$$t_{k+1}^2v_{k+1}+\tfrac1{2\lambda}\|u_{k+1}\|^2\le t_k^2v_k+\tfrac1{2\lambda}\|u_k\|^2$$で、$k\ge1$ について $t_k^2v_k\le t_1^2v_1+\frac1{2\lambda}\|u_1\|^2$ である。lem-pg-key を $y=y_1=x_0$、$x=x^*$ で使うと $v_1+\frac1{2\lambda}\|x_1-x^*\|^2\le\frac1{2\lambda}\|x_0-x^*\|^2$ なので、$t_k^2v_k\le\frac1{2\lambda}\|x_0-x^*\|^2$ である。最後に、$t_{k+1}\ge\frac{1+2t_k}2=t_k+\frac12$ と $t_1=1$ から $t_k\ge\frac{k+1}2$ である。$\square$

加速版は、1 回の計算量(勾配 1 つと近接写像 1 つ)は変わらないまま、評価の分母を $k$ から $k^2$ に上げる。その代わり、$F(x_k)$ は単調には減らない(例題「1 ノルムで罰した最小二乗」と図)。

1 ノルムの近接写像(軟しきい値)

$\mu>0$、$g(u)=\mu\|u\|_1$ なら、$\operatorname{prox}_{\lambda g}(v)$ の第 $j$ 成分は $\operatorname{sign}(v_j)\max\{|v_j|-\lambda\mu,0\}$ である。

証明を開く

最小化する式 $\sum_j\bigl(\mu|u_j|+\frac1{2\lambda}(u_j-v_j)^2\bigr)$ は成分ごとの和なので、各成分を別々に最小化すればよい。1 変数の $\lambda\mu|t|+\frac12(t-v_j)^2$ の最小点は、Moreau–吉田正則化 の例「絶対値と軟しきい値」の $J_{\lambda\mu}v_j=\operatorname{sign}(v_j)\max\{|v_j|-\lambda\mu,0\}$ である(式を正の数 $\frac1{\lambda\mu}$ 倍しても最小点は変わらず、$|t|+\frac1{2\lambda\mu}(t-v_j)^2$ になる)。$\square$

計算の手順

  1. 分ける:目的関数を $F=f+g$ に分ける。$f$ は凸で $L$ 平滑、$g$ は近接写像が閉じた形で計算できるもの(公式の表)にする。分け方は 1 通りではない。
  2. 刻み幅を決める:$L$ が分かれば $\lambda=1/L$ とする。$f=\frac12\|Ax-b\|^2$ なら $\nabla f(x)=A^{\mathsf T}(Ax-b)$ で、$L$ は $A^{\mathsf T}A$ の最大固有値である。$L$ が分からなければ、$\lambda$ を $\beta\lambda$($0<\beta<1$、たとえば $\beta=\frac12$)に縮めながら、$p=\operatorname{prox}_{\lambda g}(y-\lambda\nabla f(y))$ が $f(p)\le f(y)+\nabla f(y)\cdot(p-y)+\frac1{2\lambda}\|p-y\|^2$ を満たすまで試す(lem-pg-key の後の注意)。
  3. 反復する:近接勾配法か加速版の式で $x_k$ を更新する。
  4. 止める:$G_k:=\frac1\lambda\|x_k-x_{k+1}\|$ が許容誤差 $\varepsilon$ 以下になったら止める。$G_k=0$ は $x_k$ が不動点であること、すなわち最小点であることと同じである(prop-pg-fixed)。$g=0$ なら $G_k=\|\nabla f(x_k)\|$ である。反復の上限も置く。

例題

軟しきい値の計算

$g=\|\cdot\|_1$、$\lambda=1$、$v=(3,-0.5,1.2,-2)$ の近接写像。
使う公式:prop-pg-soft。
答え:$\operatorname{prox}_{g}(v)=(2,\,0,\,0.2,\,-1)$。絶対値が $1$ 以下の成分はちょうど $0$ になり、残りは $1$ だけ $0$ に近づく。

1 ノルムで罰した最小二乗

$A=\begin{pmatrix}1&1\\1&0.5\end{pmatrix}$、$b=(3,1)$、$\mu=0.5$ として $F(x)=\frac12\|Ax-b\|^2+0.5\|x\|_1$ を、$x_0=0$、$\lambda=1/L$ で最小化する。
使う公式:thm-pg-rate、thm-pg-fista、prop-pg-fixed。
答え:$L=\frac{13+\sqrt{153}}8\approx3.171165$、最小点 $x^*=(0,\,2.4)$、$F^*=1.4$、$R=2.4$。近接勾配法の第 1 回は $x_1\approx(1.103695,\,0.946025)$。第 1 成分は $k=48$ でちょうど $0$ になり、$F(x_k)-F^*\le10^{-6}$ となるのは $k=55$ から(評価 thm-pg-rate の右辺は $k=55$ で $0.16605$)。加速版は $k=25$ で初めて $10^{-6}$ 以下になる。

途中の計算を開く

$A^{\mathsf T}A=\begin{pmatrix}2&1.5\\1.5&1.25\end{pmatrix}$、$A^{\mathsf T}b=(4,3.5)$。固有値は $\frac{13\pm\sqrt{153}}8\approx3.1712,\ 0.0788$ で、条件数は約 $40$。最小点の確認は prop-pg-fixed の後の注意による:$\nabla f(x^*)=A^{\mathsf T}Ax^*-A^{\mathsf T}b=(-0.4,\,-0.5)$。第 2 成分は正なので $-\nabla_2f=0.5=\mu$ が要り、第 1 成分は $0$ なので $|\nabla_1f|=0.4\le\mu$ が要る。どちらも成り立つ。$F^*=\frac12(0.6^2+0.2^2)+0.5\cdot2.4=1.4$。反復は $x\mapsto\operatorname{prox}_{\lambda g}\bigl(x-\lambda(A^{\mathsf T}Ax-A^{\mathsf T}b)\bigr)$ で、近接写像は成分ごとの軟しきい値(しきい値 $\lambda\mu\approx0.157671$)。第 1 成分が $0$ になった後は 1 変数の問題になり、等比数列の速さで収束する。

図: 例題「1 ノルムで罰した最小二乗」で F(x_k) − F* を片対数で描いたもの。近接勾配法は k がおよそ 45 まではゆっくり減り、その後は直線的に速く減る。加速版は上下に振れながら近接勾配法より速く減る。破線と点線は 2 つの定理の上界で、どちらの方法の値も対応する上界より下にある。 図: 例題「1 ノルムで罰した最小二乗」で F(x_k) − F* を片対数で描いたもの。近接勾配法は k がおよそ 45 まではゆっくり減り、その後は直線的に速く減る。加速版は上下に振れながら近接勾配法より速く減る。破線と点線は 2 つの定理の上界で、どちらの方法の値も対応する上界より下にある。

箱の上の射影勾配法

$f(x)=\frac12\bigl((x_1-2)^2+10(x_2+1)^2\bigr)$ を箱 $C=[0,1]^2$ の上で最小化する。$g=I_C$、$L=10$、$\lambda=0.1$、$x_0=(0.5,0.5)$。
使う公式:公式の表の箱の行、prop-pg-fixed。
答え:$x_1=(0.65,0)$、$x_2=(0.785,0)$、$x_3=(0.9065,0)$、$x_4=(1,0)=x^*$、$f(x^*)=5.5$。

途中の計算を開く

勾配の段は $x_1\mapsto0.9x_1+0.2$、$x_2\mapsto0$ の後に $[0,1]$ へ切り詰める。第 1 成分は $0.65,0.785,0.9065$ と進み、$0.9\cdot0.9065+0.2=1.01585$ を $1$ に切り詰める。第 2 成分は $0.5-0.1\cdot15=-1\mapsto0$ で、以後 $0-1=-1\mapsto0$。$(1,0)$ からの勾配の段は $(1.1,-1)$ で、切り詰めると $(1,0)$ に戻るので不動点、したがって最小点である。

使える条件と反例

thm-pg-rate の条件のうち 1 つだけを外した例を挙げる(1 次元)。

外す条件反例成り立たなくなること
刻み幅 $\lambda\le1/L$$f=\frac12x^2$($L=1$)、$g=0$、$\lambda=3$、$x_0=1$$x_k=(-2)^k$ で発散($x_5=-32$)
$g$ の凸性$f=\frac12(x-0.4)^2$、$g=I_{\{-1,1\}}$(閉だが凸でない集合)、$\lambda=0.5$、$x_0=-1$$x_k=-1$ のまま。$F(-1)=0.98>F(1)=0.18$ で、不動点が最小点でない(prop-pg-fixed が成り立たない)
$g$ の下半連続性$f=\frac12(x-0.5)^2$、$g=I_{(0,1]}$、$\lambda=0.5$、$x_0=-5$第 1 回で $\operatorname{prox}_{\lambda g}(-2.25)$ が存在しない(最小点は $x^*=0.5$ にある)
$f$ の凸性$f=x^2+10\sin^2x$($L=22$)、$g=0$、$\lambda=\frac1{22}$、$x_0=2.5$$x_k\to2.839604$、$F\to8.947934$ で $F^*=0$ に近づかない
$L$ 平滑性$f=\frac14x^4$、$g=0$、$\lambda=0.1$、$x_0=5$$x_1=-7.5$、$x_2=34.6875$、$x_3\approx-4138.99$ と発散
最小点の存在$f=\sqrt{1+x^2}-x$($L=1$、$\inf f=0$ はとられない)、$g=0$、$\lambda=1$、$x_0=1$$F(x_k)\to0$ だが $k\,F(x_k)\to\infty$ で、どんな $C$ でも $C/k$ の評価が成り立たない
表の反例の確かめ
確認を開く

1 行目:$x_{k+1}=x_k-3x_k$。$1/L<\lambda<2/L$ では $f=\frac12x^2$ でも収束するが、lem-pg-key の証明は使えない。2 行目:$\operatorname{prox}_{\lambda g}$ は $\{-1,1\}$ のうち近い点への射影で、$-1-0.5(-1.4)=-0.3$ は $-1$ に写る。3 行目:$g$ は凸で真だが $(0,1]$ が閉でないので下半連続でない。$v=-5-0.5\cdot(-5.5)=-2.25$ で、$(u+2.25)^2$ の $(0,1]$ 上の下限は $u\downarrow0$ でしか近づけない。4 行目:$f''=2+20\cos2x\in[-18,22]$。$x=2.839604$ は $f'=0$、$f''\approx18.46>0$ の極小点。5 行目:$x_{k+1}=x_k-0.1x_k^3$。$L$ がないので条件 5 の $1/L$ は定まらず、どの $\lambda>0$ でも $\lvert x_0\rvert>\sqrt{2/\lambda}$ なら $\lvert x_{k+1}\rvert=\lvert x_k\rvert(\lambda x_k^2-1)$ は増え続けて発散する。$f$ は凸で最小点 $0$ をもつが $f''=3x^2$ は有界でない。6 行目:$f''=(1+x^2)^{-3/2}\in(0,1]$ なので凸で $L=1$。$f'(x)=-\bigl(\sqrt{1+x^2}(\sqrt{1+x^2}+x)\bigr)^{-1}$ なので $x\ge1$ で $x_{k+1}\le x_k+\frac1{2x_k^2}$、これを 3 乗すると $x_{k+1}^3\le x_k^3+\frac32+\frac34+\frac18$ で、$x_k^3\le1+2.375k$ である。$f(x)=(\sqrt{1+x^2}+x)^{-1}\ge\frac1{3x}$($x\ge1$)なので $F(x_k)\ge\frac13(1+2.375k)^{-1/3}$ となり、$kF(x_k)\to\infty$ である($k=10^6$ で $k^{1/3}F(x_k)\approx0.4368$)。

よくある誤り

誤り正しくはなぜ
$\mu\|\cdot\|_1$ の近接写像のしきい値を $\mu$ とするしきい値は $\lambda\mu$近接写像は $\lambda g$ について計算する(prop-pg-soft)
加速版で $F(x_k)$ が増えたら失敗とみなす加速版は単調でない。評価は上界の形で成り立つthm-pg-fista、例題「1 ノルムで罰した最小二乗」
止める判定に $F(x_k)-F(x_{k+1})$ だけを使う$\frac1\lambda\|x_k-x_{k+1}\|$ を使うこれが $0$ であることが最適性と同値(prop-pg-fixed)
$g$ の近接写像が計算できない分け方をする$\mu\|Dx\|_1$($D$ が一般の行列)などは別の方法(交互方向乗数法)で扱う近接写像が反復ごとの最適化問題になる
$f$ が凸でないときも最小点に収束すると考える言えるのは不動点への接近まで反例の表の 4 行目

補足

  • 近接点法と Moreau 包絡:$f=0$ の場合 $x_{k+1}=\operatorname{prox}_{\lambda g}(x_k)$ は近接点法と呼ばれる。Moreau–吉田正則化 の定理「正則化の微分可能性」により $x_{k+1}=x_k-\lambda\nabla e_\lambda g(x_k)$ なので、近接点法は Moreau 包絡 $e_\lambda g$ に刻み幅 $\lambda$ の勾配降下法を当てたものである。
  • 作用素の見方:近接勾配法の 1 回は「勾配の段(前進)」と「近接写像の段(後退)」の合成で、前進後退分割(forward–backward splitting)とも呼ばれる(PB14 §4.2、pp. 148–151)。同じ文献 §4.3(p. 152)は、外挿の係数を $\frac k{k+3}$ とする別の加速版も挙げている。$g=0$(滑らかな関数だけ)の場合の加速の別の形と、勾配だけを使う方法の収束の下界は Nesterovの加速法 で扱う。
  • 関連する方法:$g$ の近接写像が計算できないとき、変数を分けて 2 つの近接写像を交互に使うのが 交互方向乗数法 である。$f$ の 2 階導関数を使って $\lambda$ の代わりに行列で尺度を直すと、近接 Newton 法と呼ばれる方法になる。

関連項目

参考文献

[1]
Neal Parikh, Stephen Boyd, Proximal Algorithms, Foundations and Trends in Optimization, 2014, §4.2 Proximal gradient method(pp. 148–151)、§4.3 Accelerated proximal gradient method(p. 152)。頁は著者公開版の柱による

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