Aug, 2023

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

PDF
TL;DR本文提出了一种用于解决非凸、非光滑优化问题的近端次梯度方法（Prox-SubGrad），并通过建立一些子梯度上界及其关系，简化和统一了收敛速度的证明方案，同时还提出了一些新的随机子梯度上界条件，并为随机子梯度方法（Sto-SubGrad）建立了收敛和迭代复杂度。
proximal subgradient methodnonconvex optimizationnonsmooth optimizationconvergence analysisstochastic subgradient method
发现论文，激发创造
  • 重新审视亚梯度法：超越 Lipschitz 连续性的复杂度和收敛性

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

    May, 2023

  • 非光滑、非凸问题的近距离引导随机次梯度方法

    本文介绍了一种基于随机投影次梯度方法的弱凸（即均匀逼近正则）非光滑非凸函数的算法，并通过简单证明证明这种方法与用于光滑非凸问题的随机梯度方法具有相同的收敛速度；这似乎是第一个针对弱凸函数类的随机次（或确定性）梯度法的收敛速度分析。

    Jul, 2017

  • 一些针对强凸优化的次梯度方法的原始 - 对偶理论

    本文针对强凸但潜在不光滑非 Lipschitz 的优化问题，提出了新的等价的对偶描述，使得 $O (1/T)$ 收敛保证适用于几乎任何步长选择和一系列非 Lipschitz 病态问题，并提供了优化证书。

    May, 2023

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

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

    Mar, 2024

  • 随机次梯度法在弱凸函数上以 $O (k^{-1/4})$ 收敛

    本文证明了应用于弱凸问题的近端随机亚梯度法能将 Moreau 包络的梯度速率推向零点，因此我们实现了关于最小化光滑非凸函数和凸可靠函数之和的近端随机梯度下降法的收敛速率的一个开放性问题。

    Feb, 2018

  • 非 Lipschitz 连续情况下的确定性与随机次梯度方法的收敛速度

    通过对 Shor 子梯度分析的推广，我们将子梯度方法的经典收敛速度理论扩展到可适用于非 Lipschitz 函数。我们证明了在任何具有局部 Lipschitz 性的凸函数中，确定性投影子梯度算法的全局 O（1/√T）收敛速度。我们还表明，对于具有最多二次增长的凸函数，随机投影子梯度方法的收敛速度为 O（1/√T），在强凸性或较弱的二次下限条件下，该速度可进一步提高至 O (1/T)。

    Dec, 2017

  • 基于随机模型的弱凸函数最小化

    本文提出一族算法通过简单的随机模型样本和优化方法，成功的减少了目标函数。我们展示出，合理的近似质量和模型的正则性下，此类算法将自然的稳定度衡量推向 0，该衰减速度为 O (k^(-1/4))，基于此原理，我们为随机的近端子梯度法，近端次梯度法以及规则化的高斯牛顿法等提供了第一个复杂性保证。

    Mar, 2018

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

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

    Jun, 2017

  • 随机条件梯度方法：从凸优化到子模最大化

    该论文提出了基于随机条件梯度方法的优化问题求解算法，用于解决大规模维度下的凸函数、连续子模型等多种问题，并证明了当问题维度高时，该方法较与传统的随机梯度下降法更加稳定，同时计算时间复杂度也得到了有效降低。

    Apr, 2018

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

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

    Jun, 2023