Sep, 2018

分布式优化网络中最优算法的双重方法

PDF
TL;DR本研究旨在研究分布式凸优化问题的双重算法，提出一种基于适当形式化原始问题的对偶的方法，包括模拟通信限制的图，并提出分布式算法，其效率与中心化算法相同（差异不超过常数和对数因子），并且与网络的谱特性有关的最优成本。
dual-based algorithmsdistributed convex optimizationprimal problemlegendre-fenchel conjugatespectral properties
发现论文，激发创造
  • 网络中非光滑分布式优化的最优算法

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

    Jun, 2018

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

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

    Jun, 2020

  • 分布式优化的双重平均：收敛分析和网络扩展

    本文研究了分布式网络中去中心化优化的问题，尤其是基于双重平均子梯度的分布式算法及其收敛速度与网络大小和拓扑结构的关系，同时探讨了算法收敛和网络结构限制之间的关系，并证明了我们算法所需的迭代次数与网络谱隙成反比例关系。

    May, 2010

  • 非凸分布式优化

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

    Dec, 2015

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

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

    Feb, 2017

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

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

    Jun, 2020

  • 非光滑凸分散时间变网络优化的下界与最优算法

    在时间变化的网络上，解决非光滑凸分布式优化问题时，本文首次确定了通信和子梯度计算复杂性的下界，并发展了与下界匹配且在理论性能方面明显优于现有技术的最优算法。

    May, 2024

  • 并行与分布式非凸优化方法 -- 第二部分：应用

    本论文提出了一种新的基于内部凸近似的算法框架来最小化一个非凸（顺滑）目标函数的方法，该算法用于一些通信网络中的资源分配问题，并开发了一类新的分布式算法，通过在基站之间有限的信号交换实现优化，这些算法可以始终收敛于前述类别的非凸问题的 d - 平稳解。

    Jan, 2016

  • NEXT: 网内非凸优化

    本文提出了第一种算法框架，用于在具有时变（非对称）连接的多代理网络中进行非凸分布式优化，该方法利用了动态共识作为将计算分配给代理的机制，并将其定制为用于多个领域的凸和非凸问题，包括信号处理，通信，网络和机器学习。数值结果表明，新方法在凸和非凸问题上与现有分布式算法相比具有优势。

    Feb, 2016

  • 网络分布式 ADMM 的收敛速率

    本研究提出了基于 ADMM 算法的分布式算法，用于通过网络通信最小化局部已知的凸函数之和，研究表明，在函数为凸函数时，目标函数值和可行性冲突都会收敛，当函数是强凸函数且有 Lipschitz 连续梯度时，该算法生成的序列会线性收敛到最优解。此外，我们的分析还通过节点的最大和最小度以及网络的代数连通度凸显了网络结构对收敛速度的影响。

    Jan, 2016