非凸学习的 SGLD 泛化界限:两种理论视角
本文应用 Bayes-Stability 框架证明算法相关的广义误差界,得到了随机梯度 Langevin 动力学以及其他一些带噪声梯度的方法(例如加动量,小批量和加速,熵 - SGD)的数据相关的新广义误差界,论文结果较之前相关研究更紧凑。
Feb, 2019
我们提供了一种新的信息理论泛化界限,用于研究随机梯度 Langevin 动力学(SGLD),在平滑性和耗散性的假设下。我们的界限是独立于时间的,当样本大小增加时会衰减为零,无论迭代次数和步长是否固定。与以前的研究不同,我们通过关注 Kullback-Leibler 散度的时间演化来推导泛化错误界限,这与数据集的稳定性有关,并且是输出参数和输入数据集之间互信息的上界。此外,我们通过展示 SGLD 的损失函数是次指数的来建立了第一个信息理论的泛化界限。这种界限也是独立于时间的,并消除了现有工作中的步长依赖问题,通过将我们的分析与现有的非凸优化误差界限相结合,导致改进的超额风险界限。
Nov, 2023
使用加权运输成本不等式来量化 SGLD 在欧几里得 2 - 瓦瑟斯坦距离下收敛到随机分布的速率,并在非凸学习问题的背景下提供有限时间保证来找到两种风险的近似最小化器。
Feb, 2017
本文探讨了深度学习模型的一种优化方法 —— 随机梯度下降在泛化能力上的稳定性,提出了一种基于梯度方差的稳定性指标,并在此基础上分别分析了常规非凸损失函数、梯度主导性损失函数和带强凸规则化器的问题,得到了一系列改进的泛化误差界。
Feb, 2018
本研究研究了随机梯度下降(SGD)这种普遍使用的随机优化方法的泛化特性,提供了依赖于在 SGD 计算的迭代路径上评估的随机梯度的本地统计信息的泛化误差的理论上限,其关键因素是梯度的方差及目标函数沿 SGD 路径的局部光滑性以及损失函数对最终输出的扰动敏感度和信息理论泛化界限等。
Feb, 2021
本文研究了随机梯度 Langevin 动力学(SGLD)算法,针对非凸优化问题,注入适当缩放的高斯噪声来更新参数,我们分析了算法达到参数空间任意子集的的命中时间,从理论上得出结论:对于经验风险最小化,如果经验风险在点值上接近于(平滑的)总体风险,则该算法在多项式时间内实现了总体风险的近似局部最小值,逃离仅存在于经验风险的次优局部最小值。同时,我们还展示了 SGLD 如何改进学习零一损失下线性分类器的已知最佳学习结果之一。
Feb, 2017
我们为随机梯度下降(SGD)建立了数据相关的算法稳定性概念,并利用它来开发新的泛化界限;我们的结果表明,在凸和非凸问题中,预筛选初始化是稳定 SGD 的一种简单数据驱动策略,并允许我们展示出乐观的泛化界限。
Mar, 2017
我们在非凸设置下,使用均匀耗散和平滑条件对带有标签噪声的随机梯度下降(SGD)进行了泛化误差界限的研究。在合适的半度量选择下,我们建立了依赖于参数维度 $d$ 的标签噪声随机梯度流的 Wasserstein 距离压缩。利用算法稳定性框架,我们推导出了具有恒定学习率的离散化算法的时间独立泛化误差界限。我们所实现的误差界限与 $d$ 的多项式和 $n^{-2/3}$ 的速率成多项式比例,其中 $n$ 是样本大小。这个速率比在类似条件下使用参数无关高斯噪声的随机梯度朗之万动力学(SGLD)的已知最优速率 $n^{-1/2}$ 更好。我们的分析提供了关于标签噪声影响的定量洞察。
Nov, 2023
研究了具有有界更新的迭代学习算法在非凸损失函数上的泛化特性,采用信息论技术。我们的主要贡献是针对具有有界更新的这些算法提出了新的泛化误差界,超出了之前仅关注随机梯度下降(SGD)的范畴。我们的方法引入了两个新颖之处:1)我们将互信息重新表述为更新的不确定性,提供了新的视角;2)我们采用方差分解技术来分解迭代中的信息,而不是使用互信息的链式法则,从而实现了一个更简单的替代过程。我们在不同设置下分析了我们的泛化界,并展示了当模型维度与训练数据样本数量以相同的速率增加时改进的界限。为了弥合理论与实践之间的差距,我们还研究了大型语言模型中先前观察到的标度行为。最终,我们的工作为发展实用的泛化理论迈出了更进一步的步伐。
Sep, 2023
本文改进了 Pensia,Jog 和 Loh (2018) 开始的有噪声迭代学习算法的逐步分析,并在 Bu,Zou 和 Veeravalli (2019) 的基础上最近扩展。我们主要的贡献是通过数据相关估计显著提高了随机梯度 Langevin 动力学的互信息界限。我们的方法基于互信息的变分特性和使用基于训练样本子集的数据相关先验来预测小批量梯度。我们的方法在 Russo 和 Zou (2015)、Xu 和 Raginsky (2017) 的信息论框架内广泛适用。与其他依赖于梯度平方范数的边界相比,我们的边界项的数量级要小得多,同时可以与经验风险面的平坦度指标相关联。
Nov, 2019