【博士论文】基于冲量的加速优化算法

2021 年 11 月 29 日 专知

来自北京大学李欢的博士论文,入选2021年度“CCF优秀博士学位论文奖”初评名单!

https://www.ccf.org.cn/Focus/2021-11-22/750448.shtml


基于冲量的加速优化算法


优化在机器学习中扮演着重要的角色。作为理论上收敛速度最快的一阶优化算 法,加速梯度法在机器学习领域取得了广泛的应用。本文将研究经典加速算法在带 约束凸优化问题、随机凸优化问题、分布式凸优化问题和非凸优化问题上的应用。本文首先介绍加速技巧在交替方向乘子法(ADMM)中的应用,并提出了具有最优 非遍历意义收敛速度的加速ADMM算法。经典ADMM算法在求解非强凸非光滑问题 时具有遍历意义下O ( 1 K ) 收敛速度和非遍历意义下O ( 1 √ K ) 收敛速度。在稀疏和低秩学 习中,遍历意义中的取平均操作会破坏解的稀疏性和低秩性,因此在实际应用中我们 往往使用非遍历意义解。我们提出的加速ADMM具有非遍历意义下更快的O ( 1 K ) 收敛 速度。并且我们还证明了经典ADMM的非遍历意义下O ( 1 √ K ) 收敛速度是紧的,即经 典ADMM具有较慢的非遍历意义收敛速度是算法本身的特性,并非由于证明技巧不足 所致。另外,我们证明了当求解非强凸非光滑问题时,ADMM类型算法的复杂度下界 是O ( 1 K ) ,即任何ADMM类型算法都不可能比O ( 1 K ) 更快。

在大数据背景下,加速技巧不仅应用于传统优化,而且在随机优化和分布式优化 中也有广泛应用。本文研究了在随机优化领域经典的加速随机对偶坐标上升算法,并 对其原问题解的复杂度进行分析。该算法使用加速随机坐标下降法求解对偶问题,当 目标函数是强凸非光滑函数时,对偶问题解具有O ( 1 √ ϵ ) 的复杂度。在实际应用中,我 们需要使用的是原问题解,而非对偶问题解,因此我们需要度量原问题解的复杂度。已有结论显示,对于一般的带约束凸优化问题,当对偶问题解具有O ( 1 √ ϵ ) 的复杂度时, 原问题解只有O ( 1 ϵ ) 的复杂度。我们证明了如果对原问题解合适地进行加权平均,原 问题解具有和对偶问题解一样的O ( 1 √ ϵ ) 的复杂度。当将加速随机对偶坐标上升算法应 用到机器学习中经典的经验损失最小问题时,我们的收敛速度比当前已有结论提高 了O ( log 1 ϵ ) 因子。

除了随机优化领域,本文还研究了分布式优化领域的加速算法。我们首先对分布 式优化中经典的EXTRA算法重新分析,并给出了更快的O ( ( L µ + 1 1−σ2 (W) ) log 1 ϵ ) 的计算 复杂度和通信复杂度。然后我们使用Catalyst框架对EXTRA加速,得到了强凸情况下 复杂度为O (√ L µ(1−σ2 (W)) log L µ(1−σ2 (W)) log 1 ϵ ) 和非强凸情况下复杂度为O (√ L ϵ(1−σ2 (W)) log 1 ϵ ) 的加速EXTRA算法。除了对EXTRA进行扩展,我们还使用加速罚函数法对经典的分 布式加速梯度法进行解释,并给出了具有最优计算复杂度(强凸情况下 O (√ L µ log 1 ϵ ) 和非强凸情况下O (√ L ϵ ) )和接近最优通信复杂度(强凸情况下O (√ L µ(1−σ2 (W)) log2 1 ϵ ) 和 非强凸情况下O (√ L ϵ(1−σ2 (W)) log 1 ϵ ) )的分布式加速算法。与已有分布式算法相比,我们提出的加速EXTRA算法和加速罚函数法具有更低的计算复杂度,同时我们的通信复 杂度或者与当前最好算法一样,或者只比当前最好算法高 O ( log L µ(1−σ2 (W))) 或O ( log 1 ϵ ) 因子。最后,我们研究了加速算法在非凸低秩优化中的应用。我们首先分析了该问题中 目标函数的曲面性质,证明了当受限于某个特定凸集时,目标函数是受限制的局部强 凸函数。基于该性质,我们提出了交替约束加速梯度法并证明了该算法能够局部线性 收敛到最优解。相比于梯度下降法,我们的收敛速度对条件数具有最优的 √ L/µ的依赖 关系。另外,当初始值为任意值时,我们的算法能够全局收敛到梯度为0的点。



专知便捷查看

便捷下载,请关注专知公众号(点击上方蓝色专知关注)

  • 后台回复“冲量优化” 就可以获取【博士论文】基于冲量的加速优化算法》专知下载链接

专知,专业可信的人工智能知识分发 ,让认知协作更快更好!欢迎注册登录专知www.zhuanzhi.ai,获取5000+AI主题干货知识资料!


欢迎微信扫一扫加入专知人工智能知识星球群,获取最新AI专业干货知识教程资料和与专家交流咨询
点击“ 阅读原文 ”,了解使用 专知 ,查看获取5000+AI主题知识资源
登录查看更多
7

相关内容

在数学和计算机科学中,优化问题是从所有可行解中找到最佳解的问题。 根据变量是连续变量还是离散变量,优化问题可以分为两类。 具有离散变量的优化问题称为组合优化问题。 在组合优化问题中,我们正在从有限(或可能可数的无限)集中寻找对象,例如整数,置换或图。 连续变量的问题包括约束问题和多峰问题。
【博士论文】推荐系统多行为建模与隐私保护研究
专知会员服务
51+阅读 · 2021年11月27日
FPGA加速深度学习综述
专知会员服务
65+阅读 · 2021年11月13日
专知会员服务
36+阅读 · 2020年12月22日
最新《非凸优化理论》进展书册,79页pdf
专知会员服务
104+阅读 · 2020年12月18日
专知会员服务
69+阅读 · 2020年12月7日
专知会员服务
77+阅读 · 2020年6月20日
深度神经网络模型压缩与加速综述
专知会员服务
125+阅读 · 2019年10月12日
模型压缩 | 知识蒸馏经典解读
AINLP
9+阅读 · 2020年5月31日
硬件加速神经网络综述
计算机研究与发展
23+阅读 · 2019年2月1日
基于数据的分布式鲁棒优化算法及其应用【附PPT与视频资料】
人工智能前沿讲习班
25+阅读 · 2018年12月13日
基础 | 深度学习中的优化算法
黑龙江大学自然语言处理实验室
5+阅读 · 2018年5月11日
如何改进梯度下降算法
论智
9+阅读 · 2018年4月19日
绝对干货 | 随机梯度下降算法综述
菜鸟的机器学习
14+阅读 · 2017年10月30日
精品公开课 | 随机梯度下降算法综述
七月在线实验室
13+阅读 · 2017年7月11日
Arxiv
0+阅读 · 2022年2月7日
Arxiv
0+阅读 · 2022年2月4日
Arxiv
0+阅读 · 2022年2月4日
Arxiv
0+阅读 · 2022年2月3日
Arxiv
4+阅读 · 2019年4月17日
VIP会员
相关VIP内容
【博士论文】推荐系统多行为建模与隐私保护研究
专知会员服务
51+阅读 · 2021年11月27日
FPGA加速深度学习综述
专知会员服务
65+阅读 · 2021年11月13日
专知会员服务
36+阅读 · 2020年12月22日
最新《非凸优化理论》进展书册,79页pdf
专知会员服务
104+阅读 · 2020年12月18日
专知会员服务
69+阅读 · 2020年12月7日
专知会员服务
77+阅读 · 2020年6月20日
深度神经网络模型压缩与加速综述
专知会员服务
125+阅读 · 2019年10月12日
相关资讯
模型压缩 | 知识蒸馏经典解读
AINLP
9+阅读 · 2020年5月31日
硬件加速神经网络综述
计算机研究与发展
23+阅读 · 2019年2月1日
基于数据的分布式鲁棒优化算法及其应用【附PPT与视频资料】
人工智能前沿讲习班
25+阅读 · 2018年12月13日
基础 | 深度学习中的优化算法
黑龙江大学自然语言处理实验室
5+阅读 · 2018年5月11日
如何改进梯度下降算法
论智
9+阅读 · 2018年4月19日
绝对干货 | 随机梯度下降算法综述
菜鸟的机器学习
14+阅读 · 2017年10月30日
精品公开课 | 随机梯度下降算法综述
七月在线实验室
13+阅读 · 2017年7月11日
Top
微信扫码咨询专知VIP会员