Lecture 3

Exponential Concentration Inequalities and ERM

回顾：切比雪夫不等式

  • 0−10-1经验风险：

R(h)=1n∑i=1nL(h(xi),yi)=1n∑i=1nδ(h(xi),yi)δ(y^,y)=1, if   y^=y  and  0  otherwiseR(h)=\frac{1}{n}\sum_{i=1}^{n}L(h(x_i),y_i)=\frac{1}{n}\sum_{i=1}^n\delta(h(x_i),y_i)\\ \delta(\hat{y},y)=1,\,\text{if}\,\,\,\hat{y}=y\,\,\text{and}\,\,\text{0}\,\,\text{otherwise}

  • ZZ：等概率从所有样本中抽取其损失，进行KK次彼此独立的随机抽取得到一组随机变量ZZ，即Z1,Z2,…,ZKZ_1,Z_2,\dots,Z_K，其平均值为经验风险的近似值，如下所示。

SK=1K∑k=1KZk≈R(h)  and  E[SK]=E[Z]=R(h)S_K = \frac{1}{K} \sum_{k=1}^K Z_k \approx R(h) \; \text{and} \; \textbf{E}[S_K] = \textbf{E}[Z] = R(h) 

1
概率论回顾：一组随机变量的和的期望与这组随机变量各自期望的和相等。
  • 其对应的切比雪夫不等式：Var(Z)≤14\textbf{Var}(Z) \leq \frac{1}{4}的推导见另一篇。

P(∣SK−E[SK]∣≥a)≤Var(SK)a2=Var(Z)a2K≤14a2K\textbf{P}(|S_K - \textbf{E}[S_K]| \geq a) \leq \frac{\textbf{Var}(S_K)}{a^2} = \frac{\textbf{Var}(Z)}{a^2K} \leq \frac{1}{4a^2K}

  • 离散型随机变量的方差计算（两种）：Var(SK)\textbf{Var}(S_K)的推导见另一篇。

    Var(Z)=∑(Zk−E[Z])2Var(Z)=E[Z2]−(E[Z])2\textbf{Var}(Z) = \sum(Z_k - \textbf{E}[Z])^2\\ \textbf{Var}(Z) = \textbf{E}[Z^2]-(\textbf{E}[Z])^2

问题：如果我们想在该场景下，近似计算经验风险，并将误差控制在10%以内，也即令∣SK−R(h)∣≤10%|S_K-R(h)| \leq 10\%，且对应概率为99%99\%。如果使用切比雪夫不等式约束，需要对多少个样本？

列出上述要求对应的不等式：

P(∣SK−E(SK)∣≤0.1)≥0.99\textbf{P}(|S_K-\textbf{E}(S_K)| \leq 0.1) \geq 0.99

上式等价于：

P(∣SK−E(SK)∣≥0.1)≤0.01\textbf{P}(|S_K-\textbf{E}(S_K)| \geq 0.1) \leq 0.01

根据切比雪夫不等式，我们希望：

14a2K≤0.01,    a=0.1\frac{1}{4a^2K} \leq 0.01,\;\;a = 0.1

因此：K≥2500K \geq 2500，至少需要 25002500 个样本来确保近似值SKS_K与R(h)R(h)之间误差不超过 0.10.1 的概率达到 99%99\%。

局限性：需要联合近似多个模型的情况

如果有多个预测器h(1),h(2),…,h(M)h^{(1)},h^{(2)},\dots,h^{(M)}，每个预测器的经验风险由彼此独立的子样本SK(1),SK(2),…,SK(M)S_K^{(1)},S_K^{(2)},\dots,S_K^{(M)}近似估计，样本大小都为KK。

我们希望使用切比雪夫不等式得到一个概率界限，找到一个KK，使得对于任意i∈{1,2,…,M}i \in \{1,2,\dots,M\}，都有下式成立。

P(∣SK(m)−R(h(m))∣≥a)≤14a2K\textbf{P}(|S_K^{(m)}-R(h^{(m)})| \geq a) \leq \frac{1}{4a^2K}

现在对MM个预测器同时进行分析，设事件AiA_i表示近似值与真实值超过aa的事件，即：

Am={∣SK(m)−R(h(m))∣≥a}A_m = \{|S_K^{(m)}-R(h^{(m)})| \geq a\}

根据联合概率性质，如果我们希望每个假设的经验风险与真实风险的差距都小于aa，且这些事件彼此独立。根据Boole 不等式有：

P(∪Am)≤∑P(Am)≤M⋅14a2K\textbf{P}(\cup A_m) \leq \sum \textbf{P}(A_m) \leq M \cdot \frac{1}{4a^2K}

由于AmA_m之间彼此独立，有：

P(∩Am)=1−P(∪Am)=P(∣SK(m)−R(h(m))∣≤a    for all    m∈{1,…,M})≥1−M4a2K\textbf{P}(\cap A_m) = 1 - \textbf{P}(\cup A_m)\\ =\textbf{P}(|S_K^{(m)}-R(h^{(m)})| \leq a \;\; \text{for all} \;\;m \in \{1,\dots,M\})\\ \geq 1-\frac{M}{4a^2K}

注意：

P(∪Am)=P(∃m:∣SK(m)−R(h(m))∣≥a)\textbf{P}(\cup A_m) = \textbf{P}(\exists m:|S_K^{(m)}-R(h^{(m)})| \geq a)

P(∩Am)=P(∀m:∣SK(m)−R(h(m))∣≤a)\textbf{P}(\cap A_m)=\textbf{P}(\forall m:|S_K^{(m)}-R(h^{(m)})| \leq a)

问题：如果我们想在该场景下，近似计算经验风险，并将误差控制在1%以内，也即对所有预测器，令∣SK−R(h)∣≤1%|S_K-R(h)| \leq 1\%，且对应概率为99%99\%，一共 100100 个预测器。如果使用切比雪夫不等式约束，需要对多少个样本？

列出上述要求对应的不等式：

P(∣SK(m)−R(h(m))∣≤0.01    for all    m∈{1,…,100})≥0.99\textbf{P}(|S_K^{(m)}-R(h^{(m)})| \leq 0.01 \;\; \text{for all} \;\;m \in \{1,\dots,100\}) \geq 0.99

根据切比雪夫不等式，我们希望：

1−M4a2K≥0.99,  M=100,  a=0.011-\frac{M}{4a^2K} \geq 0.99,\;M=100,\;a=0.01

因此：K≥25,000,000K \geq 25,000,000，至少需要 25,000,00025,000,000 个样本来确保所有预测器的近似值SKS_K与R(h)R(h)之间误差不超过 0.010.01 的概率达到 99%99\%。

综上所述，切比雪夫不等式的局限性如下：

相比于训练单个模型的场景，多模型场景下需要非常多的样本来进行经验风险的近似计算。如果我们要在数千个模型上经历上百次迭代的训练，这个问题的严重性将成倍增长。

此外，切比雪夫不等式给出的概率界限仍然不够理想。其界限通过事件方差来计算，方差通常是关于样本量KK的倒数，当KK增加时，界限会减小，但减小速度是多项式的（如1K\frac{1}{K}或1K2\frac{1}{K^2}）。而正态分布中，偏离均值较大的事件概率以指数速度下降，这意味着远离均值的极端事件概率非常小，远比多项式递减快。

因此，虽然切比雪夫不等式提供了一种普适的界限，但在描述极端事件概率时，特别是当我们期望概率随着偏离均值的增加而显著减小时，它可能会显得过于保守。

改进：霍夫丁不等式

对总和的尾部概率有更严格的限制。

同样从0−10-1损失中随机抽样，得到一组随机变量Z1,Z2,…,ZKZ_1,Z_2,\dots,Z_K，其平均值SKS_K如下：

SK=1K∑k=1KZkS_K=\frac{1}{K}\sum_{k=1}^KZ_k

如果ZkZ_k满足限制条件：zmin≤Zk≤zmaxz_{min} \leq Z_k \leq z_{max}，则根据霍夫丁不等式，有下式成立：

P(∣SK−E[SK]∣≥a)≤2 exp(−2a2K(zmax−zmin)2)\textbf{P}(|S_K-\textbf{E}[S_K]| \geq a) \leq 2 \, \text{exp}(-\frac{2a^2K}{(z_{max}-z_{min})^2})

问题：如果我们想在该场景下，近似计算经验风险，并将误差控制在10%以内，也即令∣SK−R(h)∣≤10%|S_K-R(h)| \leq 10\%，且对应概率为99%99\%。如果使用霍夫丁不等式约束，需要多少个样本？

列出上述要求对应的不等式：

P(∣SK−E(SK)∣≤0.1)≥0.99\textbf{P}(|S_K-\textbf{E}(S_K)| \leq 0.1) \geq 0.99

上式等价于：

P(∣SK−E(SK)∣≥0.1)≤0.01\textbf{P}(|S_K-\textbf{E}(S_K)| \geq 0.1) \leq 0.01

根据霍夫丁不等式，我们希望：

2 exp(−2a2K(zmax−zmin)2)≤0.01,    a=0.12 \, \text{exp}(-\frac{2a^2K}{(z_{max}-z_{min})^2}) \leq 0.01,\;\;a = 0.1

因此：K≥265(zmax−zmin)2K \geq 265(z_{max}-z_{min})^2，令C=(zmax−zmin)2C=(z_{max}-z_{min})^2，则有K≥265CK \geq 265C。

多模型场景

如果有多个预测器h(1),h(2),…,h(M)h^{(1)},h^{(2)},\dots,h^{(M)}，每个预测器的经验风险由彼此独立的子样本SK(1),SK(2),…,SK(M)S_K^{(1)},S_K^{(2)},\dots,S_K^{(M)}近似估计，样本大小都为KK。

我们希望使用霍夫丁不等式得到一个概率界限，找到一个KK，使得对于任意i∈{1,2,…,M}i \in \{1,2,\dots,M\}，都有下式成立。

P(∣SK(m)−R(h(m))∣≥a)≤2 exp(−2a2K(zmax−zmin)2)\textbf{P}(|S_K^{(m)}-R(h^{(m)})| \geq a) \leq 2 \, \text{exp}(-\frac{2a^2K}{(z_{max}-z_{min})^2})

现在对MM个预测器同时进行分析，设事件AiA_i表示近似值与真实值超过aa的事件，即：

Am={∣SK(m)−R(h(m))∣≥a}A_m = \{|S_K^{(m)}-R(h^{(m)})| \geq a\}

根据联合概率性质，如果我们希望每个假设的经验风险与真实风险的差距都小于aa，且这些事件彼此独立。根据Boole 不等式有：

P(∪Am)≤∑P(Am)≤2M⋅ exp(−2a2K(zmax−zmin)2)\textbf{P}(\cup A_m) \leq \sum \textbf{P}(A_m) \leq 2M \cdot \, \text{exp}(-\frac{2a^2K}{(z_{max}-z_{min})^2})

由于AmA_m之间彼此独立，有：

P(∩Am)=1−P(∪Am)=P(∣SK(m)−R(h(m))∣≤a    for all    m∈{1,…,M})≥1−2M⋅ exp(−2a2K(zmax−zmin)2)\textbf{P}(\cap A_m) = 1 - \textbf{P}(\cup A_m)\\ =\textbf{P}(|S_K^{(m)}-R(h^{(m)})| \leq a \;\; \text{for all} \;\;m \in \{1,\dots,M\})\\ \geq 1-2M \cdot \, \text{exp}(-\frac{2a^2K}{(z_{max}-z_{min})^2})

注意：

P(∪Am)=P(∃m:∣SK(m)−R(h(m))∣≥a)\textbf{P}(\cup A_m) = \textbf{P}(\exists m:|S_K^{(m)}-R(h^{(m)})| \geq a)

P(∩Am)=P(∀m:∣SK(m)−R(h(m))∣≤a)\textbf{P}(\cap A_m)=\textbf{P}(\forall m:|S_K^{(m)}-R(h^{(m)})| \leq a)

问题：如果我们想在多模型场景下，近似计算经验风险，并将误差控制在10%10\%以内，也即对所有预测器，令∣SK−R(h)∣≤10%|S_K-R(h)| \leq 10\%，且对应概率为99%99\%，一共 100100 个预测器。如果使用霍夫丁不等式约束，需要多少个样本？

列出上述要求对应的不等式：

P(∣SK(m)−R(h(m))∣≤0.1    for all    m∈{1,…,100})≥0.99\textbf{P}(|S_K^{(m)}-R(h^{(m)})| \leq 0.1 \;\; \text{for all} \;\;m \in \{1,\dots,100\}) \geq 0.99

根据霍夫丁不等式，我们希望：

1−2M⋅ exp(−2a2K(zmax−zmin)2)≥0.99,  M=100,  a=0.1,  C=(zmax−zmin)21-2M \cdot \, \text{exp}(-\frac{2a^2K}{(z_{max}-z_{min})^2}) \geq 0.99,\;M=100,\;a=0.1,\;C=(z_{max}-z_{min})^2

因此：K≥500CK \geq 500C。

综上，霍夫丁不等式界限要严格得多，可以更好地适应多模型场景下的样本量估计。还有一些其他的集中不等式，其作用简述如下：

  • Azuma’s inequality：可以适用于ZkZ_k间彼此不独立的情况
  • Bennett’s inequality：可以适用于考虑方差的情况

经验风险最小化

为每个预测器分配一个dd维的参数向量，也即每一个dd维参数向量对应一个预测器。并将经验风险最小化视作一个优化问题：

minimize:R(hw)=1n∑i=1nL(hw(xi),yi)  over  w∈Rd\text{minimize}:R(h_w)=\frac{1}{n}\sum_{i=1}^nL(h_w(x_i),y_i) \; \text{over} \; w \in \mathbb{R}^d

通常，我们将经验风险视作关于参数ww的函数：

f(w)=R(hw)=1n∑i=1nL(hw(xi),yi)=1n∑i=1nfi(w)f(w)=R(h_w)=\frac{1}{n}\sum_{i=1}^nL(h_w(x_i),y_i)=\frac{1}{n}\sum_{i=1}^nf_i(w)

注意：

  1. hwh_w表示与参数向量ww相关联的假设，即模型。例如，在线性回归中，假设hw(x)=wTxh_w(x)=w^Tx。
  2. 经验风险R(hw)R(h_w)是模型在训练数据上的平均损失，其定义中LL是损失函数，例如均方误差、交叉熵等。
  3. 为了更明确地表示损失函数关于参数ww的依赖关系，我们将每个损失L(hw(xi),yi)L(h_w(x_i),y_i)表示为fi(w)f_i(w)，这样fi(w)f_i(w)表示第ii个数据点的损失。

梯度下降

依照下式的法则，迭代地降低经验风险损失的值。

wt+1=wt−αt⋅∇f(wt)=wt−αt⋅1n∑i=1n∇fi(w)w_{t+1}=w_t-\alpha_t \cdot \nabla f(w_t) = w_t - \alpha_t \cdot \frac{1}{n}\sum_{i=1}^n \nabla f_i(w)

其中，wtw_t表示迭代tt轮时的参数向量，αt\alpha_t是学习率，∇f\nabla f表示ff的梯度（偏导数向量，具体的计算与损失函数的形式有关）。那么如何考虑计算成本呢？降低计算成本的方式？

随机梯度下降：更低的计算成本

在实施梯度下降时，进行子采样：

pick    i    uniformly at a random from{1,…,n},then update wt+1=wt−αt⋅∇fi(wt)\text{pick} \;\; i \;\; \text{uniformly at a random from} \{1,\dots,n\},\text{then update } w_{t+1} = w_t - \alpha_t \cdot \nabla f_i(w_t)

具体来说，随机梯度下降的过程为：

  1. 随机选择一个数据点：

    从{1,…,n}\{1,\dots,n\}中均匀随机地选择一个索引ii，也即每个索引被选中的概率是相同的。

  2. 计算梯度并更新参数：

    • 使用选择的数据点的损失函数fif_i计算当前参数wtw_t的梯度，即∇fi(wt)\nabla f_i(w_t)。
    • 计算出的梯度更新参数，更新公式如上所示。

全批量梯度下降，在每次更新参数时需要计算整个训练集的梯度，计算成本为O(n⋅d)O(n \cdot d)，其中nn是训练样本的数量，dd是参数向量的维度。

随机梯度下降在每次更新参数时仅计算一个样本的梯度，计算成本为O(d)O(d)，显著降低了每次更新的计算成本。