Oct, 2023

非凸优化中找到稳定点的计算复杂度

PDF
TL;DR非凸优化中寻找近似驻点的计算和查询复杂性是本文的关键研究内容，其中包括在无约束域中寻找近似驻点的问题的 PLS 完备性、二维情况下的零阶算法以及近似驻点的查询复杂性的特征化，同时还研究了约束优化问题中寻找近似 KKT 点的查询复杂性，并指出约束优化中近似 KKT 点与无约束优化中近似驻点的对应关系。
approximate stationary pointsgradientnon-convex optimizationquery complexityconstrained optimization
发现论文，激发创造
  • 寻找静态点的下界 I

    该研究论文证明了在高维、潜在非凸函数上找到 ε- 稳态点的复杂性下界，并探讨了基于 Oracle 算法的复杂度测量方法，显示出梯度下降、三次正则化牛顿法和广义 p 次正则化在自然函数类中是最优的。

    Oct, 2017

  • 非凸随机优化下的下限界

    采用随机一阶方法找到梯度范数不超过 ε 的 ε- 稳定点的复杂度下界，使用具有有界方差的无偏随机梯度预言机访问光滑但可能非凸函数的一种模型，证明任何算法在最坏情况下需要至少 ε^-4 个查询才能找到 ε- 稳定点。对于噪声梯度估计满足均方光滑性质的更严格模型，我们证明了 ε^ -3 个查询的下界，建立了最近提出的方差缩减技术的最优性。

    Dec, 2019

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

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

    Feb, 2019

  • 使用随机梯度下降法找到稳定点的复杂度

    研究了随机梯度下降（SGD）算法在最小化光滑、可能非凸函数梯度范数方面的迭代复杂度，结果表明，Ghadimi 和 Lan 的上限不能得到改进，除非做出额外的假设，即使对于凸二次函数，也是如此；此外还表明，对于非凸函数，SGD 最小化梯度的可行性需要根据所选择的最优性标准而定。

    Oct, 2019

  • 寻找非光滑非凸函数的驻点的复杂度

    本文介绍了一种针对非光滑、非凸函数的最新方法，通过概率论的方法实现了解决 ReLU 神经网络参数调整中的复杂问题的方法，其中提出的梯度算法能够使结果的准确度近似于一阶算法，并在距离解决方案的距离 delta 的范围内，得出广义梯度与解决方案的凸组合。

    Feb, 2020

  • 非凸强凹 Min-Max 优化的复杂度下界

    我们通过使用第一阶 oracle 及条件数，提供了寻找 min-max 优化问题中目标函数在最小化变量上是非凸及在最大化变量上是强凸时的稳定点的复杂度的下界，这既适用于确定性 oracle 也适用于随机 oracle，并提供了各自的下界，并与其他文献的上界进行了比较。

    Apr, 2021

  • 零阶非光滑非凸随机优化的最优维度依赖算法

    研究非光滑、非凸的 Lipschitz 目标函数在具有噪声函数评估的条件下生成 $(\delta,\epsilon)$- 稳定点的复杂性，提出的算法具有 $O (d\delta^{-1}\epsilon^{-3})$ 的复杂度和最优收敛速率。

    Jul, 2023

  • 统一的连续伪凸逼近框架

    该研究提出了一种连续伪凸逼近算法以有效计算一类可能非凸优化问题的稳态点，并针对未加区分的优化问题提出了一种新的一维搜索方法。

    Jun, 2015

  • 约束优化中逃离鞍点

    本研究研究了非凸优化中的鞍点问题，提出了一个通用的框架，该框架可在多项式时间内以失配系数 $\rho<1$ 的速度收敛到问题的二阶稳定点。此外，还将研究结果扩展到了随机情形下，以更好地适应实际问题。

    Sep, 2018

  • 非凸强凹极小 - 极大优化的复杂性

    本文研究非凸强凹（NC-SC）平滑极小值问题的近似稳定点的复杂度，在一般和平均平滑有限和设置中建立了非平凡的较低复杂度下界。我们提出了一种通用的加速方案，使用现有的基于梯度的方法来解决一系列的精心制作的强凸 - 强凹子问题，进而缩小了复杂度差距，尤其是在一般情况下，我们提出的算法的复杂度几乎与下界相当。

    Mar, 2021