自适应步长的分布式极小 - 最优优化实现近乎最优收敛
该研究开发了两种分布式算法(Prox-DGD 和 DGD-ATC)的异步版本,用于解决无向网络上的共识优化问题,并且与其他算法相比,我们的算法可以使用与延迟无关的步长来收敛到它们的同步对应算法的固定点集。该研究还在部分异步和完全异步情况下,为强凸和弱凸问题建立了收敛保证,并展示了两种异步方法的收敛速度能够适应实际异步程度而不受最坏情况的限制。数值实验表明我们的异步算法具有很强的实际性能。
Dec, 2023
通过研究广义 AdaGrad 步长在凸和非凸设置中,本文证明了这些步长实现梯度渐近收敛于零的充分条件,从而填补了这些方法理论上的空白。此外,本文表明这些步长允许自动适应随机梯度噪声级别在凸和非凸情况下,实现 O(1/T)到 O(1 / 根号 T)的插值(带有对数项)。
May, 2018
该研究探讨并分析了实际分布式计算网络情况下的延迟梯度模型,允许参数更新对实际延迟进行敏感处理以产生更大的步长,从而在保持相同渐近复杂度的同时实现更快收敛,针对包含数十亿个数据和特征的真实数据集展开分布式实验,并取得鼓舞人心的改进。
Aug, 2015
该论文在两个设置中确定了强凸和光滑分布式优化的最优收敛速率:中央集权和去中心化通信。对于中央集权算法,作者表明分布式 Nesterov 加速梯度下降算法是最优的。对于基于流言蜚语 (gossip) 的去中心化算法,作者提供了第一个最优算法 MSDA 方法,并通过最小二乘回归和分类的逻辑回归问题验证了其效率。
Feb, 2017
本文针对分布式算法模型中面临的发散问题,提出了两种基于随机梯度下降的算法,并证明了其具有良好的收敛性能,这是首个针对分布式情况下的凸 - 非凸问题的线性收敛性的成果。
Apr, 2023
本文研究了节点网络上的去中心化在线随机非凸优化。通过将梯度跟踪技术集成到去中心化随机梯度下降中,我们证明了该算法具有一定的优势,并分析了其有效性和性能。同时,对于满足 Polyak-Lojasiewics 条件的全局非凸函数,我们确定了 GT-DSGD 的线性收敛性,并且在几乎每条路径上具有最优的全局亚线性收敛速度。
Aug, 2020
本文提出了一种名为 local SGDA 的算法来缓解分布式学习中的通信开销,可在广泛的分布式 minmax 优化问题下实现可证明的收敛性和更少的通信次数。
Feb, 2021
我们提出了自适应的、无需线搜索的二阶方法,以最优收敛速度解决凸凹最大最小问题,通过自适应步长,我们的算法采用简单的更新规则,每次迭代仅需解一个线性系统,消除了线搜索和回溯机制的需求,具体而言,我们基于乐观法则并将其与二阶信息合理地结合,与常见的自适应方案不同的是,我们递归地将步长定义为梯度范数和乐观更新中的预测误差的函数,我们首先分析了一种方案,其中步长需要知道 Hessian 的 Lipschitz 常数,在额外假设梯度连续 Lipschitz 的情况下,我们通过局部跟踪 Hessian 的 Lipschitz 常数并确保迭代保持有界,进一步设计了一个无需参数的版本,我们还通过将其与现有的二阶算法进行比较来评估我们算法的实际性能。
Jun, 2024
本篇论文提出了一种新的 SGD 变体算法,降低了通信开销及提高自适应学习率,经实验证明,该算法显著降低了通信开销,进而缩短了 1B 字数据集的训练时间 30%。
Nov, 2019
我们研究了分布式随机梯度上升下降(D-SGDA)算法的原始 - 对偶广义界限,通过算法稳定性方法,在凸凹和非凸非凹环境下对分布式最小最大算法的广义界限进行了改进。我们的理论研究表明,分布式结构不会破坏 D-SGDA 的稳定性和广义化能力,在某些情况下可以实现和普通 SGDA 相同的广义化能力。此外,我们还评估了凸凹设定下 D-SGDA 算法的优化误差,并将其与广义间隙相平衡,以获得最佳的总体风险。最后,我们进行了多项数值实验来验证我们的理论发现。
Oct, 2023