收敛性分析基本原理

SGD和Momentum等常用优化方法被广泛应用。这些方法处理优化问题时，凸性通常会简化处理过程，但深度学习 (deep learning)中的非凸情况则存在局部最小值和鞍点等重要障碍。但是，我们如何精确地比较不同的优化算法呢？仅仅观察它们是否最终找到一个解是不够的。我们需要量化 (quantization)它们接近解的速度。这就是收敛性分析的范畴。

理解收敛行为对于有效选择和调整优化算法非常重要。它有助于我们回答这样的问题：此算法能找到一个好的解吗？它可能需要多少次迭代或多少计算时间？它容易陷入停滞吗？

定义收敛

首先，对于生成一系列迭代点$x_0, x_1, x_2, \dots$的算法来说，收敛意味着什么？直观地看，这意味着该序列越来越接近一个关注点，通常是我们目标函数$f(x)$的一个极小点$x^*$。更正式地说，我们常考虑以下条件之一：

1. 迭代点收敛： 迭代点与最优解之间的距离趋于零：$\lim_{k \to \infty} ||x_k - x^*|| = 0$。
2. 函数值收敛： 迭代点的函数值趋近于最小函数值：$\lim_{k \to \infty} f(x_k) = f(x^*)$。
3. 梯度范数收敛： 梯度的模趋于零：$\lim_{k \to \infty} ||\nabla f(x_k)|| = 0$。这表示接近一个驻点（可以是最小值点、最大值点或鞍点）。对于非凸问题，这通常是我们能分析的最实用的标准。

尽管知道算法是否收敛很重要，但对实践而言，核心是其收敛的速度。

收敛速度

收敛速度描述了误差（例如，$f(x_k) - f(x^*)$或$||x_k - x^*||$）随着迭代次数$k$的增加而减少的速度。不同的算法表现出不同的收敛特性。令$e_k$表示第$k$次迭代时的误差。

次线性收敛

这通常是我们在实用算法中遇到的最慢的收敛类型。误差减小，但其速度慢于每次迭代的任何常数因子。典型的速度包括：

• $e_k = O(1/k)$：误差与迭代次数成反比减少。
• $e_k = O(1/\sqrt{k})$：减小得更慢。

许多随机方法，例如应用于凸函数或非凸函数的基本SGD，常表现出次线性收敛。尽管速度慢，但它们每次迭代的计算成本通常很低，这使得它们对于非常大的数据集是可行的。

线性收敛（或几何收敛）

这是一种更期望的速度。误差在每次迭代中以一个常数因子$\rho \in (0, 1)$减小。数学上，当$k$很大时： $\frac{e_{k+1}}{e_k} \approx \rho < 1$ 这意味着$e_k \approx c \cdot \rho^k$对于某个常数$c$成立。在对数尺度上，误差呈线性减小。梯度下降 (gradient descent)应用于强凸和光滑函数时通常实现线性收敛。$\rho$的值很重要；较小的$\rho$（例如0.1）意味着比接近1的$\rho$（例如0.99）快得多。

超线性收敛

此处，连续误差的比值趋近于零： $\lim_{k \to \infty} \frac{e_{k+1}}{e_k} = 0$ 这意味着收敛速度随时间加快。拟牛顿法（如BFGS和L-BFGS，在第二章讨论）在适当条件下常表现出超线性收敛。

二次收敛

这是一种极快的收敛速度。下一步的误差与当前误差的平方成比例： $\frac{e_{k+1}}{e_k^2} \approx M$ 对于某个常数$M$成立。这意味着一旦迭代点足够接近解，解中正确数字的位数在每次迭代中大致翻倍。牛顿法（第二章）是具有二次收敛性算法的经典例子，前提是在解附近满足特定条件。

下图展示了这些不同的速度，绘制了误差（对数尺度）与迭代次数的关系。

比较不同收敛速度下迭代过程中的误差减小情况。请注意，从次线性到线性，特别是到二次收敛，速度有显著提升，这些都显示在对数误差尺度上。

收敛保证的条件

理论收敛速度并非普遍适用；它们很大程度上取决于目标函数$f$的性质以及算法的具体情况。一些重要性质包括：

• 梯度的Lipschitz连续性（光滑性）： 如果函数$f$的梯度变化不会任意快，则称其为$L$-光滑的。正式来说，存在一个常数$L > 0$使得： $||\nabla f(x) - \nabla f(y)|| \le L ||x - y|| \quad \forall x, y$ 光滑性是证明许多一阶方法收敛性所需的常见假设，因为它允许我们使用梯度来限制函数的变化。它对于选择合适的步长（学习率）非常重要。

• 凸性： 如前所述，如果$f$是凸的，梯度下降 (gradient descent)（使用合适的步长）保证收敛到全局最小值$f(x^*)$。速度可能仍是次线性的。

• 强凸性： 这是一个比简单凸性更强的条件。如果函数$f$存在一个常数$\mu > 0$使得满足以下条件，则称其为$\mu$-强凸的： $f(y) \ge f(x) + \nabla f(x)^T (y-x) + \frac{\mu}{2} ||y - x||^2 \quad \forall x, y$ 本质上，该函数有一个二次下界。如果$f$既是$L$-光滑又是$\mu$-强凸的，则标准梯度下降以与条件数$\kappa = L/\mu$相关的速度线性收敛。

• 非凸性： 对于深度学习 (deep learning)中普遍存在的非凸函数，收敛保证要弱得多。我们通常不能保证收敛到全局最小值。分析常侧重于显示收敛到梯度为零的驻点 $x^*$。如我们所指出的，这些可以是局部最小值、鞍点，甚至是局部最大值。最近的研究表明，许多算法，包括SGD变体，在某些条件下能有效避开鞍点。

实际考量

尽管理论速度提供了有价值的观点，但它们并未涵盖全部情况。

• 每次迭代的成本： 具有二次收敛性的算法（如牛顿法）可能看起来更优，但对于大型模型而言，其每次迭代的成本（计算和求逆Hessian矩阵）可能非常高昂，使得收敛较慢但成本较低的方法（如SGD或Adam）在实际运行时间上更快。
• 常数和隐藏因子： 大O表示法隐藏了常数因子。渐近速度较优的方法可能只有在非常多的迭代次数之后才会变得更快。
• 随机性： 随机方法（如SGD、Adam）的分析通常更复杂，通常涉及期望收敛或高概率收敛，并且小批量采样引入的方差发挥着重要作用。
• 实现细节： 学习率调度、动量项和数值精度等因素会明显影响实际收敛行为。

在我们继续学习后续章节中的更高级算法之前，理解收敛性分析的这些基本思想非常重要。我们将看到二阶方法如何通过使用曲率信息来追求更快的速度，自适应方法如何动态调整学习率，以及大规模和分布式设置中的技术如何在追求高效收敛的同时管理计算和通信成本。分析收敛性质将是一个反复出现的主题，贯穿我们评估每种新优化技术的过程中。