Dec, 2023

从互信息到期望动力学：针对重尾随机梯度下降的新的泛化界限

PDF
TL;DR理解现代机器学习算法的泛化能力作为研究主题在过去几十年中备受关注。最近，随机梯度下降（SGD）的学习动态与重尾动态有关，这已成功应用于利用这些动态的分形属性的泛化理论中。然而，所推导出的界限依赖于超出计算能力的互信息（解耦）项。在本研究中，我们证明了一类重尾动态轨迹上的泛化界限，而无需这些互信息项。相反，我们通过比较基于经验风险的学习动态（依赖于群体风险）与基于预期风险的动态引入了一个几何解耦项。我们进一步利用重尾和分形文献中的技术对该几何项进行了上界限定，使其完全可计算。此外，为了收紧界限，我们提出了一个基于扰动动态的 PAC-Bayesian 设置，在该设置中，相同的几何项起着关键的作用，并且仍然可以使用上述描述的技术进行界定。
发现论文，激发创造
  • 随机梯度下降中的重尾现象

    本文阐述了随机梯度下降（SGD）在深度学习中的泛化性能与最小值的浅奥关系，并通过线性回归等简单问题分析证明了参数选择会对算法的收敛率及概率分布产生影响。

    Jun, 2020

  • 利用分数布朗运动得出的深度神经网络的轨迹相关的泛化界

    通过探究 SGD 的轨迹依赖假设集，建立基于 Hausdorff 维数的 Rademacher 复杂度，并通过假设集稳定性推导具有预测力的 DNN 的新型泛化边界。

    Jun, 2022

  • 神经网络中的豪斯多夫维数、重尾及泛化

    本文提出了一种使用 Feller 过程来逼近 SGD 轨迹以及使用 Hausdorff 维度控制相关广义误差的学习理论框架，同时提出了使用 Feller 过程的尾部指数作为 “容量度量” 的概念，可用于估计广义误差，并且与参数数量不同于现有文献中的容量度量。

    Jun, 2020

  • 通过数据依赖估计的信息理论广义绑定对 SGLD 的应用

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

    Nov, 2019

  • 通过分数型福克 - 普朗克方程推导重尾 SDE 的泛化界限

    通过评估与所谓的分数 Fokker-Planck 方程相关的熵流，我们证明了重尾 SDE 的具有高概率的概括界限，无需包含任何非平凡的信息论术语，并发现了一个相变现象，这表明重尾可能有利也可能有害，具体取决于问题的结构。

    Feb, 2024

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

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

    Feb, 2021

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

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

    Sep, 2023

  • 通过随机递归方程分析随机梯度下降的重尾特性

    在这篇论文中，我们回答了引用论文中的几个未解决问题，并应用不可约 - 近似 (i-p) 矩阵的理论来扩展他们的结果。

    Mar, 2024

  • 信息论泛化界的统一框架

    文中提出了一种利用概率去相关引理、对测度空间中的的概率测度进行对称化、配对和链化等技术来获得学习算法信息论泛化界限的一般性方法，进而得到新的期望值和高概率条件下泛化误差的上界，特别地，还包括了基于互信息、条件互信息、随机链和 PAC-Bayes 不等式等现有泛化界限的特例。此外，Fernique-Talagrand 上界也是一个特例。

    May, 2023

  • 信息密度和条件信息密度的泛化界

    通过指数不等式的方法，我们研究了随机学习算法的泛化误差的界限和概率分布，针对亚高斯损失函数提供了以训练数据和输出假设之间信息密度为依据的新的界限，并将该方法扩展到了基于随机选择训练数据子集的情况。

    May, 2020