LFTP 笔记整理：风险分解、优化与数学预备知识

来源：手写 PDF《LFTP优化-Ch1，Ch2》共 9 页。
整理说明：第 2 页与第 4 页内容重复，以下只保留一次；对明显的符号遗漏、转置和正负号问题按上下文进行了校正。

1. 学习问题中的三类误差

1.1 风险与正则化经验目标

给定预测函数 $f$，总体风险为

$R(f)=\mathbb E\bigl[\ell(y,f(x))\bigr].$

对参数化模型 $f_\theta$，训练时常考虑

$F(\theta) = \frac1n\sum_{i=1}^n \ell\bigl(y_i,f_\theta(x_i)\bigr) +\Omega(\theta),$

其中 $\Omega(\theta)$ 是正则项。若暂时不考虑正则项，则经验风险记为

$\widehat R(f) = \frac1n\sum_{i=1}^n \ell(y_i,f(x_i)).$

设模型类为

$\mathcal F_\Theta=\{f_\theta:\theta\in\Theta\}.$

1.2 估计误差：统计误差与优化误差

令

$\theta^*\in\arg\min_{\theta\in\Theta}R(f_\theta),$

而 $\widehat\theta$ 是算法实际返回的参数，不一定精确最小化经验风险。则

$\begin{aligned} R(f_{\widehat\theta})-R(f_{\theta^*}) ={}& \bigl[R(f_{\widehat\theta})-\widehat R(f_{\widehat\theta})\bigr]\\ &+\bigl[\widehat R(f_{\widehat\theta})-\widehat R(f_{\theta^*})\bigr]\\ &+\bigl[\widehat R(f_{\theta^*})-R(f_{\theta^*})\bigr]. \end{aligned}$

因此

$R(f_{\widehat\theta})-\inf_{\theta\in\Theta}R(f_\theta) \le 2\sup_{f\in\mathcal F_\Theta} \left|R(f)-\widehat R(f)\right| + \left[ \widehat R(f_{\widehat\theta}) - \inf_{\theta\in\Theta}\widehat R(f_\theta) \right].$

右侧分为两部分：

统计误差 $\displaystyle \operatorname{err}_{\mathrm{stat}} = 2\sup_{f\in\mathcal F_\Theta} \left|R(f)-\widehat R(f)\right|.$
优化误差 $\displaystyle \operatorname{err}_{\mathrm{opt}} = \widehat R(f_{\widehat\theta}) - \inf_{\theta\in\Theta}\widehat R(f_\theta).$

统计误差通常由函数类复杂度控制。对有限函数类可以使用集中不等式与并合界；对无限函数类，可使用覆盖数或 Rademacher 复杂度。经过对称化后，常出现形如

$2\operatorname{Rad}_n(\mathcal F_\Theta)$

的控制项，典型样本尺度为 $O(n^{-1/2})$。

实际训练中，$f_{\widehat\theta}$ 往往是由 GD 或 SGD 在有限步后得到的，而不是经验风险的精确极小点。用于泛化误差分析时，通常没有必要把优化误差压得远小于统计误差；令二者达到同一数量级即可。

1.3 逼近误差

相对于所有可测预测函数的最优风险，还存在

$\operatorname{err}_{\mathrm{approx}} = \inf_{\theta\in\Theta}R(f_\theta) - \inf_{f}R(f).$

于是总超额风险可以概括为

$\boxed{ R(f_{\widehat\theta})-\inf_f R(f) \le \operatorname{err}_{\mathrm{stat}} + \operatorname{err}_{\mathrm{opt}} + \operatorname{err}_{\mathrm{approx}}. }$

三者的含义分别是：

统计误差：有限样本导致经验风险偏离总体风险；
优化误差：有限计算步数导致未能精确求解经验优化问题；
逼近误差：模型类本身不够丰富。

1.4 常见优化收敛速度

在相应的标准假设下，常见量级为：

算法与条件	典型收敛速度
GD，凸且光滑	$F(\theta_t)-F^*=O(t^{-1})$
GD，强凸且光滑	$F(\theta_t)-F^*=O(\rho^t)$，$0<\rho<1$
SGD，一般凸问题	$O(t^{-1/2})$
SGD，强凸问题	$O(t^{-1})$

2. 最小二乘问题上的梯度下降

考虑

$F(\theta)=\frac1{2n}\|\Phi\theta-y\|_2^2.$

其梯度和 Hessian 为

$\nabla F(\theta) = \frac1n\Phi^\top(\Phi\theta-y), \qquad \nabla^2F(\theta) = H:=\frac1n\Phi^\top\Phi.$

梯度下降迭代为

$\theta_t = \theta_{t-1}-\alpha\nabla F(\theta_{t-1}).$

设 $\theta_*$ 为一个极小点，则 $\nabla F(\theta_*)=0$。因此

$\begin{aligned} \theta_t-\theta_* &= \theta_{t-1}-\theta_* - \alpha\frac1n\Phi^\top\Phi(\theta_{t-1}-\theta_*)\\ &=(I-\alpha H)(\theta_{t-1}-\theta_*). \end{aligned}$

递推得到

$\theta_t-\theta_* =(I-\alpha H)^t(\theta_0-\theta_*).$

若 $H$ 的特征值位于 $[\mu,L]$，其中 $0<\mu\le L$，则

$\|\theta_t-\theta_*\|_2^2 \le \max_{\lambda\in[\mu,L]}|1-\alpha\lambda|^{2t} \|\theta_0-\theta_*\|_2^2.$

最优常步长

取

$\alpha=\frac{2}{\mu+L},$

可以平衡区间两端的收缩因子：

$\max_{\lambda\in[\mu,L]}|1-\alpha\lambda| = \frac{L-\mu}{L+\mu}.$

令条件数

$\kappa=\frac{L}{\mu},$

则

$\|\theta_t-\theta_*\|_2^2 \le \left(\frac{\kappa-1}{\kappa+1}\right)^{2t} \|\theta_0-\theta_*\|_2^2.$

进一步，

$\left(\frac{\kappa-1}{\kappa+1}\right)^{2t} \le \left(1-\frac1\kappa\right)^{2t} \le \exp\left(-\frac{2t}{\kappa}\right).$

因此条件数越大，收敛越慢；当 $\kappa$ 有界时，梯度下降呈线性（几何）收敛。

3. 凸性、光滑性、强凸性与 PL 不等式

3.1 凸函数

若 $F$ 可微，则凸性等价于

$F(\eta) \ge F(\theta) + \nabla F(\theta)^\top(\eta-\theta).$

取 $\eta=\theta_*$ 可得

$F(\theta)-F(\theta_*) \le \nabla F(\theta)^\top(\theta-\theta_*).$

3.2 $L$-光滑

$F$ 为 $L$-光滑，意味着

$F(\eta) \le F(\theta) + \nabla F(\theta)^\top(\eta-\theta) + \frac L2\|\eta-\theta\|_2^2.$

3.3 $\mu$-强凸

$F$ 为 $\mu$-强凸，意味着

$F(\eta) \ge F(\theta) + \nabla F(\theta)^\top(\eta-\theta) + \frac\mu2\|\eta-\theta\|_2^2.$

3.4 Łojasiewicz / Polyak–Łojasiewicz 不等式

强凸函数满足

$\boxed{ \|\nabla F(\theta)\|_2^2 \ge 2\mu\bigl(F(\theta)-F^*\bigr). }$

证明：由强凸性，对任意 $\eta$，

$F(\eta) \ge F(\theta) + \nabla F(\theta)^\top(\eta-\theta) + \frac\mu2\|\eta-\theta\|_2^2.$

右侧关于 $\eta$ 的二次函数在

$\widetilde\eta = \theta-\frac1\mu\nabla F(\theta)$

处取最小值。代入得

$F(\widetilde\eta) \ge F(\theta)-\frac1{2\mu}\|\nabla F(\theta)\|_2^2.$

更直接地，对上式两端关于 $\eta$ 取下确界：

$F^* \ge F(\theta)-\frac1{2\mu}\|\nabla F(\theta)\|_2^2,$

整理即得结论。

4. 线性代数技巧

4.1 秩一扰动矩阵的逆

设 $\mathbf 1_n\in\mathbb R^n$ 为全 1 向量，且

$1+n\alpha\ne0.$

则

$\boxed{ (I+\alpha\mathbf 1_n\mathbf 1_n^\top)^{-1} = I- \frac{\alpha}{1+n\alpha} \mathbf 1_n\mathbf 1_n^\top. }$

理由是：

在 $\operatorname{span}\{\mathbf 1_n\}$ 上，矩阵的特征值为 $1+n\alpha$；
在 $\mathbf 1_n^\perp$ 上，特征值为 $1$。

也可以直接将候选逆矩阵与原矩阵相乘验证。

这是 Sherman–Morrison / Woodbury 公式的一个特例。

4.2 Schur 补与分块矩阵求逆

设

$M= \begin{pmatrix} A&B\\ C&D \end{pmatrix}.$

若 $A$ 可逆，定义 $A$ 的 Schur 补

$M/A=D-CA^{-1}B.$

若 $D$ 可逆，定义 $D$ 的 Schur 补

$M/D=A-BD^{-1}C.$

以 $A$ 为主块的分解

若 $A$ 与 $M/A$ 均可逆，则

$M = \begin{pmatrix} I&0\\ CA^{-1}&I \end{pmatrix} \begin{pmatrix} A&0\\ 0&M/A \end{pmatrix} \begin{pmatrix} I&A^{-1}B\\ 0&I \end{pmatrix}.$

因此

$M^{-1} = \begin{pmatrix} I&-A^{-1}B\\ 0&I \end{pmatrix} \begin{pmatrix} A^{-1}&0\\ 0&(M/A)^{-1} \end{pmatrix} \begin{pmatrix} I&0\\ -CA^{-1}&I \end{pmatrix},$

即

$\boxed{ M^{-1} = \begin{pmatrix} A^{-1}+A^{-1}B(M/A)^{-1}CA^{-1} &-A^{-1}B(M/A)^{-1}\\ -(M/A)^{-1}CA^{-1} &(M/A)^{-1} \end{pmatrix}. }$

以 $D$ 为主块的公式

若 $D$ 与 $M/D$ 均可逆，则

$\boxed{ M^{-1} = \begin{pmatrix} (M/D)^{-1} &-(M/D)^{-1}BD^{-1}\\ -D^{-1}C(M/D)^{-1} &D^{-1}+D^{-1}C(M/D)^{-1}BD^{-1} \end{pmatrix}. }$

Woodbury 型恒等式

比较上述两个分块逆公式，可得

$(A-BD^{-1}C)^{-1} = A^{-1} +A^{-1}B(D-CA^{-1}B)^{-1}CA^{-1},$

以及

$(D-CA^{-1}B)^{-1} = D^{-1} +D^{-1}C(A-BD^{-1}C)^{-1}BD^{-1}.$

常用特例为

$\boxed{ (I+BB^\top)^{-1} = I-B(I+B^\top B)^{-1}B^\top. }$

右乘 $B$ 后还有

$(I+BB^\top)^{-1}B = B(I+B^\top B)^{-1}.$

4.3 分块行列式

在上述可逆条件下，

$\boxed{ \det M = \det(A)\det(M/A) = \det(D)\det(M/D). }$

4.4 高斯向量的条件均值与条件协方差

若联合高斯向量

$\begin{pmatrix}x\\y\end{pmatrix} \sim \mathcal N\left( \begin{pmatrix}\mu_x\\\mu_y\end{pmatrix}, \begin{pmatrix} \Sigma_{xx}&\Sigma_{xy}\\ \Sigma_{yx}&\Sigma_{yy} \end{pmatrix} \right),$

则给定 $x=x'$ 后，

$\boxed{ \mu_{y\mid x'} = \mu_y+ \Sigma_{yx}\Sigma_{xx}^{-1}(x'-\mu_x), }$

$\boxed{ \Sigma_{y\mid x} = \Sigma_{yy} - \Sigma_{yx}\Sigma_{xx}^{-1}\Sigma_{xy}. }$

条件协方差正是一个 Schur 补。

4.5 SVD 与特征值分解

设 $X$ 的薄 SVD 为

$X=U\Sigma V^\top = \sum_{i=1}^r\sigma_i u_i v_i^\top.$

于是

$XX^\top =U\Sigma^2U^\top = \sum_{i=1}^r\sigma_i^2u_i u_i^\top,$

$X^\top X =V\Sigma^2V^\top = \sum_{i=1}^r\sigma_i^2v_i v_i^\top.$

因此：

$u_i$ 是 $XX^\top$ 的特征向量，特征值为 $\sigma_i^2$；
$v_i$ 是 $X^\top X$ 的特征向量，特征值为 $\sigma_i^2$。

再考虑对称扩张

$\mathcal M = \begin{pmatrix} 0&X\\ X^\top&0 \end{pmatrix}.$

由 $Xv_i=\sigma_i u_i$、$X^\top u_i=\sigma_i v_i$，有

$\mathcal M \frac1{\sqrt2} \begin{pmatrix}u_i\\v_i\end{pmatrix} = \sigma_i \frac1{\sqrt2} \begin{pmatrix}u_i\\v_i\end{pmatrix},$

$\mathcal M \frac1{\sqrt2} \begin{pmatrix}u_i\\-v_i\end{pmatrix} = -\sigma_i \frac1{\sqrt2} \begin{pmatrix}u_i\\-v_i\end{pmatrix}.$

因此 $\mathcal M$ 的非零特征值为奇异值 $\sigma_i$ 及其相反数 $-\sigma_i$。

5. 向量与矩阵函数求导

以下使用 Frobenius 内积

$\langle A,B\rangle_F=\operatorname{tr}(A^\top B),$

并通过

$df(X)=\langle \nabla_X f(X),dX\rangle_F$

识别梯度。

5.1 二次型

设

$F(\theta) = \frac12\theta^\top A\theta-b^\top\theta.$

则

$\boxed{ \nabla F(\theta) = \frac12(A+A^\top)\theta-b, }$

$\boxed{ \nabla^2F(\theta) = \frac12(A+A^\top). }$

若 $A=A^\top$，则简化为

$\nabla F(\theta)=A\theta-b, \qquad \nabla^2F(\theta)=A.$

5.2 最小二乘

$F(\theta) = \frac1{2n}\|y-X\theta\|_2^2.$

展开为

$F(\theta) = \frac1{2n} \left( y^\top y-2y^\top X\theta+\theta^\top X^\top X\theta \right).$

因此

$\boxed{ \nabla F(\theta) = -\frac1nX^\top(y-X\theta) = \frac1nX^\top(X\theta-y), }$

$\boxed{ \nabla^2F(\theta) = \frac1nX^\top X. }$

5.3 Logistic 回归

令 $x_i^\top$ 为 $X$ 的第 $i$ 行，$y_i\in\{-1,1\}$，并定义

$F(\theta) = \frac1n\sum_{i=1}^n \log\left(1+\exp(-y_ix_i^\top\theta)\right).$

记

$\varphi(t)=\log(1+e^t), \qquad \varphi'(t)=\sigma(t)=\frac1{1+e^{-t}},$

以及

$\varphi''(t) = \sigma(t)\sigma(-t).$

对第 $i$ 项求导：

$\nabla_\theta \varphi(-y_ix_i^\top\theta) = -y_i\sigma(-y_ix_i^\top\theta)x_i.$

定义 $g\in\mathbb R^n$：

$g_i =-y_i\sigma(-y_ix_i^\top\theta),$

则

$\boxed{ \nabla F(\theta) = \frac1nX^\top g. }$

再定义

$h_i = \sigma(y_ix_i^\top\theta) \sigma(-y_ix_i^\top\theta),$

则

$\boxed{ \nabla^2F(\theta) = \frac1nX^\top\operatorname{Diag}(h)X. }$

由于 $h_i\ge0$，Hessian 半正定，所以 Logistic 回归目标是凸函数。

5.4 常见迹函数

线性迹函数

若

$f(X)=\operatorname{tr}(A^\top X),$

则

$df=\operatorname{tr}(A^\top dX) =\langle A,dX\rangle_F,$

故

$\boxed{\nabla_X f(X)=A.}$

若

$f(X)=\operatorname{tr}(AXB),$

利用迹的循环不变性，

$df =\operatorname{tr}(A\,dX\,B) =\operatorname{tr}(BA\,dX),$

故

$\boxed{ \nabla_X f(X)=A^\top B^\top. }$

矩阵二次型

若

$f(X)=\operatorname{tr}(X^\top AX),$

则

$\boxed{ \nabla_X f(X)=AX+A^\top X. }$

若 $A$ 对称，则

$\nabla_X f(X)=2AX.$

更一般地，若

$f(X)=\operatorname{tr}(X^\top A X B),$

则

$\boxed{ \nabla_X f(X)=AXB+A^\top X B^\top. }$

5.5 逆矩阵的微分

由

$XX^{-1}=I$

两侧求微分：

$(dX)X^{-1}+X\,d(X^{-1})=0.$

因此

$\boxed{ d(X^{-1}) =-X^{-1}(dX)X^{-1}. }$

5.6 $\operatorname{tr}(AX^{-1})$ 的梯度

令

$f(X)=\operatorname{tr}(AX^{-1}).$

则

$\begin{aligned} df &=\operatorname{tr}\bigl(A\,d(X^{-1})\bigr)\\ &=-\operatorname{tr}\bigl(AX^{-1}(dX)X^{-1}\bigr)\\ &=-\operatorname{tr}\bigl(X^{-1}AX^{-1}dX\bigr). \end{aligned}$

所以一般情形下

$\boxed{ \nabla_X f(X) =-X^{-\top}A^\top X^{-\top}. }$

若 $A$ 与 $X$ 均为对称矩阵，则

$\boxed{ \nabla_X\operatorname{tr}(AX^{-1}) =-X^{-1}AX^{-1}. }$

5.7 行列式与对数行列式

Jacobi 公式为

$\boxed{ d\det X = \det X\,\operatorname{tr}(X^{-1}dX). }$

可由

$\det(X+tH) = \det X\,\det(I+tX^{-1}H)$

以及

$\left.\frac{d}{dt}\det(I+tB)\right|_{t=0} =\operatorname{tr}(B)$

得到。

因此

$\boxed{ \nabla_X\det X = \det(X)X^{-\top}. }$

进一步，

$d\log\det X = \operatorname{tr}(X^{-1}dX),$

故

$\boxed{ \nabla_X\log\det X =X^{-\top}. }$

若变量限制在可逆对称矩阵上，则分别写为

$\nabla_X\det X=\det(X)X^{-1}, \qquad \boxed{ \nabla_X\log\det X=X^{-1}. }$

6. 标准高斯尾概率的上下界

设

$Z\sim\mathcal N(0,1), \qquad \phi(x)=\frac1{\sqrt{2\pi}}e^{-x^2/2}.$

目标是证明，对任意 $t>0$，

$\boxed{ \frac14e^{-t^2} \le \mathbb P(Z>t) \le e^{-t^2/2}. }$

6.1 上界

对任意 $s>0$，由 Chernoff 方法，

$\mathbb P(Z>t) = \mathbb P(e^{sZ}>e^{st}) \le e^{-st}\mathbb E[e^{sZ}].$

标准高斯的矩母函数为

$\mathbb E[e^{sZ}]=e^{s^2/2}.$

因此

$\mathbb P(Z>t) \le \exp\left(-st+\frac{s^2}{2}\right).$

取 $s=t$ 得

$\mathbb P(Z>t) \le e^{-t^2/2}.$

6.2 下界：$0\le t\le1$

因为 $\phi(x)\le\phi(0)=1/\sqrt{2\pi}$，所以

$\mathbb P(Z>t) = \frac12-\int_0^t\phi(x)\,dx \ge \frac12-\frac{t}{\sqrt{2\pi}}.$

只需证明

$\frac12-\frac{t}{\sqrt{2\pi}} \ge \frac14e^{-t^2}.$

定义

$f(t) = \frac12-\frac{t}{\sqrt{2\pi}} - \frac14e^{-t^2}.$

则

$f'(t) =-\frac1{\sqrt{2\pi}} + \frac t2e^{-t^2}.$

函数 $te^{-t^2}$ 在 $t=1/\sqrt2$ 处达到最大值 $1/\sqrt{2e}$，故

$\frac t2e^{-t^2} \le \frac1{2\sqrt{2e}} < \frac1{\sqrt{2\pi}}.$

所以 $f'(t)<0$。于是 $f$ 在 $[0,1]$ 上递减，而

$f(1) = \frac12-\frac1{\sqrt{2\pi}}-\frac1{4e}>0.$

故 $f(t)>0$，从而

$\mathbb P(Z>t) \ge \frac14e^{-t^2}, \qquad 0\le t\le1.$

6.3 下界：$t>1$

记

$Q(t)=\mathbb P(Z>t)=\int_t^\infty\phi(x)\,dx.$

利用 $\phi'(x)=-x\phi(x)$，分部积分得

$\begin{aligned} Q(t) &= \int_t^\infty \frac1x\,x\phi(x)\,dx\\ &=-\int_t^\infty\frac1x\phi'(x)\,dx\\ &= \frac{\phi(t)}{t} - \int_t^\infty\frac{\phi(x)}{x^2}\,dx. \end{aligned}$

当 $x\ge t$ 时，$x^{-2}\le t^{-2}$，因此

$Q(t) \ge \frac{\phi(t)}t-\frac{Q(t)}{t^2}.$

整理得到经典 Mills 比下界

$\boxed{ Q(t) \ge \frac{t}{1+t^2}\phi(t) = \frac{t}{\sqrt{2\pi}(1+t^2)}e^{-t^2/2}. }$

最后只需验证，对 $t\ge1$，

$\frac{t}{\sqrt{2\pi}(1+t^2)}e^{-t^2/2} \ge \frac14e^{-t^2}.$

等价于

$G(t) := \frac{4t}{\sqrt{2\pi}(1+t^2)}e^{t^2/2} \ge1.$

其对数导数为

$\frac{d}{dt}\log G(t) = \frac1t-\frac{2t}{1+t^2}+t = \frac{1+t^4}{t(1+t^2)}>0.$

所以 $G$ 在 $[1,\infty)$ 上递增，并且

$G(1) = \sqrt{\frac{2e}{\pi}}>1.$

故对所有 $t>1$，同样有

$\mathbb P(Z>t) \ge \frac14e^{-t^2}.$

综上，

$\boxed{ \frac14e^{-t^2} \le \mathbb P(Z>t) \le e^{-t^2/2}, \qquad t>0. }$