这里回顾第二章的第一部分，这部分主要讨论训练集无限的情况下ERM的理论上界。

课程主页：

课程视频：

课件：

Chapter 2 Asymptotic Analysis

在本章中，我们使用渐近方法(即假设训练样本数$n\to \infty$)来得到ERM的上界。 然后，我们将这些结果实例化为损失函数为最大似然的情况，并讨论渐近的局限性。(在以后的章节中，我们将假设$n$有限并提供非渐近分析。)

2.1 经验风险最小化的渐近

对于ERM的渐进分析，我们希望证明其excess risk有如下上界(其中$c$是依赖于问题的常数)：

令$\left\{\left(x^{(1)}, y^{(1)}\right), \cdots,\left(x^{(n)}, y^{(n)}\right)\right\}$是训练集，$\mathcal{H}=\left\{h_\theta: \theta \in \mathbb{R}^p\right\}$是参数化的hypothesis functions集合。$\hat \theta$是ERM的minimizer，$\theta^{\star}$是population risk的minimizer，即：

注意到此时excess risk可以改写为：

那么可以给出如下定理：

定理2.1

假设：

  1. $\hat{\theta} \stackrel{p}{\rightarrow} \theta^{\star}$，当$n\to \infty$(一致性)；
  2. $\nabla^2 L\left(\theta^{\star}\right)$满秩；
  3. 其他适当的正则性条件成立；

那么，

  1. $\sqrt{n}\left(\hat{\theta}-\theta^{\star}\right)=O_P(1)$，即，$\forall \epsilon > 0$，存在$M$，使得$\sup _n \mathbb{P}\left(\left|\sqrt{n}\left(\hat{\theta}-\theta^{\star}\right)\right|_2>M\right)<\epsilon$。(这意味着$\left\{\sqrt{n}\left(\hat{\theta}-\theta^{\star}\right)\right\}$依概率有界。)
  2. $\sqrt{n}\left(\hat{\theta}-\theta^{\star}\right) \stackrel{d}{\rightarrow} \mathcal{N}\left(0,\left(\nabla^2 L\left(\theta^{\star}\right)\right)^{-1} \operatorname{Cov}\left(\nabla \ell\left((x, y), \theta^{\star}\right)\right)\left(\nabla^2 L\left(\theta^{\star}\right)\right)^{-1}\right)$。
  3. $n\left(L(\hat{\theta})-L\left(\theta^{\star}\right)\right)=O_P(1)$。
  4. $n\left(L(\hat{\theta})-L\left(\theta^{\star}\right)\right) \stackrel{d}{\rightarrow} \frac{1}{2}|S|_2^2 \text { where } S \sim \mathcal{N}\left(0,\left(\nabla^2 L\left(\theta^{\star}\right)\right)^{-1 / 2} \operatorname{Cov}\left(\nabla \ell\left((x, y), \theta^{\star}\right)\right)\left(\nabla^2 L\left(\theta^{\star}\right)\right)^{-1 / 2}\right)$。
  5. $\lim _{n \rightarrow \infty} \mathbb{E}\left[n\left(L(\hat{\theta})-L\left(\theta^{\star}\right)\right)\right]=\frac{1}{2} \operatorname{tr}\left(\nabla^2 L\left(\theta^{\star}\right)^{-1} \operatorname{Cov}\left(\nabla \ell\left((x, y), \theta^{\star}\right)\right)\right)$。

核心结论：

  • $\hat \theta - \theta^{\star}$以$1/\sqrt n$速率递减；
  • $L(\theta)-L(\theta^{\star})$以$1/n$速率递减；

准备工作

在开始证明之前，给如一个定理和引理。

定理2.2(中心极限定理)

令$X_1, \cdots, X_n$是i.i.d.随机变量，$\hat{X}=\frac{1}{n} \sum_{i=1}^n X_i$，协方差$\Sigma$有界。那么，随着$n\to \infty$，我们有：

  1. $\hat{X} \stackrel{p}{\rightarrow} \mathbb{E}[X]$。
  2. $\sqrt{n}(\hat{X}-\mathbb{E}[X]) \stackrel{d}{\rightarrow} \mathcal{N}(0, \Sigma)$。特别地，$\sqrt{n}(\hat{X}-\mathbb{E}[X])=O_P(1)$。

引理2.3

  1. 如果$Z \sim N(0, \Sigma)$，$A$是确定性矩阵，那么。
  2. 如果$Z \sim N(0, \Sigma^{-1})$，$Z\in \mathbb R^p$，那么$Z^{\top} \Sigma Z \sim \chi^2(p)$，其中$\chi^2(p)$是自由度为$p$的卡方分布；

只证明第二个结论，第一个结论在概率论中都有介绍。

根据卡方分布定理，如果$X\sim \mathcal N(0, I_p)$，那么$X^{\top} X\sim \chi^2(p)$。因为$Z \sim \mathcal N(0, \Sigma^{-1})$，根据引理1可得$\sqrt{\Sigma} Z \sim \mathcal N(0, \sqrt{\Sigma}\Sigma^{-1}\sqrt{\Sigma}^{\top})=\mathcal (0, I_p)$，因此$Z^{\top }\sqrt{\Sigma}^{\top}\sqrt{\Sigma} Z=Z^{\top} \Sigma Z \sim \chi^2(p)$。

引理2.4

如果$X_n \stackrel{d}{\rightarrow} X$，那么$X_n=O_P(1)$。

证明：

$X_n \stackrel{d}{\rightarrow} X$等价于$\mathbb{P}\left(X_n \leq t\right) \rightarrow \mathbb{P}(X \leq t)$，那么：

根据该引理，定理的2，4可以推出1，3，所以后续只需证明2，4。

证明

因为$\hat \theta$最小化$\hat{L}(\hat{\theta})$，所以$\nabla \hat{L}(\hat{\theta})=0$，将$\nabla \hat{L}$在$\theta^{\star}$附近泰勒展开可得：

变换后可得：

令：

根据中心极限定理可得：

注意到$\nabla L\left(\theta^{\star}\right)=0$，因此：

根据大数定律可得$\nabla^2 \widehat{L}\left(\theta^{\star}\right) \stackrel{p}{\rightarrow} \nabla^2 L\left(\theta^{\star}\right)$。带入公式(1)，最终得到：

即结论2。

为了证明结论4，将$L$在$\theta^{\star}$展开可得：

变换后可得：

最后一步是根据$\langle v, A v\rangle=v^{\top} A v=\left|A^{1 / 2} v\right|_2^2$。

令$S=\nabla^2 L\left(\theta^{\star}\right)^{1 / 2} \sqrt{n}\left(\hat{\theta}-\theta^{\star}\right)$，那么根据公式2可得：

带入公式3可得：

这就完成了结论4。

关于结论5，直接计算可得：

小结

这里对证明做个简单小结：

  1. 将$\hat L(\theta)$在$\theta^{\star}$附近展开，取$\theta=\hat \theta$；
  2. 将$ L(\theta)$在$\hat \theta$附近展开，取$\theta=\theta ^{\star}$；