基于牛顿法的非凸优化算法:快速躲避鞍点
本文根据统计物理学、随机矩阵理论、神经网络理论和实证证据,证明高维问题中鞍点而非局部极小值点是造成误差函数最小值难以求解的主要原因,因此,提出了一种新的二阶优化方法 —— 无鞍牛顿法,用以快速逃脱高维鞍点并优化深度或递归神经网络。
Jun, 2014
该研究论文旨在提出一种新的算法 - 无鞍牛顿法,通过对梯度下降和拟牛顿方法的比较,研究表明高维空间中的鞍点可能是局部最小值的主要原因,而不是通常认为的局部最小值过多。该算法能够快速避免高维鞍点,特别是在深度神经网络的训练中具有优势。
May, 2014
本文提出了一种使用高阶导数的算法,能够逃离高维复杂的鞍点结构,并保证能够收敛到三阶局部最优解,是现有技术的两倍,同时也证明了进一步寻找四阶局部最优解是 NP-hard 的。
Feb, 2016
本文研究表明惯性梯度下降法可以在较短的迭代次数内收敛于二阶稳定点,收敛速率与梯度下降到一阶稳定点的收敛速率匹配,当所有鞍点都是非退化的时,所有的二阶稳定点都是局部最小值,该结果表明惯性梯度下降法几乎可以在无成本的情况下脱离鞍点,并可直接应用于许多机器学习应用中,包括深度学习。
Mar, 2017
本文介绍了一种通用框架,该框架在最小化 Hessian 基础计算的同时,能够收敛到二阶临界点,侧重于解决非凸优化中的关键问题:鞍点。经实证,该策略具有较好的实际性能。
Sep, 2017
本文提供了一种新的噪声加入技术的视角,即将噪声添加到一阶信息中可以帮助从 Hessian 矩阵中提取负曲率,并通过分析一个简单的一阶过程提供了此视角的正式推理,然后提出了一种基于此技术和现有算法的一阶随机算法,实现了以几乎线性的时间复杂度(与问题的维度有关)找到接近于二阶稳定点的解的目标,从而在随机非凸优化上取得了最佳理论结果,甚至与凭借二阶信息的现有随机算法相媲美。
Nov, 2017
本研究研究了非凸优化中的鞍点问题,提出了一个通用的框架,该框架可在多项式时间内以失配系数 $\rho<1$ 的速度收敛到问题的二阶稳定点。此外,还将研究结果扩展到了随机情形下,以更好地适应实际问题。
Sep, 2018
通过选择合适的参数和注入噪音,我们分析了 Normalized Gradient Descent(NGD)这个非凸优化启发式方法,表明此方法能够逃避鞍点,并且证明了 NGD 收敛到局部最小值,而且 NGD 的收敛速度比 Ge 等人 2015 年提出的最快的一阶算法更快,我们将这个方法应用到在线张量分解问题上,并证明了在这个问题中,鞍点逃逸导致收敛到全局最小值。
Nov, 2016
本文研究了加速梯度方法在光滑非凸函数上的行为,提出了一类 Nesterov 型加速方法,并通过显式和隐式分析证明了其能够避免滑点并收敛于局部最小值。
Jul, 2023
本研究针对非凸函数的优化问题,通过分析其严格鞍点特性,提出了一种可有效优化的解法 —— 随机梯度下降法,并给出了其多项式迭代次数的局部最小值收敛保证以及应用于正交张量分解问题上的全局收敛保证。
Mar, 2015