《机器学习理论导引》笔记目录

• 第一章 : 预备知识
  • 第一章 : 预备知识(上)
  • 第一章 : 预备知识(下)
• 第二章 : 可学性
• 第三章 : 复杂度
• 第四章 : 泛化界
  • 第四章 : 泛化界(上)
  • 第四章 : 泛化界(中)
  • 第四章 : 泛化界(下)
• 第五章 : 稳定性
• 第六章 : 一致性
  • 第六章 : 一致性(上)
  • 第六章 : 一致性(下)
• 第七章 : 收敛率
  • 第七章 : 收敛率(上)
  • 第七章 : 收敛率(下)
• 第八章 : 遗憾界
  • 第八章 : 遗憾界(上)
  • 第八章 : 遗憾界(下)

0 感言

  感觉这章整体而言自己理解得并不充分，更多像是把周老师的教材进行打印，之后有时间我会重新进行整理的。

7.3 随机优化

7.3.1 凸函数

  下给出随机优化的代表性算法——随机梯度下降法 (Stochastic Gradient Descent，SGD) 的流程。

  其中要求 ${\mathbf{w}}_t$ 的随机梯度 ${\mathbf{g}}_t$ 是真实梯度 $\nabla f({\mathbf{w}}_t)$ 的无偏估计，即 :

$$\mathbb{E}[{\mathbf{g}}_t]=\nabla f({\mathbf{w}}_t)$$

  上述方法非常适合机器学习问题。下面以监督学习为例，监督学习的最终目标是最小化泛化风险，令数据分布为 $\mathcal{D}$，可以用风险最小化 (Risk Minimization) 的方法来描述监督学习的目标 :

$$\underset{\mathbf{w}\in \mathcal{W}}{\min }f(\mathbf{w})={\mathbb{E}}_{\mathbf{z}\sim \mathcal{D}}[\ell (\mathbf{w},\mathbf{z})]$$

  其中 $\mathbf{z}\in \mathcal{D}$ 表示 $\mathbf{z}$ 是从数据分布 $\mathcal{D}$ 中采样获得，$\ell (\cdot ,\cdot )$ 为损失函数，但是在现实场景中很难直接获得真实的数据分布 $\mathcal{D}$，因此经常采用经验风险最小化 (Empirical Risk Minimization，ERM) 的方法来近似风险最小化的目标 : 从数据分布 $\mathcal{D}$ 中采样获得 $m$ 个样本 ${\mathbf{z}}_1,{\mathbf{z}}_2,\cdots ,{\mathbf{z}}_m,\forall {\mathbf{z}}_i=({\mathbf{x}}_i,y_i)$，${\mathbf{x}}_i$ 为样本特征，$y_i$ 为样本标记，然后用这 $n$ 个样本来近似风险最小化的目标 :

$$\underset{\mathbf{w}\in \mathcal{W}}{\min }f(\mathbf{w})=\frac{1}{m}\sum _{i=1}^m\ell (\mathbf{w},{\mathbf{z}}_i)$$

  当 $m$ 很大的时候计算代价很高，因此采用随机梯度下降法 (Stochastic Gradient Descent，SGD) 来近似风险最小化的目标，将上述算法中第 3 步改为下式即可 :

$${\mathbf{w}}_{t+1}^{\prime }={\mathbf{w}}_t-{\eta }_t\nabla \ell \left({\mathbf{w}}_t,{\mathbf{z}}_t\right)$$

  其中 ${\mathbf{z}}_t$ 表示从数据分布 $\mathcal{D}$ 中随机采样获得的样本，从上面的描述可以看出随机梯度下降每轮迭代只需要利用 1 个样本。而对于一般的 Lipschitz 连续凸函数，随机梯度下降法的收敛速度为 $O(\frac{1}{\sqrt{T}})$，具体有如下定理 :

定理 7.4 随机梯度下降收敛率 假设目标函数的随机梯度有上界，且可行域有界，则随机梯度下降的收敛率为 $O(\frac{1}{\sqrt{T}})$。

证明 假设随机梯度上界为 $l$，可行域 $\mathcal{W}$ 直径为 $\Gamma$，即对于任意 $t\in [T],u,v\in \mathcal{W}$

$$\begin{array}{r}\Vert {\mathbf{g}}_t\Vert ⩽l\\ \Vert \mathbf{u}-\mathbf{v}\Vert ⩽\Gamma \end{array}$$

  同样为了简化分析，考虑固定的步长 ${\eta }_t=\eta$，则对于任意的 $w\in \mathcal{W}$，

$$\begin{array}{rl}& f\left({\mathbf{w}}_t\right)-f(\mathbf{w})\\ & ⩽⟨\nabla f\left({\mathbf{w}}_t\right),{\mathbf{w}}_t-\mathbf{w}⟩=⟨{\mathbf{g}}_t,{\mathbf{w}}_t-\mathbf{w}⟩+⟨\nabla f\left({\mathbf{w}}_t\right)-{\mathbf{g}}_t,{\mathbf{w}}_t-\mathbf{w}⟩\\ & =\frac{1}{\eta }⟨{\mathbf{w}}_t-{\mathbf{w}}_{t+1}^{\prime },{\mathbf{w}}_t-\mathbf{w}⟩+⟨\nabla f\left({\mathbf{w}}_t\right)-{\mathbf{g}}_t,{\mathbf{w}}_t-\mathbf{w}⟩\\ & =\frac{1}{2\eta }\left({\Vert {\mathbf{w}}_t-\mathbf{w}\Vert }^2-{\Vert {\mathbf{w}}_{t+1}^{\prime }-\mathbf{w}\Vert }^2+{\Vert {\mathbf{w}}_t-{\mathbf{w}}_{t+1}^{\prime }\Vert }^2\right)+⟨\nabla f\left({\mathbf{w}}_t\right)-{\mathbf{g}}_t,{\mathbf{w}}_t-\mathbf{w}⟩\\ & =\frac{1}{2\eta }\left({\Vert {\mathbf{w}}_t-\mathbf{w}\Vert }^2-{\Vert {\mathbf{w}}_{t+1}^{\prime }-\mathbf{w}\Vert }^2\right)+\frac{\eta }{2}{\Vert {\mathbf{g}}_t\Vert }^2+⟨\nabla f\left({\mathbf{w}}_t\right)-{\mathbf{g}}_t,{\mathbf{w}}_t-\mathbf{w}⟩\\ & \text{(利用}\Vert {\Pi }_{\mathcal{W}}(\mathbf{x})-{\Pi }_{\mathcal{W}}(\mathbf{z})\Vert ⩽\Vert \mathbf{x}-\mathbf{z}\Vert ,\forall \mathbf{x},\mathbf{z})\\ & ⩽\frac{1}{2\eta }\left({\Vert {\mathbf{w}}_t-\mathbf{w}\Vert }^2-{\Vert {\mathbf{w}}_{t+1}-\mathbf{w}\Vert }^2\right)+\frac{\eta }{2}{\Vert {\mathbf{g}}_t\Vert }^2+⟨\nabla f\left({\mathbf{w}}_t\right)-{\mathbf{g}}_t,{\mathbf{w}}_t-\mathbf{w}⟩\\ & ⩽\frac{1}{2\eta }\left({\Vert {\mathbf{w}}_t-\mathbf{w}\Vert }^2-{\Vert {\mathbf{w}}_{t+1}-\mathbf{w}\Vert }^2\right)+\frac{\eta }{2}{l}^2+⟨\nabla f\left({\mathbf{w}}_t\right)-{\mathbf{g}}_t,{\mathbf{w}}_t-\mathbf{w}⟩\end{array}$$

  对上面的不等式从 $t=1$ 到 $t=T$ 求和，得到

$$\begin{array}{rl}& \sum _{t=1}^{T}f\left({\mathbf{w}}_t\right)-Tf(\mathbf{w})\\ & ⩽\frac{1}{2\eta }\left({\Vert {\mathbf{w}}_1-\mathbf{w}\Vert }^2-{\Vert {\mathbf{w}}_{T+1}-\mathbf{w}\Vert }^2\right)+\frac{\eta T}{2}{l}^2+\sum _{t=1}^T⟨\nabla f\left({\mathbf{w}}_t\right)-{\mathbf{g}}_t,{\mathbf{w}}_t-\mathbf{w}⟩\\ & ⩽\frac{1}{2\eta }{\Vert {\mathbf{w}}_1-\mathbf{w}\Vert }^2+\frac{\eta T}{2}{l}^2+\sum _{t=1}^T⟨\nabla f\left({\mathbf{w}}_t\right)-{\mathbf{g}}_t,{\mathbf{w}}_t-\mathbf{w}⟩\\ & ⩽\frac{1}{2\eta }{\Gamma }^2+\frac{\eta T}{2}{l}^2+\sum _{t=1}^T⟨\nabla f\left({\mathbf{w}}_t\right)-{\mathbf{g}}_t,{\mathbf{w}}_t-\mathbf{w}⟩\end{array}$$

  最后，依据 Jensen 不等式，有

$$\begin{array}{rl}f\left({\overline{\mathbf{w}}}_T\right)-f(\mathbf{w})& =f\left(\frac{1}{T}\sum _{t=1}^T{\mathbf{w}}_t\right)-f(\mathbf{w})\\ & ⩽\frac{1}{T}\sum _{t=1}^{T}f\left({\mathbf{w}}_t\right)-f(\mathbf{w})\\ & ⩽\frac{{\Gamma }^2}{2\eta T}+\frac{\eta l^2}{2}+\frac{1}{T}\sum _{t=1}^T⟨\nabla f\left({\mathbf{w}}_t\right)-{\mathbf{g}}_t,{\mathbf{w}}_t-\mathbf{w}⟩\end{array}$$

  可以看出，上式与章节 7.2.1 中梯度下降分析的结果的区别在于多了一项 $\frac{1}{T}{\sum }_{t=1}^T⟨\nabla f\left({\mathbf{w}}_t\right)-{\mathbf{g}}_t,{\mathbf{w}}_t-\mathbf{w}⟩$

  下面证明随机梯度下降算法期望意义上的收敛率，利用 ${\mathbf{w}}_t$ 的随机梯度 ${\mathbf{g}}_t$ 是真实梯度 $\nabla f({\mathbf{w}}_t)$ 的无偏估计，有

$$\begin{array}{rl}& \mathbb{E}\left[\sum _{t=1}^T⟨\nabla f\left({\mathbf{w}}_t\right)-{\mathbf{g}}_t,{\mathbf{w}}_t-\mathbf{w}⟩\right]\\ =& \mathbb{E}\left[\sum _{t=1}^T⟨\nabla f\left({\mathbf{w}}_t\right),{\mathbf{w}}_t-\mathbf{w}⟩\right]-\mathbb{E}\left[\sum _{t=1}^T⟨{\mathbf{g}}_t,{\mathbf{w}}_t-\mathbf{w}⟩\right]\\ =& \sum _{t=1}^T\left[\mathbb{E}\left[⟨\nabla f\left({\mathbf{w}}_t\right),{\mathbf{w}}_t-\mathbf{w}⟩\right]-\mathbb{E}\left[⟨{\mathbf{g}}_t,{\mathbf{w}}_t-\mathbf{w}⟩\right]\right]\\ =& \sum _{t=1}^T\left[\mathbb{E}\left[⟨\mathbb{E}\left[{\mathbf{g}}_t\right],{\mathbf{w}}_t-\mathbf{w}⟩\right]-\mathbb{E}\left[⟨{\mathbf{g}}_t,{\mathbf{w}}_t-\mathbf{w}⟩\right]\right]\\ =& \sum _{t=1}^T\left[\mathbb{E}\left[{\mathbf{g}}_t,{\mathbf{w}}_t-\mathbf{w}⟩\right]-\mathbb{E}\left[⟨{\mathbf{g}}_t,{\mathbf{w}}_t-\mathbf{w}⟩\right]\right]\\ =& 0\end{array}$$

  对于上面的不等式求期望有

$$\mathbb{E}\left[f\left({\overline{\mathbf{w}}}_T\right)\right]-f(\mathbf{w})⩽\frac{{\Gamma }^2}{2\eta T}+\frac{\eta l^2}{2}=\frac{l\Gamma }{\sqrt{T}}$$

  其中令 $\eta =\Gamma /(l\sqrt{T})$

  前面的分析证明了从期望意义上的收敛率，为了分析随机梯度下降算法的理论保障，将利用针对鞅差序列的 Azuma 不等式，利用 ${\mathbf{w}}_t$ 的随机梯度 ${\mathbf{g}}_t$ 是真实梯度 $\nabla f({\mathbf{w}}_t)$ 的无偏估计，可知 $⟨\nabla f({\mathbf{w}}_1)-g_1,{\mathbf{w}}_1-\mathbf{w}⟩,\dots$ 组成一个鞅差序列，有

$$\begin{array}{rl}\left|⟨\nabla f\left({\mathbf{w}}_t\right)-{\mathbf{g}}_t,{\mathbf{w}}_t-\mathbf{w}⟩\right|& ⩽\Vert \nabla f\left({\mathbf{w}}_t\right)-{\mathbf{g}}_t\Vert \Vert {\mathbf{w}}_t-\mathbf{w}\Vert \\ & ⩽\Gamma \left(\Vert \nabla f\left({\mathbf{w}}_t\right)\Vert +\Vert {\mathbf{g}}_t\Vert \right)⩽2l\Gamma \end{array}$$

  上式的推导过程中利用了 Jensen 不等式获得 $\Vert \nabla f({\mathbf{w}}_t)\Vert$ 的上界

$$\Vert \nabla f\left({\mathbf{w}}_t\right)\Vert =\Vert \mathbb{E}\left[{\mathbf{g}}_t\right]\Vert ⩽\mathbb{E}\left[\Vert {\mathbf{g}}_t\Vert \right]⩽l$$

  根据 Azuma 不等式推论 $P\left({\sum }_{i=1}^m{X}_i⩾ϵ\right)⩽e^{-{ϵ}^2/2{\sum }_{i=1}^m{c}_i^2}$，以至少 $1-\delta$ 的概率有

$$\sum _{t=1}^T⟨\nabla f\left({\mathbf{w}}_t\right)-{\mathbf{g}}_t,{\mathbf{w}}_t-\mathbf{w}⟩⩽2l\Gamma \sqrt{2T\log \frac{1}{\delta }}$$

  将上式代入前面的不等式，以至少 $1-\delta$ 的概率有

$$\begin{array}{rl}f\left({\overline{\mathbf{w}}}_T\right)-f(\mathbf{w})& ⩽\frac{{\Gamma }^2}{2\eta T}+\frac{\eta l^2}{2}+2l\Gamma \sqrt{\frac{2}{T}\log \frac{1}{\delta }}\\ & =\frac{l\Gamma }{\sqrt{T}}\left(1+2\sqrt{2\log \frac{1}{\delta }}\right)=O\left(\frac{1}{\sqrt{T}}\right)\end{array}$$

7.3.2 强凸函数

  为了处理强凸函数，引入阶段随机梯度下降 (Epoch-GD) 算法，其流程如下 :

  若目标函数 $f:\mathcal{W}\mapsto \mathbb{R}$ 是 $\lambda$-强凸的，在期望意义上的 Epoch-GD 的额外风险界为 $O(1/[\lambda T])$，下进行相关证明

引理 7.1 将 Epoch-GD 的参数设置为 $T_1=4$ 和 ${\eta }_1=1/\lambda$，$l$ 为随机梯度的上界，令 ${\Delta }_k=f({\mathbf{w}}_1^k)-f({\mathbf{w}}^{\ast }),V_k=l^2/(\lambda 2^{k-2})$，对于任意的 $k$

$$\mathbb{E}\left[{\Delta }_k\right]⩽V_k$$

证明 当随机梯度的上界为 $l$ 时，根据先前推论 $\Vert \nabla f\left({\mathbf{w}}_t\right)\Vert =\Vert \mathbb{E}\left[{\mathbf{g}}_t\right]\Vert ⩽\mathbb{E}\left[\Vert {\mathbf{g}}_t\Vert \right]⩽l$ 可知，真实梯度的上界也为 $l$。因此，定理 7.2 成立。然后易知下面式子成立 :

$$\begin{array}{rl}{T}_k& =\frac{8l^2}{\lambda V_k}=2^{k+1}\\ {\eta }_k& =\frac{V_k}{2l^2}=\frac{1}{\lambda 2^{k-1}}\end{array}$$

  下使用数学归纳法来进行证明

• 当 $k=1$ 时，引理成立 :

  $$\mathbb{E}\left[{\Delta }_1\right]=\mathbb{E}\left[f\left({\mathbf{w}}_1^1\right)-f\left({\mathbf{w}}^{\ast }\right)\right]⩽\frac{2l^2}{\lambda }=\frac{l^2}{\lambda 2^{1-2}}=V_1$$

• 假设对于某正整数 $k⩾1$，引理仍成立 $\mathbb{E}\left[{\Delta }_k\right]⩽V_k=l^2/(\lambda 2^{k-2})$

• 对于正整数 $k+1$，令 ${\mathbb{E}}_k[X]$ 为前 $k$ 轮的期望，则有

  $$\begin{array}{rl}{\mathbb{E}}_k\left[f\left({\mathbf{w}}_1^{k+1}\right)\right]-f\left({\mathbf{w}}^{\ast }\right)& ⩽\frac{{\eta }_k{l}^2}{2}+\frac{{\Vert {\mathbf{w}}^{\ast }-{\mathbf{w}}_1^k\Vert }^2}{2{\eta }_k{T}_k}\\ & ⩽\frac{{\eta }_k{l}^2}{2}+\frac{{\Delta }_k}{{\eta }_k{T}_k\lambda }.\end{array}$$

  因此，$k+1$ 的时候情况也成立 :

$$\begin{array}{rl}\mathbb{E}\left[{\Delta }_{k+1}\right]& ⩽\frac{{\eta }_k{l}^2}{2}+\frac{\mathbb{E}\left[{\Delta }_k\right]}{{\eta }_k{T}_k\lambda }\\ & ⩽\frac{{\eta }_k{l}^2}{2}+\frac{l^2}{2^{k-2}{\eta }_k{T}_k{\lambda }^2}=\frac{l^2}{2^{k-1}\lambda }\end{array}$$

  引理得证。

定理 7.5 Epoch-GD 的收敛率 当目标函数 $f(\cdot )$ 为 $\lambda$-强凸时，Epoch-GD 期望意义上的收敛率为 $O(\frac{1}{T})$。

证明 Epoch-GD 外层循环的轮数，是由满足 ${\sum }_{i=1}^k{T}_i⩽T$ 的最大 $k$ 决定的。由于

$$\sum _{i=1}^k{2}^{i-1}{T}_1=\left(2^k-1\right)T_1⩽T$$

  因此，最后一轮迭代的轮数 $k^{†}=\lfloor {\log }_2\left(T/T_1+1\right)\rfloor$，而算法的最后输出是 ${\mathbf{w}}_1^{k^{†}+1}$，根据引理 7.1，有

$$\begin{array}{rl}\mathbb{E}\left[f\left({\mathbf{w}}_1^{k^{†}+1}\right)\right]& -f\left({\mathbf{w}}^{\ast }\right)=\mathbb{E}\left[{\Delta }_{k^{†}+1}\right]\\ & ⩽V_{k^{†}+1}=\frac{l^2}{2^{k^{†}-1}\lambda }\\ & ⩽\frac{16l^2}{\lambda T}=O\left(\frac{1}{\lambda T}\right)\end{array}$$

  定理得证。

定理 7.6 针对鞅的 Bernstein 不等式 假设 $X_1,\dots ,X_n$ 是定义在 $f=(f_i{)}_{1⩽i⩽n}$ 上的有界鞅差分序列，且满足 $\left|X_i\right|⩽M$，令

$$S_i=\sum _{j=1}^i{X}_j$$

  为对应的鞅，将条件方差 (conditional variance) 记为

$$V_n^2=\sum _{t=1}^n\mathbb{E}\left[{\delta }_t^2\mid f_{t-1}\right]$$

  那么对于任意的正数 $t$ 和 $v$，有

$$P\left(\underset{i=1,\dots ,n}{\max }{S}_i>t\text{ and }{V}_n^2⩽\nu \right)⩽\exp \left(-\frac{t^2}{2(\nu +Kt/3)}\right)$$

  因此可以得到

$$P\left(\underset{i}{\max }{S}_i>\sqrt{2\nu \tau }+\frac{2}{3}K\tau \text{ and }{V}_n^2⩽\nu \right)⩽e^{-\tau }$$

  分析内层循环的随机梯度下降在强凸函数下的收敛性质，有以下引理 :

引理 7.2 假设随机梯度上界为 $l$，目标函数 $f(\cdot )$ 为 $\lambda$-强凸。运行 $T$ 轮的随机梯度下降更新

$${\mathbf{w}}_{t+1}={\Pi }_{\mathcal{W}}\left({\mathbf{w}}_t-\eta {\mathbf{g}}_t\right)$$

  其中 ${\mathbf{g}}_t$ 是函数 $f(\cdot )$ 在 ${\mathbf{w}}_t$ 处的随机梯度，以至少 $1-\delta$ 的概率有

$$\sum _{t=1}^{T}f\left({\mathbf{w}}_t\right)-Tf\left({\mathbf{w}}^{\ast }\right)⩽\frac{\eta T{l}^2}{2}+\frac{{\Vert {\mathbf{w}}_1-{\mathbf{w}}^{\ast }\Vert }^2}{2\eta }+\frac{4l^2}{\lambda }\left(1+\frac{8}{3}\log \frac{m}{\delta }\right)$$

  其中 $m=\lceil 2{\log }_{2}T\rceil$

证明 由于 $f(\cdot )$ 是强凸的，因此

$$\begin{array}{rl}f\left({\mathbf{w}}_t\right)-f\left({\mathbf{w}}^{\ast }\right)& ⩽⟨\nabla f\left({\mathbf{w}}_t\right),{\mathbf{w}}_t-{\mathbf{w}}^{\ast }⟩-\frac{\lambda }{2}{\Vert {\mathbf{w}}_t-{\mathbf{w}}^{\ast }\Vert }^2\\ & =⟨{\mathbf{g}}_t,{\mathbf{w}}_t-{\mathbf{w}}^{\ast }⟩+⟨\nabla f\left({\mathbf{w}}_t\right)-{\mathbf{g}}_t,{\mathbf{w}}_t-{\mathbf{w}}^{\ast }⟩-\frac{\lambda }{2}{\Vert {\mathbf{w}}_t-{\mathbf{w}}^{\ast }\Vert }^2\end{array}$$

  对其从 $t=1$ 到 $T$ 进行求和，有

$$\begin{array}{rl}\sum _{t=1}^{T}f\left({\mathbf{w}}_t\right)-& Tf\left({\mathbf{w}}^{\ast }\right)⩽\frac{\eta T{l}^2}{2}+\frac{{\Vert {\mathbf{w}}_1-{\mathbf{w}}^{\ast }\Vert }^2}{2\eta }\\ & +\sum _{t=1}^T⟨\nabla f\left({\mathbf{w}}_t\right)-{\mathbf{g}}_t,{\mathbf{w}}_t-{\mathbf{w}}^{\ast }⟩-\frac{\lambda }{2}\sum _{t=1}^T{\Vert {\mathbf{w}}_t-{\mathbf{w}}^{\ast }\Vert }^2\end{array}$$

  定义鞅差序列

$${\delta }_t=⟨\nabla f\left({\mathbf{w}}_t\right)-{\mathbf{g}}_t,{\mathbf{w}}_t-{\mathbf{w}}^{\ast }⟩$$

  为了得到 ${\sum }_t{\delta }_t$ 的上界，将利用剥离技术 (peeling technique) 和针对鞅的 Bernstein 不等式。首先，注意到上面的鞅差序列是有界的 :

$$\begin{array}{rl}\left|{\delta }_t\right|& ⩽\Vert \nabla f\left({\mathbf{w}}_t\right)-{\mathbf{g}}_t\Vert \Vert {\mathbf{w}}_t-{\mathbf{w}}^{\ast }\Vert ⩽2l\frac{2l}{\lambda }=\frac{4l^2}{\lambda }\\ \text{定义}& A_T=\sum _{t=1}^T{\Vert {\mathbf{w}}_t-{\mathbf{w}}^{\ast }\Vert }^2⩽\frac{4l^{2}T}{{\lambda }^2}\end{array}$$

  对于条件方差，下面的不等式成立 :

$$V_T^2=\sum _{t=1}^T{\mathbb{E}}_{t-1}\left[{\delta }_t^2\right]⩽4l^2\sum _{t=1}^T{\Vert {\mathbf{w}}_t-{\mathbf{w}}^{\ast }\Vert }^2=4l^2{A}_T$$

• 当 $A_T⩽\frac{4l^2}{{\lambda }^{2}T}$ 时
  $$\sum _{t=1}^T{\delta }_t⩽2l\sum _{t=1}^T\Vert {\mathbf{w}}_t-{\mathbf{w}}^{\ast }\Vert ⩽2l\sqrt{T}\sqrt{\sum _{t=1}^T{\Vert {\mathbf{w}}_t-{\mathbf{w}}^{\ast }\Vert }^2}⩽\frac{4l^2}{\lambda }$$
• 当 $A_T\in \left(\frac{4l^2}{{\lambda }^{2}T},\frac{4l^{2}T}{{\lambda }^2}\right]$ 时，分解成 $m=\lceil 2{\log }_{2}T\rceil$ 种可能，即
  $$A_T\in \left(2^{i-1}\frac{4l^2}{{\lambda }^{2}T},2^i\frac{4l^2}{{\lambda }^{2}T}\right],i=1,\dots ,\lceil 2{\log }_{2}T\rceil$$

  综合上面两种情况，通过一系列变换可以证明

$$\begin{array}{rl}& P\left(\sum _{t=1}^T{\delta }_t⩾2\sqrt{4l^2{A}_T\tau }+\frac{2}{3}\frac{4l^2}{\lambda }\tau +\frac{4l^2}{\lambda }\right)\\ =& P\left(\sum _{t=1}^T{\delta }_t⩾2\sqrt{4l^2{A}_T\tau }+\frac{2}{3}\frac{4l^2}{\lambda }\tau +\frac{4l^2}{\lambda },A_T⩽\frac{4l^2}{{\lambda }^{2}T}\right)\\ +& P\left(\sum _{t=1}^T{\delta }_t⩾2\sqrt{4l^2{A}_T\tau }+\frac{2}{3}\frac{4l^2}{\lambda }\tau +\frac{4l^2}{\lambda },\frac{4l^2}{{\lambda }^{2}T}<A_T⩽\frac{4l^{2}T}{{\lambda }^2}\right)\\ =& P\left(\sum _{t=1}^T{\delta }_t⩾2\sqrt{4l^2{A}_T\tau }+\frac{2}{3}\frac{4l^2}{\lambda }\tau +\frac{4l^2}{\lambda },V_T^2⩽4l^2{A}_T,\frac{4l^2}{{\lambda }^{2}T}<A_T⩽\frac{4l^{2}T}{{\lambda }^2}\right)\\ & \text{(利用上面的分解)}\\ ⩽& \sum _{i=1}^{m}P(\sum _{t=1}^T{\delta }_t⩾2\sqrt{4l^2{A}_T\tau }+\frac{2}{3}\frac{4l^2}{\lambda }\tau +\frac{4l^2}{\lambda },\\ & V_T^2⩽4l^2{A}_T,\frac{4l^2}{{\lambda }^{2}T}{2}^{i-1}<A_T⩽\frac{4l^2}{{\lambda }^{2}T}{2}^i)\\ & \text{(利用 }{A}_T\text{ 的上下界来化简不等式)}\\ ⩽& \sum _{i=1}^{m}P\left(\sum _{t=1}^T{\delta }_t⩾\sqrt{2\frac{16l^4{2}^i}{{\lambda }^{2}T}\tau }+\frac{2}{3}\frac{4l^2}{\lambda }\tau ,V_T^2⩽\frac{16l^4{2}^i}{{\lambda }^{2}T}\right]\\ & \text{(利用定理 7.6)}\\ ⩽& m{e}^{-\tau }\end{array}$$

  然后令 $\tau =\log \frac{m}{\delta }=\log \frac{\lceil 2{\log }_{2}T\rceil }{\delta }$ 可得，以至少 $1-\delta$ 的概率有

$$\sum _{t=1}^T{\delta }_t⩽2\sqrt{4l^2{A}_T\log \frac{m}{\delta }}+\frac{8l^2}{3\lambda }\log \frac{m}{\delta }+\frac{4l^2}{\lambda }$$

  将其代入上面的累加式，以至少 $1-\delta$ 的概率有

$$\begin{array}{rl}& \sum _{t=1}^{T}f\left({\mathbf{w}}_t\right)-Tf\left({\mathbf{w}}^{\ast }\right)\\ & ⩽\frac{\eta T{l}^2}{2}+\frac{{\Vert {\mathbf{w}}_1-{\mathbf{w}}^{\ast }\Vert }^2}{2\eta }+2\sqrt{4l^2{A}_T\log \frac{m}{\delta }}+\frac{8l^2}{3\lambda }\log \frac{m}{\delta }+\frac{4l^2}{\lambda }-\frac{\lambda }{2}{A}_T\\ & ⩽\frac{\eta T{l}^2}{2}+\frac{{\Vert {\mathbf{w}}_1-{\mathbf{w}}^{\ast }\Vert }^2}{2\eta }+\frac{32l^2}{3\lambda }\log \frac{m}{\delta }+\frac{4l^2}{\lambda }\end{array}$$

  引理得证。

  利用引理 7.2 分析 Epoch-GD 外层循环的性质，得到如下引理 :

引理 7.3 令 $\delta \in (0,1)$ 表示失败的概率，定义

$$\begin{array}{rl}\tilde{\delta }& =\frac{\delta }{k^{†}}\\ k^{†}& =\lfloor {\log }_2\left(\frac{2T}{\alpha }+1\right)\rfloor \end{array}$$

  其中 $\alpha$ 为满足以下条件的最小偶数

$$\alpha ⩾24+\frac{128}{3}\log \frac{\lfloor {\log }_2\left(\frac{T}{12}+1\right)\rfloor \lceil 2{\log }_{2}T\rceil }{\delta }$$

  将 Epoch-GD 的参数设置为 $T_1=\alpha /2$ 和 ${\eta }_1=1/\lambda$，对于任意的 $k$，以至少 $(1-\tilde{\delta }{)}^{k-1}$ 的概率有

$${\Delta }_k=f\left({\mathbf{w}}_1^k\right)-f\left({\mathbf{w}}^{\ast }\right)⩽V_k=\frac{l^2}{\lambda 2^{k-2}}$$

证明 根据 $\alpha$ 的满足条件可知，$\alpha ⩾24$，因此

$$\begin{array}{rl}{k}^{†}& ⩽\lfloor {\log }_2\left(\frac{T}{12}+1\right)\rfloor \\ \tilde{\delta }& =\frac{\delta }{k^{†}}⩾\frac{\delta }{\lfloor {\log }_2\left(\frac{T}{12}+1\right)\rfloor }\end{array}$$

  由上式解出 $\delta$ 代回，可得

$$\alpha ⩾24+\frac{128}{3}\log \frac{\lceil 2{\log }_{2}T\rceil }{\tilde{\delta }}$$

  对引理 7.1 中的部分推论进行改写

$$T_k=\frac{8l^2}{\lambda V_k}=2^{k+1}\Rightarrow T_k=\frac{\alpha l^2}{\lambda V_k}=\alpha 2^{k-2}$$

  继续使用数学归纳法

• $k=1$ 时，根据定理 7.2，命题显然成立
• 假设对于正整数 $k⩾1$，${\Delta }_k⩽V_k$ 以至少 $(1-\tilde{\delta }{)}^{k-1}$ 的概率成立
• 考虑 $k+1$ 时，结合定理 7.2，以至少 $(1-\tilde{\delta })\cdot (1-\tilde{\delta }{)}^{k-1}=(1-\tilde{\delta }{)}^k$ 的概率有

$$\begin{array}{rl}{\Delta }_{k+1}& =f\left({\mathbf{w}}_1^{k+1}\right)-f\left({\mathbf{w}}^{\ast }\right)\\ & ⩽\frac{1}{T_k}\sum _{t=1}^{T_k}f\left({\mathbf{w}}_t^k\right)-f\left({\mathbf{w}}^{\ast }\right)\\ & ⩽\frac{{\eta }_k{l}^2}{2}+\frac{{\Vert {\mathbf{w}}_1^k-{\mathbf{w}}^{\ast }\Vert }^2}{2{\eta }_k{T}_k}+\frac{1}{T_k}\left(1+\frac{8}{3}\log \frac{m_k}{\tilde{\delta }}\right)\frac{4l^2}{\lambda }\\ & ⩽\frac{{\eta }_k{l}^2}{2}+\frac{{\Delta }_k}{{\eta }_k{T}_k\lambda }+\frac{1}{T_k}\left(1+\frac{8}{3}\log \frac{m_k}{\tilde{\delta }}\right)\frac{4l^2}{\lambda }\\ & ⩽\frac{V_k}{4}+\frac{2V_k}{\alpha }+\frac{\lambda V_k}{\alpha l^2}\left(1+\frac{8}{3}\log \frac{m_k}{\tilde{\delta }}\right)\frac{4l^2}{\lambda }\\ & =\frac{V_k}{4}+\frac{V_k}{\alpha }\left(6+\frac{32}{3}\log \frac{m_k}{\tilde{\delta }}\right)\end{array}$$

  其中 $m_k=\lceil 2{\log }_2{T}_k\rceil$，结合 $\alpha$ 的限制，以至少 $(1-\tilde{\delta }{)}^k$ 的概率有

$${\Delta }_{k+1}⩽\frac{V_k}{2}=V_{k+1}$$

  $k+1$ 的时候递归成立，数学归纳法成立，命题得证。

定理 7.7 Epoch-GD 大概率情况下的收敛率 若目标函数 $f(\cdot )$ 为 $\lambda$-强凸函数，Epoch-GD 以大概率取得 $O(\frac{\log \log T}{\lambda T})$ 的收敛率

证明 Epoch-GD 外层循环的轮数，是由满足 ${\sum }_{i=1}^k{T}_i⩽T$ 的最大 $k$ 决定的，由于

$$\sum _{i=1}^k{T}_i=\sum _{i=1}^k\alpha 2^{i-2}=\frac{\alpha }{2}\left(2^k-1\right)$$

  因此，最后一轮迭代的轮数 $k^{†}$ 与引理 7.3 中的定义相吻合，算法最终输出是 ${\mathbf{w}}_1^{k^{†}+1}$。根据引理 7.3，以至少 $(1-\tilde{\delta }{)}^{k^{†}}$ 的概率有

$$\begin{array}{rl}f\left({\mathbf{w}}_1^{k^{†}+1}\right)-f\left({\mathbf{w}}^{\ast }\right)& ={\Delta }_{k^{†}+1}\\ & ⩽V_{k^{†}+1}=\frac{l^2}{2^{k^{†}-1}\lambda }⩽\frac{2\alpha l^2}{\lambda T}\end{array}$$

  然后，证明概率 $(1-\tilde{\delta }{)}^{k^{†}}>1-\delta$，由于函数 $(1-\frac{1}{x}{)}^x$ 在 $x>1$ 时是增函数，因此

$$\begin{array}{rl}(1-\tilde{\delta }{)}^{k^{†}}={\left(1-\frac{\delta }{k^{†}}\right)}^{k^{†}}& ={\left({\left(1-\frac{1}{k^{†}/\delta }\right)}^{k^{†}/\delta }\right)}^{\delta }\\ & ⩾{\left({\left(1-\frac{1}{1/\delta }\right)}^{1/\delta }\right)}^{\delta }=1-\delta \end{array}$$

  由上面两式可知，以至少 $1-\delta$ 的概率有

$$f\left({\mathbf{w}}_1^{k^{†}+1}\right)-f\left({\mathbf{w}}^{\ast }\right)⩽\frac{2\alpha l^2}{\lambda T}=O\left(\frac{\log \log T}{\lambda T}\right)$$

  定理得证。

7.4 实例分析

7.4.1 支持向量机

  首先引入如何使用确定优化方法来求解支持向量机 (Supporting Vector Machine, SVM) : 令 $({\mathbf{x}}_1,y_1),\dots ,({\mathbf{x}}_m,y_m)$ 为 $m$ 个训练样本，其中 ${\mathbf{x}}_i\in {\mathbb{R}}^d,y_i\in \{-1,+1\}$，支持向量机的优化问题为 :

$$\begin{array}{rl}& \underset{\mathbf{w}}{\min }f(\mathbf{w})=\sum _{i=1}^m\max \left(0,1-y_i{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i\right)\\ & \text{ s.t. }\Vert \mathbf{w}\Vert ⩽\Lambda \end{array}$$

  由于 hinge 损失并不光滑，需要对梯度进行如下的计算替换，称之为次梯度 (sub-gradient) :

$$\begin{array}{rl}\nabla f(\mathbf{w})& =\sum _{i=1}^m{\mathbf{g}}_i,\\ {\mathbf{g}}_i& =\{\begin{array}{ll}-y_i{\mathbf{x}}_i,& 1-y_i{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i⩾0\\ 0,& 1-y_i{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i<0\end{array}\end{array}$$

  由于目标函数是凸函数，可以将 7.2.1 节中的梯度下降算法来进行求解。具体如下 :

  根据定理 7.1 的分析，可以得到如下收敛率。

定理 7.8 优化支持向量机的收敛率 梯度下降求解支持向量机的收敛率为 $O(\frac{1}{\sqrt{T}})$

证明 假设 $\Vert {\mathbf{x}}_i\Vert ⩽r,i\in [m]$，根据定理 7.1 步长的设置依赖于梯度的上界，梯度上界为

$$\Vert \nabla f(\mathbf{w})\Vert ⩽\sum _{i=1}^m\Vert y_i{\mathbf{x}}_i\Vert ⩽mr$$

  可行域的直径为 $\Gamma =2\Lambda$，根据定理 7.1，将步长设置为 $\eta =2\Lambda /(mr\sqrt{T})$ 有

$$f\left({\overline{\mathbf{w}}}_T\right)-\underset{\Vert \mathbf{w}\Vert ⩽\Lambda }{\min }f(\mathbf{w})⩽\frac{2mr\Lambda }{\sqrt{T}}=O\left(\frac{1}{\sqrt{T}}\right)$$

  定理得证。

7.4.2 对率回归

  给定训练数据集 $D=\{({\mathbf{x}}_1,y_1),\dots ,({\mathbf{x}}_m,y_m)\}$，对率回归的优化问题如下 :

$$\begin{array}{rl}\underset{\mathbf{w}}{\min }f(\mathbf{w})& =\frac{1}{m}\sum _{i=1}^m\ln \left(1+\exp \left(-y_i{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i\right)\right)\\ \text{ s.t. }& \Vert \mathbf{w}\Vert ⩽\Lambda \end{array}$$

  为了计算随机梯度，将在每一轮均匀随机选择 1 个样本作为输入，将 $t$ 轮迭代选取的样本记为 $({\mathbf{x}}_t,y_t)$，则 $f(\cdot )$ 在当前解 ${\mathbf{w}}_t$ 处的随机梯度可以计算为

$${\mathbf{g}}_t=\frac{y_t\exp \left(-y_t{\mathbf{w}}_t^{\mathrm{T}}{\mathbf{x}}_t\right)}{1+\exp \left(-y_t{\mathbf{w}}_i^{\mathrm{T}}{\mathbf{x}}_t\right)}{\mathbf{x}}_t$$

  根据定理 7.4 的分析，可以得到如下收敛率

定理 7.9 优化对率回归的收敛率 随机梯度下降求解对率回归的收敛率为 $O(\frac{1}{\sqrt{T}})$

证明 假设 $\Vert {\mathbf{x}}_i\Vert ⩽r,i\in [m]$，首先计算随机梯度的上界

$$\Vert \frac{\exp \left(-y_t{\mathbf{w}}_t^{\mathrm{T}}{\mathbf{x}}_t\right)}{1+\exp \left(-y_t{\mathbf{w}}_t^{\mathrm{T}}{\mathbf{x}}_t\right)}{y}_t{\mathbf{x}}_t\Vert ⩽\Vert {\mathbf{x}}_t\Vert ⩽r$$

  因为可行域的直径 $\Gamma =2\Lambda$，依据定理 7.4，调整步长为 $\eta =2\Lambda /(r\sqrt{T})$，则以至少 $1-\delta$ 的概率有

$$f\left({\bar{\mathbf{w}}}_T\right)-\underset{\Vert \mathbf{w}\Vert ⩽\Lambda }{\min }f(\mathbf{w})⩽\frac{2\Lambda r}{\sqrt{T}}\left(1+2\sqrt{2\log \frac{1}{\delta }}\right)=O\left(\frac{1}{\sqrt{T}}\right)$$

  定理得证