Feb, 2024

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

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

    该论文研究了随机镜像下降法在非凸优化中的非渐近稳态收敛性，特别关注了一类非凸非光滑的随机优化问题，其中目标函数可以分解为一个相对弱凸函数（可能是非 Lipschitz）和简单的非光滑凸规则化函数。论文证明，SMD 算法在收敛速率为 $O（1/√t）$ 的同时，无需使用小批量就能保证收敛到一个稳定点。

    Jun, 2018

  • 超参数非线性模型的随机镜像下降：收敛性，隐式正则化和泛化

    本研究主要探讨过参数模型中采用 stochastic mirror descent 方法，在足够小的步长下，通过初始化接近全局最小值，其可以收敛和迭代到一种接近 Bregman 散度且具有更好泛化性能的解决方案，并探究该方法中不同的隐式正则化方式对结果表现的影响。

    Jun, 2019

  • 强凸优化的最优分布式随机镜像下降

    本文研究在多智能体网络中，基于 Bregman 散度作为距离测度函数，提出了两种高效的非欧几里德随机次梯度下降算法，用于求解非平滑和强凸函数的最小值，并在模拟实验中验证其收敛速度。

    Oct, 2016

  • 鞍点问题中的乐观镜像下降：额外走 (梯度) 一英里

    本文研究了一类具有一致性属性的非单调问题中，优化镜像下降法（OMD）的收敛性和优化方式。分析表明，OMD 可以解决这些问题并推广了先前的结果，为建立凸凹博弈以外的收敛性提供了具体进展。在一系列 GAN 模型上的数值实验结果验证了分析的可行性。

    Jul, 2018

  • 用于非光滑和随机优化的随机块镜像下降方法

    本篇论文介绍了一种新的随机算法 ——Stochastic Block Mirror Descent（SBMD）方法，用于解决大规模非光滑和随机优化问题，其通过加入块状坐标分解和增量式块状平均方案到经典（随机）镜像下降法中，以显著降低后者算法的每次迭代成本。我们建立了 SBMD 方法的收敛速率及其相关的大偏差结果，用于解决一般的非光滑和随机优化问题。此外，我们还介绍了此方法的不同变体，并建立了它们用于解决强凸，平滑，复合和某些非凸优化问题的收敛速率。据我们所知，所有这些 SBMD 方法的发展都是随机优化文献中的新成果。此外，我们的一些结果对于块状坐标下降方法中的确定性优化也是新的。

    Sep, 2013

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

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

    Mar, 2024

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

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

    Aug, 2020

  • 使用带有一般散度函数的近端梯度方法加速随机变分推断

    提出了一种基于随机梯度方法的变分推断新方法，不仅利用变分参数空间的几何性质，而且即使对于非共轭模型也可以产生简单的闭合式更新，该方法也具有收敛速率分析，即使用于非凸目标的随机镜像下降。在多种问题上，实验证明新算法在该框架中导出可以导致最先进的结果。

    Oct, 2015

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

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

    Jun, 2020

  • 应用于深度学习的非凸随机 Bregman 近端梯度方法

    研究一系列随机 Bregman 近端梯度法（SBPG）方法，用于训练具有非 Lipschitz 梯度的非凸目标函数，及应用于神经网络训练中具有多项式内核函数的深度神经网络的优化算法。证明了 SBPG 及其动量版本（MSBPG）在非凸优化问题中有很好的收敛性，提出了 MSBPG 解决大规模优化中随机梯度下降法的一些不足。

    Jun, 2023