Nov, 2023

SGLD 的独立于时间的信息论泛化界

PDF
TL;DR我们提供了一种新的信息理论泛化界限，用于研究随机梯度 Langevin 动力学（SGLD），在平滑性和耗散性的假设下。我们的界限是独立于时间的，当样本大小增加时会衰减为零，无论迭代次数和步长是否固定。与以前的研究不同，我们通过关注 Kullback-Leibler 散度的时间演化来推导泛化错误界限，这与数据集的稳定性有关，并且是输出参数和输入数据集之间互信息的上界。此外，我们通过展示 SGLD 的损失函数是次指数的来建立了第一个信息理论的泛化界限。这种界限也是独立于时间的，并消除了现有工作中的步长依赖问题，通过将我们的分析与现有的非凸优化误差界限相结合，导致改进的超额风险界限。
stochastic gradient langevin dynamicsgeneralization boundssmoothnessdissipativityinformation-theoretic
发现论文，激发创造
  • 通过数据依赖估计的信息理论广义绑定对 SGLD 的应用

    本文改进了 Pensia，Jog 和 Loh (2018) 开始的有噪声迭代学习算法的逐步分析，并在 Bu，Zou 和 Veeravalli (2019) 的基础上最近扩展。我们主要的贡献是通过数据相关估计显著提高了随机梯度 Langevin 动力学的互信息界限。我们的方法基于互信息的变分特性和使用基于训练样本子集的数据相关先验来预测小批量梯度。我们的方法在 Russo 和 Zou (2015)、Xu 和 Raginsky (2017) 的信息论框架内广泛适用。与其他依赖于梯度平方范数的边界相比，我们的边界项的数量级要小得多，同时可以与经验风险面的平坦度指标相关联。

    Nov, 2019

  • 非凸学习的 SGLD 泛化界限：两种理论视角

    本文提出了两个理论，分别使用稳定性和 PAC-Bayesian 结果的非渐进离散时间分析，研究了 Stochastic Gradient Langevin Dynamics（SGLD）在非凸目标下的泛化误差，其边界没有隐含依赖于参数的维数、规范或其他容量测量，优美地刻画了非凸设置中 “快速训练保证泛化” 的现象

    Jul, 2017

  • 随机梯度下降的信息理论泛化界

    本研究研究了随机梯度下降（SGD）这种普遍使用的随机优化方法的泛化特性，提供了依赖于在 SGD 计算的迭代路径上评估的随机梯度的本地统计信息的泛化误差的理论上限，其关键因素是梯度的方差及目标函数沿 SGD 路径的局部光滑性以及损失函数对最终输出的扰动敏感度和信息理论泛化界限等。

    Feb, 2021

  • 随机梯度朗逊动力学的非凸学习：非渐近分析

    使用加权运输成本不等式来量化 SGLD 在欧几里得 2 - 瓦瑟斯坦距离下收敛到随机分布的速率，并在非凸学习问题的背景下提供有限时间保证来找到两种风险的近似最小化器。

    Feb, 2017

  • 随机梯度 Langevin 动力学的碰撞时间分析

    本文研究了随机梯度 Langevin 动力学（SGLD）算法，针对非凸优化问题，注入适当缩放的高斯噪声来更新参数，我们分析了算法达到参数空间任意子集的的命中时间，从理论上得出结论：对于经验风险最小化，如果经验风险在点值上接近于（平滑的）总体风险，则该算法在多项式时间内实现了总体风险的近似局部最小值，逃离仅存在于经验风险的次优局部最小值。同时，我们还展示了 SGLD 如何改进学习零一损失下线性分类器的已知最佳学习结果之一。

    Feb, 2017

  • 非凸学习中带噪声梯度方法的泛化误差界

    本文应用 Bayes-Stability 框架证明算法相关的广义误差界，得到了随机梯度 Langevin 动力学以及其他一些带噪声梯度的方法（例如加动量，小批量和加速，熵 - SGD）的数据相关的新广义误差界，论文结果较之前相关研究更紧凑。

    Feb, 2019

  • 具有有界更新的迭代学习算法的泛化误差界

    研究了具有有界更新的迭代学习算法在非凸损失函数上的泛化特性，采用信息论技术。我们的主要贡献是针对具有有界更新的这些算法提出了新的泛化误差界，超出了之前仅关注随机梯度下降（SGD）的范畴。我们的方法引入了两个新颖之处：1）我们将互信息重新表述为更新的不确定性，提供了新的视角；2）我们采用方差分解技术来分解迭代中的信息，而不是使用互信息的链式法则，从而实现了一个更简单的替代过程。我们在不同设置下分析了我们的泛化界，并展示了当模型维度与训练数据样本数量以相同的速率增加时改进的界限。为了弥合理论与实践之间的差距，我们还研究了大型语言模型中先前观察到的标度行为。最终，我们的工作为发展实用的泛化理论迈出了更进一步的步伐。

    Sep, 2023

  • 关于随机子集泛化误差界和随机梯度 Langevin 动力学算法

    本研究基于 Hellström 和 Durisi 的框架整合了几个使用随机子集的期望泛化误差界限，其中包括了 Bu 等人关于样本互信息和 Negrea 等人关于数据集的随机子集的界限。然后，我们介绍了 Steinke 和 Zakynthinou 在随机子采样模式下的新的类似于前两个界限的界限，并确定了该框架的一些限制。最后，我们将用于 Langevin Dynamics 的界线从 Haghifam 等人扩展到了随机梯度 Langevin Dynamics，并将其在具有潜在大梯度规范的损失函数中进行了改进。

    Oct, 2020

  • SG Langevin 动力学的（非）渐近性质

    我们研究了使用固定步长的随机梯度 Langevin 动力学（SGLD）方法的特点及其偏差，并提出了一个修正的 SGLD 方法，在步长的一阶上消除了由于随机梯度方差引起的渐近偏差，并且得到了有限时间偏差、方差和均方误差（MSE）的界限。

    Jan, 2015

  • 标签噪声随机梯度下降的泛化界

    我们在非凸设置下，使用均匀耗散和平滑条件对带有标签噪声的随机梯度下降（SGD）进行了泛化误差界限的研究。在合适的半度量选择下，我们建立了依赖于参数维度 $d$ 的标签噪声随机梯度流的 Wasserstein 距离压缩。利用算法稳定性框架，我们推导出了具有恒定学习率的离散化算法的时间独立泛化误差界限。我们所实现的误差界限与 $d$ 的多项式和 $n^{-2/3}$ 的速率成多项式比例，其中 $n$ 是样本大小。这个速率比在类似条件下使用参数无关高斯噪声的随机梯度朗之万动力学（SGLD）的已知最优速率 $n^{-1/2}$ 更好。我们的分析提供了关于标签噪声影响的定量洞察。

    Nov, 2023