Nov, 2023

分散双层优化的通信复杂度

PDF
TL;DR我们开发了一种新颖的去中心化随机双层梯度下降算法，在异构环境中具有每轮小的通信成本和通信轮数，从而比现有算法实现了更好的通信复杂度。我们还将我们的算法扩展到更具挑战性的去中心化多级优化问题。根据我们的知识，我们是第一次在异构环境下实现这些理论结果。最后，实验结果证实了我们算法的有效性。
decentralized bilevel optimizationcommunication complexitystochastic hypergradientheterogeneous settingdecentralized multi-level optimization
发现论文，激发创造
  • 基于去中心化传播的通信网络随机双层优化

    本文研究了在网络上进行分布式双层优化问题，提出了一种基于谣言传播的分布式双层学习算法，证明了该算法对于一般非凸双层优化和强凸优化具有最优的样本复杂度，并在多项任务进行的两个例子中进行了测试。

    Jun, 2022

  • 去中心化双层优化

    研究了分散设置下非凸强凸双层优化问题，在确定性和随机双层优化问题上设计了分散算法。分析了算法的收敛速度，包括在代理间观察到数据异构性的情况。通过对合成和真实数据的数值实验表明，所提出的方法是有效的。

    Jun, 2022

  • 分布式双层优化的单循环算法

    在这篇论文中，我们考虑了分散网络中的双层优化问题，提出了一种针对具有强凸下层问题的分散式双层优化的新型单循环算法。我们的算法完全是单循环算法，在逼近超梯度时不需要进行复杂的矩阵向量乘法。此外，与现有的分散式双层优化和联邦双层优化方法不同的是，我们的算法不需要任何梯度异质性假设。我们的分析结果显示，该算法达到了迄今为止双层优化算法的最佳收敛速度。

    Nov, 2023

  • 具有水平无关收敛速度的网络随机多级组合优化算法

    探讨了针对多层分布式部署的随机优化问题的两种新的分布式优化算法，并在理论上和实验中验证了两种算法的有效性。

    Jun, 2023

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

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

    Jan, 2017

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

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

    Oct, 2019

  • 图上分布式双层优化：无环算法更新和瞬态迭代复杂度

    通过引入单循环去中心化的 SBO（D-SOBA）算法，并建立其瞬态迭代复杂度，本文首次澄清了网络拓扑和数据异质性对去中心化双层算法的联合影响。与现有方法相比，D-SOBA 算法在更宽松的假设条件下实现了与现有方法相比最先进的渐近速率、渐近梯度 / 海森复杂度和瞬态迭代复杂度。数值实验验证了我们的理论发现。

    Feb, 2024

  • 分布式优化的线性收敛算法：免费发送更少的比特！

    提出了一种新的基于随机压缩算子的一阶随机算法和方差约简技术，能够在去除了通信中数据量的一定压缩的前提下，快速地在分散的装置上完成模型的机器学习训练并收敛于最优解。

    Nov, 2020

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

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

    Jun, 2020

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

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

    May, 2018