第7章：收敛率
编辑：赵志民
本章前言
本章的内容围绕学习理论中的算法收敛率（convergence rate）展开。具体来说，我们将探讨在确定性优化和随机优化中的收敛率问题，并在最后分析支持向量机的实例。
7.1 【概念解释】算法收敛率
在算法分析中，收敛率是指迭代算法逼近解或收敛到最优或期望结果的速度，它衡量算法在减少当前解与最优解之间差异的快慢。
设 \{x_k\} 是算法生成的迭代序列，我们可以根据以下公式来衡量算法的收敛率：
\begin{equation} \lim_{t\rightarrow+\infty}\frac{\|x_{t+1} - x^*\|}{\|x_t - x^*\|^p} = C \end{equation}
其中，C为收敛因子，p为收敛阶数，x^* 表示最优解，\|.\| 表示适当的范数。
根据收敛率的不同情况，我们可以将其分类如下：
- 超线性收敛：p\ge1，C=0，表明每次迭代都会使得误差减小，且减小的速度越来越快。特别地，当p\gt1时，称为p阶收敛。例如，p=2时称为平方收敛，p=3时称为立方收敛。
- 线性收敛：p=1，C\gt0，表明每次迭代都会使得误差减小（误差呈几何级数下降），但减小的速度是一定的。
- 次线性收敛：p=1，C=1，表明每次迭代都会使得误差减小，但减小的速度越来越慢。
7.2 【证明补充】凸函数的确定性优化
书中给出的梯度下降算法中，输出的是 T 轮迭代的均值 \omega，而不是最后一次迭代的结果 \omega_T。这是因为在凸函数的梯度下降过程中，所设定的步长 \eta 是启发式的，因此每次迭代产生的 \omega' 无法保证是局部最优解。
根据定理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}\nabla f(\omega_t)。这种情况下，每次迭代无需启发式算法便可得到该临域的全局最优解，这也是此算法拥有更快收敛率（线性收敛率）的原因。因此，无需返回历史 \omega 的均值。
另外，在 139页 定理7.1的（7.12）推导中，利用了第一章补充内容 AM-GM 不等式 n=2 的结论，即对于任意非负实数 x,y，有：
\begin{equation} \sqrt{xy}\le\frac{x+y}{2} \end{equation}
当且仅当 x=y 时取等号。
因此，只有当 \frac{\Gamma^2}{2\eta T}=\frac{\eta l^2}{2} 时，公式（7.12）中 \frac{\Gamma^2}{2\eta T}+\frac{\eta l^2}{2} 才能取得最小值 \frac{l\Gamma}{\sqrt T}，此时步长 \eta 应设置为 \frac{\Gamma}{l\sqrt T}。类似的推导可以在（7.35）和（7.39）中找到。
7.3 【证明补充】强凸函数的确定性优化
142页 中，在证明定理7.3时，对于（7.19）的推导补充如下。
首先，如果目标函数满足 \lambda-强凸且 \gamma-光滑，那么根据第一章补充内容中的结论，我们有 \gamma\ge\lambda。这是因为对于任意 \omega,\omega'，光滑系数 \gamma 被定义为：
\begin{equation} f(\omega)\le f(\omega')+\nabla f(\omega')^T(\omega-\omega')+\frac{\gamma}{2}\|\omega-\omega'\|^2 \end{equation}
而强凸系数 \lambda 被定义为：
\begin{equation} f(\omega)\ge f(\omega')+\nabla f(\omega')^T(\omega-\omega')+\frac{\lambda}{2}\|\omega-\omega'\|^2 \end{equation}
光滑系数 \gamma 决定了 f(\omega) 的上界，而强凸系数 \lambda 决定了 f(\omega) 的下界，因此光滑系数 \gamma 不小于强凸系数 \lambda。
接着，令 f(\alpha)=\frac{\gamma-\lambda}{\lambda}\alpha^2-\alpha，由于 \frac{\gamma-\lambda}{\lambda}\ge0，我们可以分成以下两种情况讨论：
- 当 \frac{\gamma-\lambda}{\lambda}=0 时，（7.19）转化为：
\begin{equation} \begin{align*} f(\omega_{t+1})&\le \min_{\alpha\in[0,1]}\{f(\omega_t)-\alpha (f(\omega_t)-f(\omega^*))\} \\ \Rightarrow f(\omega_{t+1})-f(\omega^*)&\le \min_{\alpha\in[0,1]}\{1-\alpha\}(f(\omega_t)-f(\omega^*)) \end{align*} \end{equation}
因为 f(\omega_t)-f(\omega^*)\ge0，所以当且仅当 \alpha=1 时，不等式右侧取得最小值 0，此时易知 f(\omega_{t+1})=f(\omega^*)。根据凸函数局部最优解等于全局最优解的结论，我们可以得到 \omega_{t+1}=\omega^*，即算法在第 t+1 轮迭代中收敛到最优解。
- 当 \frac{\gamma-\lambda}{\lambda}\gt0 时，f(\alpha) 为开口向上的二次函数。令 f'(\alpha)=2\frac{\gamma-\lambda}{\lambda}\alpha-1=0，得到 f(\alpha) 的对称轴为 \alpha=\frac{\lambda}{2(\gamma-\lambda)}。我们可以分成以下两种情况讨论：
- 当 \frac{\lambda}{2(\gamma-\lambda)}\ge1 时，f(\alpha) 取得最小值只能在 \alpha=1 处，故而得到（7.20）。
- 当 0\lt\frac{\lambda}{2(\gamma-\lambda)}\lt1 时，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，令：
\begin{equation} S_i = \sum_{j=1}^i X_j \end{equation}
将X_n 的条件方差定义为：
\begin{equation} V_n^2 = \sum_{k=1}^n \mathbb{E}[X_k^2|F_{k-1}] \end{equation}
那么对于任意正数 t 和 v，有：
\begin{equation} P(\max_{i=1,\cdots,k} S_i \gt t,V_k^2 \le v) \le \exp\left( -\frac{t^2}{2(v+Kt/3)}\right) \end{equation}
证明
考虑函数 f(x) = (e^{\theta x} -\theta x-1)/x^2，且 f(0) = \theta^2/2。
通过对该函数求导，我们知道该函数是非减的。即 f(x) \leq f(1)，当 x \leq 1 时：
\begin{equation} e^{\theta x} = 1 + \theta x + x^2f(x) \leq 1+\theta x+x^2f(1) = 1 + \theta x + g(\theta)x^2, \quad x \leq 1 \end{equation}
将其用于随机变量 X_k/K 的期望，可得：
\begin{equation} \mathbb{E} \left[\exp \left(\frac{\theta X_k}{K}\right) \bigg| \mathcal{F}_{k-1}\right] \leq 1 + \frac{\theta}{K} \mathbb{E} \left[X_k | \mathcal{F}_{k-1} \right] + \frac{g(\theta)}{K^2} \mathbb{E} \left[X_k^2 | \mathcal{F}_{k-1} \right] \end{equation}
由于 \{X_k\} 是一个鞅差序列，我们有 \mathbb{E} \left[X_k | \mathcal{F}_{k-1} \right] = 0，结合 1+x \leq e^x, x \geq 0，我们得到：
\begin{equation} \mathbb{E} \left[\exp \left(\frac{\theta X_k}{K}\right) \bigg| \mathcal{F}_{k-1}\right] = 1 + \frac{g(\theta)}{K^2} \mathbb{E} \left[X_k^2 | \mathcal{F}_{k-1} \right] \leq \exp \left(g(\theta) \frac{\mathbb{E} [X_k^2|\mathcal{F}_{k-1}]}{K^2} \right) \end{equation}
考虑一个随机过程：
\begin{equation}Q_k = \exp \left(\theta \frac{S_k}{K} - g(\theta) \frac{V_k^2}{K^2}\right), \quad Q_0 = 1\end{equation}
我们证明这个过程对于滤波 \mathcal{F}_n 是一个超鞅，即 \mathbb{E} [Q_k|\mathcal{F}_{k-1}] \leq Q_{k-1}。
证明如下：
\begin{equation} \begin{align*} \mathbb{E} [Q_k|\mathcal{F}_{k-1}] &= \mathbb{E} \left[\exp \left(\theta \frac{S_k}{K} - g(\theta) \frac{V_k^2}{K^2}\right)\bigg|\mathcal{F}_{k-1}\right] \\ &= \mathbb{E} \left[\exp \left(\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}\right)\bigg|\mathcal{F}_{k-1}\right] \\ &= \exp \left(\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}\right) \mathbb{E} \left[ \exp \left(\theta \frac{X_k}{K}\right)\bigg|\mathcal{F}_{k-1}\right] \end{align*} \end{equation}
应用之前证明的不等式，我们得到：
\begin{equation}\mathbb{E} [Q_k|\mathcal{F}_{k-1}] \leq \exp \left(\theta \frac{S_{k-1}}{K} - g(\theta) \frac{V_{k-1}^2}{K^2}\right) = Q_{k-1}\end{equation}
我们定义 A = \{k \geq 0: \max_{i=1,\cdots,k} S_i \gt t,V_k^2 \le v\}，则有：
\begin{equation}Q_k\geq \exp \left(\theta \frac{t}{K} - g(\theta) \frac{v}{K^2}\right), k \in A\end{equation}
由于 \{Q_k\} 是超鞅，我们有：
\begin{equation}\mathbb{E} [Q_k|\mathcal{F}_{k-1}] \leq \mathbb{E} [Q_{k-1}|\mathcal{F}_{k-2}] \leq \cdots \leq Q_0 = 1\end{equation}
考虑到 1 \geq \mathbb{P}(A)，我们有：
\begin{equation}1 \geq \mathbb{E} [Q_k|\mathcal{F}_{k-1}] \geq \exp \left(\theta \frac{t}{K} - g(\theta) \frac{v}{K^2}\right) \mathbb{P}(A), k \in A\end{equation}
因此：
\begin{equation} \begin{align*} \mathbb{P}(A) \leq \exp \left(g(\theta) \frac{v}{K^2} -\theta \frac{t}{K} \right) \end{align*} \end{equation}
由于上述不等式对任何 \theta \gt 0 都成立，我们可以写为：
\begin{equation}P(A) \leq \inf_{\theta \gt 0} \exp \left(g(\theta) \frac{v}{K^2} - \theta \frac{t}{K} \right)\end{equation}
检查不等式右边的一阶导数，我们知道该下确界在 \theta = \log (1+Kt/v) 处取得。
对于指数内部的表达式，我们进行如下变换：
\begin{equation} \begin{align*} \theta \frac{t}{K} - g(\theta)\frac{v}{K^2} &= \log \left(1 + \frac{Kt}{v}\right) \frac{t}{K} - \frac{v}{K^2} \left(\frac{Kt}{v} - \log \left(1 + \frac{Kt}{v}\right) \right) \\ &=\frac{v}{K^2} \left( \left(1+\frac{Kt}{v} \right) \log \left(1 + \frac{Kt}{v}\right) - \frac{Kt}{v} \right) \\ &= \frac{v}{K^2} h\left( \frac{Kt}{v} \right) \end{align*} \end{equation}
其中 h(u) = (1+u)\log(1+u) - u。
通过对表达式求二阶导数的方法，我们也可以证明：
\begin{equation} h(u) \geq \frac{u^2}{2(1 + u/3)},\quad u \geq 0 \end{equation}
综上所述，我们有：
\begin{equation} P(A) \leq \exp \left( -\frac{v}{K^2} h \left( \frac{Kt}{v} \right)\right) \leq \exp \left( - \frac{v}{K^2} \frac{K^2t^2}{2v (v+Kt/3)} \right) = \exp\left( -\frac{t^2}{2(v+Kt/3)}\right) \end{equation}
7.5 【证明补充】Epoch-GD 的收敛率
150页 引理7.2给出了Epoch-GD外层循环收敛率的泛化上界，我们对其中部分推导进行必要补充。
首先，（7.60）中第二个不等式的推导利用了Cauchy-Schwarz不等式（1.14），即 \|x^Ty\|\le\|x\|\|y\|。这里，我们令 x=\underbrace{[1,\cdots,1]}_{T}，y=\underbrace{[\|\omega_1-w^*\|,\cdots,\|\omega_T-w^*\|]}_{T}，则有：
\begin{equation} |x^Ty|=\sum_{t=1}^T\|\omega_t-w^*\|\le \sqrt{T}\sqrt{\sum_{t=1}^T\|\omega_t-w^*\|^2}=|x\|y| \end{equation}
其次，（7.62）中最后两个不等式的推导利用了一些常见的缩放技巧，我们在这里给出完整形式：
\begin{equation} \begin{align*} &\sum_{i=1}^m P\left(\sum_{t=1}^T \delta_t \ge 2\sqrt{4l^2A_T\tau}+\frac{2}{3}\frac{4l^2}{\lambda}\tau+\frac{4l^2}{\lambda},V_T^2\le4l^2A_T,A_T\in\left(\frac{4l^2}{\lambda^2T}2^{i-1},\frac{4l^2}{\lambda^2T}2^i\right)\right) \\ \le &\sum_{i=1}^m P\left(\sum_{t=1}^T \delta_t \ge 2\sqrt{4l^2A_T\tau}+\frac{2}{3}\frac{4l^2}{\lambda}\tau,V_T^2\le4l^2A_T,A_T\in\left(\frac{4l^2}{\lambda^2T}2^{i-1},\frac{4l^2}{\lambda^2T}2^i\right)\right) \\ \le &\sum_{i=1}^m P\left(\sum_{t=1}^T \delta_t \ge \sqrt{2\frac{16l^42^i}{\lambda^2T}\tau}+\frac{2}{3}\frac{4l^2}{\lambda}\tau,V_T^2\le\frac{16l^42^i}{\lambda^2T}\right) \\ \le &\sum_{i=1}^m P\left(\max_{j=1,\cdots,T}\underbrace{\sum_{t=1}^j \delta_t}_{S_j} \ge \sqrt{2\underbrace{\frac{16l^42^i}{\lambda^2T}}_{\nu}\tau}+\frac{2}{3}\underbrace{\frac{4l^2}{\lambda}}_{K}\tau,V_T^2\le\underbrace{\frac{16l^42^i}{\lambda^2T}}_{\nu}\right) \\ \le &\sum_{i=1}^m e^{-\tau} \\ = &me^{-\tau} \end{align*} \end{equation}
这里，第一个不等式利用了 \frac{4l^2}{\lambda} \gt 0 的事实对 \sum_{t=1}^T \delta_t 的范围进行概率缩放；
第二个不等式利用了 A_T 的下界和上界分别对 \sum_{t=1}^T \delta_t 和 V_T^2 的范围进行概率缩放；
第三个不等式利用了 \max_{j=1,\cdots,T}\sum_{t=1}^j \delta_t 比 \sum_{t=1}^T \delta_t 更为宽松的事实对 V_T^2 进行概率缩放；
第四个不等式利用了定理7.6的结论。
最后，（7.64）中第二个不等式的推导利用了开口向下的二次函数 f(x)=ax^2+bx+c,a\lt0 拥有最大值点 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^{\dagger}。
其次，（7.77）的推导利用了函数 f(x)=(1-\frac{1}{x})^x 在 x=\frac{k^{\dagger}}{\delta}\gt1 时单调递增的事实，以下是更严格的证明。
对函数 f(x) 两边取对数，得到：
\begin{equation} \ln f(x)=x\ln(1-\frac{1}{x}) \end{equation}
接着对两边分别求导，可得：
\begin{equation} \frac{f'(x)}{f(x)}=\ln(1-\frac{1}{x})+\frac{1}{x-1} \end{equation}
易知当 x\gt1 时，f(x)\gt0，因此我们只需要关注等式右边在 x\gt1 时的符号。
令 g(x)=\ln(1-\frac{1}{x})+\frac{1}{x-1}，则有：
\begin{equation} g'(x)=\frac{1}{x(x-1)^2} \end{equation}
易知当 x\gt1 时，g'(x)\lt0，因此：
\begin{equation} g(x)\gt\lim_{x\rightarrow+\infty}g(x)=\lim_{x\rightarrow+\infty}\ln(1-\frac{1}{x})+\lim_{x\rightarrow+\infty}\frac{1}{x-1}=0 \end{equation}
综上，当 x\gt1 时，\frac{f'(x)}{f(x)}=g(x)\gt0，即 f'(x)\gt0，因此 f(x) 在 x\gt1 时单调递增。