用对称化与chaining技术bound经验过程上确界的期望（Guntuboyina理论统计学笔记）

UC Berkeley 的课程编号规则是：编号 1–99 的为初级本科课程，编号 100–199 的为高级本科课程，编号 200–299 的为研究生课程。

本课程是 UC Berkeley 理论统计的两门课之一，另外一门是 210A。老师是 UC Berkeley 的副教授。本课程有讲义，讲义typo较多，公式引用有少量错乱。

这门课的第一部分主要讲经验过程理论，讲得比较基础，优点是讲的线索清晰，并且是从动机出发的。

对称化

现在我们考虑如何bound $\mathrm{E}{\sup }_f|(P_n-P)f|$，需要用到对称化技巧和chaining技巧。

对称化就是把$\mathrm{E}{\sup }_f|(P_n-P)f|$转变成 Rademacher 复杂度进行度量。Rademacher 复杂度是针对某个集合的，比如$\mathcal{F}$，定义是先引入一系列相互独立且独立于$X_i$’s的 Rademacher 随机变量${ϵ}_i$’s，然后定义$\mathcal{F}$ 的 Rademacher 复杂度为
$$R_n(\mathcal{F}):=\mathrm{E}\underset{f\in \mathcal{F}}{\sup }\frac{1}{n}|\sum _{i=1}^n{ϵ}_{i}f(X_i)|$$
这里的期望是对${ϵ}_i$’s和$X_i$’s求。

对称化引理说的是：
$$\mathrm{E}\underset{f\in \mathcal{F}}{\sup }|(P_n-P)f|\le 2\mathrm{E}\underset{f\in \mathcal{F}}{\sup }\frac{1}{n}|\sum _{i=1}^n{ϵ}_{i}f(X_i)|=2R_n(\mathcal{F})$$
于是，bound $\mathrm{E}{\sup }_f|(P_n-P)f|$的问题转化成了 bound $R_n(\mathcal{F})$。一种 bound $R_n(\mathcal{F})$的策略是，对于任意$X_i$’s，求$R_n(\mathcal{F})$的一致上界，即先将$X_i$’s视为固定的 $x_i$’s，计算上界，此时只需要考虑${ϵ}_i$’s的随机性。经典的做法是 chaining。

特殊情况：$\mathcal{F}$是 Boolean 函数类

现在考虑如何 bound $R_n(\mathcal{F})$。

在讲 chaining 之前，我们先考虑一种简单的特殊情况：$\mathcal{F}$是 Boolean 函数类，即里面的每个函数都是$0/1$取值的。

首先介绍一个不等式：对于$|A|<\infty$的集合$A\subseteq {\mathbb{R}}^n$，有
$$R_n(A)=\mathrm{E}\underset{a\in A}{\sup }\frac{1}{n}|\sum _{i=1}^n{ϵ}_i{a}_i|\le \sqrt{6}\sqrt{\frac{\ln (2|A|)}{n}}\underset{a\in A}{\max }\sqrt{\frac{1}{n}\sum _{i=1}^n{a}_i^2}$$
由于$a_i$’s 是固定的，随机性只来自有界随机变量 ${ϵ}_i$’s，因此可用 Hoeffding 不等式，再经过一系列处理即可得到上式。

对于 Boolean 函数类$\mathcal{F}$，对任意$f\in \mathcal{F}$，将$f(x_i)$视为$a_i$，则每个$f(x_i{)}^2\le 1$，于是$\{(f(x_1),\cdots ,f(x_n)):f\in \mathcal{F}\}$就对应了上式的$A$。该集合的基数最多为$2^n$，这个太大了，我们假设基数最多是$n$的某个多项式形式，如$n^c$，代入上式，可知随着$n\to \infty$，
$$R_n(\mathcal{F})\le \sqrt{\frac{6(\ln 2+c\ln n)}{n}}=O(\sqrt{\genfrac{}{}{0ex}{}{}{n}}$$