May, 2017

Convex Until Proven Guilty”: 非凸函数上无维度的梯度下降加速

PDF
TL;DR本研究介绍了一种新的 Nesterov 加速梯度下降法的变体，以应对光滑非凸函数的最小化问题，证明其收敛速度可以接近凸函数，在处理非凸函数方面具有优异的性能，并在此基础上提出了一种基于负曲率的证明非凸性的方法，在具有 Lipschitz 连续梯度和黑塞矩阵的情况下，可以在较少的梯度和函数计算次数内找到目标点。
nesterov's accelerated gradient descentnon-convex functionsnegative curvaturelipschitz continuous gradienthessian
发现论文，激发创造
  • 非凸优化的加速方法

    通过使用只需要计算梯度的加速梯度方法，该论文提出了一种快速求解具有 Lipschitz 连续的一阶和二阶导数的非凸优化问题的算法，该方法相较于梯度下降算法在复杂度和精度上都表现更优。

    Nov, 2016

  • 加速梯度下降比梯度下降更快地逃离鞍点

    本文针对优化算法问题，研究了一种 AGD 变体，通过使用一个启发式的 Hamiltonian 函数以及一个新的框架 improve or localize，证明了其找到 hessian-free 的二阶稳定点的速度比 GD 更快，证明了其具有更好的收敛速度特性，加深了人们对加速算法和非凸优化的理解。

    Nov, 2017

  • 广义平滑下的凸优化和非凸优化

    本文介绍了一种新的非均匀光滑条件下的优化方法，并开发出一种简单但有效的分析技术来限制沿轨迹的梯度，从而获得更强的凸优化和非凸优化问题的结果。我们通过这种新方法证明了（随机）梯度下降和 Nesterov 加速梯度法在这种一般的光滑条件下的收敛率，而不需要梯度剪裁，并允许在随机场景中的有界方差的重尾噪声。

    Jun, 2023

  • 基于梯度的非凸优化的催化剂加速

    该论文介绍了一种通用的方案，使用最初设计用于最小化凸函数的梯度下降算法来解决非凸优化问题，该方案允许我们将这些方法用于弱凸性目标，这涵盖了机器学习和信号处理中通常出现的大类非凸函数。该方案无需假定目标函数具有凸性，而是通过自适应于未知的弱凸性常数来实现其保证。最后，本文还展示了将该方案应用于增量算法的几个实验结果。

    Mar, 2017

  • 加速分布式 Nesterov 梯度下降

    本文提出了一种通过本地计算和通信来优化全局函数的分布式优化方法，并探讨了其在不同情形下的收敛速度。

    May, 2017

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

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

    Jun, 2015

  • 加速额外梯度下降：一种新的加速一阶方法

    提出了一种新的加速一阶方法 (AXGD)，采用了预测 - 校正方法，解决了凸 - 凹鞍点问题，通过隐式欧拉离散化构建了加速连续时间动态模型，并通过原始 - 对偶视角进行了分析，对于其他类别的目标也能够达到最佳收敛速度。

    Jun, 2017

  • 加速重缩放梯度下降：平滑函数的快速优化

    本文提出了下降算法族，引入了一种名为坐标梯度算法的新的一阶算法，并证明了在函数强平滑的情况下，坐标梯度算法的收敛速度比梯度下降算法更快。当目标函数为凸函数时，我们提出了两种新颖的 “加速” 下降方法的框架，一种是 Nesterov 风格的，另一种是 Monteiro 和 Svaiter 风格的，都使用单个 Lyapunov 进行加速。在相同的强平滑性假设下，坐标梯度下降可以使用两个框架加速。我们提供了一些在机器学习领域中强平滑损失函数的实例和数值实验来验证我们的理论结果，另外还介绍了一些关于 Lyapunov 优化的扩展，包括导出最优通用张量方法以及将我们的框架扩展到坐标设置中。

    Feb, 2019

  • 一种用于无导数平滑随机凸优化的加速方法

    本文研究优化问题中目标函数存在不确定的噪声干扰，提出了基于导数的无导数算法，考虑了稀疏向量情况下使用 1 范数正则化的优化模型。

    Feb, 2018

  • 非凸非线性随机规划的加速梯度方法

    该论文将 Nesterov 的加速梯度方法推广到非凸和可能的随机优化问题中，证明该方法可以最优地解决一般的非凸光滑优化问题，并可应用于重要类的复合优化问题和非凸随机优化问题，是文献中第一次确立了 AG 方法解决非凸非线性规划的收敛性。

    Oct, 2013