Nov, 2023

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

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

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

    Feb, 2019

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

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

    Jul, 2017

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

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

    Feb, 2021

  • 标签噪声 SGD 可证明偏爱扁平化全局最小值

    研究过参数化模型，标签噪音等对随机梯度下降中的正则化作用及其影响。

    Jun, 2021

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

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

    Nov, 2023

  • 均匀时间 Wasserstein 稳定性界限用于（带噪）随机梯度下降

    通过将学习理论与应用概率联系起来，引入了一种新的方法来证明随机优化算法的 Wasserstein 稳定性边界，并在强凸损失和带有附加噪声的非凸损失的情况下获得了时间均匀稳定性边界，其不随迭代次数增加而增加，并且证明了 Lyapunov 函数的重要性。

    May, 2023

  • 双重随机模型：无偏标签噪声的学习和推断稳定性

    研究了标签噪声（或观测噪声）对于随机梯度下降（SGD）的小型抽样设置具有隐式正则化效果的影响，并对其进行了理论分析与实验验证。

    Apr, 2023

  • 非凸优化中具有概率保障的随机梯度下降泛化误差界

    本文探讨了深度学习模型的一种优化方法 —— 随机梯度下降在泛化能力上的稳定性，提出了一种基于梯度方差的稳定性指标，并在此基础上分别分析了常规非凸损失函数、梯度主导性损失函数和带强凸规则化器的问题，得到了一系列改进的泛化误差界。

    Feb, 2018

  • SGD 达到零损失后会发生什么？—— 数学框架

    该论文提出了一个可以研究 Stochastic Gradient Descent 在 overparametrized 模型中的隐式偏差的通用框架，该框架使用一个描述参数极限动态的随机微分方程，并考虑了任意噪声协方差，文中给出了一些新结果，同时可以在线性模型中进行应用。

    Oct, 2021

  • 用梯度实现的维度冲击：随机凸优化中的梯度方法的泛化

    研究了梯度方法在基础随机凸优化条件下的泛化性能，并关注其与维数的依赖关系。针对全批量梯度下降（GD），通过构建学习问题，在维数为 $ d = O（n^2）$ 的情况下，可以证明经过调整以达到经验风险最优表现的典型 GD（使用 n 个训练样本）在具有常数概率的情况下，收敛为近似经验风险最小化器，且其相对于总体风险具有 Ω（1）的过量风险。这个界限对于标准 GD 需要达到非平凡测试误差的训练样本数量有一个下界 Ω（√d），回答了 Feldman（2016）和 Amir，Koren 和 Livni（2021b）提出的一个开放问题，表明非平凡的维数依赖性是不可避免的。此外，针对标准的一次遍历随机梯度下降（SGD），我们证明了同样的构建技术在样本复杂度上提供了类似的 Ω（√d）下界，以达到非平凡的经验误差，尽管它可以实现最优的测试性能。与之前的工作（Koren，Livni，Mansour 和 Sherman，2022）相比，这提供了维数依赖性的指数级改进，解决了其中的一个开放问题。

    Jan, 2024