Feb, 2017

小批量 Prox 分布式随机优化的高效内存和通信

PDF
TL;DR提出一种分布式随机优化的方法，该方法具有统计上的最优性并且可以实现近线性的加速（达到对数级因子）。该方法允许通信 - 内存权衡，具有对数级通信但线性内存或多项式通信和相应的多项式内存降低。 通过使用小批量相对迭代（小批量被动 - 侵略性更新），在每次迭代时解决小批量的子问题实现了这种通信 - 内存权衡。对此类小批量相对逼近程序的新型分析可以实现统计上的最优速率，而不管小批量的大小和平滑度，因此在之前的工作中得到了显着的改进。
distributed stochastic optimizationcommunication-memory tradeoffminibatch-prox iterationsstatistically optimal ratesmoothness
发现论文，激发创造
  • 分布式随机凸优化的极小 - 极大复杂度及间歇通信

    研究分布式随机凸优化的最小最大复杂度，在间歇通信设置下提出了一种新的下限和上限算法，以确定最佳算法。

    Feb, 2021

  • 基于模型的随机优化：加速、优化和并行计算的若干结果

    我们扩展了 Approximate-Proximal Point 方法，在随机凸优化问题中应用包括随机次梯度、近端点和束方法，同时提出了更快的模型算法和加速方案，保持了 Approximate-Proximal Point 算法的鲁棒性，同时提供了更快的收敛速度和更低的界限。我们通过实证测试证实了理论结果的可行性。

    Jan, 2021

  • 分布式随机方差减少梯度方法与通信复杂度下限

    本论文研究了用于最小化凸函数平均值的分布式优化算法，应用于统计机器学习的经验风险最小化问题。我们设计了一种分布式随机方差减少梯度算法，其在条件数方面同时增强了最佳并行运行时间、通信量和所有分布式一阶方法的通信轮数。此外，当条件数相对于每个机器中的数据大小不太大时，我们的方法及其加速扩展还可以优于现有的分布式算法，此外，还证明了广泛分布的课程的有关通信轮数的下限。我们证明了我们的加速分布式随机方差减少梯度算法实现了这一下限，从而它使用最少的通信轮数。

    Jul, 2015

  • 更优秀的随机优化算法：小批量和插值学习

    文中讨论了一种基于随机梯度估计的优化算法，解决了 Lan (2012), Cotter 等人 (2011) 和 Liu 与 Belkin (2018) 所提出的一些局限性，实现了更好的并行加速效率.

    Jun, 2021

  • 去中心化和随机优化的通讯高效算法

    本文提出了一种新的去中心化一阶方法解决在多代理网络上的非光滑和随机优化问题，其中主要贡献为提出了基于去中心化通讯滑动算法的去中心化原始 - 对偶算法，以解决在去中心化优化中通讯瓶颈。

    Jan, 2017

  • 高效分布式在线预测和随机优化：近似分布式平均方法

    研究分布式方法用于在线预测和随机优化，并提出了基于 gossip 的优化方法以实现最优的后悔界限。

    Mar, 2014

  • 面向更高效的随机分散式学习：更快的收敛与稀疏通信

    本研究提出了一种名为 DSBA 的随机算法，通过将分散的优化问题推广为单调算子求根问题来解决这一问题，具有线性收敛速度和只需稀疏通讯的优点，同时还能有效地处理像 AUC 最大化这样的学习问题。

    May, 2018

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

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

    Jun, 2020

  • 分布式延迟随机优化

    该文主要研究基于梯度的优化算法中的延迟随机梯度信息的收敛性，以及如何应用于分布式优化算法中克服通信瓶颈和同步要求的问题，结果表明在平滑随机问题中，延迟是渐近可以忽略的，且能达到最优收敛效果。

    Apr, 2011

  • 局部随机梯度下降上升：收敛分析与通信效率

    本文提出了一种名为 local SGDA 的算法来缓解分布式学习中的通信开销，可在广泛的分布式 minmax 优化问题下实现可证明的收敛性和更少的通信次数。

    Feb, 2021