※記事内に商品プロモーションを含むことがあります。
はじめに
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$$
参考
FBEの論文。
- Forward-backward truncated Newton methods for convex composite optimization (arXiv)
- Forward-backward quasi-Newton methods for nonsmooth optimization problems (arXiv)
近接写像に関して、以下の記事・書籍を参考にさせていただいた。
