Nov, 2023

过参数化线性回归的加速SGD的风险界

HTML
PDF
TL;DR我们研究了加速随机梯度下降（ASGD）在过参数化线性回归中的泛化情况，建立了数据协方差矩阵的每个特征子空间下的ASGD的过量风险界限，结果显示出ASGD在小特征值子空间中的偏差误差以指数衰减的速度优于SGD，而在大特征值子空间中，偏差误差的衰减速度较慢，且ASGD的方差误差始终大于SGD的。我们的研究表明，当初始化向量与真实权重向量的差异主要集中在小特征值子空间时，ASGD可以优于SGD。此外，当我们将分析专门应用于强凸设置下的线性回归问题时，得到的偏差误差界限比已知结果更紧。
发现论文，激发创造
  • 使用平均随机梯度下降实现优化的单遍大规模学习

    本文介绍了一种针对大规模学习的平均随机梯度下降方法，并提出了一种可以避免其使用不当学习速率时需要巨量数据才能到达渐近区域的简单方法，试验证明该方法在训练大规模线性分类器时优于其他算法。

    Jul, 2011

  • 随机梯度下降的数据相关稳定性

    我们为随机梯度下降（SGD）建立了数据相关的算法稳定性概念，并利用它来开发新的泛化界限；我们的结果表明，在凸和非凸问题中，预筛选初始化是稳定SGD的一种简单数据驱动策略，并允许我们展示出乐观的泛化界限。

    Mar, 2017

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

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

    Feb, 2018

  • 过度参数化的非线性学习: 梯度下降是否走过了最短路径?

    该论文讨论在数据过度参数化时，第一阶段优化方案（如随机梯度下降）的性质。作者发现，当损失函数在初始点的最小邻域内具有某些属性时，迭代会以几何速率收敛于全局最优解，会以接近直接的路线从初始点到达全局最优解，其中，通过引入一个新的潜力函数来作为证明技术的一部分。对于随机梯度下降（SGD），作者开发了新的鞅技巧，以保证 SGD 绝不会离开初始化的小邻域。

    Dec, 2018

  • 方向很重要：关于中等学习率的随机梯度下降的隐式偏差

    本研究针对模型学习速率为中等并逐渐降低的情况，研究了SGD和GD在超参数调节中的常见行为，以此试图解决机器学习中的算法偏差问题，并得出了不同方向偏差可能导致最终预测结果差异的结论。

    Nov, 2020

  • SGD优于GD在泛化方面（正则化没有帮助）

    本文研究了随机梯度下降和全样本梯度下降在随机凸优化模型中泛化性能的分离问题，发现经典的全样本梯度下降算法在步数相同的情况下会出现过拟合且通常需要更多的步数才能与随机梯度下降算法获得类似的泛化性能。同时本文还探讨了正则化、稳定性和隐含偏差等概念在泛化中的作用。

    Feb, 2021

  • 线性回归中恒定步长随机梯度下降的良性过拟合

    研究算法归纳偏差对于防止过度拟合的重要性，探讨使用常数步长随机梯度下降算法在超参数化情况下进行线性回归的问题和解决方案，提供了数据协方差矩阵全部的特征值，阐述一个可以使得泛化成为可能的偏差-方差分解，实验结果表明理论结果的正确性。

    Mar, 2021

  • 带有递减步长的SGD最后迭代的过参数化线性回归风险界

    本文针对几何递减步长的随机梯度下降算法在过参数化线性回归问题中的应用，对其迭代步数的风险进行了理论分析，并探讨了不同递减方法对算法优化效果的影响。

    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

  • 高维二次优化中（加速）随机梯度下降的最优性

    本研究针对高维学习中随机梯度下降（SGD）及其加速变种的最优性问题进行探讨，填补了这一领域的研究空白。通过建立动量加速SGD的收敛上界，论文提出了在特定问题下SGD或ASGD能实现最小-最大最优收敛速率的具体条件。此外，研究结果揭示了SGD在学习“稠密”特征及易问题中的高效性，并表明动量能够在相对困难的学习问题上显著加速收敛速度。

    Sep, 2024