高维非凸优化中鞍点避开问题的算法研究

论文摘要

人工智能的快速发展,离不开背后的数学基础研究。机器学习是人工智能研究的重点,机器学习可以归结为对数据集拟合的优化问题,该问题具有高维、非凸的特点。一方面,在高维情形下,计算目标函数的二阶导数Hessian矩阵将变得困难;另一方面,在非凸情形下,鞍点给算法以局部极小的假象,其数量也会随维数的增加呈指数式上升。因此,如何快速地识别并避开鞍点,成为当前高维非凸优化领域研究的热点。随机梯度下降（SGD）是机器学习优化领域的一个基础性算法,本文中讨论的算法都是在该算法基础上的改进。扰动梯度下降（PGD）算法对鞍点附近迭代点的梯度加入扰动,使得迭代可以避开鞍点。将SGD和PGD算法融合,在SGD算法的迭代格式中加入梯度扰动项,就是本文中的扰动随机梯度下降（PSGD）算法,该算法的迭代复杂度为O(ε-4d),具有快速迭代和避开鞍点的优点。立方正则化（CR）算法可以解决牛顿法中Hessian矩阵退化为奇异矩阵,以及收敛至鞍点的问题,但该算法需要计算Hessian矩阵。将CR与SGD算法融合,使用随机梯度和随机Hessian来求解CR算法的子问题,就是本文中的随机立方正则化（SCR）算法。该算法无需显式地计算Hessian矩阵,只需计算相应的Hessian-vector积,算法的迭代复杂度为O(ε-3.5)。开源数据集a9a上的逻辑回归模型是一个高维非凸优化问题,利用上述算法对该问题进行数值实验,由实验结果知:SGD算法可能会卡在鞍点处无法继续下降;PSGD算法因为使用了梯度扰动,可以避开鞍点继续下降;相比前两个算法,SCR算法借助了Hessian矩阵信息（通过Hessian-vector积获取）,所以能更早地识别并避开鞍点,因此需要更少的迭代次数,有更快的收敛速度。

论文目录

文章来源

类型: 硕士论文

作者: 陶耀

导师: 黄爱群

关键词: 非凸优化问题,鞍点,随机梯度下降算法,立方正则化方法

来源: 华中科技大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 华中科技大学

分类号: O224

DOI: 10.27157/d.cnki.ghzku.2019.000820

总页数: 63

文件大小: 1714K

下载量: 21

相关论文文献

• [1].求解非对称鞍点问题的广义修正的带位移分裂方法[J]. 云南大学学报(自然科学版) 2017(01)
• [2].鞍点问题基于半增广的松弛分裂预条件子[J]. 大学数学 2017(02)
• [3].求鞍点问题的新的原始-对偶算法[J]. 数值计算与计算机应用 2016(03)
• [4].解非对称鞍点问题的广义交替分裂预处理子的一个注记（英文）[J]. 浙江大学学报(理学版) 2017(02)
• [5].齐四次系统鞍点量公式[J]. 大连交通大学学报 2010(06)
• [6].缺参数a_(23),b_(32)的齐五次系统的前四阶鞍点量公式[J]. 大连交通大学学报 2008(02)
• [7].奇异鞍点问题的一类迭代算法的半收敛性[J]. 浙江科技学院学报 2016(03)
• [8].一类奇异鞍点问题的特征值界[J]. 安徽大学学报(自然科学版) 2012(02)
• [9].求解马鞍点的两种算法及性能分析[J]. 电脑知识与技术 2009(15)
• [10].一类有高阶鞍点的五次系统的全局结构[J]. 德州学院学报 2008(04)
• [11].求解鞍点问题的一种新的结构算法[J]. 数值计算与计算机应用 2009(02)
• [12].鞍点逼近理论在非中心χ~2分布中的应用[J]. 佳木斯大学学报(自然科学版) 2009(04)
• [13].非凸优化问题的局部鞍点和凸化[J]. 重庆工学院学报(自然科学版) 2008(06)
• [14].(h,φ)多目标规划的鞍点最优性条件[J]. 南昌大学学报(理科版) 2008(03)
• [15].一种构造指数分布族下鞍点逼近型置信区间的方法[J]. 统计与决策 2015(14)
• [16].高维空间中连接双曲鞍点的异宿环的稳定性[J]. 中国科学:数学 2014(12)
• [17].一种求解非线性鞍点问题的交替投影方法[J]. 应用数学学报 2010(05)
• [18].鞍点问题的向后误差分析[J]. 上海理工大学学报 2010(05)
• [19].鞍点问题可行解序列的有限终止性[J]. 山东理工大学学报(自然科学版) 2016(03)
• [20].一个重要统计量的鞍点逼近[J]. 数学进展 2015(05)
• [21].鞍点问题迭代算法的进一步研究[J]. 阜阳师范学院学报(自然科学版) 2012(01)
• [22].求解大型稀疏鞍点问题的对称超松弛方法[J]. 电脑知识与技术 2010(21)
• [23].机械结构可靠性灵敏度分析的鞍点估计方法[J]. 山东建筑大学学报 2013(05)
• [24].含参数形式的鞍点问题SOR-LIKE求解方法[J]. 河南科学 2014(07)
• [25].锥不变凸映射的向量鞍点[J]. 江西师范大学学报(自然科学版) 2010(04)
• [26].集值优化问题超鞍点的最优性条件[J]. 吉林大学学报(理学版) 2008(05)
• [27].速度追踪问题产生的鞍点系统的新的分裂迭代技术[J]. 计算数学 2016(04)
• [28].一种求解奇异鞍点问题新的改进SSOR方法[J]. 温州大学学报(自然科学版) 2016(02)
• [29].一类关于Uzawa-AOR方法的鞍点问题[J]. 科教文汇(上旬刊) 2015(08)
• [30].齐次规划问题的KKT点和局部鞍点[J]. 西华师范大学学报(自然科学版) 2008(04)

标签：非凸优化问题论文;  鞍点论文;  随机梯度下降算法论文;  立方正则化方法论文;