Sep, 2019

具有线性收敛率的分散近端梯度算法

PDF
TL;DR本文研究了一类非光滑的分散式多智能体最优化问题，该代理旨在最小化局部强凸光滑组成部分和一个共同的非光滑项。我们提出了一个通用的原始对偶算法框架，统一了许多现有的最先进的算法。我们在非光滑项存在的情况下，证明了所提出的方法向确切解的线性收敛。此外，对于更一般的具有代理特定非光滑术语的问题类，我们展示了使用光滑和非光滑部分的梯度和临界映射的算法类别的线性收敛在最坏的情况下无法实现。我们进一步提供了一个数字反例，展示了某些最先进的算法如何在强凸目标和不同的局部非光滑项的情况下无法线性收敛。
decentralized multi-agent optimizationprimal-dual algorithmlinear convergencenon-smooth termstate-of-the-art algorithms
发现论文，激发创造
  • 一种具有网络独立步长和分离收敛速度的去中心化近端梯度方法

    本文介绍一种新的分布式优化问题的近端 - 梯度算法，用于处理包含平滑和非平滑项的组合目标，我们提出的新算法与以前的算法相比具有一些优势，例如不需要协调步长和可得到线性收敛。

    Apr, 2017

  • 随机近端梯度算法的收敛性

    本文基于凸优化中函数是光滑和非光滑组合的形式，证明了一种适用于大类凸优化问题的随机近端梯度算法收敛性质，其避免了平均化和理论研究中常见但实际中不一定满足的有界性假设，证明了一系列强、弱收敛性结果，并得到了期望意义下的 $O (1/n)$ 的有界性结果。

    Mar, 2014

  • 凸优化中不精确近端梯度方法的收敛速率

    本文探讨了使用近端梯度法优化平滑凸函数和非平滑凸函数的和时，如果在计算平滑项的梯度或非平滑项的邻近算子时存在误差，基本的近端梯度法和加速近端梯度法可以实现与没有错误的情况下相同的收敛率，前提是错误以适当的速度减小。使用这些速度，在一组结构稀疏性问题上，我们的表现与精心选择的固定误差级别相当或更好。

    Sep, 2011

  • 去中心化随机极小极大优化算法是否能以线性收敛于有限和的非凸非凹问题？

    本文针对分布式算法模型中面临的发散问题，提出了两种基于随机梯度下降的算法，并证明了其具有良好的收敛性能，这是首个针对分布式情况下的凸 - 非凸问题的线性收敛性的成果。

    Apr, 2023

  • 一种快速的分布式近端梯度法

    该研究提出了一种基于分布式近端梯度方法来优化平均凸函数的方法，每个凸函数都是网络中各个代理的本地目标函数。该方法通过交换估计值来实现每个代理迭代更新全局最小值的目标，并使用 Nesterov-type 加速技术和多个通信步骤进行迭代，表明这种方法的收敛速率为 1/k（其中 k 是代理之间的通信轮数），这比现有的分布式方法的收敛速度更快。数值实验也验证了该方法的卓越收敛速度。

    Oct, 2012

  • 近端法的误差界、二次增长和线性收敛

    本文介绍了一种利用步长乘以线性误差边界的方法来实现凸函数最小化的近端梯度算法；通过证明将误差边界与一种自然二次生长条件的等价性，直观地解释了观察到的线性收敛现象；我们的方法将推广到用于最小化由光滑映射组成的非光滑函数的近端方法，同时观察到算法中的短步长暗示了接近稳定状态，建议作为可靠的终止准则。

    Feb, 2016

  • 去中心化在线随机非凸优化的收敛分析改进

    本文研究了节点网络上的去中心化在线随机非凸优化。通过将梯度跟踪技术集成到去中心化随机梯度下降中，我们证明了该算法具有一定的优势，并分析了其有效性和性能。同时，对于满足 Polyak-Lojasiewics 条件的全局非凸函数，我们确定了 GT-DSGD 的线性收敛性，并且在几乎每条路径上具有最优的全局亚线性收敛速度。

    Aug, 2020

  • 非光滑非凸优化的快速随机方法

    本文研究随机算法优化非凸、非光滑的有限和问题。针对此问题，本文提出快速的随机算法，可获得常数迷你批量的收敛性。本文还使用这些算法的变种，证明了比批量近端梯度下降更快的收敛性，并在非凸、非光滑函数的一个子类中证明全局线性收敛率。

    May, 2016

  • 非凸优化的多智能体投影随机梯度算法收敛性

    本文介绍了一种新的框架用于多智能体系统中分布式约束非凸优化算法的收敛分析，该算法由局部随机梯度下降和 GOSSIP 步骤组成，不需要 GOSSIP 矩阵双随机性，证明了算法收敛于 Karush-Kuhn-Tucker 点集，并适用于在自然广播场景中节省网络能量。

    Jul, 2011

  • 分布式非凸优化的原始对偶随机梯度下降算法

    本文提出了一种适用于任意连接通信网络和任何光滑（可能是非凸的）代价函数的分布式原始 - 对偶随机梯度下降（SGD）算法，证明了该算法实现了常数参数的输出线性收敛到全局最优的邻域并展示了实验结果与基线集中式 SGD 和最近提出的分布式 SGD 算法的比较效率。

    Jun, 2020