非光滑凸分散时间变网络优化的下界与最优算法
本文提出了两种基于加速的前后向算法的分散优化新算法以解决存储在网络节点上的光滑强凸函数之和的最小化问题,并显示它们是最优的算法,具有复杂性的保证。
Jun, 2020
我们提出了一种称为 DT-GO 的新颖基于八卦的算法,它在不需要了解节点出度的情况下适用于一般的有向网络,对于拥有延迟或有限确认能力的网络。我们推导了凸和非凸目标的收敛速率,并证明我们的算法实现了与集中式随机梯度下降相同的复杂度顺序,也就是说,图的拓扑结构和延迟效应只影响高阶项。此外,我们扩展了分析以适应时变网络拓扑。通过数值仿真来支持我们的理论发现。
May, 2024
本研究旨在研究分布式凸优化问题的双重算法,提出一种基于适当形式化原始问题的对偶的方法,包括模拟通信限制的图,并提出分布式算法,其效率与中心化算法相同(差异不超过常数和对数因子),并且与网络的谱特性有关的最优成本。
Sep, 2018
研究分布式优化的算法,提出了多步原始 - 对偶(MSPD)算法及其收敛率,证明了在局部正则性假设下,通信网络的结构仅对 $O (1/t)$ 的次要项产生影响。同时,提出了基于局部平滑的分布式随机平滑(DRS)算法在全局正则性假设下,其收敛速度接近于最优收敛速度,是一种简单而有效的算法。
Jun, 2018
本文提出了一种新的去中心化一阶方法解决在多代理网络上的非光滑和随机优化问题,其中主要贡献为提出了基于去中心化通讯滑动算法的去中心化原始 - 对偶算法,以解决在去中心化优化中通讯瓶颈。
Jan, 2017
该论文在两个设置中确定了强凸和光滑分布式优化的最优收敛速率:中央集权和去中心化通信。对于中央集权算法,作者表明分布式 Nesterov 加速梯度下降算法是最优的。对于基于流言蜚语 (gossip) 的去中心化算法,作者提供了第一个最优算法 MSDA 方法,并通过最小二乘回归和分类的逻辑回归问题验证了其效率。
Feb, 2017
本文提出了第一种算法框架,用于在具有时变(非对称)连接的多代理网络中进行非凸分布式优化,该方法利用了动态共识作为将计算分配给代理的机制,并将其定制为用于多个领域的凸和非凸问题,包括信号处理,通信,网络和机器学习。数值结果表明,新方法在凸和非凸问题上与现有分布式算法相比具有优势。
Feb, 2016
该文章提出了一种名为 D-GET 的去中心化随机算法,可以提高大规模机器学习中高度非凸问题的性能,同时在减少多节点通信轮数的同时,访问最少量的局部数据样本,以实现确定性有限和在线问题的小样本复杂度和通信复杂度,并优于现有方法的复杂度。
Oct, 2019