机器学习的数学

光滑性保证每次梯度步骤使 $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}$。

最优性。 设 $B$ 为满足 $\operatorname{rank}(B) \le k$ 的任意矩阵；其零空间（核）维数至少为 $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$，这两个子空间必定在原点之外也有交集：存在单位向量 $z \in S$ 使得 $Bz = 0$。

写成 $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}$，结合可达性即证明了该定理。