【深度学习】图形模型基础(7)：机器学习优化中的方差减少方法(2)-附录A

引理

这里，我们提供并证明一些辅助性引理。

引理 1：
假设对于 $i=1,\dots ,n$，$f_i(x)$ 是凸函数且具有 $L_{\text{max}}$-光滑性。假设 $i$ 在集合 { 1 , … , n } \{1, \ldots, n\} {1,…,n} 上均匀采样。那么对于任意 $x\in {\mathbb{R}}^d$，我们有：
$${\mathbb{E}}_k[\Vert \nabla f_i(x)-\nabla f_i(x_{\text{ref}}){\Vert }^2]\le 2L_{\text{max}}(f(x)-f(x_{\text{ref}})).$$

证明：
由于 $f_i$ 是凸函数，我们有：
$$f_i(z)\ge f_i(x_{\text{ref}})+⟨\nabla f_i(x_{\text{ref}}),z-x_{\text{ref}}⟩,\forall z\in {\mathbb{R}}^d.$$
由于 $f_i$ 是 $L_{\text{max}}$-光滑的，我们有：
$$f_i(z)\le f_i(x)+⟨\nabla f_i(x),z-x⟩+\frac{L_{\text{max}}}{2}\Vert z-x{\Vert }^2,\forall z,x\in {\mathbb{R}}^d.$$
因此，对于任意 $x,z\in {\mathbb{R}}^d$，我们有：
$$f_i(x_{\text{ref}})-f_i(x)\le ⟨\nabla f_i(x_{\text{ref}}),x_{\text{ref}}-z⟩+⟨\nabla f_i(x),z-x⟩+\frac{L_{\text{max}}}{2}\Vert z-x{\Vert }^2.$$
为了获得右侧的最紧上界，我们可以在 $z$ 中最小化右侧，得到：
$$z=x-\frac{1}{L_{\text{max}}}(\nabla f_i(x)-\nabla f_i(x_{\text{ref}})).$$
代入上述方程，我们得到：
$$f_i(x_{\text{ref}})-f_i(x)=⟨\nabla f_i(x_{\text{ref}}),x_{\text{ref}}-x⟩-\frac{1}{2L_{\text{max}}}\Vert \nabla f_i(x)-\nabla f_i(x_{\text{ref}}){\Vert }^2.$$
对上述表达式取期望，并使用 ${\mathbb{E}}_i[f_i(x)]=f(x)$ 和 $\mathbb{E}[\nabla f_i(x_{\text{ref}})]=0$，即可得到结果。

引理 2：
假设 $X\in {\mathbb{R}}^d$ 是一个随机向量，具有有限的方差。那么：
$$\mathbb{E}[\Vert X-\mathbb{E}[X]{\Vert }^2]\le \mathbb{E}[\Vert X{\Vert }^2].$$

证明：
$$\mathbb{E}[\Vert X-\mathbb{E}[X]{\Vert }^2]=\mathbb{E}[\Vert X{\Vert }^2]-2\mathbb{E}[\Vert X\Vert {]}^2+\mathbb{E}[\Vert X\Vert {]}^2=\mathbb{E}[\Vert X{\Vert }^2]-\mathbb{E}[\Vert X\Vert {]}^2\le \mathbb{E}[\Vert X{\Vert }^2].$$