无梯度的零阶方法高效避免鞍点
本文提出了针对非凸和凸优化的零阶随机逼近算法,并关注解决约束优化、高维设置和避免鞍点等问题。我们探索了结构稀疏假设的优点,并提出了一种使用零阶信息的被截断随机梯度算法和一种避免鞍点的算法,并讨论了它们的收敛率。
Sep, 2018
本研究表明,几乎所有初始化的一阶方法都可以避免鞍点问题,并且这种算法可以通过动态系统视角来研究,通过合适实例化的 Stable Manifold Theorem 进行全局稳定性分析。因此,除了初始化外,无需访问二阶导数信息或随机性即可证明避免鞍点。
Oct, 2017
本文研究表明惯性梯度下降法可以在较短的迭代次数内收敛于二阶稳定点,收敛速率与梯度下降到一阶稳定点的收敛速率匹配,当所有鞍点都是非退化的时,所有的二阶稳定点都是局部最小值,该结果表明惯性梯度下降法几乎可以在无成本的情况下脱离鞍点,并可直接应用于许多机器学习应用中,包括深度学习。
Mar, 2017
本文提供了一种新的噪声加入技术的视角,即将噪声添加到一阶信息中可以帮助从 Hessian 矩阵中提取负曲率,并通过分析一个简单的一阶过程提供了此视角的正式推理,然后提出了一种基于此技术和现有算法的一阶随机算法,实现了以几乎线性的时间复杂度(与问题的维度有关)找到接近于二阶稳定点的解的目标,从而在随机非凸优化上取得了最佳理论结果,甚至与凭借二阶信息的现有随机算法相媲美。
Nov, 2017
本文介绍了一种通用框架,该框架在最小化 Hessian 基础计算的同时,能够收敛到二阶临界点,侧重于解决非凸优化中的关键问题:鞍点。经实证,该策略具有较好的实际性能。
Sep, 2017
本文将通过对随机梯度下降进行深入分析,证明当目标函数满足梯度 Lipschitz、Hessian-Lipschitz 和发散噪声假设时,SGD 能够在 O(ε^ -3.5)次随机梯度计算中逃离鞍点并找到(ε,O(ε^ 0.5))- 近似二阶稳定点,从而推翻了 SGD 至少需要 O(ε^ - 4)的经典信念。此类 SGD 速率与大多数采用其他技术的加速非凸随机优化算法的速率相匹配,如 Nesterov 的动量加速,负曲率搜索,以及二次和三次正则化技巧。本文的新型分析为非凸 SGD 提供了新的见解,并可潜在地推广到广泛的随机优化算法类。
Feb, 2019
本文研究了梯度下降算法在非凸优化问题中的性能保证,发现梯度噪声对逃脱鞍点和到达二阶稳定点的效率起到了关键作用,提出了一个基于均方方法的替代方案来保证梯度噪声的相对方差较小就足以确保逃脱鞍点,而不需要注入其他噪声或采用全局分散噪声假设。
Aug, 2019
本文提出了一种使用高阶导数的算法,能够逃离高维复杂的鞍点结构,并保证能够收敛到三阶局部最优解,是现有技术的两倍,同时也证明了进一步寻找四阶局部最优解是 NP-hard 的。
Feb, 2016
本文探讨了利用仅包含部分和嘈杂信息的凸函数最小化问题,特别着重于高度平滑问题的凸优化问题,包括逻辑回归等。研究表明,相对于基于梯度的算法,高阶平滑性可用于改善估计速率,并精确地依赖于平滑度的程度,同时提出了此类算法可行性的上限。最后,作者还在在线优化设置中取得了类似的结果。
May, 2016
研究非光滑、非凸的 Lipschitz 目标函数在具有噪声函数评估的条件下生成 $(\delta,\epsilon)$- 稳定点的复杂性,提出的算法具有 $O (d\delta^{-1}\epsilon^{-3})$ 的复杂度和最优收敛速率。
Jul, 2023