Feb, 2024

李群上的随机海森拟合

PDF
TL;DR该研究通过 Hessian 拟合及其逆方法与随机 Hessian 向量积的拟合准则对常用方法（如 BFGS、Gaussian-Newton、AdaGrad 等）进行了分析，揭示了不同的 Hessian 拟合方法具有不同的收敛速度，对于欧几里得空间中的梯度下降和对称正定矩阵及一定列维数的李群上的梯度下降有次线性和线性收敛速度。在特定但足够一般的李群上，该 Hessian 拟合问题被进一步证明具有强凸性。通过噪声 Hessian 向量积、时变 Hessians 和低精度计算的不同设置对这些方法进行了测试，这些发现对于依赖于快速、稳健和准确 Hessian 估计的随机二阶优化非常有用。
hessian fittingconvergence ratesgradient descenthessian-vector productssecond order optimizations
发现论文，激发创造
  • 曲率信息的 SGD：通过通用李群预条件器

    提出了一种新的方法，通过利用从海森矩阵向量积或参数和梯度的有限差分得到的曲率信息，类似于 BFGS 算法，加速随机梯度下降（SGD）。该方法涉及两个预条件器：一个矩阵无关的预条件器和一个低秩近似预条件器。我们使用一种对随机梯度噪声稳健且不需要线性搜索或阻尼的标准在线更新两个预条件器。为了保持相应的对称性或不变性，我们将预条件器约束为某些连通的李群。李群的等变性质简化了预条件器拟合过程，而其不变性质消除了通常在二阶优化器中需要的阻尼需求。因此，参数更新的学习率和预条件器拟合的步长在自然数值化，它们的默认值在大多数情况下都能很好地工作。我们的方法为提高 SGD 的收敛速度提供了一个有希望的方向，且计算开销较低。我们证明，在多个现代深度学习架构上，基于预条件的 SGD（PSGD）在视觉，自然语言处理和强化学习任务上优于 SoTA。本文提供了复现玩具和大规模实验的代码。

    Feb, 2024

  • 加速随机矩阵求逆：一般理论和加速 BFGS 规则，用于更快的二阶优化

    本研究提出了第一种在欧几里得空间中解决线性系统问题的加速随机算法，应用于矩阵求逆问题，可得到正定矩阵，进而在优化和机器学习领域中具有广泛应用。该算法还可用于加速机器学习模型的训练。

    Feb, 2018

  • Krylov 子空间下降用于深度学习

    本研究提出了一个针对高维模型和大量训练样本的二阶优化方法，使用 Krylov 子空间进行训练加速，并在深度神经网络中的效果优于 SGD、共轭梯度下降和 L-BFGS 等算法，且优于 Hessian Free 方法。

    Nov, 2011

  • 随机块 BFGS：从数据中挤出更多曲率

    提出了一种新型的有限记忆随机块 BFGS（L-BFGS）方法，用于在随机逼近方法中加入丰富信息的曲率问题，结果显示该方法在大规模日志回归问题上具有更好的鲁棒性和显著的优越性。

    Mar, 2016

  • 统一随机梯度下降和拟牛顿法的快速大规模优化

    该研究提出了一种算法，它结合了随机梯度下降的计算效率和拟牛顿法利用的二阶曲率信息，通过维护和操作每个贡献函数的独立 Hessian 近似值实现不同的方法的统一。该算法适用于高维度优化问题，通过将这些二次近似值存储和操作在一个共享的、时变的、低维度子空间中，保持了计算可行性和限制了内存需求，且需要很少或不需要调整超参数。该算法与早期的随机二阶技术相反，早期技术将每个贡献函数的 Hessian 视为完整 Hessian 的噪声近似，而不是直接估计的目标。在七个不同的优化问题上进行了实验性的改进收敛表现，算法已发布为开源 Python 和 MATLAB 软件包。

    Nov, 2013

  • 迭代 Hessian 草图：约束最小二乘问题的快速准确解近似

    本文研究了随机草图方法，以近似解决带有一般凸约束的最小二乘问题，并提出了一种名为迭代 Hessian 草图的新方法，同时提供了数值模拟实验，包括面部表情分类实验。

    Nov, 2014

  • 神经网络可行的无鞍牛顿优化的 Hessian-Vector 乘积系列

    提出了一个既能解决大规模的 Hessian 矩阵问题，又能优化非凸性的优化算法，采用了一个无限级数截断的方法，并在多种情境下进行了验证，包括在 CIFAR-10 上训练的 ResNet-18 模型。

    Oct, 2023

  • 论 Stein 变分梯度下降的几何形式

    本文研究贝叶斯推断问题，特别关注于最近引入的斯坦变分梯度下降方法，介绍了该方法的交互粒子系统构建；并通过研究选择合适的正定核函数的问题，提出采用调整尾部的某些不可微核函数，证明在各种数值实验中这种方法具有明显的性能提升。

    Dec, 2019

  • 凸规划中的 Hessian Riemannian 梯度流

    通过带约束的极小化问题，研究以 Legendre 型的凸函数诱导的 Hessian 黎曼度量的梯度流。通过一系列引理得到了 Hessian 黎曼结构与变分不等式具有特定的积分性质的凸集的积分值，给出了 Bregman 类型距离的新动机。接着，引入了一般演变问题，并给出了微分包含的修正。在拟凸条件下，证明了一般存在和全局收敛性，对于凸最小化问题，有一些有趣的细节。讨论了一些这些梯度流的显式例子。鉴定了双轨迹，并考虑了带有正性和等式约束的凸程序的双重收敛的充分条件。建立了一些收敛速率结果。

    Nov, 2018

  • 广义高维线性反问题的几何推断

    该论文提出了一个几何统计分析框架，适用于泛化的不适定线性反问题模型，包括噪声压缩感知、符号向量恢复、迹回归、正交矩阵估计和噪声矩阵完成等特殊情况，提出了可行的计算凸规划方法，用于统计推断，包括估计、置信区间和假设检验。该论文建立了一个理论框架，以表征局部估计收敛速度，并提供统计推断保证，其结果基于局部锥几何和对偶性，并通过高斯宽度和 Sudakov 最小化估计量表征局部切锥的几何。

    Apr, 2014