Frank–Wolfe法

同義語:Frank-Wolfe法条件付き勾配法Frank–Wolfe methodFrank-Wolfe methodFrank–Wolfe algorithmconditional gradient method

概要

Frank–Wolfe法(Frank–Wolfe method)とは、コンパクトな凸集合の上で微分可能な凸関数を最小化するため、各段で現在の点での 1 次近似を集合の上で最小にする点を求め、その点へ向かって刻み幅 $2/(k+2)$ などで進む反復法である。条件付き勾配法とも呼ばれ、集合への射影を使わず線形の最小化だけで済む。曲率定数が有限なら $k$ 回目の誤差は $2C/(k+2)$ 以下に減り、線形の最小化から得られる双対ギャップが誤差の上界を与え、止める条件に使える。多面体の上では反復の点が少数の頂点の凸結合で表されて疎な近似解が得られ、その誤差の大きさ $1/k$ は改良できない。

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

前提知識: 凸関数, 凸集合, 勾配降下法

Frank–Wolfe法(Frank–Wolfe method)は、コンパクトな凸集合 $D$ の上で微分可能な凸関数 $f$ を最小化する反復法で、各段で $f$ を現在の点で 1 次近似し、その 1 次関数を $D$ 上で最小にする点 $s$ に向かって少し進む。条件付き勾配法(conditional gradient method)とも呼ばれる。Frank と Wolfe が 1956 年に多面体の上の 2 次計画のために導入した FW56。各段で解くのは $D$ 上の 線形 の最小化だけで、近接勾配法 や射影勾配法が必要とする $D$ への射影(2 次の最小化)がいらない。$D$ が頂点の凸包なら、反復の点は少数の頂点の凸結合で表され、疎な近似解が得られる。
この記事では、双対ギャップが誤差の上界を与えること(lem-fw-gap)と曲率定数の評価(lem-fw-curvature)を準備し、主定理として誤差が $O(1/k)$ で減ること(thm-fw-rate)を証明する。続いて双対ギャップ自身も $O(1/k)$ で小さくなること(prop-fw-gap-rate)、反復の点が疎であること(cor-fw-sparse)、$k$ 個の頂点で表せる点では $1/k$ より速くは近づけないこと(prop-fw-lower)を示す。

設定とアルゴリズム

$D\subseteq\mathbb R^n$ を空でないコンパクトな凸集合、$f$ を $D$ を含む開集合の上で $C^1$ 級の凸関数とする。内積を $\langle\cdot,\cdot\rangle$、Euclid ノルムを $\lvert\cdot\rvert$ と書く。$D$ はコンパクトで $f$ は連続なので、最小値 $f^*:=\min_Df$ と最小点 $x^*$ が存在する。

Frank–Wolfe 法

$x_0\in D$ をとる。$k=0,1,2,\dots$ について次を繰り返す。

  1. 線形の最小化:$s_k\in\operatorname*{arg\,min}_{s\in D}\langle s,\nabla f(x_k)\rangle$ を 1 つとる。
  2. 更新:$x_{k+1}:=(1-\gamma_k)x_k+\gamma_ks_k$。刻み幅は、固定の規則 $\gamma_k:=\dfrac2{k+2}$ か、直線探索 $\gamma_k\in\operatorname*{arg\,min}_{\gamma\in[0,1]}f\bigl(x_k+\gamma(s_k-x_k)\bigr)$ のどちらかで決める。

1 次関数 $s\mapsto\langle s,\nabla f(x_k)\rangle$ はコンパクトな $D$ 上で最小値をとるので $s_k$ は存在する。$x_{k+1}$ は $D$ の 2 点の凸結合なので $D$ に入り、反復は $D$ の外に出ない。固定の規則では $\gamma_0=1$ なので、$x_1=s_0$ は $x_0$ によらない。

双対ギャップと曲率定数

双対ギャップ

$x\in D$ について $g(x):=\max_{s\in D}\langle x-s,\nabla f(x)\rangle$ を $x$ の 双対ギャップ という。

Frank–Wolfe 法では $g(x_k)=\langle x_k-s_k,\nabla f(x_k)\rangle$ で、線形の最小化の副産物として計算できる。

双対ギャップは誤差の上界

$x\in D$ について $g(x)\ge f(x)-f^*\ge0$ であり、$g(x)=0$ と「$x$ が最小点であること」は同値である。

$f$ は凸なので 凸最適化 の補題「凸関数は接平面より上にある」により $f(x^*)\ge f(x)+\langle x^*-x,\nabla f(x)\rangle$、すなわち $f(x)-f^*\le\langle x-x^*,\nabla f(x)\rangle\le g(x)$。(引いた補題と定理は $\mathbb R^n$ 全体で定義された関数で述べられているが、証明は $D$ を含む開集合の上で微分可能なら同じく通る。)$s=x$ を入れると $g(x)\ge0$ である。$g(x)=0$ なら $f(x)\le f^*$ で $x$ は最小点である。逆に $x$ が最小点なら、凸最適化 の定理「最適性条件」によりすべての $s\in D$ で $\langle s-x,\nabla f(x)\rangle\ge0$ なので $g(x)\le0$、従って $g(x)=0$ である。$\square$

$f^*$ は未知でも $g(x_k)$ は計算できるので、$g(x_k)\le\varepsilon$ を止める条件にすれば、そのとき $f(x_k)-f^*\le\varepsilon$ が保証される。

曲率定数

$f$ の $D$ 上の 曲率定数 を
$$ C_f:=\sup\Bigl\{\frac2{\gamma^2}\bigl(f(y)-f(x)-\langle y-x,\nabla f(x)\rangle\bigr)\Bigm|x,s\in D,\ \gamma\in(0,1],\ y=x+\gamma(s-x)\Bigr\} $$
と定める(Jag13 Sect. 3、式 (3))。

$f$ が 1 次関数なら $C_f=0$ である。凸性から括弧の中は $0$ 以上なので $C_f\ge0$ である。$C_f$ の定義はノルムによらず、$D$ と $f$ を同じ可逆なアフィン変換で写しても変わらない。

曲率定数の評価

$D$ 上で $\lvert\nabla f(x)-\nabla f(y)\rvert\le L\lvert x-y\rvert$ なら、$\operatorname{diam}D:=\max_{x,y\in D}\lvert x-y\rvert$ について $C_f\le L(\operatorname{diam}D)^2$ である。

$x,s\in D$、$y=x+\gamma(s-x)$ とする。線分 $[x,y]$ は $D$ に入るので、勾配降下法 の補題「降下補題」の証明と同じく
$$ f(y)-f(x)-\langle y-x,\nabla f(x)\rangle=\int_0^1\bigl\langle\nabla f(x+t(y-x))-\nabla f(x),\,y-x\bigr\rangle\,dt\le\frac L2\lvert y-x\rvert^2=\frac{L\gamma^2}2\lvert s-x\rvert^2 $$
で、$\frac2{\gamma^2}$ を掛けると $L\lvert s-x\rvert^2\le L(\operatorname{diam}D)^2$ 以下である。$\square$

同じ議論で、任意のノルム $\|\cdot\|$ とその双対ノルム $\|\cdot\|_*$ について $\|\nabla f(x)-\nabla f(y)\|_*\le L\|x-y\|$ なら、$C_f\le L\cdot(\|\cdot\|\text{ での }D\text{ の直径})^2$ となる(Jag13 Sect. 3)。$D$ に合ったノルムを選べば、評価の定数を小さくできる。

収束の速さ

Frank–Wolfe 法の収束率

$C_f<\infty$ とする。固定の規則でも直線探索でも、すべての $k\ge1$ について
$$ f(x_k)-f^*\le\frac{2C_f}{k+2} $$
である(Jag13 Theorem 1 の $\delta=0$ の場合、固定の規則で $C_f$ を $L(\operatorname{diam}D)^2$ に替えた形は Bub15 Theorem 3.8、p. 272)。

1 段の改善を双対ギャップで表す

$h_k:=f(x_k)-f^*$、$g_k:=g(x_k)$、$\bar\gamma_k:=\frac2{k+2}$ とおく。$\gamma\in[0,1]$ について $y=x_k+\gamma(s_k-x_k)$ とすると、$C_f$ の定義($x=x_k$、$s=s_k$)と $g_k=\langle x_k-s_k,\nabla f(x_k)\rangle$ から
$$ f(y)\le f(x_k)+\gamma\langle s_k-x_k,\nabla f(x_k)\rangle+\frac{\gamma^2}2C_f=f(x_k)-\gamma g_k+\frac{\gamma^2}2C_f. $$
固定の規則では $x_{k+1}$ は $\gamma=\bar\gamma_k$ の $y$ そのもので、直線探索では $f(x_{k+1})$ は $\gamma=\bar\gamma_k$ の $f(y)$ 以下である。どちらでも、この不等式から $f^*$ を引き lem-fw-gap の $g_k\ge h_k$ を使うと、次の 1 段の不等式 を得る。
$$ h_{k+1}\le h_k-\bar\gamma_kg_k+\frac{\bar\gamma_k^2}2C_f\le(1-\bar\gamma_k)h_k+\frac{\bar\gamma_k^2}2C_f. $$
$k=0$ では $\bar\gamma_0=1$ なので $h_1\le\frac{C_f}2\le\frac{2C_f}3$ である。$h_k\le\frac{2C_f}{k+2}$($k\ge1$)を仮定すると、1 段の不等式から
$$ h_{k+1}\le\frac k{k+2}\cdot\frac{2C_f}{k+2}+\frac2{(k+2)^2}C_f=\frac{2C_f(k+1)}{(k+2)^2}\le\frac{2C_f}{k+3} $$
である。最後の不等号は $(k+1)(k+3)=(k+2)^2-1$ による。帰納法により主張が従う。$\square$

lem-fw-curvature と合わせると、$\nabla f$ が $L$-Lipschitz なら $f(x_k)-f^*\le\frac{2L(\operatorname{diam}D)^2}{k+2}$ である。評価は次元 $n$ によらず、$D$ への射影を一度も使わない。勾配降下法 の定理「凸の場合の評価」と同じ $O(1/k)$ の速さで、制約つきの問題でも線形の最小化だけで届く。
主定理は誤差 $f(x_k)-f^*$ の評価で、止める条件に使う双対ギャップについては次が言える。

双対ギャップの減少

$C_f<\infty$ とし、固定の規則か直線探索を使う。$K\ge1$ について、ある $k$($K\le k\le2K-1$)で $g(x_k)\le\dfrac{4C_f}K$ である。

prf-fw-rate の 1 段の不等式の最初の不等号の形を $k=K,\dots,2K-1$ について足すと、$h_{2K}\ge0$ から
$$ \Bigl(\min_{K\le k\le2K-1}g_k\Bigr)\sum_{k=K}^{2K-1}\bar\gamma_k\le h_K+\frac{C_f}2\sum_{k=K}^{2K-1}\bar\gamma_k^2. $$
$\sum\bar\gamma_k\ge K\cdot\frac2{2K+1}$、$\sum\bar\gamma_k^2\le K\cdot\frac4{(K+2)^2}$、thm-fw-rate から $h_K\le\frac{2C_f}{K+2}$ なので、
$$ \min g_k\le\Bigl(\frac{2C_f}{K+2}+\frac{2C_fK}{(K+2)^2}\Bigr)\frac{2K+1}{2K}=\frac{C_f(2K+2)(2K+1)}{K(K+2)^2}\le\frac{4C_f}K. $$
最後は $(2K+2)(2K+1)=4K^2+6K+2\le4(K+2)^2$ による。$\square$

Jaggi は同じ方針で、$K\ge2$ 回の反復のうちある $\hat k$ で $g(x_{\hat k})\le\frac{2\beta C_f}{K+2}$($\beta=\frac{27}8$)となることを示している(Jag13 Theorem 2)。

疎な近似解

反復の点の疎性

$D$ が有限集合 $A$ の凸包であるとし、線形の最小化の解 $s_k$ をいつも $A$ からとる(1 次関数の多面体上の最小値は頂点でとられ、頂点は $A$ に属するので可能である)。固定の規則では、$k\ge1$ について $x_k$ は $A$ の高々 $k$ 個の元の凸結合で、$f(x_k)-f^*\le\frac{2C_f}{k+2}$ をみたす。とくに標準単体 $\Delta_n:=\{x\in\mathbb R^n\mid x_i\ge0,\ \sum x_i=1\}$ 上の滑らかな凸関数は、$0$ でない座標が高々 $k$ 個で誤差が $\frac{2C_f}{k+2}$ 以下の点をもつ。

$x_1=s_0$ で、$x_{k+1}$ は $x_k$ と $s_k$ の凸結合なので、帰納法により $x_k$ は $s_0,\dots,s_{k-1}$ の凸結合である。誤差は thm-fw-rate による。$\Delta_n$ は $A=\{e_1,\dots,e_n\}$(標準基底)の凸包である。$\square$

Carathéodoryの定理(凸幾何) によれば $\Delta_n$ のどの点も $n$ 個の頂点の凸結合だが、$k\ll n$ 個で $O(1/k)$ の近似ができるということである。この $O(1/k)$ は改良できない。

疎な点の誤差の下界

$f(x):=\lvert x\rvert^2$ を $\Delta_n$ 上で考える。$C_f=4$、$f^*=\frac1n$ であり、$1\le k\le n$ について、$0$ でない座標が高々 $k$ 個の $x\in\Delta_n$ はすべて $f(x)-f^*\ge\frac1k-\frac1n$ をみたす(Jag13 Lemma 3)。

$f(y)-f(x)-\langle y-x,2x\rangle=\lvert y-x\rvert^2=\gamma^2\lvert s-x\rvert^2$ なので $C_f=2\max_{x,s\in\Delta_n}\lvert s-x\rvert^2$ である。$\lvert s-x\rvert^2$ は各変数について凸なので最大は頂点の組でとられ、$\lvert e_i-e_j\rvert^2=2$ から $C_f=4$。$x$ の台を $T$($\#T\le k$)とすると、Cauchy–Schwarzの不等式 により $1=\sum_{i\in T}x_i\le\sqrt{\#T}\,\lvert x\rvert$、すなわち $\lvert x\rvert^2\ge\frac1{\#T}\ge\frac1k$。$k=n$ の場合から $f^*\ge\frac1n$ で、$x=(\frac1n,\dots,\frac1n)$ で等号が成り立つ。$\square$

$k\le n/2$ なら下界は $\frac1{2k}$ 以上で、cor-fw-sparse の上界 $\frac8{k+2}$ と同じ $1/k$ の大きさである。$k$ 回目の点が $k$ 個の頂点で表される方法は、関数が強凸でも($\lvert x\rvert^2$ は強凸)、次元によらない定数で $1/k$ より速く誤差を減らすことはできない。Jaggi は双対ギャップについても $k< n$ で $\frac2k$ の下界を示している(Jag13 Lemma 4)。

線形の最小化の例

線形の最小化が安く解けることが、この方法を使う理由である。

単体と 1 ノルムの球
  1. $D=\Delta_n$ なら、$i:=\operatorname*{arg\,min}_j\partial_jf(x)$ について $s=e_i$ が解である。1 次関数の多面体上の最小は頂点でとられ、頂点 $e_j$ での値は $\partial_jf(x)$ だからである。手間は勾配の座標の最小を探す $O(n)$ で、標準単体 への射影(並べ替えを含む)より軽い。
  2. $D=\{x\mid\sum_j\lvert x_j\rvert\le\tau\}$ なら、頂点は $\pm\tau e_j$ で、$\langle\pm\tau e_j,\nabla f(x)\rangle=\pm\tau\partial_jf(x)$ なので、$i:=\operatorname*{arg\,max}_j\lvert\partial_jf(x)\rvert$ について $s=-\tau\,\mathrm{sign}(\partial_if(x))\,e_i$ が解である。固定の規則では $k$ 回目の点の $0$ でない座標は高々 $k$ 個で、1 ノルムの制約つきの最小二乗(Lasso 型の問題)の疎な近似解が得られる(Bub15 §3.3、pp. 273–275)。
  3. 行列のトレースノルム(特異値の和)の球の上では、線形の最小化は勾配の行列の最大の特異値に対応する特異ベクトルの組を 1 つ求めることに帰着し、射影に必要な完全な 特異値分解 より軽い(Jag13 Sect. 1)。
区間の上の 2 次関数

$D=[-1,1]$、$f(x)=\frac{x^2}2$、$x_0=1$ とし、固定の規則を使う。$x\ne0$ では $s=-\mathrm{sign}(x)$ である。$x_1=-1$ で、帰納法により
$$ x_{2m}=\frac1{2m+1},\qquad x_{2m+1}=-\frac1{2m+1}\qquad(m\ge0) $$
となる。実際、$x_{2m}=\frac1{2m+1}$ なら $\bar\gamma_{2m}=\frac1{m+1}$ で $x_{2m+1}=\frac m{m+1}\cdot\frac1{2m+1}-\frac1{m+1}=-\frac1{2m+1}$、$x_{2m+1}=-\frac1{2m+1}$ なら $\bar\gamma_{2m+1}=\frac2{2m+3}$ で $x_{2m+2}=-\frac1{2m+3}+\frac2{2m+3}=\frac1{2m+3}$ である。点は最小点 $0$ の両側を往復しながら近づく。$C_f=\max_{x,s}(s-x)^2=4$ で、thm-fw-rate の上界は $\frac8{k+2}$、実際の誤差は $\frac{x_k^2}2\le\frac1{2k^2}$($k\ge1$)である。最小点が $D$ の内部にあるので、反復の点は端点 $\pm1$ の側へ引っ張られ続ける。

反例:微分できない凸関数では収束しない

$D=[0,1]^2$、$f(x,y)=\lvert x-y\rvert-\frac{x+y}4$ とする。$f$ は凸で、$f^*=f(1,1)=-\frac12$ である。$x>y$ では $\nabla f=(\frac34,-\frac54)$ で線形の最小化の解は $(0,1)$ だけ、$x< y$ では $\nabla f=(-\frac54,\frac34)$ で解は $(1,0)$ だけである。$(x_0,y_0)=(1,0)$ から固定の規則で進むと、点はいつも直線 $x+y=1$ の上にあり、$(x_k,y_k)=(\frac12+e_k,\frac12-e_k)$ と書くと $e_k$ は ex-fw-interval の $x_k$ の $\frac12$ 倍になる。$e_k\ne0$ なので $f$ は各反復の点で微分可能で、方法は最後まで定義される。しかし
$$ f(x_k,y_k)=2\lvert e_k\rvert-\frac14\to-\frac14>f^* $$
で、最小値に近づかない。$e_k>0$ のとき $\langle(x_k,y_k)-(0,1),\nabla f\rangle=1+2e_k$ なので、勾配から計算した「双対ギャップ」も $1$ 以上に留まる。$f$ は対角線 $x=y$ で微分できず、対角線の近くの点 $x$ から反対側へ短く進む $y$ をとると $C_f$ の定義の量はいくらでも大きくなるので、$C_f=+\infty$ であり thm-fw-rate の仮定が満たされていない。

主張反例満たされない条件
連続な凸関数なら Frank–Wolfe 法は最小値に収束するex-fw-nonsmooth$f$ が微分可能で $C_f<\infty$
$k$ 個の頂点の凸結合で、強凸な関数の誤差を $1/k$ より速く減らせる$\Delta_n$ 上の $\lvert x\rvert^2$(prop-fw-lower)$k\ge n$($n$ 個の頂点なら誤差を $0$ にできる)
強凸で最小点が $D$ の内部にあれば、固定の規則でも誤差は等比級数的に減るex-fw-interval($\lvert x_k\rvert\ge\frac1{k+1}$)刻み幅が $0$ に近づかないこと(固定の規則では $\bar\gamma_k\to0$)

関連項目

参考文献

[2]
Martin Jaggi, Revisiting Frank-Wolfe: Projection-free sparse convex optimization, Proceedings of the 30th International Conference on Machine Learning, PMLR 28(1) (2013), 427–435, 2013, Sect. 1、Sect. 3(曲率定数の式 (3)、Theorem 1、Theorem 2)、Lemma 3・Lemma 4

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