Oct, 2019

自适应梯度下降（无需下降）

PDF
TL;DR本文提供一个简明的证明，只需遵循两个规则即可自动化梯度下降：1）不要过快增加步长，2）不要超出局部曲率；通过遵循这些规则，可以得到对局部几何条件自适应的方法，收敛保证只取决于解的附近的平滑度，因此收敛于任何凸问题中，包括可以最小化任意连续两次可微的凸函数的问题，本文将探讨该方法在一系列凸和非凸问题上的性能。
gradient descentstepsizeslocal curvatureconvergence guaranteesconvex optimization
发现论文，激发创造
  • 适应性多梯度方法在准凸向量优化和多任务学习中的应用

    我们提出了一种适应性步长方法，用于解决一个广泛类别的非凸多目标规划问题，且不包含线搜索技术，适用于无界约束集。我们证明了在适度假设下，该方法的收敛性，并应用该方法进行了一些实验以验证其有效性。

    Feb, 2024

  • 方向平滑性和梯度方法：收敛性和适应性

    我们开发了一种梯度下降法的新次优性边界，该边界依赖于优化路径中的目标条件，而不是全局最坏情况下的常数。我们的证明关键在于方向平滑性，这是一种梯度变化的度量，我们用它来开发上界约束。通过求解隐式方程来最小化这些上界约束，我们展示了这些方程对于凸二次函数是容易解决的，并为两种传统步长提供了新的保证。对于一般函数，我们证明了 Polyak 步长和归一化梯度下降法尽管不使用方向平滑性的任何知识，但能够获得快速的路径相关性。逻辑回归上的实验证明，我们的收敛保证比基于 L 平滑性的传统理论更紧致。

    Mar, 2024

  • 一种全局收敛的增量式牛顿法

    本文提出了增量 Newton 方法和梯度增长条件，通过实例研究，发现增量 Newton 方法需要满足梯度增长条件才能达到线性收敛率，进而得到了分布式优化方法的线性收敛率结果。

    Oct, 2014

  • 比梯度下降法更快地找到局部极小值

    本文介绍了一种非凸二阶优化算法，其时间复杂度与样本维度和训练样本数量呈线性关系，在训练神经网络和其他非凸目标的机器学习问题上具有广泛应用，并可以保证返回近似局部最小值。

    Nov, 2016

  • 自适应步长随机梯度下降算法的收敛性

    通过研究广义 AdaGrad 步长在凸和非凸设置中，本文证明了这些步长实现梯度渐近收敛于零的充分条件，从而填补了这些方法理论上的空白。此外，本文表明这些步长允许自动适应随机梯度噪声级别在凸和非凸情况下，实现 O（1/T）到 O（1 / 根号 T）的插值（带有对数项）。

    May, 2018

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

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

    Dec, 2018

  • 自适应近端梯度方法用于凸优化

    本文探讨了凸优化中的两个基本一阶算法，梯度下降法（GD）和近端梯度法（ProxGD）。我们着重于通过利用光滑函数的局部曲率信息，使这些算法完全自适应。我们提出了基于观察到的梯度差异的 GD 和 ProxGD 的自适应版本，因此没有额外的计算成本。此外，我们证明了方法的收敛性，仅需假设梯度在局部利普希茨连续。此外，所提出的版本允许使用比 [MM20] 最初建议的更大的步长。

    Aug, 2023

  • 一种几何替代 Nesterov 加速梯度下降算法的方法

    我们提出了一种新的优化方法，通过类似于椭球体法的简单几何解释，实现了超平滑何强凸函数的无约束优化，并在数值实验中证明了其优于 Nesterov 加速梯度下降。

    Jun, 2015

  • 随机梯度下降算法自适应步长的局部二次收敛

    研究了一种在求解矩阵求逆等问题中具有局部二次收敛性的随机梯度下降优化方法，该方法采用自适应步长和一阶优化方法，为优化方法在深度学习中的应用提供了一条快速收敛的途径。

    Dec, 2021

  • 随机梯度下降法在非凸目标函数中的收敛速率

    本文研究了随机梯度下降法在非全局凸函数的情况下，实现局部收敛和收敛速率的估计，尤其适用于机器学习中的简单目标函数。

    Apr, 2019