近接勾配法とFISTA
Proximal Gradient Method (ISTA) and its acceleration (FISTA)
このページの目標
目的関数が滑らかな項と非滑らかな項の和 $F(x)=f(x)+g(x)$ で書かれる合成最小化を、勾配法を破綻させずに解く近接勾配法（ISTA）と、その加速版 FISTA を導く。劣微分による最適性条件から前進後退分割として自然に導出し、収束率（ISTA は $O(1/k)$、FISTA は $O(1/k^2)$）と実装上の工夫、Lasso・全変動・圧縮センシングなどの応用までを一つの記事にまとめる。
前提知識
- 近接作用素 — 近接写像 $\operatorname{prox}_{\lambda g}$ の定義・性質・閉形式（本記事の中心的な道具）
- 数値最適化の収束率と加速法 — 滑らかな場合の勾配法・Nesterov 加速法と収束率の枠組み
- 凸解析の基礎（劣微分 $\partial g$、$L$-滑らかさ、$\mu$-強凸性）
§1. 合成最小化という舞台
現代の最適化では、目的関数が性質の異なる二つの項の和で書かれる場面が非常に多い:
$$\min_{x\in\mathbb{R}^n}\; F(x) = f(x) + g(x).$$ここで $f$ は滑らかな凸関数（微分可能で勾配が $L$-Lipschitz 連続、例：二乗誤差 $\tfrac12\|Ax-b\|^2$）、$g$ は非滑らかな凸関数（微分できない点を持つが凸、例：$\ell_1$ ノルム $\|x\|_1$、凸集合の指示関数 $\iota_C$）である。
$g$ が入るのには理由がある。$\ell_1$ 正則化は解をスパースにし（Lasso）、全変動（TV）は画像のエッジを保ち、指示関数は制約を表す。いずれも「望ましい構造を強制する」働きを持つが、その代償として微分できない角を生む。
なぜ勾配法をそのまま使えないか
$g$ が微分できない以上、$\nabla F = \nabla f + \nabla g$ が定義できず、勾配降下法 $x_{k+1}=x_k-\eta\nabla F(x_k)$ が書けない。劣勾配法（$\nabla g$ を劣勾配で置き換える）は使えるが、非滑らかさのため収束が $O(1/\sqrt{k})$ と遅い。$g$ の構造を丸ごと扱う別の道具が要る——それが近接写像である。
§2. 最適性条件と前進後退分割
$F=f+g$ の最小化点 $x^\star$ は、劣微分を用いた最適性条件
$$0 \in \nabla f(x^\star) + \partial g(x^\star)$$を満たす（$f$ は滑らかなので勾配、$g$ は非滑らかなので劣微分）。この包含関係を、任意のステップ幅 $\eta>0$ を挟んで書き換えると
$$0 \in \eta\nabla f(x^\star) + \eta\,\partial g(x^\star) \;\Longleftrightarrow\; x^\star - \eta\nabla f(x^\star) \in x^\star + \eta\,\partial g(x^\star) = (I+\eta\partial g)(x^\star).$$両辺にレゾルベント $(I+\eta\partial g)^{-1}=\operatorname{prox}_{\eta g}$（＝近接写像。近接作用素 §5 参照）を作用させると、$x^\star$ は次の不動点方程式を満たす:
定理 2.1（合成最適性の不動点表現）
真閉凸関数 $g$ と $\eta>0$ に対し、$x^\star$ が $F=f+g$ の最小化点であることは、次と同値である:
$$x^\star = \operatorname{prox}_{\eta g}\!\bigl(x^\star - \eta\nabla f(x^\star)\bigr).$$右辺は二段構えになっている。$x-\eta\nabla f(x)$ は $f$ に沿った前進（陽的）勾配ステップ、$\operatorname{prox}_{\eta g}$ は $g$ に沿った後退（陰的）ステップである。この分解を前進後退分割（forward-backward splitting）と呼ぶ。最適性条件がそのまま「前進してから後退する」写像の不動点になっている点が本質で、この写像を反復すれば最小化点に近づく——それが次節の近接勾配法である。
§3. 近接勾配法（ISTA）
定理 2.1 の不動点写像をそのまま反復に用いる:
アルゴリズム 3.1（近接勾配法 / ISTA）
初期点 $x_0$、ステップ幅 $\eta=1/L$（$L$ は $\nabla f$ の Lipschitz 定数）。$k=0,1,2,\ldots$ に対して
$$x_{k+1} = \operatorname{prox}_{\eta g}\!\bigl(x_k - \eta\nabla f(x_k)\bigr).$$各反復は「$f$ の勾配で一歩進み、$g$ の近接写像で引き戻す」だけである。$g$ の近接写像が閉形式（例：$\ell_1$ なら軟しきい値）で計算できれば、1 反復のコストは勾配法とほぼ同じ（$\nabla f$ の評価が支配的）になる。$g=\|\cdot\|_1$ の場合、この反復は縮小としきい値処理を繰り返すことから ISTA（Iterative Shrinkage-Thresholding Algorithm）と呼ばれる。
定理 3.2（ISTA の収束）
$f$ が $L$-滑らかな凸関数、$g$ が真閉凸関数、$\eta=1/L$ のとき、関数値ギャップは
$$F(x_k) - F(x^\star) \le \dfrac{L\,\|x_0 - x^\star\|^2}{2k}$$を満たす。すなわち $O(1/k)$ 収束で、滑らかな凸関数に対する勾配法と同じオーダーである。$f$ が加えて $\mu$-強凸なら線形収束 $O\bigl((1-\mu/L)^k\bigr)$ になる。
Moreau 包絡線から見た近接ステップ
近接写像は $g$ を滑らかに丸めた Moreau 包絡線 $M_{\eta g}$ の勾配ステップと等価であった（近接作用素 §8）。したがって ISTA は「$f$ の勾配ステップ＋$g$ の（実質的な）勾配ステップ」とも読め、非滑らかな $g$ を滑らかな最小化の枠組みへ引き込んでいる。これが $O(1/k)$ という滑らかな場合と同じ速さの理由である。
§4. 加速——FISTA
滑らかな場合、Nesterov 加速勾配法（NAG）は外挿（慣性）項の導入だけで $O(1/k)$ を $O(1/k^2)$ に改善した（収束率と加速法 §4）。同じ外挿アイデアを近接勾配法へ移植したのが FISTA（Fast ISTA, Beck & Teboulle 2009）である。
アルゴリズム 4.1（FISTA）
初期化: $x_0$、$y_1=x_0$、$t_1=1$。$k=1,2,\ldots$ に対して
- $x_k = \operatorname{prox}_{(1/L)g}\!\bigl(y_k - \tfrac{1}{L}\nabla f(y_k)\bigr)$ （予測点 $y_k$ で前進後退ステップ）
- $t_{k+1} = \dfrac{1+\sqrt{1+4t_k^2}}{2}$
- $y_{k+1} = x_k + \dfrac{t_k-1}{t_{k+1}}\,(x_k - x_{k-1})$ （外挿＝慣性）
ISTA との違いは、勾配・近接ステップを現在点 $x_k$ ではなく前ステップとの差分で外挿した予測点 $y_k$ で評価する点だけである。この一手間で収束が一段速くなる:
定理 4.2（FISTA の収束）
$$F(x_k) - F(x^\star) \le \dfrac{2L\,\|x_0 - x^\star\|^2}{(k+1)^2}$$すなわち $O(1/k^2)$。滑らかな場合の NAG と同じオーダーであり、$\varepsilon$-最適解に要する反復数は ISTA の $O(1/\varepsilon)$ から $O(1/\sqrt{\varepsilon})$ へ改善される。
単調性の注意
FISTA は外挿のため関数値 $F(x_k)$ が単調に減るとは限らない（振動しうる）。実用では単調版（MFISTA）や次節の restart で単調性を回復させることが多い。
ISTA と FISTA を一目で対比すると次のようになる。
| ISTA | FISTA | |
|---|---|---|
| 収束率（凸 $F$） | $O(1/k)$ | $\mathbf{O(1/k^2)}$ |
| 1 反復のコスト | $\nabla f$ 1 回＋$\operatorname{prox}$ 1 回 | 同じ（$\nabla f$ 1 回＋$\operatorname{prox}$ 1 回） |
| 外挿（慣性） | なし | あり（予測点 $y_k$ で評価） |
| 関数値の単調性 | 単調に減少 | 非単調（振動しうる）→ restart で回復 |
| $\varepsilon$-最適解までの反復数 | $O(1/\varepsilon)$ | $O(1/\sqrt{\varepsilon})$ |
§5. 収束率の位置づけ
合成問題の 1 階法の速さを、滑らかな場合（収束率と加速法）と対応させて整理する。
| 手法 | 凸 $F$ | 強凸 $F$ | 備考 |
|---|---|---|---|
| 劣勾配法 | $O(1/\sqrt{k})$ | $O(1/k)$ | $g$ の構造を使わない |
| 近接勾配法（ISTA） | $O(1/k)$ | $O((1-\mu/L)^k)$ | 滑らかな勾配法と同じ |
| FISTA | $\mathbf{O(1/k^2)}$ | $O((1-\sqrt{\mu/L})^k)$ | Nesterov 加速と同じ最適オーダー |
重要なのは、非滑らかさは収束の速さを損なわないという事実である。近接写像で $g$ を丸ごと扱えるため、ISTA は滑らかな勾配法と同じ $O(1/k)$、FISTA は Nesterov と同じ $O(1/k^2)$ を達成する。$O(1/k^2)$ は Nemirovski-Yudin の下界に照らして 1 階法の漸近最適であり（収束率と加速法 §6）、FISTA はその最適オーダーを非滑らかな合成問題へそのまま持ち込む。
§6. 実装上の工夫
6.1 ステップ幅の自動調整（backtracking）
Lipschitz 定数 $L$ が未知、または大域的な $L$ が過大なとき、各反復で局所的な $L$ を探索する。試行値 $\hat L$ を倍々に増やしながら、次の下降補題が満たされるまで縮小ステップをやり直す:
$$F(x_{k+1}) \le f(y_k) + \langle \nabla f(y_k),\, x_{k+1}-y_k\rangle + \tfrac{\hat L}{2}\|x_{k+1}-y_k\|^2 + g(x_{k+1}).$$これにより事前に $L$ を知らなくても $O(1/k^2)$ が保たれる（Beck & Teboulle 2009 の backtracking 版）。
6.2 リスタート（restart）
FISTA の非単調な振動を抑えるには、外挿係数を $t_k\leftarrow 1$ に戻すリスタートが有効である。判定は軽い方が良い:
- 関数値リスタート: $F(x_{k+1})>F(x_k)$ になったら restart
- 勾配リスタート: $\langle y_k-x_{k+1},\,x_{k+1}-x_k\rangle>0$ なら restart（関数値の再評価が要らず軽い）
強凸性が未知でも、リスタート付き FISTA は実用上ほぼ線形収束の速さを示すことが多い。
6.3 近接写像が閉形式で解けないとき（inexact prox）
$g$ の近接写像が解析的に求まらない場合（例：重なりのあるグループ正則化、TV）、内部で小さな最適化を解いて近接写像を近似する。近似誤差が反復とともに十分速く $0$ へ減れば、外側の $O(1/k^2)$ は保たれる（inexact proximal gradient）。$\nabla f$ が確率的にしか得られない大規模学習では、確率的近接勾配法（prox-SGD）が用いられる。
§7. 代表的な応用と近接写像
近接勾配法が実用的なのは、代表的な正則化 $g$ の近接写像が閉形式で書けるからである（導出・一覧は 近接作用素 §7）。
| 問題 | 非滑らか項 $g$ | $\operatorname{prox}_{\eta g}$ |
|---|---|---|
| Lasso 回帰 | $\lambda\|x\|_1$ | 軟しきい値 $S_{\eta\lambda}(v)$ |
| グループ Lasso | $\lambda\sum_g\|x_g\|_2$ | 群軟しきい値（ブロックごと） |
| 非負制約付き回帰 | $\iota_{\{x\ge 0\}}(x)$ | $\max(v,0)$（成分ごとの射影） |
| 箱制約 | $\iota_{[l,u]}(x)$ | $\operatorname{clip}(v,l,u)$ |
| 全変動（TV）画像復元 | $\lambda\,\mathrm{TV}(x)$ | 閉形式なし → inexact prox（§6.3） |
例 7.1（Lasso と ISTA/FISTA）
Lasso は $f(x)=\tfrac12\|Ax-b\|^2$（$L=\lambda_{\max}(A^\top A)$）、$g(x)=\lambda\|x\|_1$。ISTA の 1 反復は
$$x_{k+1} = S_{\eta\lambda}\!\bigl(x_k - \eta A^\top(Ax_k-b)\bigr),$$すなわち「残差の勾配で一歩進み、軟しきい値で小さな成分を $0$ に潰す」。これを FISTA の外挿で加速したものが、圧縮センシング・スパース回帰で広く使われる標準アルゴリズムである。
まとめ
本章のポイント
- 合成最小化 $F=f+g$（$f$ 滑らか凸、$g$ 非滑らか凸）は、勾配法をそのまま使えない
- 最適性条件 $0\in\nabla f+\partial g$ は、前進後退写像 $\operatorname{prox}_{\eta g}(x-\eta\nabla f(x))$ の不動点と同値
- この写像を反復するのが近接勾配法（ISTA）で、$O(1/k)$ 収束（滑らかな勾配法と同じ）
- Nesterov の外挿を加えた FISTA は $O(1/k^2)$ で、1 階法の最適オーダー
- 非滑らかさは速さを損なわない——近接写像が $g$ を丸ごと扱うため
- 実装は backtracking・restart・inexact prox が要点
- Lasso・グループ Lasso・TV・制約付き問題など、近接写像が計算できる限り大規模に適用可能
参考文献
- Beck, A., & Teboulle, M. (2009). "A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems". SIAM J. Imaging Sciences, 2(1), 183–202.
- Parikh, N., & Boyd, S. (2014). Proximal Algorithms. Foundations and Trends in Optimization, 1(3), 127–239. Online
- Combettes, P. L., & Wajs, V. R. (2005). "Signal Recovery by Proximal Forward-Backward Splitting". Multiscale Modeling & Simulation, 4(4), 1168–1200.
- Nesterov, Y. (2013). "Gradient methods for minimizing composite functions". Mathematical Programming, 140(1), 125–161.
- Beck, A. (2017). First-Order Methods in Optimization. SIAM.
よくある質問
Q1. 近接勾配法（ISTA）とは何か
目的関数が滑らかな凸関数 $f$ と非滑らかな凸関数 $g$ の和 $F=f+g$ で書かれる合成最小化を解く反復法である。1 反復は $x_{k+1}=\operatorname{prox}_{\eta g}(x_k-\eta\nabla f(x_k))$ で、$f$ には前進（勾配）ステップ、$g$ には後退（近接写像）ステップを適用する（前進後退分割）。$\eta=1/L$ で $O(1/k)$ 収束する。$g=\|\cdot\|_1$ の場合を特に ISTA と呼ぶ。
Q2. FISTA が近接勾配法より速いのはなぜか
FISTA は ISTA に Nesterov の外挿（慣性）項を加えた加速版である。勾配・近接ステップを現在点ではなく予測点 $y_k$ で評価することで、収束率を $O(1/k)$ から $O(1/k^2)$ へ一段改善する。これは滑らかな場合の Nesterov 加速勾配法と同じ最適オーダーで、1 反復あたりの計算量は ISTA とほぼ同じである。
Q3. 近接勾配法はどんな問題に使うか
非滑らかな正則化や制約を含む合成最小化に使う。代表例は Lasso（$\ell_1$ 正則化、近接写像は軟しきい値）、グループ Lasso（群軟しきい値）、全変動による画像復元、圧縮センシング、凸集合への射影で表せる制約付き問題である。近接写像が閉形式または安価に計算できる限り、勾配法と同等のコストで大規模問題にも適用できる。