Chapter 7: 收敛率¶
约 2679 个字 4 张图片 预计阅读时间 9 分钟
几乎全是凸优化里边的知识，如果学过会很爽
本章关注优化算法的收敛率/Convergence Rate，首先回顾一下优化问题的一般形式：
其中 \(f(\cdot)\) 是优化的目标函数，\(\boldsymbol{w}\) 是优化变量，\(\mathcal{W}\) 是优化变量的可行域。为了方便讨论，下面仅关注凸优化问题，即要求上述优化问题的目标函数 \(f(\cdot)\) 是凸函数，优化变量 \(\boldsymbol{w}\) 的可行域 \(\mathcal{W}\) 是凸集合。注意到，第 1 章所提到的支持向量机的主问题和对偶问题均可以表示为上述形式。在评价不同的优化算法时，会有收敛条件和收敛率这两个角度来对优化进程进行评估和考量。
1. 基本概念¶
令上述优化问题的最优解为 \(\boldsymbol{w}^* \in \arg\min_{\boldsymbol{w}\in\mathcal{W}} f(\boldsymbol{w})\)，优化算法旨在高效地寻找优化问题的最优解 \(\boldsymbol{w}^*\)，或目标函数的最小值 \(f(w^*)\)。然而，精确求解优化问题一般而言是非常困难的。因此，优化算法通常设计为迭代算法，不断近似求解优化问题。记迭代优化算法为 \(\mathcal{A}\)，该算法生成一组序列 \(\{\boldsymbol{w}_1, \boldsymbol{w}_2, \ldots, \boldsymbol{w}_t, \ldots\}\) 来不断逼近目标函数的最优解 \(\boldsymbol{w}^*\)。一般而言，迭代优化算法采用如下更新方法，
其中 \(\mathcal{M}\) 为优化算法的更新策略，\(\mathcal{O}\) 为函数信息源。
根据所使用的函数信息源 \(\mathcal{O}\) 的不同，常用优化算法可以分为零阶算法、一阶算法和二阶算法：
- 零阶算法：仅利用函数值来优化的算法，典型的零阶优化算法有遗传算法、粒子群算法和模拟退火算法等。
- 一阶算法：利用函数的梯度信息来优化的算法，典型的一阶优化算法有梯度下降/Gradient Descent/GD 算法和随机梯度下降/Stochastic Gradient Descent/SGD 算法等。
- 二阶算法：利用函数的 Hessian 矩阵来优化的算法，典型的二阶优化算法有牛顿法。
刻画优化算法性能有两种等价的衡量准则：收敛率和迭代复杂度。假设算法迭代了 \(T\) 轮，\(\boldsymbol{w}_T\) 为最终输出。
-
收敛率旨在刻画优化误差 \(f(\boldsymbol{w}_T) - f(\boldsymbol{w}^*)\) 与迭代轮数 \(T\) 之间的关系，常见的收敛率有
\[f(\boldsymbol{w}_T) - f(\boldsymbol{w}^*) = O\left(\frac{1}{\sqrt{T}}\right), O\left(\frac{1}{T}\right), O\left(\frac{1}{T^2}\right), O\left(\frac{1}{\beta^T}\right),\]其中 \(\beta > 1\)。上面列举的收敛率越来越快，最后一种收敛率 \(O(1/\beta^T)\) 通常被称为线性收敛，因为误差位于误差和迭代次数的对数线性坐标图中的一根直线的下方。
-
迭代复杂度则是刻画为了达到 \(\epsilon\)-最优解，需要的迭代轮数。具体而言，迭代复杂度描述为了达到 \(f(\boldsymbol{w}_T) - f(\boldsymbol{w}^*) \leq \epsilon\)，迭代轮数 \(T\) 和 \(\epsilon\) 的关系。上述收敛率所对应的迭代复杂度分别为：
\[T = \Omega\left(\frac{1}{\epsilon^2}\right), \Omega\left(\frac{1}{\epsilon}\right), \Omega\left(\frac{1}{\sqrt{\epsilon}}\right), \Omega\left(\log\frac{1}{\epsilon}\right).\]
收敛率和迭代复杂度反映了目标函数的最优性。当最优解唯一时，也可以采用当前解和最优解之间的距离 \(d(\boldsymbol{w}_t, \boldsymbol{w}^*)\) 作为评估优化算法性能的指标，其中 \(d(\cdot,\cdot)\) 是某距离度量函数，如欧氏距离 \(d(\boldsymbol{w}_t, \boldsymbol{w}^*) = \|\boldsymbol{w}_t - \boldsymbol{w}^*\|\)。
常见的优化算法可以分为确定优化/Deterministic Optimization 和随机优化/Stochastic Optimization 两类。确定优化利用函数的真实信息来进行迭代更新，而随机优化则会利用一些随机信息（如梯度的无偏估计）来进行迭代更新。下面将分别介绍确定优化方法和随机优化方法，并考虑凸函数和强凸函数两种情况。
2. 确定优化¶
2.1 凸函数¶
对于一般的凸优化问题，可以采用梯度下降达到 \(O(1/\sqrt{T})\) 的收敛率，我们这里考虑的是梯度投影法，基本流程如下：
在第 \(t\) 轮迭代中，首先计算函数 \(f(\cdot)\) 在 \(\boldsymbol{w}_t\) 上的梯度 \(\nabla f(\boldsymbol{w}_t)\)，然后依据梯度下降 \(\boldsymbol{w}'_{t+1} = \boldsymbol{w}_t - \eta_t \nabla f(\boldsymbol{w}_t)\) 更新当前解，其中 \(\eta_t > 0\) 为步长。这里需要注意的是，在原始问题中存在 \(\boldsymbol{w} \in \mathcal{W}\) 的约束。但是通过梯度下降获得的中间解 \(\boldsymbol{w}'_{t+1}\) 不必属于集合 \(\mathcal{W}\)。因此还需要通过投影操作 \(\boldsymbol{w}_{t+1} = \Pi_\mathcal{W}(\boldsymbol{w}'_{t+1})\) 保证下一轮的解属于 \(\mathcal{W}\)。投影操作的定义为：
其目的是在集合 \(\mathcal{W}\) 中寻找距离输入最近的点。最后，将算法 \(T\) 轮迭代的平均值作为输出。
下面给出采用固定步长梯度下降的收敛率。
定理 7.1（梯度下降收敛率）：假设目标函数 \(f(\cdot)\) 是凸的 \(l\)-Lipschitz 连续函数，且可行域 \(\mathcal{W}\) 有界，则采用固定步长梯度下降的收敛率为 \(O\left(1/\sqrt{T}\right)\)。
证明
假设可行域 \(\mathcal{W}\) 直径为 \(\Gamma\)，并且目标函数满足 \(l\)-Lipschitz 连续，即对于任意 \(\boldsymbol{u}, \boldsymbol{v} \in \mathcal{W}\)，
为了简化分析，考虑固定的步长 \(\eta_t = \eta\)。
对于任意的 \(\boldsymbol{w} \in \mathcal{W}\)，
最后一个不等号利用了凸集合投影操作的非扩展性质：
注意到目标函数满足 \(l\)-Lipschitz连续，所以我们可以得到：
对上式从 \(t=1\) 到 \(T\) 求和，有：
根据 Jensen 不等式可以得到：
因此，
这使用了均值不等式的性质，其中步长设置为 \(\eta = \Gamma/(l\sqrt{T})\)。
定理得证。
2.2 强凸函数¶
本节考虑目标函数 \(f : \mathcal{W} \mapsto \mathbb{R}\) 是 \(\lambda\)-强凸函数，即其满足 \(f(\boldsymbol{z}) \geq f(\boldsymbol{x}) + \nabla f(\boldsymbol{x})^{\mathrm{T}}(\boldsymbol{z} - \boldsymbol{x}) + \frac{\lambda}{2}\lVert \boldsymbol{z} - \boldsymbol{x} \rVert^2\)。对于 \(\lambda\)-强凸函数，有以下定理：
定理 7.2（强凸函数性质）：假设 \(f\) 为 \(\lambda\)-强凸函数，\(\boldsymbol{w}^*\) 为其最优解，对于任意 \(\boldsymbol{w} \in \mathcal{W}\) 有
此外，若梯度有上界 \(l\)，则
我们也要求其是一个 \(\gamma\)-Lipschitz 连续函数，即对于任意 \(\boldsymbol{w}, \boldsymbol{v} \in \mathcal{W}\)，有
根据我们在凸优化已经证明的内容，这等价于：
针对光滑且强凸函数的梯度下降算法的基本流程如下：
和一般的凸函数的梯度下降方法类似，每轮迭代的优化式子的闭式解为：
因此，其本质仍然是梯度投影法。对于上述梯度下降算法，有如下定理：
定理 7.3（梯度下降收敛率）：若目标函数满足 \(\lambda\)-强凸且 \(\gamma\)-Lipschitz 连续，梯度下降取得了线性收敛率 \(O\left(1/\beta^T\right)\)，其中 \(\beta > 1\)。
证明
根据目标函数的性质以及更新公式，
这就到了对二次函数进行优化：
-
如果 \(\lambda/(2(\gamma-\lambda)) \geq 1\)，令 \(\alpha = 1\)，则有
\[f(\boldsymbol{w}_{t+1}) - f(\boldsymbol{w}^*) \leq \frac{\gamma-\lambda}{\lambda}(f(\boldsymbol{w}_t) - f(\boldsymbol{w}^*)) \leq 1/2(f(\boldsymbol{w}_t) - f(\boldsymbol{w}^*)).\] -
如果 \(\lambda/(2(\gamma-\lambda)) < 1\)，令 \(\alpha = \lambda/(2(\gamma-\lambda))\)，则有
\[f(\boldsymbol{w}_{t+1}) - f(\boldsymbol{w}^*) \leq (1 - \frac{\lambda}{4(\gamma - \lambda)})(f(\boldsymbol{w}_t) - f(\boldsymbol{w}^*)) = \frac{4\gamma-5\lambda}{4(\gamma-\lambda)}(f(\boldsymbol{w}_t) - f(\boldsymbol{w}^*)).\]
因此，令
那么下式总是成立
将上式扩展可得
定理得证。
如果目标函数只满足强凸性质，就可以采用后面针对强凸函数的随机优化算法，仅需要将随机梯度改为真实梯度。
3. 随机优化¶
3.1 凸函数¶
3.2 强凸函数¶
3.3 Epoch-GD 的大概率结论¶
注意到，Epoch-GD 同样可以用于确定优化场景，此时，将随机梯度替换成真实梯度，收敛率保持不变。因此，对于目标函数是强凸的确定优化，可以直接应用 Epoch-GD 算法得到 \(O(1/[\lambda T])\) 的收敛率。此外，还可以证明随机情况下 Epoch-GD 以大概率取得 \(O(\log\log T / [\lambda T])\) 的收敛率。但是这部分证明过于复杂，下面只列举结论，有时间再补充证明。
证明
证明
证明
4. 分析实例¶
4.1 支持向量机¶
我们分析如何使用确定优化方法求解支持向量机，唯一区别就是我们使用的是次梯度，而不是一般意义的梯度。
算法的第五行出现了错误，应该是 \(\boldsymbol{w}_{t+1}^{\prime} = \dfrac{\Lambda}{\max(\lVert \boldsymbol{w}_{t+1}^{\prime}\rVert, \Lambda)} \boldsymbol{w}_{t+1}^{\prime}\)。
4.2 对率回归¶
