Jun, 2024

最小二乘法回归的小批量梯度下降离散误差动态

PDF
TL;DR我们研究了无重复抽样的最小批量梯度下降在最小二乘回归中的离散动力学。我们证明最小批量梯度下降的动力学和泛化误差取决于原始特征 X 和一组新特征 X̃之间的样本交叉协方差矩阵 Z，在学习过程中每个特征都被之前出现的最小批次平均修改。利用这个表示，我们严格证明了最小批量梯度下降的动力学与全批量梯度下降在步长的线性尺度规则下达到了一致的主导阶。我们还研究了连续时间梯度流分析不能检测到的离散化效应，并显示最小批量梯度下降收敛到与步长相关的解，与全批量梯度下降相反。最后，我们利用自由概率理论工具，在假设随机矩阵模型的情况下，数值计算了 Z 的谱。
mini-batch gradient descentleast squares regressionsample cross-covariance matrixdynamicsgeneralization error
发现论文，激发创造
  • 随机梯度流对最小二乘隐式正则化

    研究隐式正则化的小批量随机梯度下降，以最小二乘回归为基础问题，利用具有与随机梯度下降相同矩的连续时间随机微分方程，称为随机梯度流。给出了随时间 t 随机梯度流的超额风险的界限，超过了具有调整参数 λ=1/t 的岭回归，此界限可以从明确的常数（例如小批量大小，步长，迭代次数）计算出来，显示了这些数量如何精确地推动超额风险。数值实验表明，边界可以很小，表明两种估计值之间存在紧密关系。给出了一个类似的结果，将随机梯度流和岭的系数联系起来。这些结果不受数据矩阵 X 的任何条件限制，并且跨越整个优化路径（不仅仅在收敛处）

    Mar, 2020

  • 常值步长最小均方：偏差 - 方差权衡与最优抽样分布

    本文考虑了最小二乘回归问题，提出了平均恒定步长随机梯度下降（也称最小均方误差）的性能的详细渐近分析。在强凸情况下，我们提供了一个高度渐近展开式。我们的分析提供了对随机逼近算法的新见解。

    Nov, 2014

  • 最小二乘回归的随机梯度下降并行化：小批量、平均和模型错误

    该研究探讨了在随机梯度下降中广泛使用的平均方案的好处。特别是，通过对最小二乘回归的随机逼近问题进行非渐进超额风险分析，提供了这些方案的性能保证，并提出了高度可并行化的随机梯度下降方法。同时，该研究认为，为了保证最小极大风险，针对混浊噪声的步长必须是噪声属性的一个函数。

    Oct, 2016

  • SGD: 一般分析和改进速率

    提出 SGD 收敛的通用简单定理，该定理可描述与特定概率法相关的各种 SGD 变体的收敛性。该定理是第一次执行这种分析，大多数 SGD 的变体以前从未明确考虑过。论文依赖于最近引入的期望平滑性的概念，并不依赖于随机梯度方差的统一界限。

    Jan, 2019

  • 带有马尔可夫数据的最小二乘回归：基本限制和算法

    研究了最小二乘线性回归的问题，其中数据点依赖于并从马尔可夫链中采样。在不同的噪声设置下，建立了关于底层马尔可夫链混合时间 $\tau_{mix}$ 的尖锐信息理论极小值下界来解决此问题。我们发现，与独立数据的优化相比，具有马尔可夫数据的优化通常更加困难，一个只在大约 $ ilde {\Theta}(\tau_{mix})$ 个样本中工作的平凡算法 (SGD-DD) 是极小化最优的。此外，我们还研究了实践中出现的结构化数据集，例如高斯自回归动态，它们能否拥有更高效的优化方案。令人惊讶的是，即使在这个特定的自然环境下，具有一定步长的随机梯度下降法与常数并没有比 SGD-DD 算法更好。相反，我们提出了一种基于体验复盘的算法 —— 一种流行的强化学习技术 —— 它可以实现更好的误差率。我们的改进速率是第一个在有趣的马尔可夫链上优于 SGD-DD 的算法之一，也为在实践中支持使用经验回放提供了首个理论分析。

    Jun, 2020

  • 线性回归的私有梯度下降：更紧凑的误差界限和特定实例的不确定性估计

    我们对标准差分隐私梯度下降方法在线性回归中的分析进行了改进，得出基于输入的合理假设，在每个时间步骤上迭代的分布特征。我们的分析结果揭示了算法的准确性新的发现：对于适当选择的超参数，样本复杂度仅与数据维度呈线性关系。这与（非私有）普通最小二乘估计器以及依赖于复杂的自适应梯度裁剪方案的最新私有算法（Varshney 等，2022 年；Liu 等，2023 年）的维度相关性一致。我们对迭代分布的分析还允许我们构建适应特定数据集算法的方差的置信区间。我们通过对合成数据进行实验证实了我们的定理。

    Feb, 2024

  • 随机梯度下降中小批量噪声的强度

    分析随机梯度下降中，小批量抽样引起的噪声和波动，揭示了大学习率可以通过引入隐含的正则化来帮助泛化的内在规律，并且可以提供一种理解随机梯度下降离散时序性对其功率规律现象的影响。

    Feb, 2021

  • SGD 的精确均方线性稳定性分析

    本文推导出了随机梯度下降法 (SGD) 的稳定性阈值的显式表达式，并给出了与批量大小相关的最简单的必要稳定性条件。

    Jun, 2023

  • 有限学习率随机梯度下降的噪声与波动

    本文探究了随机梯度下降（SGD）及其变种在非消失学习率模式下的基本性质，特别是推导了离散时间 SGD 在二次损失函数中的稳态分布，讨论了其影响，并考虑了 SGD 变体的逼近误差、小批量噪音效应、最优贝叶斯推断、从尖锐最小值的逃逸率和几种包括阻尼牛顿法、自然梯度下降和 Adam 的二阶方法的稳态协方差等应用。

    Dec, 2020

  • 贝叶斯视角下的泛化和随机梯度下降

    研究机器学习中的二个核心问题 —— 如何预测最小值是否能推广到测试集，以及为什么随机梯度下降找到的最小值能很好地推广；探讨了小批量大小影响参数朝向大证据最小值的作用；当学习速率固定时，建议选择使测试集准确性最大化的最佳批次大小。

    Oct, 2017