Mar, 2024

Horoballs 和次梯度方法

PDF
TL;DR探索凸优化在 Hadamard 空间上的应用，我们考虑了类似于次梯度算法的迭代方法。与传统方法不同的是，我们的方法适用于一般的 Hadamard 空间，采用了底层空间本身的框架，并且依赖于目标级集的次凸性。对于这个受限制的目标类别，我们证明了一个类似于通常形式的复杂度结果，特别地，复杂度不依赖于空间曲率的下界。
convex optimizationhadamard spacessubgradient algorithmhorospherical convexitycomplexity
发现论文，激发创造
  • 测地凸优化的一阶方法

    该研究提出了一种称为测地凸性的新概念，将向量空间凸性推广到非线性度量空间，并在 Hadamard 流形上开发了迭代复杂度分析，为一些一阶算法提供了全局复杂度上限。研究结果还揭示了流形几何，尤其是分段曲率如何影响收敛速度。这是第一篇为一般 g - 凸优化的一阶算法提供全局复杂度分析的工作。

    Feb, 2016

  • 双曲空间中的梯度下降

    本研究展示了在利用双曲空间进行优化时，利用梯度下降的计算方法是直接的，并说明了采用该方法的优点和量化结果。

    May, 2018

  • 超半空间中解决大边际分类器的凸松弛

    通过将问题转化为多项式优化，使用半定松弛和稀疏矩和平方松弛方法来近似最优解，在广泛的实验中表现优于投影梯度下降方法。

    May, 2024

  • 重新审视亚梯度法：超越 Lipschitz 连续性的复杂度和收敛性

    本文研究了基于次梯度方法的非光滑优化问题，针对具有凸性和弱凸性的目标函数，推导了次梯度方法的收敛性和复杂度界限，证明了步长的选取可以控制其移动轨迹，从而保证算法的收敛性。同时，还将该方法拓展到了截断型、随机型、增量型等非 Lipschitz 函数的问题上。

    May, 2023

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

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

    Nov, 2011

  • Hamiltonian Descent 方法

    研究了一种基于动力学系统模拟的优化方法，该方法使用常量步长和一阶梯度信息，在更大的凸函数类中实现线性收敛性，包括那些在其极小值点处可能具有奇异或未有界的二阶导数，该方法的动力学梯度映射可以设计成以凸共轭的形式整合信息，允许在非平滑或非强凸的凸函数上实现线性收敛。

    Sep, 2018

  • 具有 Hölder 增长函数的更快次梯度方法

    本文探讨次梯度法在极值点问题（特别是带有 Hölder 增长 ）中，固定和衰减步长下的收敛性及误差，并介绍了一种名为 “下降楼梯” 的步长方式，最终提出了一种自适应变体方法以实现更快的收敛速度。

    Apr, 2017

  • 在更细粒度上的优化：有界局部次梯度变化视角

    这篇文章研究了在有界局部次梯度变化情况下的非光滑优化问题，定义了目标函数的类别，包括传统优化问题中基于目标函数的 Lipschitz 连续性或梯度的 Holder/Lipschitz 连续性的函数，并且包含了既不是 Lipschitz 连续也没有 Holder 连续梯度的函数类别。研究结果表明在传统的优化问题类别中，所定义的类别参数能够得到更为精细的复杂度界限，并恢复了最坏情况下的传统 oracle 复杂度界限，同时对于不是最坏情况的函数通常能够得到更低的 oracle 复杂度。此外，该文章还强调了在并行计算环境中非光滑优化的复杂度与次梯度集合的平均宽度有关。

    Mar, 2024

  • 加速概率测度空间的优化

    在机器学习应用中，梯度优化方法的加速是一个实际和理论上感兴趣的问题。大多数研究关注欧几里得空间上的优化，但鉴于在许多机器学习问题中需要在概率测度空间上进行优化，研究在这个背景下的加速梯度方法很有意义。为此，我们介绍了与欧几里得空间中基于矩的方法类似的哈密顿流方法。我们证明了基于这种方法的算法可以实现任意高阶的收敛速度。数值例子证明了我们的论断。

    Oct, 2023

  • 黎曼自适应优化方法

    将 Adam、Adagrad 和 Amsgrad 等流行的自适应随机优化方法扩展到里曼流形上面的困难以及基于里曼流形的优化算法和渐进结果的提出，同时在实验中证明该算法比原算法更快且表现更好。

    Oct, 2018