近接勾配法(proximal gradient method)とは、微分できる関数 $f$ と、微分できなくてもよい凸関数 $g$ の和の最小点を探すため、$f$ の勾配の逆向きに進んでから $g$ の近接写像をとる操作を繰り返す反復法である。$g$ が絶対値の和なら近接写像は軟しきい値になり、LASSO のような疎な解を求める問題に使う。$f$ が凸で勾配が定数 $L$ の Lipschitz 連続、$g$ が凸で下半連続、最小点があり刻み幅が $1/L$ 以下なら、目的関数の誤差は反復回数に反比例して減り、$f$ が強凸なら最小点までの距離が等比数列の速さで減る。慣性の項を加えた加速版では誤差が反復回数の 2 乗に反比例して減る。
前提知識: 勾配降下法, 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 強凸」のとおりとする。この記事の評価を使う条件をまとめる。
近接写像の例($\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 |
$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$ を加えた不等式が成り立つ。
$F(x)=+\infty$ なら明らかなので、$g(x)<+\infty$ とする。次の 3 つを使う。
この証明で $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〜5 を仮定し、$x_k$ を近接勾配法の点列とする。
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〜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 ノルムで罰した最小二乗」と図)。
$\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$
$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$ に近づく。
$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 つの定理の上界で、どちらの方法の値も対応する上界より下にある。
$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 行目 |
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する