Jun, 2020

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

PDF
TL;DR本文研究了最小 - 最大优化算法在非凸 /non-concave 问题中的表现，发现其极限点包含在共同的平均场系统的 ICT 集合中，其吸引子与算法相关，但存在不包含问题静止点的虚假吸引子，这可能导致算法收敛失败。
min-max optimizationnon-convex/non-concave problemsmean-field systemattractorsconvergence failures
发现论文，激发创造
  • 结构化非凸 - 非凹二次规划的高效优化方法

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

    Oct, 2020

  • 弱凸凹性最小最大优化：可证明算法及其在机器学习中的应用

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

    Oct, 2018

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

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

    Jul, 2022

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

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

    Sep, 2020

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

    本文概述了一种重要的 min-max 问题子类的最新进展，其中最小化和最大化问题可以是非凸和 / 或非凹的，包括诸如 fair beamforming、 training generative adversarial networks (GANs)， robust machine learning 等广泛应用，强调了该问题的重要性并讨论了该问题的理论挑战，同时提供了解决非凸 min-max 问题的最新理论和算法进展的选定回顾，并指出了未来的研究方向和待解决问题。

    Jun, 2020

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

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

    Oct, 2018

  • 随机梯度下降法在极小极大问题中的稳定性和泛化性

    通过算法稳定性的视角，对凸凹和非凸非凹情形下的随机梯度方法在极小极大问题中的泛化能力进行了全面的分析，建立了稳定性与泛化能力之间的定量联系。在凸凹情形下，稳定性分析表明了随机梯度下降算法对于平滑和非平滑的极小极大问题皆可达到最优的泛化界。我们还确定了泛函弱凸弱凹和梯度占主导地位的问题的泛化界。

    May, 2021

  • 极大极小优化的最终迭代收敛速率

    该研究论文阐述了针对非凸函数最优化问题中的后向迭代收敛的挑战性，介绍了哈密顿梯度下降算法以及协作优化算法，并证明了这些算法在某些情况下表现出线性收敛性。

    Jun, 2019

  • 交替近端梯度步骤用于（随机）非凸 - 凹极小极大问题

    本文针对非凸凹的情况，在最小极大问题中应用交替梯度下降方法找到临界点并证明了一种新的全局收敛速率。

    Jul, 2020

  • 非凸集合交替极小化和交替下降

    本文研究了应用于两个变量上且每个变量可被限制在潜在非凸约束集上的损失函数的交替最小化方法，该方法在高维统计学和信号处理中常常出现。作者提出了本地凹率系数来度量非凸集合的凹性，进一步揭示了交替和非交替方法之间的重要区别。此外，作者还提出了不精确算法的一组足够条件，以确保其快速收敛，并通过多任务回归等例子进行了验证。

    Sep, 2017