Mar, 2024

去中心化随机次梯度法用于非光滑非凸优化

PDF
TL;DR我们集中研究具有非凸非光滑目标函数的分布式优化问题，特别是非光滑神经网络的分布式训练。我们引入一个统一框架，名为 DSM，用于分析分布式随机次梯度方法的全局收敛性。我们证明了在温和条件下，我们提出的框架的全局收敛性，通过建立生成的序列渐近逼近其相关微分纳入的轨迹。此外，我们证明了我们提出的框架包括各种现有的高效分布式次梯度方法，包括分布式随机次梯度下降（DSGD），带有梯度跟踪技术的 DSGD（DSGD-T）和带有动量的 DSGD（DSGDm）。此外，我们引入 SignSGD，使用符号映射来规范 DSGDm 中的更新方向，并证明其包含在我们提出的框架中。因此，我们的收敛结果首次证明了这些方法在应用于非光滑非凸目标时的全局收敛性。初步的数值实验表明，我们提出的框架在非光滑神经网络的训练中产生了高效的分布式次梯度方法，具有收敛性保证。
decentralized optimization problemsnonsmooth neural networksglobal convergencedecentralized subgradient methodsdsm framework
发现论文，激发创造
  • 去中心化在线随机非凸优化的收敛分析改进

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

    Aug, 2020

  • 非光滑非凸优化中随机次梯度方法的收敛性保证

    本研究论文探讨了随机梯度下降（SGD）方法及其变种在训练非光滑激活函数构建的神经网络中的收敛性质，提出了一种新的框架，分别为更新动量项和变量分配不同的时间尺度。在一些温和条件下，我们证明了我们提出的框架在单一时间尺度和双时间尺度情况下的全局收敛性。我们展示了我们提出的框架包含了许多著名的 SGD 类型方法，包括 heavy-ball SGD、SignSGD、Lion、normalized SGD 和 clipped SGD。此外，当目标函数采用有限和形式时，我们证明了基于我们提出的框架的这些 SGD 类型方法的收敛性质。特别地，在温和的假设条件下，我们证明了这些 SGD 类型方法以随机选择的步长和初始点找到了目标函数的 Clarke 稳定点。初步的数值实验表明了我们分析的 SGD 类型方法的高效性。

    Jul, 2023

  • 非凸分散学习的统一细化收敛分析

    本研究探讨了解决分布式优化问题的多种方法，包括 EXTRA、Exact-Diffusion/D^2 和梯度跟踪算法等，研究表明这些方法在网络拓扑敏感性上相对于 DSGD 较弱。该研究针对此问题提出了一种统一的分布式算法 SUDA，并建立了 SUDA 的收敛性，实验结果证明该算法对网络拓扑较为鲁棒。

    Oct, 2021

  • 用于非凸联邦优化的随机梯度方法的统一分析

    本文研究了 SGD 变体在平滑非凸情况下的表现，并提出了一种通用的假设模型来精确建模随机梯度的二阶矩，并给出了所有满足统一假设的方法的单一收敛分析。此外，作者提出了两种新的通用算法框架来处理分布式 / 联邦非凸优化问题，并说明这些方法均满足他们的统一假设，因此这个统一的收敛分析也包括了许多利用压缩通讯的分布式方法。最后，文章提供了一种在 PL 条件下获得更快线性收敛速度的统一分析。

    Jun, 2020

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

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

    May, 2016

  • 非凸分散梯度下降

    本研究探讨了去中心化算法在非凸一致优化中的应用和属性，特别针对非光滑函数和非凸集的情况，提出了 Prox-DGD 算法，通过现有的 convex setting 证明其误差收敛性。

    Aug, 2016

  • 基于拉格朗日法的非平滑非凸优化方法的开发

    本文中我们考虑在闭凸子集上最小化一个非光滑非凸的目标函数 $f (x)$，同时满足附加的非光滑非凸约束 $c (x) = 0$。我们开发了一个统一的框架来发展基于 Lagrangian 的方法，在每次迭代中通过某些子梯度方法对原始变量进行单步更新。这些子梯度方法被 “嵌入” 到我们的框架中，以黑盒更新原始变量的方式加以合并。我们证明了在温和条件下，我们提出的框架继承了这些嵌入子梯度方法的全局收敛性保证。此外，我们证明了我们的框架可以扩展到解决具有期望约束的约束优化问题。基于我们提出的框架，我们展示了一系列现有的随机子梯度方法，包括 proximal SGD、proximal momentum SGD 和 proximal ADAM，可以嵌入到基于 Lagrangian 的方法中。对深度学习任务的初步数值实验表明，我们提出的框架可以为非凸非光滑约束优化问题提供高效的 Lagrangian-based 方法变体，并具有收敛性保证。

    Apr, 2024

  • 用广义的布雷格曼散度驯服非凸随机镜像下降

    该论文重新审视了当今非凸优化设置中随机镜像下降（Stochastic Mirror Descent，SMD）的收敛性。通过支持一般距离生成函数（distance generating function，DGF）的新的非凸 SMD 收敛分析，该论文克服了先前结果对于具有光滑连续的梯度的可微性 DGF 的限制，并仅依赖于标准假设。此外，该论文通过 Bregman 前向 - 后向包络建立了收敛性，该包络是比常用的梯度映射的平方范数更强的度量。进一步，该论文将结果扩展到在次高斯噪声下的高概率收敛和在广义 Bregman Proximal Polyak-Lojasiewicz 条件下的全局收敛。此外，通过利用非光滑 DGFs，我们展示了改进的 SMD 理论在各种非凸机器学习任务中的优势。值得注意的是，在非凸差分隐私（differentially private，DP）学习的背景下，我们的理论提供了一个（几乎）维度无关的效用界算法。对于训练线性神经网络的问题，我们开发了可证明收敛的随机算法。

    Feb, 2024

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

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

    May, 2018

  • 随机符号下降方法：新算法和更好的理论

    本文介绍了一种基于符号的压缩方法，即 Stochastic Sign Descent with Momentum（SSDM）, 用于在分布式环境下解决符号 SGD 方法的收敛问题，同时可以保持 1 位压缩和小批量大小。

    May, 2019