Sep, 2023
开关与征服：通过切换随机梯度预算器解决分散鞍点问题的高效算法
Switch and Conquer: Efficient Algorithms By Switching Stochastic Gradient Oracles For Decentralized Saddle Point Problems
Chhavi Sharma, Vishnu Narayanan, P. Balamurugan
TL;DR我们考虑了一类在没有中央服务器的分散环境中的非光滑强凸 - 强凹鞍点问题。为了解决这类问题的共识形式，我们开发了一种不精确原始对偶混合梯度（inexact PDHG）算法，该算法允许通用梯度计算预言更新原始和对偶变量。我们首先研究了不精确 PDHG 与随机方差减少梯度（SVRG）预言的性能。我们的数值研究揭示出了 IPDHG 与 SVRG 预言的迭代过程中的初始保守进展现象。为了解决这个问题，我们提出了一个简单且有效的切换思想，即在更新的初始阶段使用广义随机梯度（GSG）计算预言来加快迭代过程，然后在适当的时机切换到 SVRG 预言。提出的算法被命名为带压缩的分散近端切换随机梯度方法（C-DPSSG），并被证明以线性速率收敛到一个 ε- 精确的鞍点解。除了提供高精度的解决方案外，我们的研究还揭示出利用 GSG 和 SVRG 预言的最佳收敛阶段使 C-DPSSG 非常适合获得低 / 中等准确度的解决方案，这对某些应用非常有用。对两个基准机器学习应用进行的数值实验显示了 C-DPSSG 的竞争性能，验证了我们的理论发现。