局部随机梯度下降上升:收敛分析与通信效率
我们研究了分布式随机梯度上升下降(D-SGDA)算法的原始 - 对偶广义界限,通过算法稳定性方法,在凸凹和非凸非凹环境下对分布式最小最大算法的广义界限进行了改进。我们的理论研究表明,分布式结构不会破坏 D-SGDA 的稳定性和广义化能力,在某些情况下可以实现和普通 SGDA 相同的广义化能力。此外,我们还评估了凸凹设定下 D-SGDA 算法的优化误差,并将其与广义间隙相平衡,以获得最佳的总体风险。最后,我们进行了多项数值实验来验证我们的理论发现。
Oct, 2023
本论文证明了局部随机梯度下降算法在凸问题上能够以与小批量随机梯度下降算法相同的速率收敛,并且与工人数量和小批量大小呈线性加速关系,其中通信轮数可以减少长达 T ^ {1/2} 个因子。
May, 2018
本文利用现有的一阶数据异质性假设,为本地 SGD 提供了新的下界,显示了这些假设不足以证明本地更新步骤的有效性。此外,在相同的假设下,我们证明了加速小批量 SGD 的极小 - 极大优化性质,完全解决了几个问题类的分布式优化。我们的结果强调了需要更好的数据异质性模型,以了解本地 SGD 在实践中的有效性。为此,我们考虑了高阶平滑性和异质性假设,并提供了新的上界,暗示了当数据异质性较低时,本地 SGD 优于小批量 SGD。
May, 2024
本文提出了一种适用于任意连接通信网络和任何光滑(可能是非凸的)代价函数的分布式原始 - 对偶随机梯度下降(SGD)算法,证明了该算法实现了常数参数的输出线性收敛到全局最优的邻域并展示了实验结果与基线集中式 SGD 和最近提出的分布式 SGD 算法的比较效率。
Jun, 2020
本文主要介绍分布式深度神经网络训练算法的通信拓扑设计选择及异步去中心化算法如何通过 LASGD 实现模型同步,实验证明 LASGD 相较于 SGD 及业界领先的基于八卦协议的算法加速了大规模图像分类数据集 ImageNet 的训练速度。
Mar, 2022
本文研究了一种名为 local distributed SGD 的分布式优化算法,其中数据在计算节点之间进行划分,计算节点进行本地更新,定期交换模型以进行平均化,并对其进行收敛分析,结果表明它可以大大降低通信成本并且适用性比当前理论推测的更为广泛,同时提出了一种自适应同步方案,验证理论和方案的实验结果在 AWS EC2 云和内部 GPU 集群上运行良好。
Oct, 2019
本研究提出了一种名为 LD-SGD 的算法,该算法结合了本地更新和分散式通信,提供了分析框架,并给出了收敛的充分条件。该框架为分散式优化设计了更新方案,并具有理论和实际的通信优化效果,从而在分散式设置中提高了通信效率。
Oct, 2019
本文研究了局部 SGD(也称为并行 SGD 和联邦平均),一个自然且常用的随机分布式优化方法。在凸设置中,我们证明了局部 SGD 严格优于小批量 SGD,并且加速局部 SGD 在凸二次目标上是最小极值最优的。同时,我们还提供了总体上至少有时优于小批量 SGD 的第一个保证,并展示了局部 SGD 存在一种性能下限,比小批量 SGD 保证更差。
Feb, 2020
本文旨在研究在异构样本上进行非凸优化的联邦分布式学习,具体而言,我们将分析分布式方法相对于均匀样本中的隐含方差减少特性在异构样本中的应用,并证明其在广义的非凸和条件下的收敛性与最优性.
Oct, 2019
本文提出了一种名为 SAGDA 的新算法框架,用于降低联邦 min-max 学习的通信复杂度,并在此基础上提高了对标准 FSGDA 方法通信复杂度的理解。
Oct, 2022