Dec, 2019

并行重启 SPIDER -- 与最优计算复杂度的通信高效分布式非凸优化

PDF
TL;DR本文提出了一种基于 SPIDER 梯度估计器的分布式算法，可用于处理随机的平滑、非凸优化问题，该算法结合了最优化方差减少技术与并行 SGD 算法，优化了可以用于联邦学习的非相同分布的数据的模型，提出的算法具有最优迭代复杂度复杂度，并实现了与现有方法相同的线性加速。
distributed algorithmoptimizationvariance-reductioncommunication complexityfederated learning
发现论文，激发创造
  • D-SPIDER-SFO: 非凸问题快速收敛的分布式优化算法

    提出一种分散化版本的 SPIDER-SFO 算法（D-SPIDER-SFO），该算法在解决非凸优化问题时具有与其集中化版本相似的计算复杂度，达到了解决分散化网络中非凸优化问题的最先进水平，具有非常高的效率。

    Nov, 2019

  • SPIDER: 随机路径一体化微分估计实现非凸优化接近最优

    本文提出了一种称为 SPIDER 的新技术，它可以用于显著降低计算成本跟踪许多确定性感兴趣数量，我们将 SPIDER 应用于两项任务，即随机一阶和零阶方法。

    Jul, 2018

  • 非凸优化的快速随机交替方向乘子方法

    本文提出了一个基于 SPIDER 的更快的用于非凸优化的随机交替方向乘法方法（SPIDER-ADMM），证明了 SPIDER-ADMM 能够实现记录性的增量一阶 Oracle 复杂度，并且扩展了 SPIDER-ADMM 到在线设置，并提出了更快的在线 SPIDER-ADMM。

    Aug, 2020

  • SpiderBoost 和 Momentum：更快的随机方差缩减算法

    本文提出了 SpiderBoost 算法，扩展了 SPIDER 并克服了其在实践中收敛速度慢以及处理涉及非光滑正则化器的目标函数的缺点，可以通过使用 Proximal Mapping 处理复合优化，并利用动量方案实现了理论上的近乎最优巨大 Oracle 复杂度和实验结果的实质性改善。

    Oct, 2018

  • 随机变量度量近端梯度算法及方差约减在非凸复合优化中的应用

    提出了 Perturbed Proximal Preconditioned SPIDER (3P-SPIDER) 算法，适用于解决有限和非凸复合优化问题，是随机变量度量前向 - 后向算法，提出了迷你批处理策略以减少方差并控制收敛，并通过逻辑回归模型的推理应用进行了数值比较。

    Jan, 2023

  • 网络中平滑且强凸分布式优化的最优算法

    该论文在两个设置中确定了强凸和光滑分布式优化的最优收敛速率：中央集权和去中心化通信。对于中央集权算法，作者表明分布式 Nesterov 加速梯度下降算法是最优的。对于基于流言蜚语 (gossip) 的去中心化算法，作者提供了第一个最优算法 MSDA 方法，并通过最小二乘回归和分类的逻辑回归问题验证了其效率。

    Feb, 2017

  • 网络中非光滑分布式优化的最优算法

    研究分布式优化的算法，提出了多步原始 - 对偶（MSPD）算法及其收敛率，证明了在局部正则性假设下，通信网络的结构仅对 $O (1/t)$ 的次要项产生影响。同时，提出了基于局部平滑的分布式随机平滑（DRS）算法在全局正则性假设下，其收敛速度接近于最优收敛速度，是一种简单而有效的算法。

    Jun, 2018

  • 一种联合梯度估计和跟踪的分散非凸优化样本和通信复杂度改进方法

    该文章提出了一种名为 D-GET 的去中心化随机算法，可以提高大规模机器学习中高度非凸问题的性能，同时在减少多节点通信轮数的同时，访问最少量的局部数据样本，以实现确定性有限和在线问题的小样本复杂度和通信复杂度，并优于现有方法的复杂度。

    Oct, 2019

  • 分散优化中平滑强凸问题的最优实用算法

    本文提出了两种基于加速的前后向算法的分散优化新算法以解决存储在网络节点上的光滑强凸函数之和的最小化问题，并显示它们是最优的算法，具有复杂性的保证。

    Jun, 2020

  • 非凸分布式优化

    该研究分析分布式非凸优化问题，针对多智能体网络模型，利用一些技术假设证明分布式推送算法在目标函数的临界点处收敛，并利用扰动动力学证明扰动过程的几乎肯定收敛性。

    Dec, 2015