本文提出了一种使用高阶导数的算法,能够逃离高维复杂的鞍点结构,并保证能够收敛到三阶局部最优解,是现有技术的两倍,同时也证明了进一步寻找四阶局部最优解是 NP-hard 的。
Feb, 2016
本研究研究了非凸优化中的鞍点问题,提出了一个通用的框架,该框架可在多项式时间内以失配系数 $\rho<1$ 的速度收敛到问题的二阶稳定点。此外,还将研究结果扩展到了随机情形下,以更好地适应实际问题。
Sep, 2018
本文提供了一种新的噪声加入技术的视角,即将噪声添加到一阶信息中可以帮助从 Hessian 矩阵中提取负曲率,并通过分析一个简单的一阶过程提供了此视角的正式推理,然后提出了一种基于此技术和现有算法的一阶随机算法,实现了以几乎线性的时间复杂度(与问题的维度有关)找到接近于二阶稳定点的解的目标,从而在随机非凸优化上取得了最佳理论结果,甚至与凭借二阶信息的现有随机算法相媲美。
Nov, 2017
本文研究表明惯性梯度下降法可以在较短的迭代次数内收敛于二阶稳定点,收敛速率与梯度下降到一阶稳定点的收敛速率匹配,当所有鞍点都是非退化的时,所有的二阶稳定点都是局部最小值,该结果表明惯性梯度下降法几乎可以在无成本的情况下脱离鞍点,并可直接应用于许多机器学习应用中,包括深度学习。
Mar, 2017
本文介绍一种修改了牛顿法更新方式的二阶方法,通过替换海森矩阵的负特征值为绝对值,并使用其截断版本来考虑目标的曲率,以获得比随机梯度下降更快的局部最小值收敛速度。
Jul, 2017
本研究表明,几乎所有初始化的一阶方法都可以避免鞍点问题,并且这种算法可以通过动态系统视角来研究,通过合适实例化的 Stable Manifold Theorem 进行全局稳定性分析。因此,除了初始化外,无需访问二阶导数信息或随机性即可证明避免鞍点。
Oct, 2017
本文根据统计物理学、随机矩阵理论、神经网络理论和实证证据,证明高维问题中鞍点而非局部极小值点是造成误差函数最小值难以求解的主要原因,因此,提出了一种新的二阶优化方法 —— 无鞍牛顿法,用以快速逃脱高维鞍点并优化深度或递归神经网络。
Jun, 2014
本文研究了非凸优化中的无导数算法,利用有限差分器进行梯度逼近,最终提出了一种使用嘈杂的零阶方法来避免鞍点的算法,并在收敛速度上达到了与精确梯度接近的性能。
Oct, 2019
该研究论文旨在提出一种新的算法 - 无鞍牛顿法,通过对梯度下降和拟牛顿方法的比较,研究表明高维空间中的鞍点可能是局部最小值的主要原因,而不是通常认为的局部最小值过多。该算法能够快速避免高维鞍点,特别是在深度神经网络的训练中具有优势。
May, 2014
本文将通过对随机梯度下降进行深入分析,证明当目标函数满足梯度 Lipschitz、Hessian-Lipschitz 和发散噪声假设时,SGD 能够在 O(ε^ -3.5)次随机梯度计算中逃离鞍点并找到(ε,O(ε^ 0.5))- 近似二阶稳定点,从而推翻了 SGD 至少需要 O(ε^ - 4)的经典信念。此类 SGD 速率与大多数采用其他技术的加速非凸随机优化算法的速率相匹配,如 Nesterov 的动量加速,负曲率搜索,以及二次和三次正则化技巧。本文的新型分析为非凸 SGD 提供了新的见解,并可潜在地推广到广泛的随机优化算法类。
Feb, 2019