Jun, 2020

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

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

    该研究论文旨在提出一种新的算法-无鞍牛顿法，通过对梯度下降和拟牛顿方法的比较，研究表明高维空间中的鞍点可能是局部最小值的主要原因，而不是通常认为的局部最小值过多。该算法能够快速避免高维鞍点，特别是在深度神经网络的训练中具有优势。

    May, 2014

  • 高维非凸优化中鞍点问题的识别与攻克

    本文根据统计物理学、随机矩阵理论、神经网络理论和实证证据，证明高维问题中鞍点而非局部极小值点是造成误差函数最小值难以求解的主要原因，因此，提出了一种新的二阶优化方法——无鞍牛顿法，用以快速逃脱高维鞍点并优化深度或递归神经网络。

    Jun, 2014

  • 非凸优化中逃离高阶鞍点的高效方法

    本文提出了一种使用高阶导数的算法，能够逃离高维复杂的鞍点结构，并保证能够收敛到三阶局部最优解，是现有技术的两倍，同时也证明了进一步寻找四阶局部最优解是NP-hard的。

    Feb, 2016

  • 局部鞍点优化：一种曲率利用方法

    本文研究了基于梯度下降的优化方法在处理鞍点问题时的局限性，提出一种新的优化方法——利用曲率信息跳出非最优静态点，证明了采用曲率信息的梯度方法和Adagrad等方法都能够跳出非最优静态点，并在常见鞍点问题上提供了实证结果。

    May, 2018

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

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

    Oct, 2018

  • 使用迭代一阶方法解决一类非凸极小极大博弈

    利用多阶梯度下降上升算法解决机器学习中非凸场景下最小最大鞍点问题，给出了基于 Polyak-Lojasiewicz 条件的算法和 Concave 最大玩家目标函数的算法，并在 Fashion-MNIST 数据集上进行公平分类实验。

    Feb, 2019

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

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

    Jun, 2020

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

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

    Oct, 2020

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

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

    Jul, 2022

  • 最小-最大问题的统计力学

    这项研究针对最小-最大优化问题的理解难题，提出了一种统计力学形式以分析高维极限下的平衡值。研究表明，在双线性最小-最大博弈和简单GAN中，训练数据量与泛化误差之间的关系，为有效学习提供了假数据与真实数据的最优比例，从而为基于最小-最大问题的多种机器学习方法的理论分析奠定基础。

    Sep, 2024