Oct, 2023

一种简单的无需线搜索的凸优化均匀最优方法

PDF
TL;DR本文提出了一种新的加速梯度下降方法（AC-FGM），可以在没有给定全局 Lipschitz 常数或使用线性搜索过程的情况下，实现平滑凸优化的最优收敛速率，并将 AC-FGM 扩展到具有 Hölder 连续梯度的凸优化问题，自动实现所有问题类别的最优收敛速率，并在凸优化中演示了 AC-FGM 相对于以前开发的无参数方法的优势。
line search proceduresconvex optimizationaccelerated gradient descentac-fgmparameter-free methods
发现论文，激发创造
  • 优化梯度法的收敛分析

    本文考虑了光滑凸函数的无约束极小化问题，并给出了分析收敛性质的结果，同时探讨了针对光滑凸函数的最优一阶算法。

    Oct, 2015

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

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

    Jun, 2015

  • 凸优化的梯度方法：在较弱条件下获得更好的收敛速率

    本文研究了梯度方法在凸优化中的收敛行为，证明了仅满足某些线段上的 Lipschitz 连续性和强凸性条件时，其复杂度可达到已知的最优值。同时，利用切线条件和投影的约束得到了更为松弛的条件，并应用于稀疏优化问题中构造更快的求解算法。

    Mar, 2013

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

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

    Jun, 2023

  • 自适应近端梯度方法的普适性无需近似

    通过分析，我们展示了对于凸问题，自适应的近端梯度方法不受传统的 Lipschitzian 假设的限制。我们的分析揭示了一类无需线搜索的方法仍然在纯粹的局部 Hölder 梯度连续性下收敛，特别是连续可微分的半代数函数。为了解决局部 Lipschitz 连续性的缺失，流行的方法围绕着 ε- 预测器和 / 或线搜索程序。相反，我们利用 Hölder 不等式，而不需要任何近似，同时保持自适应方案的无需线搜索的特性。此外，我们在先验地不了解局部 Hölder 常数和 Hölder 连续性的阶的情况下，证明了完全序列的收敛性。在数值实验中，我们将其与基准方法在涵盖局部和全局 Hölder 设置的各种机器学习任务中进行比较。

    Feb, 2024

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

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

    Oct, 2019

  • 非强凸优化的一阶方法线性收敛

    本文研究了解决光滑的非强凸约束优化问题的一些一阶方法的收敛率，提供了一些松弛的强凸条件并证明了它们对于多种一阶方法的线性收敛是足够的，最后证明了所提出的松弛强凸条件涵盖了求解线性系统、线性规划和线性约束凸问题的重要应用。

    Apr, 2015

  • 一种线性收敛的条件梯度算法及其在在线和随机优化中的应用

    本研究介绍了一种基于条件梯度算法的优化模型，可用于求解线性优化问题和非线性凸优化问题，并给出了一种基于此算法的在线凸优化算法，具有线性收敛速度和最优的遗憾保证。

    Jan, 2013

  • 非凸优化的加速方法

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

    Nov, 2016

  • 在线自适应方法、普适性和加速

    本文针对凸无约束优化问题提出了一种新方法，通过一种自适应学习率规则和线性耦合两个序列的方式，利用重要权重和自适应在线学习算法的思想实现了对光滑目标、非光滑一般情况和随机优化的加速收敛。实证分析表明了本方法在上述场景中的适用性并证实了我们的理论发现。

    Sep, 2018