Oct, 2023

分散随机梯度下降上升算法的稳定性和泛化性

HTML
PDF
TL;DR我们研究了分布式随机梯度上升下降（D-SGDA）算法的原始-对偶广义界限，通过算法稳定性方法，在凸凹和非凸非凹环境下对分布式最小最大算法的广义界限进行了改进。我们的理论研究表明，分布式结构不会破坏D-SGDA的稳定性和广义化能力，在某些情况下可以实现和普通SGDA相同的广义化能力。此外，我们还评估了凸凹设定下D-SGDA算法的优化误差，并将其与广义间隙相平衡，以获得最佳的总体风险。最后，我们进行了多项数值实验来验证我们的理论发现。
发现论文，激发创造
  • 随机梯度下降的数据相关稳定性

    我们为随机梯度下降（SGD）建立了数据相关的算法稳定性概念，并利用它来开发新的泛化界限；我们的结果表明，在凸和非凸问题中，预筛选初始化是稳定SGD的一种简单数据驱动策略，并允许我们展示出乐观的泛化界限。

    Mar, 2017

  • 非光滑凸损失的随机梯度下降稳定性

    本研究为首次探讨随机梯度下降算法（SGD）在非光滑凸损失函数上的一致稳定性，得出了相关上下限并基于此获得了多项新且有用的泛化误差界限和差分隐私非光滑随机凸优化算法，且显著优于同类算法。

    Jun, 2020

  • 随机梯度下降的稳定性和泛化的精细分析

    本文提供了一种算法——随机梯度下降的稳定性和泛化性的细致分析，通过消除梯度有界性、减轻光滑性和凸性函数的限制，提出了新的稳定性度量，并开发了受 SGD 迭代的风险控制的新型约束，给出了受最佳模型行为影响的泛化范围，从而在低噪声环境下使用稳定性方法得到了第一个快速上界。

    Jun, 2020

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

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

    Aug, 2020

  • 分散随机梯度下降的稳定性和泛化能力

    本论文提出了分散化随机梯度下降法的新方法，并使用（非）凸优化理论建立了第一个针对分散化随机梯度下降法的稳定性和泛化保证。我们的理论结果基于少数常见且温和的假设，并揭示分散化将首次降低SGD的稳定性。通过使用多种分散化设置和基准机器学习模型，证实了我们的理论发现。

    Feb, 2021

  • 随机梯度下降法在极小极大问题中的稳定性和泛化性

    通过算法稳定性的视角，对凸凹和非凸非凹情形下的随机梯度方法在极小极大问题中的泛化能力进行了全面的分析，建立了稳定性与泛化能力之间的定量联系。在凸凹情形下，稳定性分析表明了随机梯度下降算法对于平滑和非平滑的极小极大问题皆可达到最优的泛化界。我们还确定了泛函弱凸弱凹和梯度占主导地位的问题的泛化界。

    May, 2021

  • 非凸和非光滑问题随机优化的稳定性和泛化

    本文针对非凸非光滑问题提出新的算法稳定性度量方法，同时建立它们与梯度之间的量化关系，并使用采样确定算法导出了随机梯度下降算法和其自适应变种的误差界。

    Jun, 2022

  • 拓扑感知的去中心化SGD的泛化

    研究了分散随机梯度下降（D-SGD）算法的算法稳定性和分布特性，证明了D-SGD认为的共识模型具有稳定性，证明了D-SGD具有一般化的可行性。D-SGD的可行性与谱间隙呈正相关，并且可以解释为什么最初的培训阶段的共识控制可以确保更好的一般化，这是 vanilla-D-SGD 的拓扑感知广义性的第一个工作。

    Jun, 2022

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

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

    Apr, 2023

  • 分散式 SGD 算法的稳定性和泛化分析改进

    本文提出 Decentralized Stochastic Gradient Descent 算法的泛化误差分析，并据此证明在凸设置下，不论选择哪种通信图，D-SGD算法的泛化界限与经典SGD算法相同，即前人论述的通信图对泛化的不利影响并不成立。

    Jun, 2023