最小二乗損失に対する勾配降下法の収束

$X\in\mathbb{R}^{n\times d}$ の列ベクトルは線形独立とし、$L(\boldsymbol{w})=\frac{1}{2n}\|X\boldsymbol{w}-\boldsymbol{y}\|^2$、$A:=\frac{1}{n}X^{\mathsf{T}}X$ とおく。このとき $A$ は対称正定値であり、その固有値を重複を込めて $0<\lambda_1\le\lambda_2\le\cdots\le\lambda_d$ と並べる。$\boldsymbol{w}^{\star}$ を 系 3.4 の唯一の最小点、$\eta>0$ を定数とし、点列を $\boldsymbol{w}_{k+1}=\boldsymbol{w}_k-\eta\nabla L(\boldsymbol{w}_k)$ で定める。

1. すべての初期点 $\boldsymbol{w}_0\in\mathbb{R}^d$ に対して $\boldsymbol{w}_k\to\boldsymbol{w}^{\star}$ となるための必要十分条件は $\eta < 2/\lambda_d$ である。
2. $\eta < 2/\lambda_d$ のとき、$\rho(\eta):=\max\{|1-\eta\lambda_1|,\,|1-\eta\lambda_d|\}$ とおくと $\rho(\eta)<1$ であり、すべての $k\ge 0$ で $\|\boldsymbol{w}_k-\boldsymbol{w}^{\star}\| \le \rho(\eta)^k\,\|\boldsymbol{w}_0-\boldsymbol{w}^{\star}\|$ が成り立つ。
3. $\rho(\eta)$ を最小にする学習率は $\eta^{\star}=\dfrac{2}{\lambda_1+\lambda_d}$ であり、そのとき $\rho(\eta^{\star})=\dfrac{\kappa-1}{\kappa+1}$ である。ここで $\kappa:=\lambda_d/\lambda_1$ は $A$ の条件数である。