第5章勾配法（最適化） | Lemma — 数学ロードマップ

この章の目標

最急降下法とアルミホ条件による直線探索を定式化し、直線探索が有限回で終わることを証明できる

降下補題から、 $L$ -平滑な凸関数での $O(1/k)$ の収束と強凸関数での線形収束を証明し、どの量がどの速さで収束するかを正確に述べられる

二次関数で条件数が収束を遅くするしくみを計算で示し、スケーリングの重要性を説明できる

ネステロフの加速勾配法の $O(1/k^2)$ の評価を、1 次の方法の下界と比べて説明できる

共役勾配法が二次関数を $n$ 回以内の反復で最小化することを説明できる

射影勾配法・近接勾配法で制約や $\lVert x \rVert_1$ を含む問題を解き、ソフト閾値関数が近接写像であることを証明できる

前提：第2章、02-linear-algebra 第8章（正定値性・固有値）。最適性条件は第1章で扱った。ラッソの統計的な意味は 24 機械学習の数理第2章にある。

100 万個の特徴量をもつロジスティック回帰のように、実務の最適化問題の多くは変数が非常に多い。第6章のニュートン法は $n \times n$ のヘッセ行列を使うので $n = 10^6$ では現実的でなく、勾配 $\nabla f(x)$ だけを使う1 次の方法 (first-order method) が主役になる。本章では、その速さが第2章の $L$ -平滑性と強凸性（定義 2.21）から導かれ、条件数 $\kappa = L/\mu$ に支配されることを示す。後半では、より速い加速法と共役勾配法、制約や微分できない項 $\lambda\lVert x \rVert_1$ を扱う射影勾配法・近接勾配法を学ぶ。

$f\colon \mathbb{R}^n \to \mathbb{R}$ は微分可能とし、最小点 $x^{\ast}$ があるとき $p^{\ast} = f(x^{\ast})$ と書く。 $0$ に収束する数列 $e_k \geq 0$ について、ある $0 < q < 1$ と $C$ で $e_k \leq Cq^k$ となることを線形収束 (linear convergence)、 $e_{k+1}/e_k \to 0$ を超 1 次収束 (superlinear)、 $e_{k+1} \leq Ce_k^2$ を 2 次収束 (quadratic)、 $O(1/k)$ のように線形収束より遅いものを劣線形収束 (sublinear) という。

5.1 最急降下法と降下補題

単位ベクトル $d$ の方向の変化率 $\langle \nabla f(x), d \rangle$ は、コーシー–シュワルツの不等式より $-\lVert \nabla f(x) \rVert$ 以上で、 $\nabla f(x) \neq 0$ なら等号は $d = -\nabla f(x)/\lVert \nabla f(x) \rVert$ のときに限る。 $-\nabla f(x)$ は最も急に下る方向である。

定義 5.1（最急降下法, gradient descent）初期点 $x_0$ とステップ幅 $t_k > 0$ を与え、 $x_{k+1} = x_k - t_k\nabla f(x_k)$ （ $k = 0, 1, 2, \dots$ ）で点列を作る方法を最急降下法（勾配法）という。機械学習ではステップ幅を学習率 (learning rate) とよぶ。

ステップ幅が小さすぎれば進まず、大きすぎれば谷を飛び越える。どこまで大きくしてよいかを教えるのが次の不等式である。

補題 5.2（降下補題, descent lemma） $f$ が $L$ -平滑ならば、すべての $x, y$ について
$f(y) \leq f(x) + \langle \nabla f(x), y - x \rangle + \frac{L}{2}\lVert y - x \rVert^2$

証明. 第2章定理 2.23 (1)（ $L$ -平滑性の特徴づけ）で示した。要点は、微分積分学の基本定理により

f(y) - f(x) - \langle \nabla f(x), y - x \rangle = \int_0^1 \langle \nabla f(x + s(y - x)) - \nabla f(x), y - x \rangle\,ds \leq \int_0^1 Ls\lVert y - x \rVert^2\,ds = \frac{L}{2}\lVert y - x \rVert^2

となることである（不等号はコーシー–シュワルツの不等式と $L$ -平滑性による）。 $\square$

凸性は使っていない。 $f$ は $x$ で接する放物面で上から押さえられる。

系 5.3（1 回の反復での減少量） $f$ を $L$ -平滑とし、 $x^{+} = x - t\nabla f(x)$ , $0 < t \leq 1/L$ とすると
$f(x^{+}) \leq f(x) - t\Bigl(1 - \frac{Lt}{2}\Bigr)\lVert \nabla f(x) \rVert^2 \leq f(x) - \frac{t}{2}\lVert \nabla f(x) \rVert^2$

証明. 補題 5.2 で $y = x^{+}$ とすると右辺は $f(x) - t\lVert \nabla f(x) \rVert^2 + \frac{Lt^2}{2}\lVert \nabla f(x) \rVert^2$ で、 $t \leq 1/L$ なら $1 - Lt/2 \geq 1/2$ 。 $\square$

注意 5.4（非凸の場合）凸性がなくても、 $f \geq f_{\inf}$ なら $t_k = 1/L$ として系 5.3 を $i = 0, \dots, k - 1$ について足すと $\frac{1}{2L}\sum_{i < k}\lVert \nabla f(x_i) \rVert^2 \leq f(x_0) - f_{\inf}$ で、 $\min_{i < k}\lVert \nabla f(x_i) \rVert^2 \leq 2L(f(x_0) - f_{\inf})/k$ 、 $\nabla f(x_k) \to 0$ を得る。保証されるのは停留点に近づくことだけで、鞍点（第1章例 1.23 の原点など）の近くで止まることもある。

5.2 直線探索とアルミホ条件

$L$ は多くの場合わからず、わかっても大域的な $L$ は局所的な曲がり方より大きすぎることが多い。 $f(x_k + td)$ を厳密に最小化するのは高くつくので、「十分に減った」ことだけを確かめる。

定義 5.5（アルミホ条件, Armijo condition） $d$ を $x$ における降下方向（ $\langle \nabla f(x), d \rangle < 0$ ）、 $0 < c < 1$ とする。ステップ幅 $t > 0$ が
$f(x + td) \leq f(x) + ct\langle \nabla f(x), d \rangle \tag{5.1}$
を満たすとき、アルミホ条件を満たすという。初期値 $\bar{t} > 0$ と $0 < \beta < 1$ を決め、 $t = \bar{t}, \beta\bar{t}, \beta^2\bar{t}, \dots$ と試して (5.1) を満たす最初の $t$ を採る方法をバックトラッキング (backtracking line search) という。

(5.1) の右辺は傾きを $c$ 倍にゆるめた接線である。 $c$ は小さめ（たとえば $10^{-4}$ ）、 $\beta = 1/2$ がよく使われる。

命題 5.6（バックトラッキングは有限回で終わる） $f$ が $x$ で微分可能で $\langle \nabla f(x), d \rangle < 0$ ならば、ある $t_0 > 0$ があって、 $0 < t \leq t_0$ のすべての $t$ が (5.1) を満たす。したがってバックトラッキングは有限回の試行で終わる。さらに $f$ が $L$ -平滑で $d = -\nabla f(x) \neq 0$ なら、 $0 < t \leq 2(1 - c)/L$ のすべての $t$ が (5.1) を満たし、採られる $t$ は $\min(\bar{t}, 2\beta(1 - c)/L)$ 以上である。

証明. $a = -\langle \nabla f(x), d \rangle > 0$ , $r(t) = f(x + td) - f(x) + at$ とおくと、微分可能性より $r(t)/t \to 0$ （ $t \to +0$ ）。(5.1) は $r(t) \leq (1 - c)at$ と同値で、 $(1 - c)a > 0$ なので十分小さい $t > 0$ で成り立つ。試す $t = \beta^j\bar{t}$ は $0$ に近づくから、有限回で $t_0$ 以下になる。後半：系 5.3 の計算から $f(x - t\nabla f(x)) \leq f(x) - t(1 - Lt/2)\lVert \nabla f(x) \rVert^2$ で、 $t \leq 2(1 - c)/L$ なら $1 - Lt/2 \geq c$ なので (5.1) が成り立つ。最初の $\bar{t}$ が採られなければ、採られた $t$ について $t/\beta$ は (5.1) を満たさなかったので $t/\beta > 2(1 - c)/L$ 。 $\square$

したがって $L$ を知らなくても毎回 $f(x_{k+1}) \leq f(x_k) - ct_{\min}\lVert \nabla f(x_k) \rVert^2$ （ $t_{\min} = \min(\bar{t}, 2\beta(1 - c)/L)$ ）が保証される。ここから次節と同じ議論で、 $\mu$ -強凸なら関数値の誤差は毎回 $1 - 2c\mu t_{\min}$ 倍以下になり（定理 5.8 の証明の前半を参照）、 $c = 1/2$ なら定理 5.7 の評価が $1/L$ を $t_{\min}$ に置き換えた形で成り立つ（問題 5.2）。 $c < 1/2$ でも $O(1/k)$ の収束は示せるが、定数は変わる。ウルフ条件は第6章で扱う。

5.3 収束の速さ

定理 5.7（ $L$ -平滑な凸関数での収束） $f$ を $L$ -平滑な凸関数とし、最小点 $x^{\ast}$ をもつとする。 $t_k = 1/L$ の最急降下法について $f(x_k)$ と $\lVert x_k - x^{\ast} \rVert$ は単調非増加で、 $k \geq 1$ について
$f(x_k) - p^{\ast} \leq \frac{L\lVert x_0 - x^{\ast} \rVert^2}{2k}$

証明. $g = \nabla f(x_k)$ とおく。系 5.3 と凸関数の 1 次条件 $f(x_k) \leq p^{\ast} + \langle g, x_k - x^{\ast} \rangle$ （第2章定理 2.14）より

\begin{aligned} f(x_{k+1}) &\leq p^{\ast} + \langle g, x_k - x^{\ast} \rangle - \frac{1}{2L}\lVert g \rVert^2 = p^{\ast} + \frac{L}{2}\Bigl(\lVert x_k - x^{\ast} \rVert^2 - \Bigl\lVert x_k - x^{\ast} - \frac{1}{L}g \Bigr\rVert^2\Bigr) \\ &= p^{\ast} + \frac{L}{2}\bigl(\lVert x_k - x^{\ast} \rVert^2 - \lVert x_{k+1} - x^{\ast} \rVert^2\bigr) \end{aligned}

（最初の等号は展開すれば確かめられる）。左辺は $p^{\ast}$ 以上なので $\lVert x_{k+1} - x^{\ast} \rVert \leq \lVert x_k - x^{\ast} \rVert$ 。 $f(x_{k+1}) \leq f(x_k)$ は系 5.3 による。上の不等式を $k = 0, \dots, K - 1$ について足すと右辺は順に打ち消し合い、 $\sum_{k=1}^{K}(f(x_k) - p^{\ast}) \leq \frac{L}{2}\lVert x_0 - x^{\ast} \rVert^2$ 。 $f(x_k)$ は単調非増加だから左辺は $K(f(x_K) - p^{\ast})$ 以上である。 $\square$

精度を 1 桁上げるには反復回数が 10 倍要る。評価は次元 $n$ によらない。定数の異なる評価もある（Nesterov, Lectures on Convex Optimization の 2.1 節は別の議論で $\frac{2L\lVert x_0 - x^{\ast} \rVert^2}{k + 4}$ を示している）。

定理 5.8（強凸関数での線形収束） $f$ を $\mu$ -強凸かつ $L$ -平滑とし、 $\kappa = L/\mu$ とする。 $t_k = 1/L$ の最急降下法について
$f(x_k) - p^{\ast} \leq \Bigl(1 - \frac{1}{\kappa}\Bigr)^k(f(x_0) - p^{\ast}), \qquad \lVert x_k - x^{\ast} \rVert^2 \leq \Bigl(1 - \frac{1}{\kappa}\Bigr)^k\lVert x_0 - x^{\ast} \rVert^2$
すなわち、目的関数の値の誤差と、最小点までの距離の 2 乗が、どちらも毎回 $1 - 1/\kappa$ 倍以下になる（距離そのものは $\sqrt{1 - 1/\kappa}$ 倍以下）。

証明. 第2章系 2.24 より、 $f$ はただ一つの最小点 $x^{\ast}$ をもち、 $\frac{1}{2L}\lVert \nabla f(x) \rVert^2 \leq f(x) - p^{\ast} \leq \frac{1}{2\mu}\lVert \nabla f(x) \rVert^2$ が成り立つ（右側はポリャク–ロヤシェヴィチの不等式）。

関数値：系 5.3 と右側の不等式より $f(x_{k+1}) - p^{\ast} \leq f(x_k) - p^{\ast} - \frac{1}{2L}\lVert \nabla f(x_k) \rVert^2 \leq (1 - \frac{\mu}{L})(f(x_k) - p^{\ast})$ 。

距離： $g = \nabla f(x_k)$ とすると $\lVert x_{k+1} - x^{\ast} \rVert^2 = \lVert x_k - x^{\ast} \rVert^2 - \frac{2}{L}\langle g, x_k - x^{\ast} \rangle + \frac{1}{L^2}\lVert g \rVert^2$ 。強凸性の特徴づけ（第2章定理 2.22 の 2）の不等式 $p^{\ast} \geq f(x_k) + \langle g, x^{\ast} - x_k \rangle + \frac{\mu}{2}\lVert x^{\ast} - x_k \rVert^2$ から $\langle g, x_k - x^{\ast} \rangle \geq f(x_k) - p^{\ast} + \frac{\mu}{2}\lVert x_k - x^{\ast} \rVert^2$ 、左側の不等式から $\lVert g \rVert^2 \leq 2L(f(x_k) - p^{\ast})$ 。代入すると $f(x_k) - p^{\ast}$ の項が打ち消し合い、 $\lVert x_{k+1} - x^{\ast} \rVert^2 \leq (1 - \frac{\mu}{L})\lVert x_k - x^{\ast} \rVert^2$ 。 $\square$

$(1 - 1/\kappa)^k \leq e^{-k/\kappa}$ なので、誤差を $\varepsilon$ 倍にするには約 $\kappa\log(1/\varepsilon)$ 回で足りる。ステップ幅 $2/(\mu + L)$ では距離が毎回 $\frac{\kappa - 1}{\kappa + 1}$ 倍以下になる（Nesterov の本の 2.1 節。二次関数の場合は次節で示す）。

5.4 条件数と収束の遅さ

$Q \succ 0$ の固有値を $\mu = \lambda_1 \leq \cdots \leq \lambda_n = L$ とし、 $f(x) = \frac{1}{2}x^{\top}Qx - c^{\top}x$ を考える。 $x^{\ast} = Q^{-1}c$ , $\nabla f(x) = Q(x - x^{\ast})$ なので、固定ステップ $t$ の最急降下法の誤差 $e_k = x_k - x^{\ast}$ は $e_{k+1} = (I - tQ)e_k$ に従う。 $Q$ の正規直交な固有ベクトル $u_i$ （02-linear-algebra 第7章定理 7.32）で $e_0 = \sum_i a_iu_i$ と展開すると、 $e_k = \sum_i(1 - t\lambda_i)^ka_iu_i$ である。

命題 5.9（二次関数での最急降下法） $\rho(t) = \max_i\lvert 1 - t\lambda_i \rvert = \max(\lvert 1 - t\mu \rvert, \lvert 1 - tL \rvert)$ とすると $\lVert e_k \rVert \leq \rho(t)^k\lVert e_0 \rVert$ である。

$\rho(t) < 1 \iff 0 < t < 2/L$ 。 $t > 2/L$ なら、 $u_n$ の成分は毎回 $\lvert 1 - tL \rvert > 1$ 倍になり、 $a_n \neq 0$ なら発散する。

$\rho(t)$ は $t = 2/(\mu + L)$ で最小値 $\frac{\kappa - 1}{\kappa + 1}$ をとる。 $t = 1/L$ なら $\rho = 1 - 1/\kappa$ である。

証明. $\lVert e_k \rVert^2 = \sum_i(1 - t\lambda_i)^{2k}a_i^2 \leq \rho(t)^{2k}\lVert e_0 \rVert^2$ で、 $\lvert 1 - t\lambda \rvert$ は $\lambda$ の凸関数なので最大は $\lambda = \mu, L$ でとられる。1 は $\lvert 1 - t\lambda \rvert < 1 \iff 0 < t\lambda < 2$ による。2： $\lvert 1 - t\mu \rvert$ は $t \leq 1/\mu$ で減少、 $\lvert 1 - tL \rvert$ は $t \geq 1/L$ で増加するので、最大値は $1 - t\mu = tL - 1$ 、すなわち $t = 2/(\mu + L)$ で最小になり、値は $\frac{L - \mu}{L + \mu}$ 。 $\square$

最も急な方向（ $\lambda = L$ ）に合わせて $t < 2/L$ とすると、最も緩い方向（ $\lambda = \mu$ ）の誤差は毎回 $1 - t\mu > 1 - 2/\kappa$ 倍にしかならない。これが条件数の大きい問題で勾配法が遅い理由である。

例 5.10（谷底のジグザグ） $f(x) = \frac{1}{2}(x_1^2 + \kappa x_2^2)$ （ $\kappa > 1$ ）を、毎回 $t$ を厳密に最小化する直線探索（二次関数では $t = \lVert g \rVert^2/(g^{\top}Qg)$ , $g = \nabla f(x)$ ）で $x_0 = (\kappa, 1)$ から解く。 $x = a(\kappa, \sigma)$ （ $\sigma = \pm 1$ ）なら $g = a\kappa(1, \sigma)$ 、 $t = 2/(\kappa + 1)$ で、次の点は $a\frac{\kappa - 1}{\kappa + 1}(\kappa, -\sigma)$ になる。よって

x_k = \Bigl(\frac{\kappa - 1}{\kappa + 1}\Bigr)^k\bigl(\kappa, (-1)^k\bigr), \qquad f(x_k) = \Bigl(\frac{\kappa - 1}{\kappa + 1}\Bigr)^{2k}f(x_0)

で、点は $x_2$ の符号を毎回変えながら谷底を往復する。 $f(x_k) \leq 10^{-6}f(x_0)$ となる最小の $k$ は、 $\kappa = 10, 100, 1000$ でそれぞれ $35, 346, 3454$ 回で、ほぼ $\kappa$ に比例する（NumPy で確かめた）。直線探索を厳密にしても、方向が悪ければ遅い。

注意

「学習率を大きくすれば速く収束する」は誤りである。命題 5.9 のとおり $t > 2/L$ では発散し、 $t = 2/L$ でも $u_n$ 方向の誤差は符号を変えるだけで減らない。損失が振動したり増え続けたりしたら、まず学習率と特徴量のスケール（ $L$ を決める）を疑う。

ヒント

実務では 条件数は変数のスケールで大きく変わる（第2章例 2.25 と直後の「実務では」）。基本の対策は特徴量の標準化と、 $x = Py$ と変数を取り替えて $y$ について勾配法を行う前処理 (preconditioning) である（ $x$ で書くと $x_{k+1} = x_k - tPP^{\top}\nabla f(x_k)$ 。 $PP^{\top}$ を毎回その点でのヘッセ行列の逆行列に取り替え、 $t = 1$ としたものがニュートン法）。学習率はバックトラッキングで決めるほうが安全なことが多い。また、勾配が小さくても最小点に近いとは限らず、 $\lVert x - x^{\ast} \rVert$ は $\lVert \nabla f(x) \rVert/\mu$ 程度まで大きくありうる。

5.5 ネステロフの加速勾配法

最急降下法は直前の点の勾配しか使わない。過去の勾配も使えばどこまで速くできるか。まず限界を述べる。

定理 5.11（1 次の方法の下界、主張） $1 \leq k \leq (n - 1)/2$ と $x_0 \in \mathbb{R}^n$ に対し、 $L$ -平滑な凸な二次関数 $f$ で、 $x_j \in x_0 + \operatorname{span}\lbrace \nabla f(x_0), \dots, \nabla f(x_{j-1}) \rbrace$ （ $j = 1, \dots, k$ ）を満たす任意の点列について $f(x_k) - p^{\ast} \geq \frac{3L\lVert x_0 - x^{\ast} \rVert^2}{32(k + 1)^2}$ となるものが存在する（Nesterov の本の 2.1 節）。

$O(1/k)$ と $O(1/k^2)$ のすき間を埋めるのがネステロフ（1983 年）の方法である。

定義 5.12（ネステロフの加速勾配法, accelerated gradient method） $y_0 = x_0$ とし、 $k = 0, 1, 2, \dots$ について
$x_{k+1} = y_k - \frac{1}{L}\nabla f(y_k), \qquad y_{k+1} = x_{k+1} + \frac{k}{k + 3}(x_{k+1} - x_k)$

$y_{k+1}$ は直前の移動の方向に慣性（モメンタム）で少し先へ進んだ点で、そこで勾配を計算する。

定理 5.13（加速勾配法の収束） $f$ を $L$ -平滑な凸関数とし、最小点 $x^{\ast}$ をもつとする。定義 5.12 の点列は、 $k \geq 1$ について $f(x_k) - p^{\ast} \leq \dfrac{2L\lVert x_0 - x^{\ast} \rVert^2}{(k + 1)^2}$ を満たす。

証明. $\theta_k = 2/(k + 2)$ 、 $v_0 = x_0$ , $v_{k+1} = x_k + (x_{k+1} - x_k)/\theta_k$ とおくと、帰納法で $y_k = (1 - \theta_k)x_k + \theta_kv_k$ が確かめられ（ $\theta_{k+1}(\theta_k^{-1} - 1) = \frac{k}{k + 3}$ による）、 $g = \nabla f(y_k)$ として $v_{k+1} = v_k - \frac{1}{\theta_kL}g$ となる。系 5.3 より $f(x_{k+1}) \leq f(y_k) - \frac{1}{2L}\lVert g \rVert^2$ 。凸性 $f(y_k) \leq f(z) + \langle g, y_k - z \rangle$ を $z = x_k$ と $z = x^{\ast}$ について $1 - \theta_k$ 倍と $\theta_k$ 倍して足すと、 $y_k - (1 - \theta_k)x_k - \theta_kx^{\ast} = \theta_k(v_k - x^{\ast})$ より

f(x_{k+1}) - p^{\ast} \leq (1 - \theta_k)(f(x_k) - p^{\ast}) + \theta_k\langle g, v_k - x^{\ast} \rangle - \frac{1}{2L}\lVert g \rVert^2

最後の 2 項は、 $v_{k+1}$ の式を展開すると $\frac{\theta_k^2L}{2}(\lVert v_k - x^{\ast} \rVert^2 - \lVert v_{k+1} - x^{\ast} \rVert^2)$ に等しい。 $\theta_k^2$ で割り、 $\frac{1 - \theta_k}{\theta_k^2} = \frac{k(k + 2)}{4} \leq \frac{(k + 1)^2}{4}$ を使うと、 $E_k = \frac{(k + 1)^2}{4}(f(x_k) - p^{\ast}) + \frac{L}{2}\lVert v_k - x^{\ast} \rVert^2$ は $k \geq 1$ で単調非増加で、 $\theta_0 = 1$ より $E_1 \leq \frac{L}{2}\lVert x_0 - x^{\ast} \rVert^2$ 。よって $\frac{(k + 1)^2}{4}(f(x_k) - p^{\ast}) \leq E_k \leq \frac{L}{2}\lVert x_0 - x^{\ast} \rVert^2$ 。 $\square$

定理 5.11 より、この速さは定数倍を除いて改善できない（加速法は最適な 1 次の方法である）。 $f$ が $\mu$ -強凸なら、慣性の係数を定数 $\frac{\sqrt{\kappa} - 1}{\sqrt{\kappa} + 1}$ にした方法（ $x_{-1} = x_0$ として $y_k = x_k + \frac{\sqrt{\kappa} - 1}{\sqrt{\kappa} + 1}(x_k - x_{k-1})$ , $x_{k+1} = y_k - \frac{1}{L}\nabla f(y_k)$ ）が $f(x_k) - p^{\ast} \leq (1 - 1/\sqrt{\kappa})^k(f(x_0) - p^{\ast} + \frac{\mu}{2}\lVert x_0 - x^{\ast} \rVert^2)$ を満たし（主張。Nesterov の本の 2.2 節）、反復回数が $\kappa\log(1/\varepsilon)$ から $\sqrt{\kappa}\log(1/\varepsilon)$ に減る。

注意

加速法では $f(x_k)$ は単調に減るとは限らない。慣性で谷を行き過ぎて値が一時的に増えるのは正常な動作である（増えたら慣性をリセットする再出発 (restart) という工夫もある）。定理 5.13 は凸性と正確な勾配を前提にしている。非凸関数ではこの保証はなく、勾配に誤差があると、加速法は最急降下法より誤差を蓄積しやすい。

5.6 共役勾配法

二次関数 $f(x) = \frac{1}{2}x^{\top}Qx - c^{\top}x$ （ $Q \succ 0$ ）の最小化は $Qx = c$ を解くことと同じである。 $Q$ が大きく疎なとき、 $Q$ とベクトルの積だけで解く方法として共役勾配法が使われる。

定義 5.14（共役） $0$ でないベクトル $d_0, \dots, d_{m-1}$ が $d_i^{\top}Qd_j = 0$ （ $i \neq j$ ）を満たすとき $Q$ -共役 ( $Q$ -conjugate) という。

$Q$ -共役は内積 $\langle u, v \rangle_Q = u^{\top}Qv$ についての直交性なので、 $Q$ -共役なベクトルは一次独立である。

定理 5.15（共役方向法は $n$ 回で終わる） $d_0, \dots, d_{n-1}$ を $Q$ -共役とし、 $x_0$ から直線 $x_k + \alpha d_k$ 上の最小点 $x_{k+1} = x_k + \alpha_kd_k$ , $\alpha_k = -\nabla f(x_k)^{\top}d_k/(d_k^{\top}Qd_k)$ （ $\alpha$ についての導関数 $\nabla f(x_k)^{\top}d_k + \alpha d_k^{\top}Qd_k$ を $0$ にする値）へ順に進むと、 $x_n = x^{\ast}$ である。

証明. $d_i$ は基底なので $x^{\ast} - x_0 = \sum_i\sigma_id_i$ と書け、 $d_k$ との $Q$ -内積をとると $\sigma_k = d_k^{\top}Q(x^{\ast} - x_0)/(d_k^{\top}Qd_k)$ 。 $x_k - x_0 \in \operatorname{span}\lbrace d_0, \dots, d_{k-1} \rbrace$ は $d_k$ と $Q$ -直交し、 $\nabla f(x_k) = Q(x_k - x^{\ast})$ だから $-\nabla f(x_k)^{\top}d_k = d_k^{\top}Q(x^{\ast} - x_k) = d_k^{\top}Q(x^{\ast} - x_0)$ 。よって $\alpha_k = \sigma_k$ で、 $x_n = x_0 + \sum_i\sigma_id_i = x^{\ast}$ 。 $\square$

共役な方向を、勾配から 1 本ずつ作りながら進むのが共役勾配法である。

定義 5.16（共役勾配法, conjugate gradient method） $r_0 = Qx_0 - c$ （ $= \nabla f(x_0)$ ）、 $d_0 = -r_0$ とし、 $r_k \neq 0$ である間、次を繰り返す。
$\alpha_k = \frac{r_k^{\top}r_k}{d_k^{\top}Qd_k}, \quad x_{k+1} = x_k + \alpha_kd_k, \quad r_{k+1} = r_k + \alpha_kQd_k, \quad d_{k+1} = -r_{k+1} + \frac{r_{k+1}^{\top}r_{k+1}}{r_k^{\top}r_k}d_k$

定理 5.17（共役勾配法の性質、主張） $Q \succ 0$ とする。 $r_k \neq 0$ である限り、 $d_0, \dots, d_k$ は $Q$ -共役、 $r_0, \dots, r_k$ は互いに直交し、 $x_k$ は $x_0 + \operatorname{span}\lbrace r_0, Qr_0, \dots, Q^{k-1}r_0 \rbrace$ 上の $f$ の最小点である。したがって厳密に計算すれば、高々 $n$ 回（実は $Q$ の相異なる固有値の個数以下の回数）で $x_k = x^{\ast}$ となる。また $\lVert v \rVert_Q = \sqrt{v^{\top}Qv}$ として $\lVert x_k - x^{\ast} \rVert_Q \leq 2\bigl(\frac{\sqrt{\kappa} - 1}{\sqrt{\kappa} + 1}\bigr)^k\lVert x_0 - x^{\ast} \rVert_Q$ が成り立つ（Nocedal–Wright, Numerical Optimization 第5章）。

例 5.18 $x_0 = 0$ から

f(x) = 2x_1^2 + 2x_1x_2 + x_2^2 - 2x_1 = \frac{1}{2}x^{\top}Qx - c^{\top}x, \qquad Q = \begin{pmatrix} 4 & 2 \\ 2 & 2 \end{pmatrix}, \quad c = \begin{pmatrix} 2 \\ 0 \end{pmatrix}

を最小化する（ $x^{\ast} = (1, -1)$ , $p^{\ast} = -1$ , $\kappa = (7 + 3\sqrt{5})/2 \approx 6.85$ ）。共役勾配法では $r_0 = (-2, 0)$ , $d_0 = (2, 0)$ , $\alpha_0 = 4/16 = 1/4$ で $x_1 = (1/2, 0)$ , $r_1 = (0, 1)$ 。次に $d_1 = -r_1 + \frac{1}{4}d_0 = (1/2, -1)$ で、 $Qd_1 = (0, -1)$ より $d_0^{\top}Qd_1 = 0$ （共役）、 $\alpha_1 = 1/(d_1^{\top}Qd_1) = 1$ で $x_2 = (1, -1) = x^{\ast}$ 。2 回で終わる。同じ点から厳密な直線探索の最急降下法を行うと、 $x_1$ は同じだがその後は $(1/2, -1/2), (3/4, -1/2), (3/4, -3/4), \dots$ とジグザグに進み、 $f(x_k) - p^{\ast} = 2^{-k}$ で（sympy で厳密に確かめた）有限回では終わらない。

丸め誤差があると共役性が少しずつ崩れて $n$ 回での終了は保証されないが、共役勾配法は大規模な正定値の連立一次方程式（リッジ回帰の正規方程式、第6章のニュートン方程式など）の反復解法として広く使われる。二次関数でない $f$ への拡張を非線形共役勾配法という。

固有値が $1$ から $\kappa$ まで等間隔に並ぶ $n = 100$ 次元の二次関数（ $Q$ は対角、 $c = \mathbf{1}$ , $x_0 = 0$ ）で、 $\lVert x_k - x^{\ast} \rVert \leq 10^{-6}\lVert x_0 - x^{\ast} \rVert$ となるまでの反復回数を NumPy で数えると次のようになった（加速法は強凸版）。

$\kappa$	$10$	$100$	$1000$	$10000$
最急降下法（ $t = 1/L$ ）	121	1351	13802	138148
加速法	41	156	519	1660
共役勾配法	22	46	51	52

$\kappa$ が 10 倍になると、最急降下法の回数はほぼ 10 倍（ $\kappa\log 10^6 \approx 13.8\kappa$ に近い）、加速法はほぼ $\sqrt{10} \approx 3.2$ 倍で、理論どおりそれぞれ $\kappa$ と $\sqrt{\kappa}$ に比例する。共役勾配法は $n = 100$ 回より少ない回数で終わる。

5.7 射影勾配法

非負制約・上下限・予算制約のように、閉凸集合 $C$ の上で $f$ を最小化したいことは多い。勾配で進んだ点を $C$ に射影して戻す方法

x_{k+1} = P_C\bigl(x_k - t\nabla f(x_k)\bigr)

を射影勾配法 (projected gradient method) という。箱への射影は成分ごとの切り詰め、球への射影は縮小で、ともに安く計算できる（第2章例 2.5）。

命題 5.19（射影勾配法の不動点） $C$ を空でない閉凸集合、 $f$ を微分可能な凸関数、 $t > 0$ とする。 $x^{\ast} \in C$ が $C$ 上の $f$ の最小点であるための必要十分条件は $x^{\ast} = P_C(x^{\ast} - t\nabla f(x^{\ast}))$ である。

証明. 射影定理（第2章定理 2.4）の特徴づけ (2.1) より、 $x^{\ast} = P_C(x^{\ast} - t\nabla f(x^{\ast}))$ は「すべての $y \in C$ で $\langle -t\nabla f(x^{\ast}), y - x^{\ast} \rangle \leq 0$ 」と同値で、これは凸最適化の最適性条件（第2章定理 2.19 の 2）により $x^{\ast}$ が $C$ 上の最小点であることと同値である。 $\square$

射影勾配法が止まる点はちょうど最適解である。 $t = 1/L$ なら定理 5.7 と同じ評価が成り立つ（次節の定理 5.23 で $h = 0$ とした場合）。強凸なら線形収束する（問題 5.6）。

5.8 近接勾配法とラッソ

ラッソ $\frac{1}{2}\lVert Ax - b \rVert^2 + \lambda\lVert x \rVert_1$ は $x_i = 0$ で微分できないので、そのままでは勾配法が使えない（劣勾配で代用すると値が単調に減らず、収束も遅い）。そこで、滑らかな部分だけを 1 次近似する。

以下、 $C$ を空でない閉凸集合、 $f$ を $L$ -平滑な凸関数、 $h\colon \mathbb{R}^n \to \mathbb{R}$ を連続な凸関数（微分可能でなくてよい。実は $\mathbb{R}^n$ 上の凸関数は常に連続である）とし、 $C$ 上で $F = f + h$ を最小化する。主な例は $C = \mathbb{R}^n$ , $h = \lambda\lVert x \rVert_1$ （ラッソ）と $h = 0$ （射影勾配法）である。 $f$ だけを $x_k$ で 1 次近似して罰則を加えた $\langle \nabla f(x_k), u - x_k \rangle + \frac{1}{2t}\lVert u - x_k \rVert^2 + h(u)$ を $C$ 上で最小化することは、平方完成により $h(u) + \frac{1}{2t}\lVert u - (x_k - t\nabla f(x_k)) \rVert^2$ を最小化することと同じである。

定義 5.20（近接写像, proximal operator） $t > 0$ , $v \in \mathbb{R}^n$ に対し $T_t(v) = \operatorname{argmin}_{u \in C}\bigl(h(u) + \frac{1}{2t}\lVert u - v \rVert^2\bigr)$ とする。 $C = \mathbb{R}^n$ のときこれを $\operatorname{prox}_{th}(v)$ と書き、 $th$ の近接写像という。 $h = 0$ なら $T_t = P_C$ である。 $x_{k+1} = T_t(x_k - t\nabla f(x_k))$ で点列を作る方法を近接勾配法 (proximal gradient method) という。

最小点はただ一つ存在する。実際、 $h$ は $0$ で劣勾配 $s$ をもつ（第2章定理 2.27）ので $h(u) \geq h(0) + \langle s, u \rangle$ で、目的関数は連続かつ強圧的だから最小点をもち（第1章定理 1.11）、狭義凸だから最小点は一つである（第2章定理 2.18）。

命題 5.21（ $\ell^1$ ノルムの近接写像はソフト閾値） $\lambda, t > 0$ とすると、 $\operatorname{prox}_{t\lambda\lVert \cdot \rVert_1}(v)$ の第 $i$ 成分は $S_{t\lambda}(v_i) = \operatorname{sign}(v_i)\max(\lvert v_i \rvert - t\lambda, 0)$ である。

証明. 目的関数を $t$ 倍すると $\sum_i\bigl(t\lambda\lvert u_i \rvert + \frac{1}{2}(u_i - v_i)^2\bigr)$ と成分ごとの和に分かれるので、各成分で $\varphi(u) = a\lvert u \rvert + \frac{1}{2}(u - v)^2$ （ $a = t\lambda$ ）を最小化すればよい。平方完成すると

\varphi(u) = \frac{1}{2}\bigl(u - (v - a)\bigr)^2 + av - \frac{a^2}{2} \quad (u \geq 0), \qquad \varphi(u) = \frac{1}{2}\bigl(u - (v + a)\bigr)^2 - av - \frac{a^2}{2} \quad (u \leq 0)

$v > a$ なら、 $[0, \infty)$ 上の最小点は $v - a > 0$ で、 $(-\infty, 0]$ 上では $v + a > 0$ より $u = 0$ が最小点だから、全体の最小点は $v - a$ 。 $v < -a$ なら同様に $v + a$ 。 $\lvert v \rvert \leq a$ なら $v - a \leq 0 \leq v + a$ より、どちらの半直線でも $u = 0$ が最小点である。 $\square$

これは第2章例 2.30 のソフト閾値を、劣勾配を使わずに示し直したものである。 $f(x) = \frac{1}{2}\lVert Ax - b \rVert^2$ では $\nabla f(x) = A^{\top}(Ax - b)$ , $L = \lambda_{\max}(A^{\top}A)$ （ $A$ の最大特異値の 2 乗）で、ラッソの近接勾配法は成分ごとに

x_{k+1} = S_{t\lambda}\bigl(x_k - tA^{\top}(Ax_k - b)\bigr)

となる（ISTA, iterative shrinkage-thresholding algorithm）。勾配で一歩進み、絶対値が $t\lambda$ 以下の成分をちょうど $0$ にし、残りを $t\lambda$ だけ $0$ に寄せる。

補題 5.22（近接写像の基本不等式） $p = T_t(v)$ ならば、すべての $z \in C$ について
$h(z) + \frac{1}{2t}\lVert z - v \rVert^2 \geq h(p) + \frac{1}{2t}\lVert p - v \rVert^2 + \frac{1}{2t}\lVert z - p \rVert^2$

証明. $\phi(u) = h(u) + \frac{1}{2t}\lVert u - v \rVert^2$ 、 $0 < s < 1$ , $u_s = p + s(z - p) \in C$ とする。 $h$ の凸性と恒等式 $\lVert (1 - s)a + sb \rVert^2 = (1 - s)\lVert a \rVert^2 + s\lVert b \rVert^2 - s(1 - s)\lVert a - b \rVert^2$ （ $a = p - v$ , $b = z - v$ ）より $\phi(u_s) \leq (1 - s)\phi(p) + s\phi(z) - \frac{s(1 - s)}{2t}\lVert z - p \rVert^2$ 。 $\phi(p) \leq \phi(u_s)$ と合わせて $s$ で割ると $\phi(p) \leq \phi(z) - \frac{1 - s}{2t}\lVert z - p \rVert^2$ で、 $s \to 0$ とすればよい。 $\square$

定理 5.23（近接勾配法の収束） $F = f + h$ が $C$ 上で最小点 $x^{\ast}$ をもつとし、 $0 < t \leq 1/L$ , $x_0 \in C$ とする。近接勾配法の点列について $F(x_{k+1}) \leq F(x_k)$ で、 $k \geq 1$ について $F(x_k) - F(x^{\ast}) \leq \dfrac{\lVert x_0 - x^{\ast} \rVert^2}{2tk}$ である。

証明. $x \in C$ 、 $g = \nabla f(x)$ 、 $v = x - tg$ 、 $x^{+} = T_t(v)$ 、 $z \in C$ とする。降下補題（ $1/t \geq L$ ）と凸性 $f(x) \leq f(z) + \langle g, x - z \rangle$ より $f(x^{+}) \leq f(z) + \langle g, x^{+} - z \rangle + \frac{1}{2t}\lVert x^{+} - x \rVert^2$ 。補題 5.22 に $\lVert z - v \rVert^2 - \lVert x^{+} - v \rVert^2 = \lVert z - x \rVert^2 - \lVert x^{+} - x \rVert^2 + 2t\langle g, z - x^{+} \rangle$ を代入すると $h(x^{+}) \leq h(z) + \langle g, z - x^{+} \rangle + \frac{1}{2t}(\lVert z - x \rVert^2 - \lVert x^{+} - x \rVert^2 - \lVert z - x^{+} \rVert^2)$ 。2 式を足すと

F(x^{+}) \leq F(z) + \frac{1}{2t}\bigl(\lVert z - x \rVert^2 - \lVert z - x^{+} \rVert^2\bigr) \tag{5.2}

$z = x$ とすると $F(x^{+}) \leq F(x)$ 。 $z = x^{\ast}$ とすると定理 5.7 の証明と同じ形の不等式になり、同様に足し合わせればよい。 $\square$

$C = \mathbb{R}^n$ , $h = 0$ なら定理 5.7 に戻る。近接勾配法に定義 5.12 型の慣性をつけた FISTA（Beck–Teboulle, 2009 年）は $F(x_k) - F(x^{\ast}) \leq \frac{2L\lVert x_0 - x^{\ast} \rVert^2}{(k + 1)^2}$ を満たす（主張）。

次のコードは、50 件・20 個の特徴量のうち 3 個（番号 2, 7, 15）だけが効くデータで、ラッソを近接勾配法で解く。

import numpy as np

rng = np.random.default_rng(0)
m, n = 50, 20
A = rng.standard_normal((m, n))
x_true = np.zeros(n); x_true[[2, 7, 15]] = [3.0, -2.0, 1.5]   # 効く特徴量は 3 個だけ
b = A @ x_true + 0.5 * rng.standard_normal(m)
L = np.linalg.norm(A, 2) ** 2                  # f(x) = ||Ax - b||^2 / 2 の L
soft = lambda v, a: np.sign(v) * np.maximum(np.abs(v) - a, 0.0)

print("least squares:", np.count_nonzero(np.linalg.lstsq(A, b, rcond=None)[0]), "nonzeros")
for lam in [2.0, 15.0]:
    x = np.zeros(n)
    for k in range(3000):
        x = soft(x - A.T @ (A @ x - b) / L, lam / L)       # 近接勾配法（ISTA）
    print(f"lam={lam:4.1f}  support={np.flatnonzero(x)}  values={np.round(x[x != 0], 2)}")

least squares: 20 nonzeros
lam= 2.0  support=[ 0  2  7  9 14 15 18 19]  values=[-0.14  2.93 -1.96 -0.16  0.02  1.4   0.07 -0.04]
lam=15.0  support=[ 2  7 15]  values=[ 2.63 -1.46  1.11]

最小二乗法の係数は 20 個すべてが $0$ でない。 $\lambda = 2$ では小さな係数が 5 個残り、 $\lambda = 15$ ではちょうど 2, 7, 15 番だけが残るが、その係数は真の値 $3, -2, 1.5$ より $0$ 側に縮んでいる。

ヒント

実務では ラッソの罰則は係数の大きさに一様にかかるので、特徴量を標準化してから使う（単位を変えると選ばれる変数が変わる）。 $\lambda$ は交差検証で選ぶことが多い。係数は $0$ 側に偏る（上の出力）ので、効果の大きさを報告するときは、選ばれた変数だけで最小二乗法をやり直すなどの補正を検討する。計算には FISTA のほか、成分ごとにソフト閾値を繰り返す座標降下法も広く使われる。

まとめ

$L$ -平滑なら $t \leq 1/L$ の最急降下法は毎回 $\frac{t}{2}\lVert \nabla f(x_k) \rVert^2$ 以上 $f$ を減らす（降下補題）。凸でなくても、下に有界なら勾配は $0$ に近づく。
アルミホ条件のバックトラッキングは有限回で終わり、 $L$ -平滑なら $t \geq \min(\bar{t}, 2\beta(1 - c)/L)$ が保証される。
$L$ -平滑な凸関数では $f(x_k) - p^{\ast} \leq L\lVert x_0 - x^{\ast} \rVert^2/(2k)$ 。強凸なら関数値の誤差と距離の 2 乗がともに毎回 $1 - 1/\kappa$ 倍以下になる。
二次関数では誤差は固有ベクトルごとに $1 - t\lambda_i$ 倍になり、 $t < 2/L$ が必要で、 $\mu$ の方向が遅れる。反復回数は $\kappa$ に比例する。スケーリング・前処理が効く。
加速法は $O(1/k^2)$ を達成し、1 次の方法として定数倍を除いて最適である。強凸なら反復回数は $\sqrt{\kappa}$ に比例する。値は単調に減るとは限らない。
共役勾配法は二次関数を厳密計算で $n$ 回以内に最小化する。
射影勾配法と ISTA を含む近接勾配法は $O(1/k)$ で収束し、不動点は最適解である。 $\lambda\lVert x \rVert_1$ の近接写像はソフト閾値で、ラッソの解がスパースになる。

演習問題

問題 5.1 ★ $f(x) = \frac{1}{2}(x_1^2 + 10x_2^2)$ を $x_0 = (1, 1)$ から最急降下法で最小化する。(1) $L, \mu, \kappa$ を求め、 $t = 1/L$ のときの $x_k$ を求めよ。 $f(x_k) \leq 10^{-6}$ となる最小の $k$ を求め、定理 5.8 から保証される回数と比べよ。(2) $t = 2/(\mu + L)$ のときの $x_k$ を求めよ。(3) $t = 0.25$ のとき何が起こるか。

解答

(1) $\nabla^2 f = \operatorname{diag}(1, 10)$ より $\mu = 1$ , $L = 10$ , $\kappa = 10$ 。 $t = 0.1$ では $x_{k+1} = (0.9x_{k,1}, 0)$ なので、 $k \geq 1$ で $x_k = (0.9^k, 0)$ 、 $f(x_k) = \frac{1}{2} \cdot 0.81^k$ 。これが $10^{-6}$ 以下になるのは $k \geq \log(2 \times 10^{-6})/\log 0.81 \approx 62.3$ 、すなわち $k = 63$ から。定理 5.8 の評価 $f(x_k) \leq 0.9^kf(x_0) = 5.5 \cdot 0.9^k$ からは $k \geq 148$ しか保証されない。二次関数では誤差が毎回 $1 - 1/\kappa$ 倍（命題 5.9）、関数値はその 2 乗の $0.81$ 倍になるので、一般の関数向けの定理 5.8 は保守的である。

(2) $1 - t = 9/11$ , $1 - 10t = -9/11$ なので $x_k = \bigl((9/11)^k, (-9/11)^k\bigr)$ 、 $f(x_k) = 5.5 \cdot (81/121)^k$ 。2 つの方向が同じ速さで減る。

(3) $1 - 10 \cdot 0.25 = -1.5$ なので $x_{k,2} = (-1.5)^k$ となり発散する（ $t > 2/L = 0.2$ ）。 $x_{k,1} = 0.75^k$ は収束するが、 $f(x_k) \to \infty$ 。

問題 5.2 ★★ $f$ を $L$ -平滑な凸関数（最小点 $x^{\ast}$ をもつ）とし、最急降下法のステップ幅を $c = 1/2$ のアルミホ条件のバックトラッキング（初期値 $\bar{t}$ 、縮小率 $\beta$ ）で決める。 $t_{\min} = \min(\bar{t}, \beta/L)$ として $f(x_k) - p^{\ast} \leq \frac{\lVert x_0 - x^{\ast} \rVert^2}{2t_{\min}k}$ を示せ。

解答

命題 5.6 より採られる $t_k$ は $\min(\bar{t}, 2\beta(1 - 1/2)/L) = t_{\min}$ 以上で、(5.1) より $f(x_{k+1}) \leq f(x_k) - \frac{t_k}{2}\lVert g_k \rVert^2$ （ $g_k = \nabla f(x_k)$ ）。凸性 $f(x_k) \leq p^{\ast} + \langle g_k, x_k - x^{\ast} \rangle$ と合わせ、 $x_{k+1} = x_k - t_kg_k$ を使って定理 5.7 の証明と同様に平方完成すると

f(x_{k+1}) - p^{\ast} \leq \langle g_k, x_k - x^{\ast} \rangle - \frac{t_k}{2}\lVert g_k \rVert^2 = \frac{1}{2t_k}\bigl(\lVert x_k - x^{\ast} \rVert^2 - \lVert x_{k+1} - x^{\ast} \rVert^2\bigr)

左辺は $0$ 以上なので括弧内も $0$ 以上で、 $1/t_k \leq 1/t_{\min}$ より右辺は $\frac{1}{2t_{\min}}(\lVert x_k - x^{\ast} \rVert^2 - \lVert x_{k+1} - x^{\ast} \rVert^2)$ 以下。 $k = 0, \dots, K - 1$ について足し、 $f(x_k)$ が単調非増加であることを使えば $K(f(x_K) - p^{\ast}) \leq \frac{1}{2t_{\min}}\lVert x_0 - x^{\ast} \rVert^2$ 。

問題 5.3 ★★ $t > 0$ とする。(1) $\lambda, \mu > 0$ , $h(x) = \lambda\lVert x \rVert_1 + \frac{\mu}{2}\lVert x \rVert^2$ （エラスティックネットの罰則）について $\operatorname{prox}_{th}(v)_i = \frac{1}{1 + t\mu}S_{t\lambda}(v_i)$ を示せ。(2) $C = [0, 1]^n$ , $h = 0$ のとき $T_t(v)$ を求めよ。

解答

(1) 成分ごとに分かれ、 $\gamma = 1 + t\mu$ とすると

t\lambda\lvert u \rvert + \frac{t\mu}{2}u^2 + \frac{1}{2}(u - v)^2 = \gamma\Bigl(\frac{t\lambda}{\gamma}\lvert u \rvert + \frac{1}{2}\Bigl(u - \frac{v}{\gamma}\Bigr)^2\Bigr) + \frac{1}{2}\Bigl(v^2 - \frac{v^2}{\gamma}\Bigr)

で、最後の項は $u$ によらないから、命題 5.21 の証明より最小点は $S_{t\lambda/\gamma}(v/\gamma) = \operatorname{sign}(v)\max(\lvert v \rvert - t\lambda, 0)/\gamma = S_{t\lambda}(v)/\gamma$ 。 $\ell^1$ 罰則で小さい成分を $0$ にし、 $\ell^2$ 罰則で全体を $1/(1 + t\mu)$ 倍に縮める。

(2) $T_t(v) = P_C(v)$ は成分ごとの切り詰め $\min(\max(v_i, 0), 1)$ で（第2章例 2.5）、 $t$ によらない。

問題 5.4 ★★ 定理 5.23 の設定で、(1) $x^{\ast} \in C$ が $F$ の最小点であるための必要十分条件は $x^{\ast} = T_t(x^{\ast} - t\nabla f(x^{\ast}))$ であることを、(5.2) を使って示せ。(2) ラッソ（ $C = \mathbb{R}^n$ , $h = \lambda\lVert x \rVert_1$ ）について、(1) の条件を $g = \nabla f(x^{\ast}) = A^{\top}(Ax^{\ast} - b)$ の成分で書け。

解答

(1) $x^{+} = T_t(x^{\ast} - t\nabla f(x^{\ast}))$ とする。(5.2) で $x = z = x^{\ast}$ とすると $F(x^{+}) \leq F(x^{\ast}) - \frac{1}{2t}\lVert x^{\ast} - x^{+} \rVert^2$ 。 $x^{\ast}$ が最小点なら $F(x^{+}) \geq F(x^{\ast})$ なので $x^{+} = x^{\ast}$ 。逆に $x^{+} = x^{\ast}$ なら、(5.2) で $x = x^{\ast}$ とすると任意の $z \in C$ で $F(x^{\ast}) \leq F(z) + \frac{1}{2t}(\lVert z - x^{\ast} \rVert^2 - \lVert z - x^{\ast} \rVert^2) = F(z)$ 。

(2) 条件は各 $i$ で $x_i^{\ast} = S_{t\lambda}(x_i^{\ast} - tg_i)$ 。 $x_i^{\ast} > 0$ なら $x_i^{\ast} - tg_i - t\lambda = x_i^{\ast}$ より $g_i = -\lambda$ 、 $x_i^{\ast} < 0$ なら $g_i = \lambda$ 、 $x_i^{\ast} = 0$ なら $\lvert tg_i \rvert \leq t\lambda$ より $\lvert g_i \rvert \leq \lambda$ 。まとめて「 $x_i^{\ast} \neq 0$ なら $g_i = -\lambda\operatorname{sign}(x_i^{\ast})$ 、 $x_i^{\ast} = 0$ なら $\lvert g_i \rvert \leq \lambda$ 」で、 $t$ によらない。第2章定理 2.29（劣勾配による最適性条件）の条件 $0 \in g + \lambda\partial\lVert x^{\ast} \rVert_1$ と同じ形で、実装ではこの条件の破れの大きさを停止判定に使える。

問題 5.5 ★★ 次の判断は正しいか。(1) 最小二乗法の勾配法を学習率 $0.01$ で回していたが、ある特徴量（金額）の単位を千円から円に変えた（値が 1000 倍になった）ところ発散した。分析者は「単位を変えても最適な予測は同じはずなので、実装の誤りだ」と判断した。(2) 加速勾配法を実装したら、目的関数の値が途中で増える反復があった。分析者は「降下法なのに値が増えるのは誤りだ」と判断した。

解答

(1) 実装の誤りとは限らない。 $f(x) = \frac{1}{2}\lVert Ax - b \rVert^2$ で $A$ の第 $j$ 列 $a_j$ を 1000 倍すると、 $\lVert a_j \rVert^2$ は $10^6$ 倍になり、 $L = \lambda_{\max}(A^{\top}A) \geq e_j^{\top}A^{\top}Ae_j = \lVert a_j \rVert^2$ （レイリー商）なので新しい $L$ は $10^6\lVert a_j \rVert^2$ 以上になる。 $\lVert a_j \rVert^2 > 2 \times 10^{-4}$ なら（普通のデータではまず成り立つ） $t = 0.01 > 2/L$ で、安定条件（命題 5.9）が破れて発散する。最適な予測は変わらない（その係数が $1/1000$ 倍になるだけ）が、勾配法の速さと安定性は変わるのである。特徴量の標準化か、バックトラッキングで対処する。

(2) 誤り。加速法は単調な降下法ではなく、慣性で値が一時的に増えることがある（5.5 節）。保証されているのは $f(x_k) - p^{\ast} \leq 2L\lVert x_0 - x^{\ast} \rVert^2/(k + 1)^2$ という上界だけである。実装の確認には、慣性をなくすと値が単調に減ることや、小さな問題で既知の解に近づくことを調べるとよい。

問題 5.6 ★★ $C$ を空でない閉凸集合、 $f$ を $\mu$ -強凸かつ $L$ -平滑とし、 $x^{\ast}$ を $C$ 上の最小点とする。射影勾配法 $x_{k+1} = P_C(x_k - \frac{1}{L}\nabla f(x_k))$ について $\lVert x_{k+1} - x^{\ast} \rVert^2 \leq (1 - \frac{\mu}{L})\lVert x_k - x^{\ast} \rVert^2$ を示せ（ヒント：命題 5.19、射影の非拡大性、第2章定理 2.22・2.23）。

解答

命題 5.19 より $x^{\ast} = P_C(x^{\ast} - \frac{1}{L}\nabla f(x^{\ast}))$ 。射影の非拡大性（第2章定理 2.4）より、 $e = x_k - x^{\ast}$ , $\delta = \nabla f(x_k) - \nabla f(x^{\ast})$ として

\lVert x_{k+1} - x^{\ast} \rVert^2 \leq \Bigl\lVert e - \frac{1}{L}\delta \Bigr\rVert^2 = \lVert e \rVert^2 - \frac{2}{L}\langle \delta, e \rangle + \frac{1}{L^2}\lVert \delta \rVert^2

$L$ -平滑な凸関数の性質 $\langle \delta, e \rangle \geq \frac{1}{L}\lVert \delta \rVert^2$ （第2章定理 2.23 の (d)）より $\frac{1}{L^2}\lVert \delta \rVert^2 \leq \frac{1}{L}\langle \delta, e \rangle$ なので、右辺は $\lVert e \rVert^2 - \frac{1}{L}\langle \delta, e \rangle$ 以下で、強凸性 $\langle \delta, e \rangle \geq \mu\lVert e \rVert^2$ （第2章定理 2.22 の 3）よりさらに $(1 - \frac{\mu}{L})\lVert e \rVert^2$ 以下である。制約があっても、制約のない場合（定理 5.8）と同じ速さで距離が縮む。