📂最適化理論

FISTA: 高速反復ソフトしきい値アルゴリズム

アルゴリズム ¹

$$ \argmin_{\beta} \left( {{ 1 } \over { 2 }} \left\| Y - X \beta \right\|_{2}^{2} + \lambda \left\| \beta \right\|_{1} \right) $$

上のような BPDN、またはラッソ回帰問題 を解く方法として、次の更新則を FISTA^{Fast Iterative Soft Thresholding Algorithm} と呼ぶ。 $$ \begin{align*} \gamma^{(k)} =& S_{\lambda} \left( \beta^{(k)} - \alpha X^{T} \left( X \beta^{(k)} - Y \right) \right) \\ t_{k+1} =& {{ 1 + \sqrt{ 1 + 4 t_{k}^{2} }} \over { 2 }} \\ \beta^{(k+1)} =& \gamma^{(k)} + \left( {{ t_{k} - 1 } \over { t_{k+1} }} \right) \left( \gamma^{(k)} - \gamma^{(k-1)} \right) \end{align*} $$ ここで $\alpha$ はステップサイズ^{step size}で、ベクトル化された^vectorizedソフトしきい値化 $S_{\lambda} : \mathbb{R}^{n} \to \mathbb{R}^{n}$ はベクトルの各成分ごとに ソフトしきい値化 $\eta_{S} \left( x ; \lambda \right)$ を適用する関数だ。初期値としては $\gamma^{(1)} = \beta^{(0)}$ と $t_{1} = 1$ を使える。

説明

FISTAは プラクシマル・グラディエントメソッド の一種で、モーメンタム手法 を通じて ISTA を発展させたアルゴリズムだ。$\left( \gamma^{(k)} - \gamma^{(k-1)} \right)$ は見たまま慣性の方向を計算して勾配降下を加速する役割を果たす。

性能面では FISTA は ISTA よりはるかに優れており、実装もそれほど複雑ではないためラッソ問題を解く際によく使われる。FISTA を紹介した論文は 2025 年時点で引用回数が 15000 回を超えている。