第7章：收敛率

编辑：赵志民

---

本章前言

本章的内容围绕学习理论中的算法收敛率（Convergence Rate）展开。具体来说，我们将探讨在确定性优化和随机优化中的收敛率问题，并在最后分析支持向量机的实例。

7.1 【概念解释】算法收敛率

在算法分析中，收敛率是指迭代算法逼近解或收敛到最优或期望结果的速度，它衡量算法在减少当前解与最优解之间差异的快慢。

设 $\{x_k\}$ 是算法生成的迭代序列，我们可以根据以下公式来衡量算法的收敛率：

$$\underset{t\to +\mathrm{\infty }}{lim}\frac{\parallel x_{t+1}-x^{\ast }\parallel }{\parallel x_t-x^{\ast }{\parallel }^p}=C$$

其中，$C$为收敛因子，$p$为收敛阶数，$x^{\ast }$ 表示最优解，$\parallel .\parallel$ 表示适当的范数。

根据收敛率的不同情况，我们可以将其分类如下：

1. 超线性收敛：$p\ge 1$，$C=0$，表明每次迭代都会使得误差减小，且减小的速度越来越快。特别地，当$p>1$时，称为$p$阶收敛。例如，$p=2$时称为平方收敛，$p=3$时称为立方收敛。
2. 线性收敛：$p=1$，$C>0$，表明每次迭代都会使得误差减小（误差呈几何级数下降），但减小的速度是一定的。
3. 次线性收敛：$p=1$，$C=1$，表明每次迭代都会使得误差减小，但减小的速度越来越慢。

7.2 【证明补充】凸函数的确定性优化

书中给出的梯度下降算法中，输出的是 $T$ 轮迭代的均值 $\omega$，而不是最后一次迭代的结果 ${\omega }_T$。这是因为在凸函数的梯度下降过程中，所设定的步长 $\eta$ 是启发式的，因此每次迭代产生的 ${\omega }^{\prime }$ 无法保证是局部最优解。

根据定理7.1，$T$ 轮迭代的 $\omega$ 均值具有次线性收敛率，而无法证明最后一次迭代值 ${\omega }_T$ 也具有相同的收敛率。因此，返回 $\omega$ 的均值虽然会增加计算代价，但可以确保稳定的收敛率。这一思想在7.3.1和7.3.2中梯度下降算法中也有体现。

作为对比，在7.2.2中的强凸函数梯度下降算法中，我们只输出了最后一次迭代值 ${\omega }_T$。这是因为在强凸函数的条件下，每次迭代的梯度更新都有闭式解 ${\omega }_{t+1}={\omega }_t-\frac{1}{\gamma }\mathrm{\nabla }f({\omega }_t)$。这种情况下，每次迭代无需启发式算法便可得到该临域的全局最优解，这也是此算法拥有更快收敛率（线性收敛率）的原因。因此，无需返回历史 $\omega$ 的均值。

另外，在 139页 定理7.1的（7.12）推导中，利用了第一章补充内容 AM-GM 不等式 $n=2$ 的结论，即对于任意非负实数 $x,y$，有：

$$\sqrt{xy}\le \frac{x+y}{2}$$

当且仅当 $x=y$ 时取等号。

因此，只有当 $\frac{{\mathrm{\Gamma }}^2}{2\eta T}=\frac{\eta l^2}{2}$ 时，公式（7.12）中 $\frac{{\mathrm{\Gamma }}^2}{2\eta T}+\frac{\eta l^2}{2}$ 才能取得最小值 $\frac{l\mathrm{\Gamma }}{\sqrt{T}}$，此时步长 $\eta$ 应设置为 $\frac{\mathrm{\Gamma }}{l\sqrt{T}}$。类似的推导可以在（7.35）和（7.39）中找到。

7.3 【证明补充】强凸函数的确定性优化

142页 中，在证明定理7.3时，对于（7.19）的推导补充如下。

首先，如果目标函数满足 $\lambda$-强凸且 $\gamma$-光滑，那么根据第一章补充内容中的结论，我们有 $\gamma \ge \lambda$。这是因为对于任意 $\omega ,{\omega }^{\prime }$，光滑系数 $\gamma$ 被定义为：

$$f(\omega )\le f({\omega }^{\prime })+\mathrm{\nabla }f({\omega }^{\prime }{)}^T(\omega -{\omega }^{\prime })+\frac{\gamma }{2}\parallel \omega -{\omega }^{\prime }{\parallel }^2$$

而强凸系数 $\lambda$ 被定义为：

$$f(\omega )\ge f({\omega }^{\prime })+\mathrm{\nabla }f({\omega }^{\prime }{)}^T(\omega -{\omega }^{\prime })+\frac{\lambda }{2}\parallel \omega -{\omega }^{\prime }{\parallel }^2$$

光滑系数 $\gamma$ 决定了 $f(\omega )$ 的上界，而强凸系数 $\lambda$ 决定了 $f(\omega )$ 的下界，因此光滑系数 $\gamma$ 不小于强凸系数 $\lambda$。

接着，令 $f(\alpha )=\frac{\gamma -\lambda }{\lambda }{\alpha }^2-\alpha$，由于 $\frac{\gamma -\lambda }{\lambda }\ge 0$，我们可以分成以下两种情况讨论：

1. 当 $\frac{\gamma -\lambda }{\lambda }=0$ 时，（7.19）转化为：

$$\begin{array}{rl}f({\omega }_{t+1})& \le \underset{\alpha \in [0,1]}{min}\{f({\omega }_t)-\alpha (f({\omega }_t)-f({\omega }^{\ast }))\}\\ \Rightarrow f({\omega }_{t+1})-f({\omega }^{\ast })& \le \underset{\alpha \in [0,1]}{min}\{1-\alpha \}(f({\omega }_t)-f({\omega }^{\ast }))\end{array}$$

因为 $f({\omega }_t)-f({\omega }^{\ast })\ge 0$，所以当且仅当 $\alpha =1$ 时，不等式右侧取得最小值 $0$，此时易知 $f({\omega }_{t+1})=f({\omega }^{\ast })$。根据凸函数局部最优解等于全局最优解的结论，我们可以得到 ${\omega }_{t+1}={\omega }^{\ast }$，即算法在第 $t+1$ 轮迭代中收敛到最优解。

2. 当 $\frac{\gamma -\lambda }{\lambda }>0$ 时，$f(\alpha )$ 为开口向上的二次函数。令 $f^{\prime }(\alpha )=2\frac{\gamma -\lambda }{\lambda }\alpha -1=0$，得到 $f(\alpha )$ 的对称轴为 $\alpha =\frac{\lambda }{2(\gamma -\lambda )}$。我们可以分成以下两种情况讨论：
   • 当 $\frac{\lambda }{2(\gamma -\lambda )}\ge 1$ 时，$f(\alpha )$ 取得最小值只能在 $\alpha =1$ 处，故而得到（7.20）。
   • 当 $0<\frac{\lambda }{2(\gamma -\lambda )}<1$ 时，$f(\alpha )$ 取得最小值在 $\alpha =\frac{\lambda }{2(\gamma -\lambda )}$ 处，故而得到（7.21）。

余下的推导部分与书中相同，此处不再赘述。

7.4 【定理证明】鞅差序列的 Bernstein 不等式

149页 定理7.6 给出了鞅差序列的 Bernstein 不等式，我们在这里给出完整的证明过程。

假设 $X_1,\cdots ,X_n$ 是定义在 $f=(f_i{)}_{1\le i\le n}$ 上的有界鞅差序列且 $|X_i|\le K$，令：

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

将$X_n$ 的条件方差定义为：

$$V_n^2=\sum _{k=1}^n\mathbb{E}[X_k^2|F_{k-1}]$$

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

$$P(\underset{i=1,\cdots ,k}{max}{S}_i>t,V_k^2\le v)\le \exp (-\frac{t^2}{2(v+Kt/3)})$$

证明

考虑函数 $f(x)=(e^{\theta x}-\theta x-1)/x^2$，且 $f(0)={\theta }^2/2$。 通过对该函数求导，我们知道该函数是非减的。即 $f(x)\le f(1)$，当 $x\le 1$ 时：

$$e^{\theta x}=1+\theta x+x^{2}f(x)\le 1+\theta x+x^{2}f(1)=1+\theta x+g(\theta )x^2,x\le 1$$

将其用于随机变量 $X_k/K$ 的期望，可得：

$$\mathbb{E}[\exp \left(\frac{\theta X_k}{K}\right)|{\mathcal{F}}_{k-1}]\le 1+\frac{\theta }{K}\mathbb{E}[X_k|{\mathcal{F}}_{k-1}]+\frac{g(\theta )}{K^2}\mathbb{E}[X_k^2|{\mathcal{F}}_{k-1}]$$

由于 $\{X_k\}$ 是一个鞅差序列，我们有 $\mathbb{E}[X_k|{\mathcal{F}}_{k-1}]=0$，结合 $1+x\le e^x,x\ge 0$，我们得到：

$$\mathbb{E}[\exp \left(\frac{\theta X_k}{K}\right)|{\mathcal{F}}_{k-1}]=1+\frac{g(\theta )}{K^2}\mathbb{E}[X_k^2|{\mathcal{F}}_{k-1}]\le \exp (g(\theta )\frac{\mathbb{E}[X_k^2|{\mathcal{F}}_{k-1}]}{K^2})$$

考虑一个随机过程：

$$Q_k=\exp (\theta \frac{S_k}{K}-g(\theta )\frac{V_k^2}{K^2}),Q_0=1$$

我们证明这个过程对于滤波 ${\mathcal{F}}_n$ 是一个超鞅，即 $\mathbb{E}[Q_k|{\mathcal{F}}_{k-1}]\le Q_{k-1}$。

证明如下：

$$\begin{array}{rl}\mathbb{E}[Q_k|{\mathcal{F}}_{k-1}]& =\mathbb{E}[\exp (\theta \frac{S_k}{K}-g(\theta )\frac{V_k^2}{K^2})|{\mathcal{F}}_{k-1}]\\ & =\mathbb{E}[\exp (\theta \frac{S_{k-1}}{K}-g(\theta )\frac{V_{k-1}^2}{K^2}-g(\theta )\frac{\mathbb{E}[X_k^2|{\mathcal{F}}_{k-1}]}{K^2}+\theta \frac{X_k}{K})|{\mathcal{F}}_{k-1}]\\ & =\exp (\theta \frac{S_{k-1}}{K}-g(\theta )\frac{V_{k-1}^2}{K^2}-g(\theta )\frac{\mathbb{E}[X_k^2|{\mathcal{F}}_{k-1}]}{K^2})\mathbb{E}[\exp \left(\theta \frac{X_k}{K}\right)|{\mathcal{F}}_{k-1}]\end{array}$$

应用之前证明的不等式，我们得到：

$$\mathbb{E}[Q_k|{\mathcal{F}}_{k-1}]\le \exp (\theta \frac{S_{k-1}}{K}-g(\theta )\frac{V_{k-1}^2}{K^2})=Q_{k-1}$$

我们定义 $A=\{k\ge 0:\underset{i=1,\cdots ,k}{max}{S}_i>t,V_k^2\le v\}$，则有：

$$Q_k\ge \exp (\theta \frac{t}{K}-g(\theta )\frac{v}{K^2}),k\in A$$

由于 $\{Q_k\}$ 是超鞅，我们有：

$$\mathbb{E}[Q_k|{\mathcal{F}}_{k-1}]\le \mathbb{E}[Q_{k-1}|{\mathcal{F}}_{k-2}]\le \cdots \le Q_0=1$$

考虑到 $1\ge \mathbb{P}(A)$，我们有：

$$1\ge \mathbb{E}[Q_k|{\mathcal{F}}_{k-1}]\ge \exp (\theta \frac{t}{K}-g(\theta )\frac{v}{K^2})\mathbb{P}(A),k\in A$$

因此：

$$\begin{array}{r}\mathbb{P}(A)\le \exp (g(\theta )\frac{v}{K^2}-\theta \frac{t}{K})\end{array}$$

由于上述不等式对任何 $\theta >0$ 都成立，我们可以写为：

$$P(A)\le \underset{\theta >0}{inf}\exp (g(\theta )\frac{v}{K^2}-\theta \frac{t}{K})$$

检查不等式右边的一阶导数，我们知道该下确界在 $\theta =\log (1+Kt/v)$ 处取得。

对于指数内部的表达式，我们进行如下变换：

$$\begin{array}{rl}\theta \frac{t}{K}-g(\theta )\frac{v}{K^2}& =\log (1+\frac{Kt}{v})\frac{t}{K}-\frac{v}{K^2}(\frac{Kt}{v}-\log (1+\frac{Kt}{v}))\\ & =\frac{v}{K^2}((1+\frac{Kt}{v})\log (1+\frac{Kt}{v})-\frac{Kt}{v})\\ & =\frac{v}{K^2}h\left(\frac{Kt}{v}\right)\end{array}$$

其中 $h(u)=(1+u)\log (1+u)-u$。

通过对表达式求二阶导数的方法，我们也可以证明：

$$h(u)\ge \frac{u^2}{2(1+u/3)},u\ge 0$$

综上所述，我们有：

$$P(A)\le \exp (-\frac{v}{K^2}h\left(\frac{Kt}{v}\right))\le \exp (-\frac{v}{K^2}\frac{K^2{t}^2}{2v(v+Kt/3)})=\exp (-\frac{t^2}{2(v+Kt/3)})$$

7.5 【证明补充】Epoch-GD 的收敛率

150页 引理7.2给出了Epoch-GD外层循环收敛率的泛化上界，我们对其中部分推导进行必要补充。

首先，（7.60）中第二个不等式的推导利用了Cauchy-Schwarz不等式（1.14），即 $\parallel x^{T}y\parallel \le \parallel x\parallel \parallel y\parallel$。这里，我们令 $x=\underset{T}{\underbrace{[1,\cdots ,1]}}$，$y=\underset{T}{\underbrace{[\parallel {\omega }_1-w^{\ast }\parallel ,\cdots ,\parallel {\omega }_T-w^{\ast }\parallel ]}}$，则有：

$$|x^{T}y|=\sum _{t=1}^T\parallel {\omega }_t-w^{\ast }\parallel \le \sqrt{T}\sqrt{\sum _{t=1}^T\parallel {\omega }_t-w^{\ast }{\parallel }^2}=|x\parallel y|$$

其次，（7.62）中最后两个不等式的推导利用了一些常见的缩放技巧，我们在这里给出完整形式：

$$\begin{array}{rl}& \sum _{i=1}^{m}P(\sum _{t=1}^T{\delta }_t\ge 2\sqrt{4l^2{A}_T\tau }+\frac{2}{3}\frac{4l^2}{\lambda }\tau +\frac{4l^2}{\lambda },V_T^2\le 4l^2{A}_T,A_T\in (\frac{4l^2}{{\lambda }^{2}T}{2}^{i-1},\frac{4l^2}{{\lambda }^{2}T}{2}^i))\\ \le & \sum _{i=1}^{m}P(\sum _{t=1}^T{\delta }_t\ge 2\sqrt{4l^2{A}_T\tau }+\frac{2}{3}\frac{4l^2}{\lambda }\tau ,V_T^2\le 4l^2{A}_T,A_T\in (\frac{4l^2}{{\lambda }^{2}T}{2}^{i-1},\frac{4l^2}{{\lambda }^{2}T}{2}^i))\\ \le & \sum _{i=1}^{m}P(\sum _{t=1}^T{\delta }_t\ge \sqrt{2\frac{16l^4{2}^i}{{\lambda }^{2}T}\tau }+\frac{2}{3}\frac{4l^2}{\lambda }\tau ,V_T^2\le \frac{16l^4{2}^i}{{\lambda }^{2}T})\\ \le & \sum _{i=1}^{m}P(\underset{j=1,\cdots ,T}{max}\underset{S_j}{\underbrace{\sum _{t=1}^j{\delta }_t}}\ge \sqrt{2\underset{\nu }{\underbrace{\frac{16l^4{2}^i}{{\lambda }^{2}T}}}\tau }+\frac{2}{3}\underset{K}{\underbrace{\frac{4l^2}{\lambda }}}\tau ,V_T^2\le \underset{\nu }{\underbrace{\frac{16l^4{2}^i}{{\lambda }^{2}T}}})\\ \le & \sum _{i=1}^m{e}^{-\tau }\\ =& m{e}^{-\tau }\end{array}$$

这里，第一个不等式利用了 $\frac{4l^2}{\lambda }>0$ 的事实对 $\sum _{t=1}^T{\delta }_t$ 的范围进行概率缩放； 第二个不等式利用了 $A_T$ 的下界和上界分别对 $\sum _{t=1}^T{\delta }_t$ 和 $V_T^2$ 的范围进行概率缩放； 第三个不等式利用了 $\underset{j=1,\cdots ,T}{max}\sum _{t=1}^j{\delta }_t$ 比 $\sum _{t=1}^T{\delta }_t$ 更为宽松的事实对 $V_T^2$ 进行概率缩放； 第四个不等式利用了定理7.6的结论。

最后，（7.64）中第二个不等式的推导利用了开口向下的二次函数 $f(x)=a{x}^2+bx+c,a<0$ 拥有最大值点 $x_0=-\frac{b}{2a}$ 的事实。我们令 $x=\sqrt{A_T}$，然后取 $a=-\frac{\lambda }{2},b=2\sqrt{4l^2\ln \frac{m}{\delta }},c=0$，则易知 $f(x)$ 的最大值为 $\frac{8l^2}{\lambda }\ln \frac{m}{\delta }$，于是得到了（7.64）中的结论。

进一步地，152页引理7.3利用数学归纳法给出了特定步长和迭代次数下Epoch-GD外层循环收敛率的泛化上界，这为154页定理7.7中Epoch-GD的收敛率奠定了基础。我们对后者的部分推导进行必要补充。

首先，观察（7.75）可以发现，Epoch-GD外层的迭代次数 $k$ 需要满足 $\frac{\alpha }{2}(2^k-1)\le T$，即 $k=\lfloor {\log }_2(\frac{2T}{\alpha }+1)\rfloor$，因此构造了（7.66）中的 $k^{†}$。

其次，（7.77）的推导利用了函数 $f(x)=(1-\frac{1}{x}{)}^x$ 在 $x=\frac{k^{†}}{\delta }>1$ 时单调递增的事实，以下是更严格的证明。

对函数 $f(x)$ 两边取对数，得到：

$$\ln f(x)=x\ln (1-\frac{1}{x})$$

接着对两边分别求导，可得：

$$\frac{f^{\prime }(x)}{f(x)}=\ln (1-\frac{1}{x})+\frac{1}{x-1}$$

易知当 $x>1$ 时，$f(x)>0$，因此我们只需要关注等式右边在 $x>1$ 时的符号。 令 $g(x)=\ln (1-\frac{1}{x})+\frac{1}{x-1}$，则有：

$$g^{\prime }(x)=\frac{1}{x(x-1{)}^2}$$

易知当 $x>1$ 时，$g^{\prime }(x)<0$，因此：

$$g(x)>\underset{x\to +\mathrm{\infty }}{lim}g(x)=\underset{x\to +\mathrm{\infty }}{lim}\ln (1-\frac{1}{x})+\underset{x\to +\mathrm{\infty }}{lim}\frac{1}{x-1}=0$$

综上，当 $x>1$ 时，$\frac{f^{\prime }(x)}{f(x)}=g(x)>0$，即 $f^{\prime }(x)>0$，因此 $f(x)$ 在 $x>1$ 时单调递增。