Mar, 2024

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

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

    通过使用分量函数的梯度和prox oracles提供了最小化m个凸函数平均值的复杂性的严格上下界；我们表明决定性和随机优化之间存在显着差距。对于光滑函数，我们表明在确定性和随机设置中，加速梯度下降(AGD)和SVRG的加速变体分别是最优的，并且梯度Orcale足以获得最佳速率。对于非光滑函数，通过接入prox oracles可降低复杂度，因此，我们提出基于平滑的最优方法，以改进仅使用梯度访问的方法。

    May, 2016

  • 随机凸优化中梯度变小的复杂性

    本文探讨了在随机凸优化问题中寻找近似驻点的 oracle 复杂度问题和其和全局 oracle 模型的关系，并提出了一种扩展的递归正则化算法以实现接近最优率，并揭示了 stochastic optimization 和 learning 的复杂度之间的一些惊人区别。

    Feb, 2019

  • 高度并行非光滑凸优化的复杂性

    研究在高度并行的梯度预言下，非光滑凸优化问题中梯度下降算法的优化次数上限，证明了仅当算法经过~(d)^(1/2)轮的交互，梯度下降才是最优算法，并提出一种思路更优的算法。

    Jun, 2019

  • 有约束极小极大优化的复杂性

    本文通过分析优化问题的计算复杂性，阐明了一系列非凸非凹目标函数的约束极值优化问题存在的困难，同时证明了该问题在Nemirovsky-Yudin模型中的难度，这与最小化问题在同样设置下可以使用Projected Gradient Descent进行近似局部最小值的行为形成了对比。

    Sep, 2020

  • 投影高效次梯度法和最优非光滑 Frank-Wolfe 法

    我们介绍了MOPES方法和MOLES方法，用于在具有昂贵的投影和线性最小化查询的情况下，高效地寻找在强凸约束集上的次优解。 MOPES方法通过Moreau-Yosida平滑和加速的一阶方案结合，并通过仅需O(ε ^ -1)投影查询和最少的O(ε ^ -2)函数值查询即可找到次优解。 MOLES方法仅具有线性最小化查询，但需要更多的函数值查询。

    Oct, 2020

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

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

    May, 2023

  • 亚线性复杂度下非凸非光滑约束组合问题的一阶优化方法：下界复杂度与近似最优方法

    本文针对一个类别的复合非凸非光滑优化问题，通过使用两个不同的一阶预言机，在最优性公差ϵ>0的情况下建立FOMs的下界复杂性界，并提出一个非精确近端梯度法来解决该问题。所提出的IPG方法的预言机复杂度与我们建立的下界匹配。

    Jul, 2023

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

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

    Aug, 2023

  • 梯度下降的非均匀平滑性

    该研究介绍了一种局部一阶平滑性oracle（LFSO），可以用于调整梯度下降方法的步长，从而改善全局和局部收敛性。通过应用LFSO于修正的一阶方法，可以在非强凸问题中实现全局线性收敛速度，从而提高了一般（加速）一阶方法的收敛率下界。

    Nov, 2023

  • 非光滑非凸优化中有意义局部保证的困难性研究

    本研究探讨了非光滑非凸优化的oracle复杂性，针对局部算法在给定一定条件下无法在子指数时间内提供有意义的局部保证的问题。通过分析，我们发现即使所有近似驻点都是全局极小值，局部利普希茨函数的局部算法在最坏情况下依然不能提供有效的函数值保证，这与光滑情况下标准梯度方法的结果形成鲜明对比。此发现对理论计算机科学文献中的困难性研究提供了补充。

    Sep, 2024