数値最適化の収束率と加速法

Convergence rates, acceleration, and the Nemirovski-Yudin lower bound

このページの目標

勾配法・ニュートン法といった基本アルゴリズムの収束率を、関数の滑らかさ ($L$) と強凸性 ($\mu$) を用いて定量的に評価する。さらに Nesterov の加速勾配法が $O(1/k^2)$ を達成し、これが 1 階法の最適収束率であることを Nemirovski-Yudin の下界から理解する。非滑らかな合成問題（近接勾配法・FISTA）への橋渡しも示す。

前提知識

§1. 収束率と最適性の視点

最急降下法・ニュートン法・準ニュートン法は、最適解へ向けて反復点を「動かす」アルゴリズムである。本章では、これらが「どれだけ速く」最適解に近づくかを定量的に評価し、さらに「もっと速くできるか」を問う。鍵は次の二つの問題意識である:

  1. 収束率の解析: 関数の滑らかさと曲がり方をどう数値化し、それが反復回数とどう結びつくか
  2. 最適性: 与えられたクラスの関数に対して、1 階情報 (勾配) だけ使う方法で達成可能な最速の収束率はいくらか

後者の答えは驚くべきもので、素朴な勾配法は最適ではなく、Nesterov 加速法が漸近的に最適となる。1983 年の Nesterov の論文以降、これが多くの応用分野で標準となった。

§2. 滑らかさ・強凸性・条件数

定義 2.1 ($L$-滑らか性)

微分可能な凸関数 $f: \mathbb{R}^n \to \mathbb{R}$ が $L$-滑らか ($L$-smooth) であるとは、勾配 $\nabla f$ が $L$-Lipschitz 連続であること、すなわち任意の $x, y$ について

$$\|\nabla f(x) - \nabla f(y)\| \le L\,\|x - y\|.$$

$f \in C^2$ ならば、これは Hessian の最大固有値が常に $L$ 以下である ($\nabla^2 f(x) \preceq L I$) ことと同値である。

定義 2.2 ($\mu$-強凸性)

$f$ が $\mu$-強凸 ($\mu$-strongly convex, $\mu > 0$) であるとは、任意の $x, y$ について

$$f(y) \ge f(x) + \langle \nabla f(x), y - x\rangle + \dfrac{\mu}{2}\|y - x\|^2.$$

$f \in C^2$ ならば $\nabla^2 f(x) \succeq \mu I$ と同値。直観的には「どこでも 2 次関数 $\dfrac{\mu}{2}\|x\|^2$ 以上に曲がる」性質。

定義 2.3 (条件数)

$f$ が $L$-滑らかかつ $\mu$-強凸ならば、条件数を

$$\kappa := \dfrac{L}{\mu} \ge 1$$

で定義する。$\kappa = 1$ は 2 次関数 $\dfrac{\mu}{2}\|x\|^2$ のような「完全に球対称」な場合、$\kappa \gg 1$ は「細長い谷」を持つ場合に対応する。条件数が大きいほど最適化は難しい。

例 2.1 (2 次関数)

$f(x) = \dfrac{1}{2} x^\top A x$ ($A \succ 0$) のとき、$L = \lambda_{\max}(A)$, $\mu = \lambda_{\min}(A)$, $\kappa = \lambda_{\max}/\lambda_{\min} = \mathrm{cond}(A)$。線形代数の条件数と一致する。

§3. 1 階法の収束率

3.1 滑らかな凸関数: 勾配法は $O(1/k)$

$f$ が $L$-滑らかな凸関数 (強凸でない) のとき、ステップサイズ $\eta = 1/L$ の勾配法

$$x_{k+1} = x_k - \dfrac{1}{L} \nabla f(x_k)$$

に対し、関数値ギャップは次を満たす:

定理 3.1 (滑らかな凸の勾配法)

$$f(x_k) - f(x^*) \le \dfrac{L\,\|x_0 - x^*\|^2}{2k}$$

すなわち $O(1/k)$ 収束。$\varepsilon$-最適解を得るには $k \sim L \|x_0 - x^*\|^2 / \varepsilon$ 反復必要。

3.2 強凸の場合: 線形収束 $O((1 - 1/\kappa)^k)$

$f$ が加えて $\mu$-強凸ならば、同じステップサイズで線形収束:

定理 3.2 (強凸の勾配法)

$$\|x_k - x^*\|^2 \le \left(1 - \dfrac{1}{\kappa}\right)^k \|x_0 - x^*\|^2$$

$\varepsilon$-最適解には $k \sim \kappa \log(1/\varepsilon)$ 反復。条件数 $\kappa$ に比例する反復数がボトルネック。

これが古典的勾配法の限界である。次節でこれを改善する加速法を扱う。

§4. Nesterov 加速勾配法

4.1 動機: 重ボール法

Polyak (1964) は重ボール法 (Heavy-ball method) を導入した:

$$x_{k+1} = x_k - \eta \nabla f(x_k) + \beta (x_k - x_{k-1})$$

第 2 項が「慣性 (momentum)」を表す。2 次関数では $\eta, \beta$ を適切に選ぶと条件数 $\kappa$ に対する反復数を $\sqrt{\kappa}$ に改善できるが、一般の強凸関数では大域収束が保証されないという欠点があった。

4.2 Nesterov の加速勾配法 (NAG)

Nesterov (1983) は重ボール法を変形し、勾配を $x_k$ ではなく予測点 $y_k$ で評価する方式を提案した。$L$-滑らかな凸関数に対して:

アルゴリズム 4.1 (Nesterov 加速勾配法, 凸の場合)

初期化: $x_0 = y_0$、$t_0 = 1$。反復 $k = 0, 1, \ldots$:

  1. $x_{k+1} = y_k - \dfrac{1}{L} \nabla f(y_k)$ (勾配ステップ)
  2. $t_{k+1} = \dfrac{1 + \sqrt{1 + 4 t_k^2}}{2}$
  3. $y_{k+1} = x_{k+1} + \dfrac{t_k - 1}{t_{k+1}} (x_{k+1} - x_k)$ (外挿)

定理 4.1 (NAG の収束率, 凸の場合)

$$f(x_k) - f(x^*) \le \dfrac{2 L\,\|x_0 - x^*\|^2}{(k+1)^2}$$

すなわち $O(1/k^2)$。勾配法の $O(1/k)$ より 1 オーダー速い。

4.3 強凸の場合の加速

$f$ が $L$-滑らかかつ $\mu$-強凸ならば、外挿係数を $\beta = (\sqrt{\kappa}-1)/(\sqrt{\kappa}+1)$ と固定する加速法は:

定理 4.2 (NAG の収束率, 強凸の場合)

$$f(x_k) - f(x^*) \le L\,\|x_0 - x^*\|^2 \left(1 - \dfrac{1}{\sqrt{\kappa}}\right)^k$$

$\varepsilon$-最適解には $k \sim \sqrt{\kappa} \log(1/\varepsilon)$ 反復。古典勾配法の $\kappa \log(1/\varepsilon)$ に比べ、条件数の平方根に依存する点が決定的。

§5. 2 階法の収束率 — Newton と準ニュートン

5.1 Newton 法の局所 Q-2次収束

$f \in C^2$ で Hessian が解の近傍で Lipschitz 連続かつ正則ならば、Newton 反復 $x_{k+1} = x_k - [\nabla^2 f(x_k)]^{-1} \nabla f(x_k)$ は十分良い初期点から

$$\|x_{k+1} - x^*\| \le C\,\|x_k - x^*\|^2$$

を満たす (Q-2次収束)。実用上は 5-10 反復で機械精度に到達する。

局所収束の裏側 — 大域化と計算コスト

Newton 法の収束率は局所的には最強だが、それは解の近くから始めた場合に限られ、遠い初期点からは発散することもある。そのため実用では、信頼領域法・直線探索付き Newton 法・三次正則化 (cubic regularization) などで大域化して用いる。

また 1 反復のコストは、Hessian を含む線形方程式を解くために $O(n^3)$ と重い。そこで大規模問題では、Hessian を陽に構成しない Hessian-free Newton (CG ベース) が用いられる。

5.2 BFGS の超線形収束

BFGS 等の準ニュートン法は Hessian を直接計算せず勾配履歴から低ランク更新で近似する。$L$-滑らかかつ $\mu$-強凸で初期 Hessian 近似が良ければ、解の近傍で

$$\lim_{k \to \infty} \dfrac{\|x_{k+1} - x^*\|}{\|x_k - x^*\|} = 0$$

すなわち Q-超線形収束を持つ (Q-2次より弱いが線形より強い)。1 反復のコストが $O(n^2)$ で、Newton 法より軽い。L-BFGS では $O(mn)$ ($m$ は記憶ステップ数) でさらに軽い。

§6. 最適収束率の下界 — Nemirovski-Yudin

1 階法はどこまで速くなれるのか? 1983 年に Nemirovski と Yudin は厳密な下界を与えた:

定理 6.1 (Nemirovski-Yudin の下界, 凸の場合)

任意の 1 階法 (各反復で勾配だけを使い、$x_k$ は $\{x_0, \nabla f(x_0), \ldots, \nabla f(x_{k-1})\}$ の張る部分空間に属する) に対し、ある $L$-滑らかな凸関数 $f$ と初期点 $x_0$ が存在して

$$f(x_k) - f(x^*) \ge \dfrac{3 L\,\|x_0 - x^*\|^2}{32(k+1)^2}$$

すなわち $\Omega(1/k^2)$ の下界が成り立つ。次元 $n \ge 2k$ で達成可能。

定理 4.1 (NAG の $O(1/k^2)$) と定理 6.1 (下界 $\Omega(1/k^2)$) を併せると:

結論: Nesterov 加速法は (定数倍を除き) 最適

滑らかな凸関数のクラスにおいて、1 階法で達成可能な最速の収束率は $\Theta(1/k^2)$ であり、Nesterov 加速勾配法はこれを (定数倍を除き) 達成する。

下界は「1 階法」に対するもの

この下界は勾配だけを使う 1 階法に対する主張であり、Hessian など 2 階情報を使う Newton 法（§5）には適用されない。Newton 法が局所的に $O(1/k^2)$ よりはるかに速い Q-2次収束を示すのは、この下界の枠外だからである。

収束率の比較：勾配法 O(1/k)、Nesterov 加速法 O(1/k²)、Nemirovski-Yudin 下界 Ω(1/k²) 大 小 k 反復回数（対数） 誤差 f(x_k) − f(x*)（対数） 赤破線（下界）より下は達成不可能。 加速法はその境界に張り付く＝最適。 勾配法 O(1/k) Nesterov 加速法 O(1/k²) 下界 Ω(1/k²)
図1. 収束率の比較（両対数）。古典的勾配法は傾き $-1$（$O(1/k)$）、Nesterov 加速法は傾き $-2$（$O(1/k^2)$）で、加速法のほうが急に誤差が減る。赤破線の Nemirovski-Yudin 下界 $\Omega(1/k^2)$ は 1 階法が到達できる誤差の限界（床）を表し、その線より下（＝より速い収束）は達成できない。加速法の線はこの床のすぐ上に張り付くため、1 階法として漸近的に最適である。縦軸の誤差 $f(x_k)-f(x^*)$ が小さいほど、少ない反復で高精度に到達する。

強凸の場合も同様に、下界は $\Omega((1 - 1/\sqrt{\kappa})^k)$ であり、Nesterov 加速法の強凸版がこの収束率を達成する。

§7. 非滑らかな拡張への橋渡し

目的関数が滑らかな項と非滑らかな項の和 $F(x)=f(x)+g(x)$（$f$ は $L$-滑らかな凸関数、$g$ は $\|x\|_1$ や指示関数などの非滑らかな凸関数）になる合成問題では、$g$ が微分できないため勾配法をそのまま使えない。しかし $g$ の近接写像を通せば、本章の加速の考え方はそのまま生きる。$f$ の勾配ステップと $g$ の近接写像を交互に適用する近接勾配法（ISTA）は $O(1/k)$、それに §4 と同じ外挿を加えた FISTA は $O(1/k^2)$ を達成する——非滑らかでも滑らかな場合と同じ最適オーダーである。

前進後退分割によるアルゴリズムの導出、収束の証明、backtracking・restart などの実装、Lasso・全変動・圧縮センシングへの応用は、独立記事 近接勾配法とFISTA にまとめた。近接写像そのものの定義・性質・閉形式は 近接作用素 を参照。

まとめ

本章のポイント

  • 関数の性質は $L$-滑らかさと $\mu$-強凸性で測り、比 $\kappa = L/\mu$ が条件数
  • 古典勾配法: 滑らかな凸で $O(1/k)$、強凸で $O((1 - 1/\kappa)^k)$
  • Nesterov 加速勾配法 (NAG): 凸で $O(1/k^2)$、強凸で $O((1 - 1/\sqrt{\kappa})^k)$
  • Nemirovski-Yudin の下界により、NAG は 1 階法の漸近最適
  • Newton 法は局所 Q-2次、BFGS は局所 Q-超線形
  • 非滑らかな合成問題への拡張（近接勾配法 ISTA・加速版 FISTA）と、restart・backtracking などの実装は 近接勾配法とFISTA にまとめた

これらの収束率の解析は、続く章 (確率的最適化、変分問題、リーマン多様体上の最適化など) でも基本道具となる。

参考文献

  • Nesterov, Y. (1983). "A method of solving a convex programming problem with convergence rate $O(1/k^2)$". Soviet Math. Dokl. 27 (2): 372-376.
  • Nesterov, Y. (2004). Introductory Lectures on Convex Optimization: A Basic Course. Kluwer.
  • Beck, A., Teboulle, M. (2009). "A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems". SIAM J. Imaging Sciences 2 (1): 183-202.
  • Nemirovski, A. S., Yudin, D. B. (1983). Problem Complexity and Method Efficiency in Optimization. Wiley.
  • Bubeck, S. (2015). "Convex Optimization: Algorithms and Complexity". Foundations and Trends in Machine Learning 8 (3-4): 231-357. arXiv:1405.4980

よくある質問

Nesterov 加速法が通常の勾配法より速い理由は？

外挿項によって過去の運動方向を再利用できるため。条件数 $\kappa$ への依存が $\kappa \to \sqrt{\kappa}$ に改善され、特に $\kappa$ が大きい (谷が細長い) ときに劇的な高速化となる。Nemirovski-Yudin の下界により、これは 1 階法では最適。

2 次関数の条件数とは何か？

$f(x) = \dfrac{1}{2}x^\top A x$ ($A \succ 0$) では、$\kappa = \lambda_{\max}(A)/\lambda_{\min}(A) = \mathrm{cond}(A)$ で、線形代数の条件数と一致する。Hessian の固有値の比が幾何的には「等高線の細長さ」を表す。

FISTA は何に使うか？

Lasso、画像復元、圧縮センシングなど、非滑らかな正則化付きの最小化を解くのに使う。目的関数が $f(x) + g(x)$（$f$ は滑らかな凸関数、$g$ は近接写像を計算できる非滑らかな凸関数）の形のとき、$O(1/k^2)$ の速さで収束する標準手法である。

Newton 法と BFGS の使い分けは？

Newton 法は局所 Q-2次収束で最強だが 1 反復の Hessian 計算 $O(n^3)$ が高い。中〜大規模では BFGS (局所 Q-超線形, $O(n^2)$) や L-BFGS ($O(mn)$, $m$ は記憶ステップ数) が選ばれる。$n \gtrsim 10^3$ では L-BFGS、$n \gtrsim 10^6$ では確率的 + 加速・分散最適化が現実的。