JavaScriptを有効にしてください

滑らかではない凸最適化とForward-backward envelope

 ·   3 min read

はじめに

Forward-backward envelope (FBE) に関する論文を読んだので、備忘録として残す。
FBEは滑らかではない凸最適化問題に対して、ニュートン法などを適用するための関数である。

滑らかでない(=微分不可能な)凸関数の最小化問題を解く手法として、forward-backward splitting (FBS) や近接勾配法 (proximal gradient method) などがある。
これらの手法は1次の勾配情報を使用するため、大規模な問題では収束が遅くなる。

P. PatrinosやL. Stellaらによって提案されたFBEは、元の最小化問題から得られる微分可能な関数である。
FBEを用いることでニュートン法等を適用でき、q-超1次収束 (superlinear convergence) ないしq-2次収束 (quadratic convergence) に収束性が向上する。

この記事では、まず対象となる問題およびその例としてLasso最適化を示す。
次に、FBEの導入として近接写像 (proximal mapping) とモーロー包 (Moreau envelope) について述べる。
最後に、FBEの定義と特徴をまとめている。

対象となる最小化問題

以下の最小化問題を考える。

$$ \mathrm{minimize} \ F(x) = f(x) + g(x) $$

ここで、$x \in \mathbb{R}^n$であり、$f(x)$は微分可能な凸関数、$g(x)$は微分可能とは限らない凸関数とする。

このような最小化問題の例としてLasso回帰が挙げられる。
Lasso回帰の最小化問題は、

$$ \min_{\bm{w}} \left\{ \sum_{i=1}^{N} (y_i - \bm{w}^\top \bm{x}_i)^2 + C || \bm{w} ||_1 \right\} $$

と記述される。ここで、$N$はデータ点数、$\bm{w}$は係数ベクトル、$C$は正則化の強さに関する重み係数、$|| \cdot ||_1$はL1ノルムである。
この場合、$f(x), g(x)$は以下のようになる。

$$ f(x) = \sum_{i=1}^{N} (y_i - \bm{w}^\top \bm{x}_i)^2 $$
$$ g(x) = C || \bm{w} ||_1 $$

近接写像とモーロー包

まず、近接写像とモーロー包について述べる。

滑らかとは限らない凸関数$g(x)$に対する近接写像は次式で定義される。

$$ \mathrm{prox}_{\gamma g} (x) := \argmin_u \left\{ g(u) + \frac{1}{2 \gamma} || u - x ||^2 \right\} $$

大雑把にいえば、近接写像とは$x$の近傍において、関数$g$を最小化する$u$を求めるものである。ユークリッド距離の2乗の項$|| u - x ||^2$によって、$u$がなるべく$x$の近傍に留まるようにしている。なお、$\gamma$は、近接写像を用いた最適化手法である近接勾配法における、解の更新幅に対応する。

また、次式で定義される$g^\gamma (x)$を、$g(x)$のモーロー包と呼ぶ。

$$ g^\gamma (x) := \min_u \left\{ g(u) + \frac{1}{2 \gamma} || u - x ||^2 \right\} $$

モーロー包は滑らかな凸関数である。

FBEの定義と特徴

最初に示した最小化問題の関数$F(x)=f(x)+g(x)$に対し、FBEは次式の$F_\gamma (x)$で定義される。

$$ F_\gamma (x) := f(x) - \frac{\gamma}{2} || \nabla f(x) ||_2^2 + g^\gamma (x - \gamma \nabla f(x)) $$

また、FBEは以下のようにも記述できる。

$$ \begin{array}{ll} F_\gamma (x) &= \min_{u \in \mathbb{R}^n} \left\{ f(x) + \nabla f(x)^\top (u-x) + g(u) + \frac{1}{2\gamma} ||u-x||^2 \right\} \\ &= f(x) +g(P_\gamma (x)) - \gamma \nabla f(x)^\top G_\gamma (x) + \frac{\gamma}{2} ||G_\gamma (x)||^2 \end{array} $$

ただし、

$$ P_\gamma (x) := \mathrm{prox}_{\gamma g} (x - \gamma \nabla f(x)) $$ $$ G_\gamma (x) := \gamma^{-1} (x - P_\gamma (x)) $$

である。

FBEである$F_\gamma$について以下の性質が成り立つ。

  • $F_\gamma$は連続微分可能であり、勾配は次式となる。

$$ \nabla F_\gamma (x) = (I - \gamma \nabla^2 f(x)) G_\gamma (x) $$

  • $\gamma \in (0, 1/L_f)$のとき、$F$の最適解と$F_\gamma$の最適解は一致し、そのときの目的関数の値も一致する。すなわち、以下が成り立つ(画像参照)。

$$ \argmin F = \argmin F_\gamma, \ \min F = \min F_\gamma$$

forward-backward-envelope

参考

FBEの論文。

近接写像に関して、以下の記事・書籍を参考にさせていただいた。

シェアする

Helve
WRITTEN BY
Helve
関西在住、電機メーカ勤務のエンジニア。Twitterで新着記事を配信中です