关于在弱一阶和二阶梯度Lipschitz条件下SignSGD算法的收敛性

《Artificial Intelligence》：On the Convergence of SignSGD under Weak First- and Second-Order Gradient Lipschitz

　　陶孙 | 刘新望
中国国防科技大学计算机科学与技术学院，长沙

**摘要**
基于符号的随机方法因其仅需少量符号位信息即可有效更新特定字段而受到越来越多的关注。然而，这些方法的收敛性分析始终依赖于函数具有全局一阶或二阶梯度Lipschitz性的强假设；这类假设非常严格，在实际应用中（如训练深度神经网络）通常不成立。本文重新审视了基于符号的方法，并在更现实的一阶和二阶梯度Lipschitz性假设下研究了这些方案的收敛性。我们证明了这些弱假设适用于带有权重衰减的二层神经网络类。接着，我们在弱一阶梯度Lipschitz性框架下证明了基于符号的方法的收敛性，并引入了一个修改后的二阶条件，该条件仍然允许在相应的基于符号的框架内实现非凸加速。与其他方法不同，我们的发现基于较为宽松的假设，从而拓宽了其适用范围。

**引言**
广泛使用的随机梯度下降（SGD）[1] 是解决机器学习和统计中出现的根本优化问题的主要算法：
**min_w ∈ R^d, f(w) := E[ξ ~ D_f(w; ξ)],**
其中D表示统计样本空间Ξ上的概率分布。然而，在某些情况下（如通信效率高的训练），传统的SGD可能效率不高。在这种情况下，通常会采用压缩随机梯度的方法。一种巧妙的方法是使用随机梯度每个坐标的符号，这被称为SignSGD。在SignSGD的每次迭代中，从一个分布D中独立抽取一个数据点ξ_t，然后执行参数更新：
**w_{t+1} = w_t ? γ · Sign[?_f(w_t; ξ_t)],**
其中γ > 0表示步长。然而，当使用小批量时，(2)式可能不会收敛[2], [3]。为了解决这个问题，已经开发了错误反馈和动量等措施来提高SignSGD的收敛性[4], [5]。尽管有这些改进，SignSGD在每次迭代中仍然丢弃了大量信息，从直观角度来看，其性能不如SGD。然而，令人惊讶的数值结果表明，在某些情况下，SignSGD可以与SGD相媲美甚至更快[2], [3], [4], [5]。实际上，在[6]的论文中，作者提出了一种称为LION的基于符号的方法，它在训练过程中表现出出色的数值性能，并能有效缓解过拟合问题。尽管在[5]中提出了一种基于符号的可证明加速算法，但其证明依赖于一个很强的平滑性假设：梯度需要满足一阶和二阶Lipschitz条件，而这些条件对于训练深度神经网络来说并不现实。因此，[5]中提出的理论无法解释基于符号的方法的优势。事实上，目前关于SignSGD的收敛性结果都是基于一阶梯度Lipschitz性的假设[2], [3], [4], [5]。然而，这一假设无法充分解释为什么SignSGD在深度神经网络训练中能够收敛，更不用说实现非凸加速了。因此，本文主要解决的问题是：
**在不依赖一阶梯度Lipschitz性假设的情况下，基于符号的方法的收敛性是否可能？我们能否在弱一阶和二阶梯度Lipschitz性条件下建立基于符号的方法的理论优势？**
本文对这个问题给出了肯定的回答。

**一阶梯度Lipschitz平滑性**
一阶梯度Lipschitz平滑性是非凸SGD收敛性的一个关键假设。数学上，它通常假设目标函数f满足：
**∥?_f(x) ? ?_f(y)∥ ≤ L · ∥x ? y∥**（一阶梯度Lipschitz），
其中L > 0且x, y ∈ R^d。尽管一阶梯度Lipschitz性在随机优化分析中经常被使用[7]，但在许多机器学习任务中（尤其是在神经网络训练中）并不成立[8]。例如，对于以下简单的一阶矩阵近似：
**min_x ∈ R^d, D(x) := 1/2 · ∥x×x^T ? Y∥^2,**
其中Y ∈ R^d×d，一阶梯度Lipschitz性也不成立[9]。如果函数D满足一阶梯度Lipschitz性，那么对于任意x ∈ R^d，必须有**∥?_2D(x)∥ ∞**。然而，设x = t^e_1（e_1是仅有第一个元素为1其余元素为零的向量），则有**∥?_2D(x)∥ ∞ ≥ ∥x∥^2 · I + 2 · x×x^T ? Y∥ ∞ ≥ |∥t^2·I + 2t^2e_1e_1^?∥ ∞ → ∞**（当t → +∞时），表明D不满足一阶梯度Lipschitz性。因此，基于一阶梯度Lipschitz性的理论难以解释那些不满足一阶梯度Lipschitz性的优化问题的收敛现象。

**为了解决神经网络训练中收敛性与一阶梯度Lipschitz性之间的差距**，[8], [10]提出了一个更现实的一阶梯度假设：
**假设1.1**
**对于任意x, y ∈ R^d，存在常数L_1, r > 0和L_2 ≥ 0，使得∥y ? x∥ ≤ r时，函数f满足∥?_f(y) ? ?_f(x)∥ ≤ (L_1 + L_2 · ∥?_f(x)∥)∥y ? x∥。**
显然，当L_2 = 0时，(4)式退化为一阶梯度Lipschitz性。在[8]的论文中，作者通过数值验证证明了假设1.1在许多任务中是成立的。(3)式中的函数也满足假设1.1，具体细节可以在补充材料中找到。已经证明，在假设1.1下SGD可能不会收敛，因为即使两点非常接近，两个梯度之间的差异也可能是无界的。为了保证具有弱Lipschitz性质的SGD的收敛性，需要对梯度进行额外操作，例如梯度裁剪[11], [12], [13], [14], [15]。尽管梯度裁剪可以保证在弱一阶梯度Lipschitz性下的收敛性，但它对噪声的要求比SGD更高，具体来说是几乎必然（a.s.）有界的噪声[8]。

**关于非凸SGD加速的研究**
已经有大量研究致力于加速非凸优化。非凸加速器要求目标函数不仅满足一阶梯度Lipschitz性，还必须满足二阶梯度Lipschitz性才能实现理论上的加速，因为凸性通常不存在[16], [17], [18], [19], [20], [21]，即需要满足：
**∥?_2f(x) ? ?_2f(y)∥ ∞ ≤ H · ∥x ? y∥**（二阶梯度Lipschitz），其中H > 0。然而，在许多应用中甚至不存在一阶梯度Lipschitz性，更不用说二阶梯度Lipschitz性了。例如，考虑简单函数(3)，它也不满足二阶梯度Lipschitz性。事实上，如果满足二阶梯度Lipschitz性，那么?_3f(x)必须均匀有界。然而，通过直接计算可得**|[?_3f(x)]_{1,1,1}| → ∞**（当|x_1| → +∞时）。

**相关工作的综述**
我们简要回顾了三类相关工作：
1. **弱平滑性**：研究在弱平滑性下的随机优化算法是必要且有意义的，因为实践中一阶梯度Lipschitz性常常不成立。Zhang等人首次考虑了**∥?_2f(x)∥ ∞ ≤ L_1 + L_2 · ?_f(x)∥**的裁剪SGD，并证明了当梯度范数迅速增加时裁剪SGD的性能更优[22]。需要注意的是，条件(5)并不是一阶梯度Lipschitz性的直接放松，因为它要求函数具有二次可微性。[10]中的作者在二次可微性假设下建立了条件(5)的较弱形式(4)，该形式不需要二次可微性，因此比一阶梯度Lipschitz性更加灵活。此外，[10]中的作者推导了在弱平滑性条件(4)下通用裁剪SGD算法的收敛速率。这些分析有助于我们理解在无法满足一阶梯度Lipschitz性的情况下随机优化算法的行为和有效性。值得注意的是，上述论文中的分析都包含了几乎必然有界的噪声这一更强假设，这比常用的有界方差假设更为严格。这种更强的假设使得在弱平滑性下对随机优化算法的分析和理解更加严谨。[23]中的作者证明了在弱一阶梯度Lipschitz性下的归一化SGD的收敛性，进一步放宽了裁剪方法中所使用的几乎必然有界噪声假设。除了收敛性分析外，弱平滑性下的泛化性质也受到了广泛关注[24]，因为评估机器学习模型的测试准确性对研究人员和从业者都非常重要。在[25]的研究中，作者研究了在弱平滑性假设下从给定分布中采样的概率分布采样算法。这项分析揭示了在存在弱平滑性情况下基于采样的优化算法的行为和性能。

2. **加速非凸优化**：已经有很多研究致力于加速凸确定性情况下的一阶优化算法，例如Nesterov方法[26]。然而，在[27]中发现，即使对于强凸且二次连续可微的函数，在使用常规步长和动量时，Nesterov方法也可能发散。这在将Nesterov方法扩展到一般的非凸随机情况时构成了挑战。有趣的是，存在一些可证明的确定性非凸加速算法，但这些算法要求函数满足二阶梯度Lipschitz平滑性，因为凸性不存在[16], [17], [18], [19], [20]，即需要满足：**∥?_2f(x) ? ?_2f(y)∥ ∞ ≤ H · ∥x ? y∥**（二阶梯度Lipschitz）。然而，在许多应用中甚至不存在一阶梯度Lipschitz性，更不用说二阶梯度Lipschitz性了。例如，简单函数(3)也不满足二阶梯度Lipschitz性。实际上，如果满足二阶梯度Lipschitz性，那么?_3f(x)必须均匀有界。然而，通过直接计算可得**|[?_3f(x)]_{1,1,1}| → ∞**（当|x_1| → +∞时）。

**结论**
本文提供了一个肯定的答案：在不依赖一阶梯度Lipschitz性假设的情况下，基于符号的方法的收敛性是可能的。我们能够在弱一阶和二阶梯度Lipschitz性条件下建立基于符号的方法的理论优势。一阶梯度Lipschitz平滑性对于非凸SGD的收敛性是一个关键假设。数学上，它通常假设目标函数f满足：**∥?_f(x) ? ?_f(y)∥ ≤ L · ∥x ? y∥**（一阶梯度Lipschitz），其中L > 0且x, y ∈ R^d。尽管一阶梯度Lipschitz性在随机优化分析中常用[7]，但在许多机器学习任务中（尤其是在神经网络训练中）并不成立[8]。例如，对于以下简单的一阶矩阵近似：
**min_x ∈ R^d, D(x) := 1/2 · ∥x×x^T ? Y∥^2**，如果函数D满足一阶梯度Lipschitz性，那么必须有**∥?_2D(x)∥ ∞**。然而，设x = t^e_1（e_1是仅有第一个元素为1其余元素为零的向量），则有**∥?_2D(x)∥ ∞ ≥ ∥x∥^2 · I + 2 · x×x^T ? Y∥ ∞ ≥ |∥t^2·I + 2t^2e_1e_1^?∥ ∞ ≥ 3t^2 ? ∥Y∥ ∞ → ∞**（当t → +∞时），表明D不满足一阶梯度Lipschitz性。因此，基于一阶梯度Lipschitz性的理论难以解释那些不满足一阶梯度Lipschitz性的优化问题的收敛现象。

为了弥合神经网络训练中的收敛性与不可接受的一阶梯度Lipschitz性之间的差距，[8], [10]提出了一个更现实的一阶梯度假设：
**假设1.1**
**对于任意x, y ∈ R^d，存在常数L_1, r > 0和L_2 ≥ 0，使得∥y ? x∥ ≤ r时，函数f满足∥?_f(y) ? ?_f(x)∥ ≤ (L_1 + L_2 · ∥?_f(x)∥)∥y ? x∥。**
显然，当L_2 = 0时，(4)式退化为一阶梯度Lipschitz性。在[8]的论文中，作者通过数值验证证明了假设1.1在许多任务中是成立的。(3)式中的函数也满足假设1.1，详细内容可以在补充材料中找到。已经证明，在假设1.1下SGD可能不会收敛，因为即使两点非常接近，两个梯度之间的差异也可能是无界的。为了保证具有弱Lipschitz性质的SGD的收敛性，需要对梯度进行额外操作，例如梯度裁剪[11], [12], [13], [14], [15]。尽管梯度裁剪可以在弱一阶梯度Lipschitz性下保证收敛，但它对噪声的要求比SGD更严格，具体来说是几乎必然有界的噪声[8]。

**加速非凸SGD**
已经有研究致力于加速非凸SGD。非凸加速器要求目标函数除了满足一阶梯度Lipschitz性外，还必须满足二阶梯度Lipschitz性才能实现理论上的加速，因为凸性通常不存在[16], [17], [18], [19], [20], [21]，即需要满足：**∥?_2f(x) ? ?_2f(y)∥ ∞ ≤ H · ∥x ? y∥**（二阶梯度Lipschitz），其中H > 0。然而，在许多应用中甚至不存在一阶梯度Lipschitz性，更不用说二阶梯度Lipschitz性了。例如，考虑简单函数(3)，它也不满足二阶梯度Lipschitz性。事实上，如果满足二阶梯度Lipschitz性，那么?_3f(x)必须均匀有界。然而，通过直接计算可得**|[?_3f(x)]_{1,1,1}| → ∞**（当|x_1| → +∞时）。通过考虑一种类似Lipschitz的坐标性质，在[41]中提出了一种具有根据历史梯度调整步长的健壮的通用SignSGD算法。在一篇较新的论文[5]中，作者证明了即使在这些假设更弱的情况下，仅使用简单的动量也足以保证SignSGD的收敛性。此外，[5]的作者提出了一种在了一阶和二阶梯度Lipschitz平滑性条件下具有理论保证的加速版本的SignSGD。在论文[42]、[43]中，作者证明了基于符号的SGD在重尾噪声下比普通SGD更具鲁棒性。[44]研究了带有权重衰减的基于符号的算法的泛化能力。在论文[6]中，作者提出了一种称为LION的基于符号的方法，该方法在视觉 transformers 和扩散模型上的表现明显优于流行的Adam优化器[45]。数值实验显示了LION的效率，但缺乏理论解释。[46]的作者对LION方法进行了详细的收敛性分析，表明它在问题维度上的依赖性是最优的，并且其收敛速度具有竞争力。他们还提供了实证支持，表明在实际应用中，基于符号的方法的性能会随着问题维度的增加而提高。本文旨在证明在弱平滑性假设下加速Sign方法的加速效果，并对其在实际训练中的优势提供理论解释。本工作的主要贡献可以总结如下：

- 我们提出了一个证明，展示了在弱一阶梯度Lipschitz假设下基于符号的方法的收敛性。我们的发现表明，通过使用简单的动量，基于符号的方法可以达到与SGD相当的收敛速度。
- 我们提出了一个更现实的假设来表征二阶梯度Lipschitz性质，这个假设比传统的二阶梯度Lipschitz平滑性要弱得多。对于一大类带有权重衰减的双层神经网络训练，我们严格证明了如果激活函数满足一个温和的假设，那么这种弱二阶梯度Lipschitz性质就成立。
- 在这种弱平滑情况下，我们仍然能够证明在这种弱一阶和二阶梯度Lipschitz平滑性下，加速SignSGD具有非凸加速效果，这大大扩展了其潜在应用范围。此外，我们还解释了为什么当梯度爆炸时，加速SignSGD的加速效果可以优于其他非凸加速方法。

**符号说明：**
本文使用E[·]表示关于底层概率空间的期望值。我们使用‖·‖表示向量的L2范数，使用‖·‖op表示矩阵的谱范数。我们使用?3f表示函数f的三阶梯度，即?3f(x)∈R3，[?3f(x)]i,j,k=?f(x)?xi?xj?xk。给定一个整数n，我们用[n]表示集合{1,2,…,n}。函数f的最小值表示为min f。给定两个序列{at}和{bt}，如果存在一个正常数00，且‖·‖?是Rd的某种范数。
值得注意的是，符号操作符也满足条件1。考虑到这一点，在条件1下，以下命题成立：
**命题5.1：**设w?,m∈Rd是任意向量，w″=w??γT(m)，?:=m??f(w?)。如果假设1.1成立，且0<γ≤max{alu2l2,r}，则有f(w″)?f(w)

**未引用的参考文献：** 图3和算法2。
**credi作者贡献声明：**
tao sun：撰写——审阅与编辑；撰写——初稿。xinwang liu：撰写——初稿。

**利益冲突声明：**
我们正在提交题为“关于在弱一阶和二阶梯度lipschitz下signsgd的收敛性”的修订手稿，以便在“人工智能”期刊上发表。我们想确认这项工作是原创的，之前没有发表过，也没有在其他地方以全部或部分形式正在考虑发表。所有作者都已审阅并批准了手稿的提交和发表。 **未引用的参考文献：** 图3和算法2。 **credi作者贡献声明：** tao sun：撰写——审阅与编辑；撰写——初稿。xinwang liu：撰写——初稿。 **利益冲突声明：**>
**未引用的参考文献：** 图3和算法2。
**credi作者贡献声明：**
tao sun：撰写——审阅与编辑；撰写——初稿。xinwang liu：撰写——初稿。

**利益冲突声明：**
我们正在提交题为“关于在弱一阶和二阶梯度lipschitz下signsgd的收敛性”的修订手稿，以便在“人工智能”期刊上发表。我们想确认这项工作是原创的，之前没有发表过，也没有在其他地方以全部或部分形式正在考虑发表。所有作者都已审阅并批准了手稿的提交和发表。>