座標降下法(coordinate descent)とは、多変数の関数を最小にするのに、各段で座標を 1 つだけ選び、ほかの座標を止めたままその座標だけを偏微分の向きに動かすか、その座標について厳密に最小にする反復法で、座標を順に回す巡回の方法と、毎回一様に選ぶ無作為の方法がある。最小値をとり初期点の下位集合が有界な凸関数では、座標ごとの Lipschitz 定数の最大値 $L_{\max}$ の逆数を刻み幅とする無作為の方法の誤差の期待値は段数に反比例して減り、強凸なら等比数列の速さで減る。2 次関数で座標ごとに厳密に最小にする巡回の方法は Gauss–Seidel 法と同じで、微分可能な凸関数に座標ごとに分かれた凸な項を足した関数でも座標ごとの最小点は全体の最小点になるので、LASSO の計算に使われる。
座標降下法(coordinate descent)は、多変数の関数 $f\colon\mathbb R^n\to\mathbb R$ を最小にするのに、各段で座標を 1 つだけ選び、ほかの座標を止めたままその座標だけを動かして $f$ を下げる反復法である。動かし方は、その座標の偏微分の向きに一定の刻みで進むか、その座標について厳密に最小にするかのどちらかが基本で、座標の選び方には、順に回す 巡回 と、毎回一様な確率で選ぶ 無作為 がある。
1 段で計算するのは偏微分 1 つ(または 1 変数の最小化 1 回)だけなので、変数が多く、1 つの座標の更新が安く済む問題に向く。2 次関数で座標ごとに厳密に最小にする巡回の方法は、連立 1 次方程式の Gauss–Seidel法 と同じ計算になる。統計学の LASSO の標準的な計算法もこの方法である(HTF09 §3.8.6)。
この記事では、座標ごとの Lipschitz 定数を定義して、無作為な座標降下法の誤差の期待値の評価(thm-cd-random)を証明し、勾配降下法 と比べる。次に、$f$ に座標ごとに分かれた凸な項を足した関数では、座標ごとの最小点が全体の最小点であること(thm-cd-separable)を示し、分かれていない項では成り立たない反例を挙げる。
$e_1,\dots,e_n$ を $\mathbb R^n$ の標準基底、$\lvert\cdot\rvert$ を Euclid ノルム、$\partial_if$ を第 $i$ 座標についての偏微分とする。$f$ は微分可能で、$\nabla f$ は連続であるとする。
$L_1,\dots,L_n>0$ が、すべての $x\in\mathbb R^n$、$t\in\mathbb R$、$i$ について
$$
\bigl\lvert\partial_if(x+te_i)-\partial_if(x)\bigr\rvert\le L_i\lvert t\rvert
$$
を満たすとき、$L_i$ を $f$ の第 $i$ 座標の Lipschitz 定数 という。$L_{\max}:=\max_iL_i$ とおく。
これは、各座標の直線 $t\mapsto f(x+te_i)$ に制限した 1 変数関数の導関数が $L_i$-Lipschitz 連続であるという条件である。$\nabla f$ 全体の Lipschitz 定数 $L$(勾配降下法 の「$L$ 平滑」)と比べると、次が成り立つ。
1. $\lvert\partial_if(x+te_i)-\partial_if(x)\rvert\le\lvert\nabla f(x+te_i)-\nabla f(x)\rvert\le L\lvert te_i\rvert=L\lvert t\rvert$ である。
2. $\partial_if(x+te_i)-\partial_if(x)=\int_0^t\partial_i^2f(x+se_i)\,ds$ で、凸関数の Hesse 行列は半正定値なので対角成分は $0$ 以上である。よって絶対値は $L_i\lvert t\rvert$ 以下である。各点の Hesse 行列 $H$ は半正定値なので、最大の固有値は固有値の和すなわち跡 $\sum_iH_{ii}\le\sum_iL_i$ 以下で、作用素ノルムも同じ値以下である。$\nabla f(y)-\nabla f(x)=\int_0^1H(x+s(y-x))(y-x)\,ds$ から $\lvert\nabla f(y)-\nabla f(x)\rvert\le(\sum_iL_i)\lvert y-x\rvert$ である。$\square$
したがって $C^2$ 級の凸関数では、最良の定数どうしで $L_{\max}\le L\le nL_{\max}$ である。右の等号は $f(x)=\frac12(x_1+\dots+x_n)^2$ で成り立つ(Hesse 行列は全成分が $1$ の行列で、$L_i=1$、$L=n$)。左の等号は座標ごとに分かれた $f(x)=\sum_ic_ix_i^2$ で成り立つ(Wri15 p. 12 も $1\le L/L_{\max}\le n$ を述べる)。
初期点 $x_0\in\mathbb R^n$ をとる。$k=0,1,2,\dots$ について座標 $i_k\in\{1,\dots,n\}$ を選び、
$$
x_{k+1}:=x_k-\alpha_k\,\partial_{i_k}f(x_k)\,e_{i_k}
$$
とする。$\alpha_k>0$ は刻み幅である。$i_k$ の選び方が
$x_k$ と $x_{k+1}$ は第 $i_k$ 座標だけが異なる。刻み幅は以下では $\alpha_k=1/L_{\max}$ とする(Wri15 Algorithm 3 と Theorem 1、BCN18 §7.3 の Theorem 7.1 と同じ選び方)。
$f$ が座標ごとの Lipschitz 定数 $L_1,\dots,L_n$ をもつなら、すべての $x$ と $i$ で
$$
f\Bigl(x-\frac1{L_{\max}}\partial_if(x)\,e_i\Bigr)\le f(x)-\frac1{2L_{\max}}\bigl(\partial_if(x)\bigr)^2
$$
である。
$\varphi(t):=f(x+te_i)$ は $C^1$ 級で $\varphi'(t)=\partial_if(x+te_i)$ なので、$\varphi'$ は $L_i$-Lipschitz 連続である。勾配降下法 の補題「降下補題」の証明を 1 変数で行うと
$$
\varphi(t)-\varphi(0)-\varphi'(0)t=\int_0^1\bigl(\varphi'(st)-\varphi'(0)\bigr)t\,ds\le\int_0^1L_is\,t^2\,ds=\frac{L_i}2t^2
$$
である。$t=-\varphi'(0)/L_{\max}$ を入れ、$L_i\le L_{\max}$ を使うと
$$
\varphi(t)\le\varphi(0)-\frac{\varphi'(0)^2}{L_{\max}}+\frac{L_i}{2L_{\max}^2}\varphi'(0)^2\le\varphi(0)-\frac{\varphi'(0)^2}{2L_{\max}}
$$
である。$\square$
とくに、どの座標の選び方でも $f(x_0)\ge f(x_1)\ge f(x_2)\ge\cdots$ で、点列は初期点の 下位集合 $\{x\mid f(x)\le f(x_0)\}$ から出ない。
$f$ を微分可能な凸関数で、座標ごとの Lipschitz 定数 $L_1,\dots,L_n$ をもち、最小値 $f^*$ をとるものとする。$(x_k)$ を刻み幅 $1/L_{\max}$ の無作為な座標降下法の点列とし、$\mathbb E$ は $i_0,i_1,\dots$ についての期待値とする。
$x_k$ は $i_0,\dots,i_{k-1}$ で決まり、$i_k$ はそれらと独立で一様に分布する。$x_k$ を止めて $i_k$ について平均すると、lem-cd-descent から
$$
\mathbb E\bigl[f(x_{k+1})\bigm|x_k\bigr]\le f(x_k)-\frac1{2L_{\max}}\cdot\frac1n\sum_{i=1}^n\bigl(\partial_if(x_k)\bigr)^2=f(x_k)-\frac{\lvert\nabla f(x_k)\rvert^2}{2nL_{\max}}
$$
である。この不等式を $(\ast)$ とよぶ。$\delta_k:=f(x_k)-f^*\ge0$、$\phi_k:=\mathbb E\delta_k$ とおく。
1. $x^*\in S$ をとる。$f$ は凸なので $\delta_k\le\nabla f(x_k)\cdot(x_k-x^*)$ で(凸関数 の接線の不等式)、$x_k$ は下位集合にあるので $\lvert x_k-x^*\rvert\le R_0$ である。Cauchy–Schwarzの不等式 から $\lvert\nabla f(x_k)\rvert\ge\delta_k/R_0$ である($R_0=0$ なら $x_0$ は最小点で主張は明らか)。$(\ast)$ の全体の期待値をとり、Jensenの不等式 $\mathbb E\delta_k^2\ge\phi_k^2$ を使うと、$c:=2nL_{\max}R_0^2$ として
$$
\phi_{k+1}\le\phi_k-\frac{\mathbb E\delta_k^2}c\le\phi_k-\frac{\phi_k^2}c
$$
である。ある $k$ で $\phi_k=0$ なら以後も $0$ である。すべての $k$ で $\phi_k>0$ なら、$\phi_{k+1}\le\phi_k$ から
$$
\frac1{\phi_{k+1}}-\frac1{\phi_k}=\frac{\phi_k-\phi_{k+1}}{\phi_k\phi_{k+1}}\ge\frac{\phi_k-\phi_{k+1}}{\phi_k^2}\ge\frac1c
$$
で、$k$ 回足すと $\frac1{\phi_k}\ge\frac1{\phi_0}+\frac kc>\frac kc$、すなわち $\phi_k< c/k$ である。
2. 勾配降下法 の命題「勾配の小ささから誤差が分かる」により $\lvert\nabla f(x)\rvert^2\ge2m\bigl(f(x)-f^*\bigr)$ である(強凸性の不等式の右辺を $y$ について最小にすると $f^*\ge f(x)-\lvert\nabla f(x)\rvert^2/(2m)$ になることによる)。これを $(\ast)$ に入れると $\mathbb E[\delta_{k+1}\mid x_k]\le(1-\frac m{nL_{\max}})\delta_k$ で、全体の期待値をとって繰り返すと主張を得る。係数は $0$ 以上である:$m$ 強凸性の不等式を座標の直線に制限して lem-cd-descent の証明の不等式と比べると $m\le L_i\le L_{\max}$ である。$\square$
1 は Wri15 Theorem 1(pp. 13–14)、2 は同 Theorem 1 の後半と BCN18 Theorem 7.1(p. 72)にある。Wri15 は、この証明が Nesterov(Nes12 §2)の解析を簡単にしたものだと述べる。
勾配降下法との比べ方。 勾配 1 つは偏微分 $n$ 個ぶんなので、偏微分 1 つが勾配の $1/n$ 程度の手間で計算できる問題では、座標降下法の $n$ 段と 勾配降下法 の 1 段が同じ費用になる(BCN18 p. 72 の「Favorable Problem Structures」)。$m$ 強凸の場合、刻み幅 $1/L$ の勾配降下法の保証は 1 段で $1-\frac mL\le e^{-m/L}$ 倍、無作為な座標降下法の保証は $n$ 段で $(1-\frac m{nL_{\max}})^n\le e^{-m/L_{\max}}$ 倍である。$L_{\max}\le L\le nL_{\max}$ なので、指数で比べて座標降下法の保証が劣ることはなく、$L$ が $nL_{\max}$ に近い(座標どうしが強く結びついた)関数では指数がおよそ $n$ 倍になる。ex-cd-compare はその場合である。
$f$ が微分できない場合、座標ごとに下げられない点でも最小点とは限らない(反例の表の 1 行目)。しかし、微分できない部分が座標ごとに分かれていれば、座標ごとの最小点は全体の最小点である。
$f\colon\mathbb R^n\to\mathbb R$ を微分可能な凸関数、$h_1,\dots,h_n\colon\mathbb R\to\mathbb R$ を凸関数とし、
$$
F(x):=f(x)+\sum_{i=1}^nh_i(x_i)
$$
とおく。点 $x$ が、すべての $i$ で 1 変数関数 $t\mapsto F(x+(t-x_i)e_i)$ の最小点になっているなら、$x$ は $F$ の $\mathbb R^n$ の上の最小点である。
$i$ を固定し、$g(t):=f(x+(t-x_i)e_i)$、$h:=h_i$ とおく。$g$ は微分可能な凸関数で $g'(x_i)=\partial_if(x)$ である。$t\in\mathbb R$ と $0< s\le1$ について、仮定から $g(x_i+s(t-x_i))+h(x_i+s(t-x_i))\ge g(x_i)+h(x_i)$ で、$h$ の凸性から $h(x_i+s(t-x_i))\le(1-s)h(x_i)+sh(t)$ である。この 2 つから
$$
\frac{g(x_i+s(t-x_i))-g(x_i)}s+h(t)-h(x_i)\ge0
$$
で、$s\downarrow0$ とすると
$$
h_i(t)-h_i(x_i)\ge-\partial_if(x)\,(t-x_i)\qquad(t\in\mathbb R)
$$
である。この不等式を $(\ast\ast)$ とよぶ。任意の $y\in\mathbb R^n$ について、$f$ の凸性(接線の不等式)と $(\ast\ast)$ を $t=y_i$ で足し合わせると
$$
F(y)-F(x)\ge\nabla f(x)\cdot(y-x)-\sum_{i=1}^n\partial_if(x)(y_i-x_i)=0
$$
である。$\square$
$h_i=0$ なら、これは「すべての偏微分が $0$ の点は凸関数の最小点」ということである。$f(\beta)=\frac12\lvert y-X\beta\rvert^2$、$h_i(t)=\lambda\lvert t\rvert$ とすると $F$ は LASSO の目的関数で、同記事の命題「手順の正しさ」が述べる「1 周の間どの係数も変わらなかった点は最小点」はこの定理の特別な場合である。分かれた項をもつ問題の座標降下法では、lem-cd-descent の偏微分の一歩の代わりに、$h_i$ を含めた 1 変数の問題を解く(LASSO では軟しきい値の式で解ける)。
$A$ を $n$ 次の実対称な 正定値行列、$b\in\mathbb R^n$ とし、$f(x)=\frac12x\cdot Ax-b\cdot x$ とする。第 $i$ 座標についての厳密な最小化は
$$
x_i\leftarrow\frac1{A_{ii}}\Bigl(b_i-\sum_{j\ne i}A_{ij}x_j\Bigr)
$$
である。したがって巡回の座標ごとの厳密な最小化を $n$ 段ずつまとめたものは、$Ax=b$ に対する Gauss–Seidel法 の 1 段に等しく、どの初期点からも $Ax=b$ の解($f$ の最小点)に収束する。
$f(x+te_i)=f(x)+t\,(Ax-b)_i+\frac{A_{ii}}2t^2$ で $A_{ii}>0$ なので、最小点は $t=-(Ax-b)_i/A_{ii}$ で、更新後の第 $i$ 成分は $x_i-\frac1{A_{ii}}\bigl(\sum_jA_{ij}x_j-b_i\bigr)$ すなわち上の式である。これを $i=1,\dots,n$ の順に、新しく求めた成分をその場で使って行うのが Gauss–Seidel 法である。収束は Gauss–Seidel法 の系「Hermite 正定値行列での SOR 法」($\omega=1$ の場合)による。$\square$
$A_{ii}$ がすべて等しければ、$L_i=A_{ii}=L_{\max}$ なので、刻み幅 $1/L_{\max}$ の一歩は厳密な最小化と同じである。最小二乗の問題 $\frac12\lvert Aw-b\rvert^2$ では、座標ごとの厳密な最小化は正規方程式 $A^{\mathsf T}Aw=A^{\mathsf T}b$ への Gauss–Seidel 法になる(Wri15 p. 7)。
$\lvert\rho\rvert< 1$、$A=\begin{pmatrix}1&\rho\\\rho&1\end{pmatrix}$、$b=0$ とする。最小点は $0$ である。巡回の厳密な最小化は prop-cd-gs により $x_1\leftarrow-\rho x_2$、$x_2\leftarrow-\rho x_1$ で、1 周で $x_2$ は $\rho^2$ 倍になる。1 周の終わりには $x_1=-\rho x_2$ なので $f=\frac12(1-\rho^2)x_2^2$ で、$f$ は 1 周ごとに $\rho^4$ 倍になる。$\rho=0.6$ なら $x_2$ は 1 周で $0.36$ 倍である。$\rho\to1$ では等高線の楕円が対角線の向きに細長くなり、座標軸の向きにしか動けない方法は小刻みなジグザグでしか進めない。
$n=100$、$e=(1,\dots,1)$、$A=I+ee^{\mathsf T}$、$b=e_1$、$f(x)=\frac12x\cdot Ax-b\cdot x$、$x_0=0$ とする。$A$ の固有値は $e$ の向きの $101$ と、それに直交する向きの $1$ なので $m=1$、$L=101$ で、対角成分は $2$ なので $L_{\max}=2$ である。$f(x_0)-f^*=\frac12b\cdot A^{-1}b=\frac{50}{101}\approx0.4950$ である。$\partial_if(x)=x_i+\sum_jx_j-b_i$ は、和 $\sum_jx_j$ を持ち回れば 1 段で計算できる。
刻み幅 $1/L$ の勾配降下法を $k$ 段、刻み幅 $1/L_{\max}$ の無作為な座標降下法を $kn$ 段行う。勾配降下法では、$e$ の向きの誤差は 1 段目で消え、直交する向きの誤差は 1 段ごとに $\frac{100}{101}$ 倍になるので、$f(x_k)-f^*=\frac12(1-\frac1n)(\frac{100}{101})^{2k}$ である。座標降下法の列は誤差の期待値である。誤差 $d_k:=x_k-x^*$ は $d_{k+1}=(I-\frac12e_{i_k}e_{i_k}^{\mathsf T}A)d_k$ を満たすので、$P_k:=\mathbb E[d_kd_k^{\mathsf T}]$ は $P_{k+1}=P_k-\frac1{2n}(AP_k+P_kA)+\frac1{4n}\operatorname{diag}(AP_kA)$($\operatorname{diag}$ は対角成分だけを残した行列)を満たし、$\mathbb Ef(x_k)-f^*=\frac12\operatorname{tr}(AP_k)$ である。表の値はこれで計算した(数値計算による値)。
| $k$ | 勾配降下法 | その保証 $(1-\frac1{101})^k\cdot0.4950$ | 座標降下法($kn$ 段、期待値) | その保証 $(1-\frac1{200})^{kn}\cdot0.4950$ |
|---|---|---|---|---|
| $5$ | $0.4481$ | $0.4710$ | $1.74\times10^{-2}$ | $4.04\times10^{-2}$ |
| $10$ | $0.4057$ | $0.4482$ | $6.1\times10^{-4}$ | $3.29\times10^{-3}$ |
| $20$ | $0.3325$ | $0.4057$ | $7.5\times10^{-7}$ | $2.19\times10^{-5}$ |
勾配降下法の刻み幅は最大の固有値 $101$ に縛られて小さく、固有値 $1$ の向きにはほとんど進まない。座標降下法の刻み幅は対角成分 $2$ だけで決まる。保証は 勾配降下法 の定理「強凸の場合の 1 次収束」の 2 と thm-cd-random の 2 による。
各行は 1 つの条件だけを外している。
| 外す条件 | 反例 | 成り立たなくなる結論 |
|---|---|---|
| 微分できない項が座標ごとに分かれること | $F(x,y)=x^2+y^2-2x-2y+3\lvert x-y\rvert$($f=x^2+y^2-2x-2y$ に項 $3\lvert x-y\rvert$ を足したもの) | thm-cd-separable の結論($(0,0)$ は座標ごとの最小点で $F=0$ だが、$F(1,1)=-2$ が最小値。$(0,0)$ から始めた座標ごとの厳密な最小化は動かない) |
| $f$ の凸性 | $f(x)=2\cos x_1+\frac12x_1^2+\frac12x_2^2$、$x_0=0$($L_1=3$、$L_2=1$) | thm-cd-random の 1($\nabla f(0)=0$ で点は $0$ のまま、$f(x_k)=2$、$f^*\le\frac{\pi^2}8$) |
| 刻み幅が $1/L_{\max}$ 以下であること | $n=1$、$f(x)=\frac12x^2$($L_{\max}=1$)、刻み幅 $3$ | lem-cd-descent の降下($x_{k+1}=-2x_k$ で $f(x_k)=4^kf(x_0)\to\infty$) |
1 行目:$y=0$ に止めると $F(t,0)=t^2-2t+3\lvert t\rvert$ は $t>0$ で $t^2+t>0$、$t< 0$ で $t^2-5t>0$ なので、最小点は $t=0$ である。$F$ は $x$ と $y$ の入れ替えで変わらないので、$x=0$ に止めた場合も同じである。一方 $F(x,y)\ge(x-1)^2+(y-1)^2-2\ge-2$ で、等号は $(1,1)$ でだけ成り立つ。$f$ は微分可能な凸関数で、$3\lvert x-y\rvert$ も凸だが、2 つの座標にまたがるので thm-cd-separable の形でない。2 行目:$\partial_1f=-2\sin x_1+x_1$、$\partial_2f=x_2$ はどちらも $0$ で $0$ なので、どの座標を選んでも点は動かない。$\partial_1^2f=1-2\cos x_1$ の絶対値は $3$ 以下なので $L_1=3$ ととれ、$x_1=0$ で $\partial_1^2f=-1$ なので $f$ は凸でない。$2\cos x_1\ge-2$ から下位集合 $\{f\le2\}$ は $\lvert x\rvert^2\le8$ に含まれるので $R_0$ は有限で、$f$ は最小値をとる。$f^*\le f(\frac\pi2,0)=\frac{\pi^2}8< 2$ なので、評価の右辺が $0$ に近づいても誤差は $2-\frac{\pi^2}8$ 以上のままである。3 行目:$x_{k+1}=x_k-3x_k=-2x_k$ である。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する