Jun, 2020

非凸极值优化：应用、挑战和最新的理论进展

PDF
TL;DR本文概述了一种重要的 min-max 问题子类的最新进展，其中最小化和最大化问题可以是非凸和 / 或非凹的，包括诸如 fair beamforming、 training generative adversarial networks (GANs)， robust machine learning 等广泛应用，强调了该问题的重要性并讨论了该问题的理论挑战，同时提供了解决非凸 min-max 问题的最新理论和算法进展的选定回顾，并指出了未来的研究方向和待解决问题。
min-max optimization problemsaddle point problemnon-convex min-max problemsrobust machine learninggenerative adversarial networks
发现论文，激发创造
  • 弱凸凹性最小最大优化：可证明算法及其在机器学习中的应用

    本文研究了一类非凸的最小值最大值问题，其中目标函数在最小化变量上是弱凸的，在最大化变量上是凸的。针对不同的光滑和不光滑的实例，我们提出了近端引导随机次梯度方法和近端引导随机方差减少方法。同时，我们分析了所提出方法在找到最小值和最大值对应的几乎稳定点的时间复杂性。

    Oct, 2018

  • 一类非凸极小极大问题的混合块逐次逼近算法及其应用

    本文提出了名为 Hybrid Block Successive Approximation 的简单算法来解决一类分块非凸极小极大问题，其中最小化问题由多个块组成，而最大化问题是凸的。通过使用正则化和惩罚序列，该算法稳定收敛于一些合理定义的一阶稳定解，并在几个不同的问题上进行了数值测试，包括鲁棒学习问题、非凸极小效用最大化问题以及干扰通道中出现的某些无线干扰问题。

    Feb, 2019

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

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

    Sep, 2020

  • 具有耦合线性约束的极小化问题：计算复杂性，对偶性和解决方法

    本研究探讨了一类特殊的极小极大问题，其中有线性约束同时涉及到极小化和极大化的决策变量，研究发现该问题具有挑战性，违反了经典的最大最小不等式，是 NP 难问题，我们提出了一种对偶理论，并分析了其中杠杆率为零的条件，得出一类基于对偶问题的稳态解并评估了在网络流问题中的实际应用。

    Oct, 2021

  • 结构化非凸 - 非凹二次规划的高效优化方法

    通过提出一种新的结构化非凸 - 非凹 min-max 优化问题类，引入了一个泛化的外推方法，该方法证明收敛到一个稳定点。这种算法不仅适用于欧几里得空间，还适用于一般的 l p-norm 有限维实向量空间，同时对其在随机 oracle 条件下的稳定性和样本复杂度提供了边界。

    Oct, 2020

  • 无梯度的极小极大优化：收敛性和在对抗机器学习中的应用

    本文研究了黑盒环境下有约束的鲁棒（最小 - 最大）优化问题，并采用了零阶梯度估计器与交替投影随机梯度下降 - 上升方法的优化框架，称为 ZO-Min-Max，旨在探索在对抗机器学习中的黑盒最小 - 最大优化与黑盒逃避和污染攻击之间的可能联系。实证评估表明了该方法的有效性和可扩展性。

    Sep, 2019

  • 弱凸弱凹极大极小问题的一阶收敛理论

    本研究考虑了一类非凸非凹极值问题的一阶收敛理论和算法，它在机器学习中有广泛的应用，包括训练生成式对抗网络（GAN）。我们提出了一种算法框架，通过解决一系列强单调变分不等式，证明了所提出的方法的一阶收敛性和收敛率，并在 GAN 的训练中证明了所提出的算法的有效性。

    Oct, 2018

  • 一类非凸非凹极小极大问题的固定时间收敛

    本文提出了一种基于固定时间的收敛鞍点动力系统，用于在标准凸凹性假设的放松下解决极小极大问题。

    Jul, 2022

  • 极值优化算法的局限性：收敛于虚假非关键集合

    本文研究了最小 - 最大优化算法在非凸 /non-concave 问题中的表现，发现其极限点包含在共同的平均场系统的 ICT 集合中，其吸引子与算法相关，但存在不包含问题静止点的虚假吸引子，这可能导致算法收敛失败。

    Jun, 2020

  • 非凸问题何时不再可怕？

    通过二阶信赖域算法，我们可以高效地找到满足所有局部极小值点也是全局极小值点并且任何一点的方向曲率为负的非凸优化问题的全局极小解。

    Oct, 2015