非凸优化(nonconvex optimization)是优化理论的核心研究领域之一,因为许多前沿机器学习问题都具有非凸的损失函数,包括深度神经网络、主成分分析、张量分解等。在最坏的情况下,找到非凸函数的全局最小值属于 NP-hard 问题。不过最近的许多实证与理论工作都表明,对于大量有着广泛应用的机器学习问题,所有局部最小值几乎都与全局最小值相等。因此,许多理论工作专注于寻找局部最优解而不是全局最优解。在这些工作中,鞍点成为了设计算法的主要障碍,因为高维的非凸目标函数可能含有大量鞍点,且它们往往具有远大于全局最优解的函数值。

因此,逃离鞍点是非凸优化理论中最重要的问题之一。具体来说,对于二阶可导的 维函数 ,我们的目标是找到一个 近似的局部最优解。近期的实证研究表明,现实世界中复杂的机器学习问题往往可以被简单的算法有效解决,这些算法在实践中也可以更容易地实现与维护。与之相反,具有嵌套循环结构的优化算法在问题规模增长时往往具有较大的开销,或存在调参不便、数值稳定性较弱等问题,使它们较难找到实际应用。出于这一考量,现有的逃离鞍点的研究多聚焦于开发基于梯度下降的,具有单循环结构的简单优化算法。在本文之前,最先进的算法为 Jin 等人提出的扰动加速梯度下降算法(perturbed accelerated gradient descent, PAGD),它可以在 次循环内找到一个 近似的局部最优解。

成为VIP会员查看完整内容
23

相关内容

专知会员服务
36+阅读 · 2021年5月30日
最新《非凸优化理论》进展书册,79页pdf
专知会员服务
104+阅读 · 2020年12月18日
专知会员服务
18+阅读 · 2020年12月9日
专知会员服务
69+阅读 · 2020年12月7日
【Google】梯度下降,48页ppt
专知会员服务
78+阅读 · 2020年12月5日
【NeurIPS2020-北大】非凸优化裁剪算法的改进分析
专知会员服务
27+阅读 · 2020年10月11日
【ICML2020】机器学习无参数在线优化,294页ppt
专知会员服务
53+阅读 · 2020年8月1日
【KDD2020】最小方差采样用于图神经网络的快速训练
专知会员服务
27+阅读 · 2020年7月13日
八篇NeurIPS 2019【图神经网络(GNN)】相关论文
专知会员服务
43+阅读 · 2020年1月10日
【博士论文】基于冲量的加速优化算法
专知
7+阅读 · 2021年11月29日
梯度下降算法的工作原理
极市平台
6+阅读 · 2020年11月2日
【优博微展2019】李志泽:简单快速的机器学习优化方法
清华大学研究生教育
13+阅读 · 2019年10月8日
从动力学角度看优化算法:自适应学习率算法
PaperWeekly
8+阅读 · 2018年12月27日
如何改进梯度下降算法
论智
9+阅读 · 2018年4月19日
算法优化|梯度下降和随机梯度下降 — 从0开始
全球人工智能
6+阅读 · 2017年12月25日
机器学习(18)之支持向量机原理(三)线性不可分支持向量机与核函数
机器学习算法与Python学习
3+阅读 · 2017年9月23日
Arxiv
0+阅读 · 2022年2月7日
Arxiv
0+阅读 · 2022年2月7日
Arxiv
0+阅读 · 2022年2月5日
Optimality and Stability in Non-Convex Smooth Games
Arxiv
0+阅读 · 2022年2月3日
VIP会员
相关VIP内容
专知会员服务
36+阅读 · 2021年5月30日
最新《非凸优化理论》进展书册,79页pdf
专知会员服务
104+阅读 · 2020年12月18日
专知会员服务
18+阅读 · 2020年12月9日
专知会员服务
69+阅读 · 2020年12月7日
【Google】梯度下降,48页ppt
专知会员服务
78+阅读 · 2020年12月5日
【NeurIPS2020-北大】非凸优化裁剪算法的改进分析
专知会员服务
27+阅读 · 2020年10月11日
【ICML2020】机器学习无参数在线优化,294页ppt
专知会员服务
53+阅读 · 2020年8月1日
【KDD2020】最小方差采样用于图神经网络的快速训练
专知会员服务
27+阅读 · 2020年7月13日
八篇NeurIPS 2019【图神经网络(GNN)】相关论文
专知会员服务
43+阅读 · 2020年1月10日
相关资讯
【博士论文】基于冲量的加速优化算法
专知
7+阅读 · 2021年11月29日
梯度下降算法的工作原理
极市平台
6+阅读 · 2020年11月2日
【优博微展2019】李志泽:简单快速的机器学习优化方法
清华大学研究生教育
13+阅读 · 2019年10月8日
从动力学角度看优化算法:自适应学习率算法
PaperWeekly
8+阅读 · 2018年12月27日
如何改进梯度下降算法
论智
9+阅读 · 2018年4月19日
算法优化|梯度下降和随机梯度下降 — 从0开始
全球人工智能
6+阅读 · 2017年12月25日
机器学习(18)之支持向量机原理(三)线性不可分支持向量机与核函数
机器学习算法与Python学习
3+阅读 · 2017年9月23日
微信扫码咨询专知VIP会员