機械学習の数学

滑らかさにより、各勾配ステップは勾配の大きさの二乗に比例する量だけ $L$ を減少させることが保証されるため、$L(\theta_k)$ は決して増加しない。凸性により、そのステップごとの減少量をまだ残っているギャップ $L(\theta_k) - L(\theta^\star)$ と比較できる。$K$ ステップにわたって保証された減少量を足し合わせる — 望遠鏡和 — と、総減少量が有界であることが分かり、非増加数列における最良点は平均以上に良いはずなので、最終的なギャップは $1/K$ のように縮小するはずである。

$L$-滑らかさにより、任意の $x, y$ に対して: $L(y) \le L(x) + \nabla L(x)^\top (y-x) + \dfrac{L}{2}\|y-x\|^2$。$y = \theta_{k+1} = \theta_k - \dfrac{1}{L}\nabla L(\theta_k)$、$x = \theta_k$ とおくと降下補題が得られる: $L(\theta_{k+1}) \le L(\theta_k) - \dfrac{1}{2L}\|\nabla L(\theta_k)\|^2$。

$L$ の凸性により: $L(\theta_k) \le L(\theta^\star) + \nabla L(\theta_k)^\top(\theta_k - \theta^\star)$。これを降下補題に加えると: $L(\theta_{k+1}) - L(\theta^\star) \le \nabla L(\theta_k)^\top(\theta_k - \theta^\star) - \dfrac{1}{2L}\|\nabla L(\theta_k)\|^2$。

右辺を平方完成すると: $\nabla L(\theta_k)^\top(\theta_k - \theta^\star) - \dfrac{1}{2L}\|\nabla L(\theta_k)\|^2 = \dfrac{L}{2}\left(\|\theta_k - \theta^\star\|^2 - \left\|\theta_k - \theta^\star - \dfrac{1}{L}\nabla L(\theta_k)\right\|^2\right) = \dfrac{L}{2}\left(\|\theta_k - \theta^\star\|^2 - \|\theta_{k+1} - \theta^\star\|^2\right)$、なぜなら $\theta_{k+1} - \theta^\star = \theta_k - \theta^\star - \dfrac{1}{L}\nabla L(\theta_k)$ であるから。

よって $L(\theta_{k+1}) - L(\theta^\star) \le \dfrac{L}{2}\left(\|\theta_k - \theta^\star\|^2 - \|\theta_{k+1} - \theta^\star\|^2\right)$。これを $k = 0, \dots, K-1$ について足し合わせると、右辺は望遠鏡式に縮約されて $\dfrac{L}{2}\left(\|\theta_0 - \theta^\star\|^2 - \|\theta_K - \theta^\star\|^2\right) \le \dfrac{L}{2}\|\theta_0 - \theta^\star\|^2$ となる。

降下補題はまた $L(\theta_k)$ が非増加であることも示すので、$L(\theta_K)$ は $L(\theta_1), \dots, L(\theta_K)$ の平均以下である: $L(\theta_K) - L(\theta^\star) \le \dfrac{1}{K}\sum_{k=1}^K \left(L(\theta_k) - L(\theta^\star)\right) \le \dfrac{L\|\theta_0 - \theta^\star\|^2}{2K}$ となり、まさに主張された評価式が得られる。

特異値は $A$ が各直交方向 $v_i$ に沿ってベクトルをどれだけ引き伸ばすかを測る；最大のものを残し最小のものを捨てることは、$A$ が最も引き伸ばさない方向を捨てることに等しい。他のどのランク $k$ 行列 $B$ も、上位 $k+1$ 個の特異方向のうちいずれかの方向を再現し損なわざるを得ない（それらは $k$ 次元の像に収まるには多すぎる）、そしてその失敗には少なくとも $\sigma_{k+1}$ の代償がかかる。

達成可能性。 $U, V$ が正規直交な列を持つため、$\|A - A_k\|_2 = \|U(\Sigma - \Sigma_k)V^\top\|_2 = \|\Sigma - \Sigma_k\|_2$ であり、ここで $\Sigma_k$ は上位 $k$ 個の特異値を残し残りをゼロにしたものである。$\Sigma - \Sigma_k$ は成分 $0, \dots, 0, \sigma_{k+1}, \dots, \sigma_r$ を持つ対角行列であるため、その作用素ノルムは最大成分 $\sigma_{k+1}$ である。

最適性。 $\operatorname{rank}(B) \le k$ を満たす任意の行列 $B$ をとる；その零空間（核）の次元は少なくとも $n - k$ である。$S = \operatorname{span}(v_1, \dots, v_{k+1})$ を $(k+1)$ 次元部分空間とする。$\dim(\ker B) + \dim(S) \ge (n-k) + (k+1) = n+1 > n$ であるため、この2つの部分空間は原点以外でも交わらねばならない: $Bz = 0$ を満たす単位ベクトル $z \in S$ が存在する。

$z = \sum_{i=1}^{k+1} c_i v_i$（$\sum_{i=1}^{k+1} c_i^2 = 1$、$z$ が単位ノルムを持ち $v_i$ が正規直交であるため）と書く。$Bz = 0$ であるから、$u_i$ の正規直交性を用いて $\|(A-B)z\| = \|Az\| = \left\|\sum_{i=1}^{k+1} c_i \sigma_i u_i\right\| = \sqrt{\sum_{i=1}^{k+1} c_i^2 \sigma_i^2}$ となる。

$i \le k+1$ に対して $\sigma_i \ge \sigma_{k+1}$ であるため、$\sum_{i=1}^{k+1} c_i^2 \sigma_i^2 \ge \sigma_{k+1}^2 \sum_{i=1}^{k+1} c_i^2 = \sigma_{k+1}^2$。よって、ランク $\le k$ の任意の行列 $B$ に対して $\|A-B\|_2 \ge \|(A-B)z\| \ge \sigma_{k+1}$ となり、達成可能性と合わせて定理が証明される。