Nov, 2023

动态有向图中的离散分布优化

PDF
TL;DR我们提出了一个分布式优化的离散时间模型，适用于具有动态有向图的连续时间分布式学习，并消除了对链接进行随机权重设计的需求，通过共识算法、矩阵扰动理论和 Lyapunov 理论，我们证明了梯度跟踪步长和离散时间步长的收敛性和动态稳定性，该工作在链接删除或数据丢失的情况下改善了现有随机权重无向网络的性能，而无需重新运行耗时和计算复杂的算法。该提出的优化框架在分布式分类和学习中具有应用价值。
发现论文，激发创造
  • 分布式优化在时变图上实现几何收敛

    本文考虑基于动态图的分布式优化问题，提出了 DIGing 和 Push-DIGing 算法来解决无向和有向图的问题，同时证明了在强凸性假设下，这些算法以几何级数的速率收敛。

    Jul, 2016

  • 时变网络中的去中心化优化与任意延迟

    我们提出了一种称为 DT-GO 的新颖基于八卦的算法，它在不需要了解节点出度的情况下适用于一般的有向网络，对于拥有延迟或有限确认能力的网络。我们推导了凸和非凸目标的收敛速率，并证明我们的算法实现了与集中式随机梯度下降相同的复杂度顺序，也就是说，图的拓扑结构和延迟效应只影响高阶项。此外，我们扩展了分析以适应时变网络拓扑。通过数值仿真来支持我们的理论发现。

    May, 2024

  • 图上粒子系统，第二部分：分布随机连续优化的动力学

    研究了具有连续节点的图网中的分布式优化问题，提出了基于随机梯度下降和梯度追踪算法的解决方案，并证明了节点状态的二阶矩一致有界性和收敛性。若本地代价函数强凸，则节点状态收敛至全局代价函数的极小值，并且随机梯度追踪算法的辅助状态均方一致收敛至极小值处的全局代价函数梯度值。

    Jul, 2024

  • 时变有向图上的分布式优化

    本文研究了通过节点之间的交流来进行分布式优化的问题，提出了一种基于广播的算法，即 subgradient-push algorithm, 计算其收敛速率.

    Mar, 2013

  • 分布式延迟随机优化

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

    Apr, 2011

  • 分散随机优化与梯度追踪简介

    本文综述了基于梯度追踪和方差减少的去中心化随机一阶优化方法，介绍了这些算法在去中心化机器学习模型训练中的应用。

    Jul, 2019

  • ADD-OPT：加速分布式定向优化

    本文提出了一种名为 ADD-OPT 的分布式优化算法，它能够在具有强全局性连续 Lipschitz 梯度的强凸目标函数情况下，以最佳已知收敛速度 O (μ^k)，k 为迭代次数。此外，ADD-OPT 支持一定范围的步长，并对此进行了模拟。

    Jul, 2016

  • 分布式随机梯度追踪方法

    本文研究了分布式多智能体优化问题，其中每个智能体拥有一个光滑和强凸的本地代价函数。在仅具有本地代价函数梯度的无偏估计时，我们提出了一种分布式随机梯度跟踪方法（DSGT）和一种类似于 Gossip 的随机梯度跟踪方法（GSGT），并展示了这些方法对大规模网络的可比性能和通信成本的差异。

    May, 2018

  • 具有动态拓扑和本地更新的去中心化 SGD 的统一理论

    这篇论文介绍了一种统一的收敛性分析方法，涵盖了许多分散式随机梯度下降方法，具有计算成本低、数据本地性和沟通效率等优点，并包括本地随机梯度下降更新和自适应网络拓扑上的同步和成对传递更新，我们推导了光滑（凸和非凸）问题的通用收敛率，并在不同的数据分布和 iid 数据设置下进行了插值。

    Mar, 2020

  • 一种灵活的梯度追踪方法的计算 - 通讯权衡

    提出了一种灵活的梯度跟踪方法，用于解决非独立同分布情况下网络上的分布式随机优化问题，利用设计良好的李亚普诺夫函数，导出了计算和通信复杂度，以实现在光滑和强凸目标函数上的任意精度。

    Jun, 2023