Jul, 2023

随机组合梯度下降算法的稳定性和概化能力

PDF
TL;DR通过统计学习理论的算法稳定性角度，本文提供了随机组合梯度下降算法的稳定性和泛化分析，包括引入组合均匀稳定性的概念、建立其与复合优化问题泛化性能的定量关系、针对两种常用的随机组合梯度下降算法 SCGD 和 SCSC 建立组合均匀稳定性结果，并通过权衡稳定性结果和优化误差，导出了 SCGD 和 SCSC 的维度无关的超额风险界限。据我们所知，这是第一次关于随机组合梯度下降算法稳定性和泛化分析的结果。
stochastic compositional optimizationgeneralization analysisalgorithmic stabilitystochastic compositional gradient descentexcess risk bounds
发现论文，激发创造
  • 随机组合优化问题的解决几乎像解随机优化问题那么简单

    本文提出了一种新的 Stochastically Corrected Stochastic Compositional 梯度方法 (SCSC)，该方法可应用于用于强化学习和元学习等应用中的随机组合优化问题，并使用 SGD 的改进来加速收敛。

    Aug, 2020

  • 随机组合梯度下降：最小化期望值函数组合的算法

    通过提出一种随机复合梯度下降 (SCGD) 算法来解决最小化一个包含期望值或两个期望值函数组合的非线性函数的问题；该算法可以令 SCGD 收敛于凸优化问题的最优解，并且可以加速收敛于平稳点来解决非凸问题，进而解决学习、估计、动态规划等实践中常见的关于期望值函数组合的随机优化问题。

    Nov, 2014

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

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

    Feb, 2021

  • 随机组合优化加速

    提出一种新的随机优化方法，即加速随机复合近端梯度方法（ASC-PG）来解决随机组合优化问题。该方法能够处理非平滑正则化惩罚，并在几个重要特例中达到最优样本误差复杂度，而且应用于强化学习具有良好的表现。

    Jul, 2016

  • 方差降低梯度下降的有限和复合优化

    本文提出了两种算法解决有限和场景中的组合优化问题，并应用于机器学习、统计学和金融等领域，取得了比现有算法更好的收敛速度。

    Oct, 2016

  • 在分散式随机组合极小化优化中实现线性加速

    通过开发一种新的具有动量的分布式随机组合梯度下降上升算法，我们解决了分布式组合极小化问题中内层函数的共识误差，并证明了其能够实现线性加速。我们相信这种算法设计能够促进分布式组合优化的发展。对于不平衡分类问题，我们的广泛实验结果证明了算法的有效性。

    Jul, 2023

  • 随机梯度下降优化方法的适应性

    该研究介绍了一种名为 SCSG 的自适应算法，通过批量方差降低和几何随机变量技术，该算法对强凸性和目标精度具有适应性，实现了比其他已有适应性算法更好的理论复杂度。

    Apr, 2019

  • 优化随机函数组合的无偏模拟

    本文介绍了一种用于解决随机函数组合的凸优化问题的无偏梯度仿真算法，并将其与两个方差减少算法相结合，得出该算法基于无偏梯度仿真展现出令人满意的收敛性能，最后为两个随机函数组合优化问题应用了该算法：最大化 Cox 部分似然模型和训练条件随机场。

    Nov, 2017

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

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

    Jun, 2023

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

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

    Oct, 2023