Feb, 2024

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

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

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

    Aug, 2023

  • 保障自适应方法：巴基莱 - 波尔温法和其他步长选择的全局收敛

    通过对于凸最小化问题的自适应方法的最新进展的利用，本文提供了一种无需线搜索的近端梯度下降框架，用于全局化收敛于流行的步长选择，如 Barzilai-Borwein 和一维 Anderson 加速。该框架可以处理梯度可微函数只具有局部 Holder 连续性的问题。我们的分析不仅包含但也改进了现有结果，并以数值证据来证明快速步长选择和自适应方法之间的协同作用。

    Apr, 2024

  • 增量方法的最后迭代收敛及其在持续学习中的应用

    基于应用于连续学习中的动机，我们首次获得了增量梯度和增量近端方法的最后迭代的收敛性保证，适用于一般凸平滑以及凸 Lipschitz 设置，同时几乎与平均迭代的最佳收敛性保证相匹配。

    Mar, 2024

  • 适应性多梯度方法在准凸向量优化和多任务学习中的应用

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

    Feb, 2024

  • 自适应一阶优化方法的收敛性：近端梯度和交替最小化算法

    基于最近的无线搜索自适应近端梯度方法，本文提出了 AdaPG^rπ 框架，通过提供更大的步长策略和改进的下界，统一和扩展了现有的结果。讨论了参数 π 和 r 的不同选择，并通过数值模拟证明了所得方法的有效性。为了更好地理解基本理论，还建立了一个允许时变参数的更一般的收敛性设置。最后，通过探索对偶设置，提出了一种自适应交替最小化算法。这种算法不仅包含了额外的适应性，而且扩展了其适用性，超出了标准强凸设置。

    Nov, 2023

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

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

    Oct, 2023

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

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

    Oct, 2019

  • 针对最小化复合非凸、非光滑和非 Lipschitz 函数的次梯度方法的统一分析

    本文提出了一种用于解决非凸、非光滑优化问题的近端次梯度方法（Prox-SubGrad），并通过建立一些子梯度上界及其关系，简化和统一了收敛速度的证明方案，同时还提出了一些新的随机子梯度上界条件，并为随机子梯度方法（Sto-SubGrad）建立了收敛和迭代复杂度。

    Aug, 2023

  • 超越凸性和 Lipschitz 梯度连续性的一阶方法及其在二次逆问题中的应用

    利用可适应性光滑函数的概念和 Bregman 基础的近端梯度方法，在解决具有复杂目标函数的非凸、非光滑最小化问题时，实现全局收敛。

    Jun, 2017

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

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

    Mar, 2024