机器学习中的加速一阶优化算法

1、院士推荐。本书由Michael I. Jordan院士、徐宗本院士、罗智泉院士联袂推荐。

2、作者知名。本书由机器学习和计算机视觉领域的国际知名专家，北京大学信息科学技术学院机器感知与智能教育部重点实验室教授林宙辰领衔撰写。

3、内容前沿。概述了机器学习中加速一阶优化算法的新进展，全面介绍了各种情形下的加速一阶优化算法。

4、主流热门。以当前机器学习会议的热门话题加速算法为主线，涵盖机器学习中常用的凸优化、非凸优化，以及随机优化和分布式优化。

机器学习是关于从数据中建立预测或描述模型，以提升机器解决问题能力的学科。在建立模型后，需要采用适当的优化算法来求解模型的参数，因此优化算法是机器学习的重要组成部分。但是传统的优化算法并不完全适用于机器学习，因为通常来说机器学习模型的参数维度很高或涉及的样本数巨大，这使得一阶优化算法在机器学习中占据主流地位。

本书概述了机器学习中加速一阶优化算法的新进展。书中全面介绍了各种情形下的加速一阶优化算法，包括确定性和随机性的算法、同步和异步的算法，以求解带约束的问题和无约束的问题、凸问题和非凸问题，对算法思想进行了深入的解读，并对其收敛速度提供了详细的证明。

本书面向机器学习和优化领域的研究人员，包括人工智能、信号处理及应用数学特别是计算数学专业高年级本科生、研究生，以及从事人工智能、信号处理领域产品研发的工程师。

林宙辰
机器学习和计算机视觉领域的国际知名专家，目前是北京大学信息科学技术学院机器感知与智能教育部重点实验室教授。他曾多次担任多个业内顶级会议的领域主席，包括CVPR、ICCV、ICML、NIPS/NeurIPS、AAAI、 IJCAI和ICLR。他曾任IEEE Transactions on Pattern Analysis and Machine Intelligence编委，现任International Journal of Computer Vision和Optimization Methods and Software的编委。他是IAPR和IEEE的会士。

李 欢
于2019 年在北京大学获得博士学位，专业为机器学习。目前是南开大学人工智能学院助理研究员，研究兴趣包括优化和机器学习。

方 聪
于2019 年在北京大学获得博士学位，专业为机器学习。目前是北京大学助理教授，研究兴趣包括机器学习和优化。

　　★优化算法一直是推动近年来机器学习发展的引擎。在机器学习领域中，基于梯度的方法比高阶优化方法更可取，并且考虑到计算完全的梯度有可能不可行，因此随机梯度法是机器学习领域优化算法的代名词。这些限制与解决非凸优化问题、控制随机采样引起的方差以及开发在分布式平台上运行的算法的需求结合在一起，对优化提出了一系列新的挑战。林宙辰、李欢和方聪所著的这本书是该新兴领域的一本完整的专著。该书详细介绍了基于梯度的算法，重点关注加速的概念。任何希望在机器学习领域工作的研究人员都应该对统计和优化领域有基本的了解，这本书正是了解基本的优化算法并开始机器学习研究的出发点。
　　——Michael I.Jordan，美国科学院、美国工程院、美国艺术与科学院三院院士，加州大学伯克利分校电气工程与计算机科学系和统计系教授
　　

　　★优化是机器学习的核心主题之一。在得益于纯粹优化领域的进步的同时，机器学习中的优化也形成了自己的特点。一个显著的现象是，一阶算法或多或少地成了机器学习的主流优化方法。这本由林宙辰、李欢和方聪合著的专著及时满足了对加速一阶算法进行快速学习的需求。该书首先概述了加速一阶算法的发展历程，尽管略显粗略，但提供的信息极为丰富，然后，介绍了针对不同类别问题的代表性工作，并提供了详细的证明，这些证明极大地方便了读者对基本思想的理解和对基本技术的掌握。毫无疑问，这本书对于那些想要学习新的机器学习优化算法的人来说是至关重要的参考书。
　　——徐宗本，中国科学院院士，西安交通大学数学与统计学院教授
　　

　　★一阶优化方法一直是求解面向大数据的机器学习、信号处理和人工智能问题的主要工具。一阶优化方法虽然概念上很简单，但需要仔细分析并充分了解才能有效地进行部署。该研究专著对一阶优化方法的算法方面进行了出色的介绍，重点是算法设计和收敛性分析。它深入讨论了加速、非凸、约束和异步实现的问题。专著中涉及的主题和给出的结果非常及时，并且与机器学习、信号处理、人工智能领域的研究人员和从业人员都息息相关。对于对机器学习的优化方面感兴趣的每个人来说，它都应该是一本重要的参考书。
　　——罗智泉，加拿大皇家科学院院士，香港中文大学（深圳）副校长

推荐序一
推荐序二
推荐序三
中文版前言
英文版前言
致谢
作者介绍
符号表
第 1 章 绪论 1
11 机器学习中的优化问题举例 1
111 正则化的经验损失模型 1
112 矩阵填充及低秩学习模型 3
12 一阶优化算法 3
13 加速算法中的代表性工作综述 4
14 关于本书 7
参考文献 7
第 2 章 无约束凸优化中的加速算法 14
21 梯度下降法 14
22 重球法 15
23 加速梯度法 16
24 求解复合凸优化问题的加速梯度法 23
241 第一种 Nesterov 加速邻近梯度法 23
242 第二种 Nesterov 加速邻近梯度法 27
243 第三种 Nesterov 加速邻近梯度法 31
25 非精确加速邻近梯度法 33
251 非精确加速梯度法 42
252 非精确加速邻近点法 42
26 重启策略 43
27 平滑策略 45
28 高阶加速方法 50
29 从变分的角度解释加速现象 55
参考文献 60
第 3 章 带约束凸优化中的加速算法 63
31 线性等式约束问题的一些有用结论 63
32 加速罚函数法 66
321 一般凸目标函数 71
322 强凸目标函数 71
33 加速拉格朗日乘子法 72
331 原始问题的解 74
332 加速增广拉格朗日乘子法 76
34 交替方向乘子法及非遍历意义下的加速算法 77
341 情形 1：一般凸和非光滑目标函数 82
342 情形 2：强凸非光滑目标函数 83
343 情形 3：一般凸和光滑目标函数 85
344 情形 4：强凸和光滑目标函数 87
345 非遍历意义收敛速度 88
35 原始–对偶算法 98
351 情形 1：两个函数均非强凸 100
352 情形 2：只有一个函数强凸 101
353 情形 3：两个函数均强凸 103
36 Frank-Wolfe 算法 104
参考文献 108
第 4 章 非凸优化中的加速梯度算法 112
41 带冲量的邻近梯度法 112
411 收敛性理论 113
412 单调加速邻近梯度法 120
42 快速收敛到临界点 120
421 能够检测强凸性质的 AGD 121
422 负曲率下降算法 123
423 非凸加速算法 125
43 快速逃离鞍点 128
431 几乎凸的情形 128
432 完全非凸情形 130
433 非凸加速梯度下降法 131
参考文献 136
第 5 章 加速随机算法 138
51 各自凸情况 139
511 加速随机坐标下降算法 140
512 方差缩减技巧基础算法 147
513 加速随机方差缩减方法 152
514 黑盒加速算法 158
52 各自非凸情况 160
53 非凸情况 166
531 随机路径积分差分估计子 167
532 冲量加速 173
54 带约束问题 174
55 无穷情况 197
参考文献 200
第 6 章 加速并行算法

推 荐 序 一

优化算法一直是推动近年来机器学习发展的引擎．机器学习的需求与使用优化工具箱的其他学科的需求不同，最显著的差别是，参数空间是高维的，需要优化的函数通常是数百万项之和．在这种情况下，基于梯度的方法比高阶优化方法更可取，并且考虑到计算完全的梯度有可能不可行，因此随机梯度法是机器学习领域优化算法的代名词．这些限制与解决非凸优化问题、控制随机采样引起的方差以及开发在分布式平台上运行的算法的需求结合在一起，对优化提出了一系列新的挑战．令人惊讶的是，过去十年中许多挑战已经被研究人员解决．

林宙辰、李欢和方聪所著的这本书是该新兴领域的第一本完整的专著．该书详细介绍了基于梯度的算法，重点关注加速的概念．加速是现代优化中的关键概念，它提供了新的算法和对可达到的收敛速度的深入探索．该书还介绍了随机方法（包括方差控制），并包括有关异步分布式实现的资料．

任何希望在机器学习领域工作的研究人员都应该对统计和优化领域有基本的了解，这本书正是了解基本的优化算法并开始机器学习研究的绝佳出发点．

Michael I. Jordan

于伯克利 .加州大学伯克利分校

2019 年 10 月

推 荐 序 二

优化是机器学习的核心主题之一．在得益于纯粹优化领域的进步的同时，机器学习中的优化也形成了自己的特点．一个显著的现象是，一阶算法或多或少地成了机器学习的主流优化方法．虽然有一些书籍或预印本介绍了机器学习中使用的部分或全部主要优化算法，但本书着眼于最近机器学习优化中的一个明显的潮流，即加速一阶算法．加速一阶算法起源于Polyak的重球法并被Nesterov的一系列工作所引发，目前已成为优化和机器学习领域的热门话题，并取得了丰硕的成果．这些成果已经大大超出了无约束（和确定性）凸优化的传统范围．新的成果包括约束凸优化和非凸优化的加速、随机算法以及通用加速框架，例如Katyusha算法和Catalyst加速框架，其中一些甚至具有接近最佳的收敛速度．不幸的是，现有文献散布在广泛的出版物中，因此掌握基本加速技巧并全面了解这个快速发展的领域变得非常困难．

幸运的是，这本由林宙辰、李欢和方聪合著的专著及时满足了对加速一阶算法进行快速学习的需求．该书首先概述了加速一阶算法的发展历程，尽管略显粗略，但提供的信息极为丰富．然后，介绍了针对不同类别问题的代表性工作，并提供了详细的证明，这些证明极大地方便了读者对基本思想的理解和对基本技术的掌握．毫无疑问，这本书对于那些想要学习最新的机器学习优化算法的人来说是至关重要的参考书．

我认识林宙辰博士已有很长时间了．他以扎实的工作、深刻的见解以及对来自不同研究领域的问题的细致分析给我留下了深刻的印象．鉴于我和他有很多共同的研究兴趣，其中之一是基于学习的优化，我很高兴看到这本书经过精心撰写后终于出版了．

徐宗本

于西安 .西安交通大学

2019 年 10 月

推 荐 序 三

一阶优化方法一直是求解面向大数据的机器学习、信号处理和人工智能问题的主要工具．一阶优化方法虽然概念上很简单，但需要仔细分析并充分了解才能有效地进行部署．加速、非光滑、非凸、并行和分布式实现等问题至关重要，因为它们会对算法的收敛行为和运行时间产生重大影响．

该研究专著对一阶优化方法的算法方面进行了出色的介绍，重点是算法设计和收敛性分析．它深入讨论了加速、非凸、约束和异步实现的问题．专著中涉及的主题和给出的结果非常及时，并且与机器学习、信号处理、人工智能领域的研究人员和从业人员都息息相关．专著有意识地避免了复杂性下限的理论问题，以让位于算法设计和收敛性分析．总体而言，作者对各方面材料的处理相当均衡，并且在整个专著中提供了许多有用的见解．

该专著的作者在机器学习和优化相结合方面具有丰富的研究经验．专著写得很好，读起来也很流畅．对于对机器学习的优化方面感兴趣的每个人来说，它都应该是一本重要的参考书．

罗智泉

于深圳 .香港中文大学（深圳）

2019 年 10 月

中文版前言
本书的英文版交稿后，对于是否要出版中文版，我的确纠结了一段时间毕竟本书并非优化算法的入门书，能够关注它的人士一般都有较好的数学和英文基础，在此前提下，出版中文版似乎没什么必要，而且会占用我们的科研时间，让我们继续在“已知”的范围内打圈圈，妨碍我们去探寻“未知”然而，庚子年突发新冠疫情，习近平总书记“把论文写在祖国大地上”的号召越发深入人心另外，不少好友在得知英文版将要出版的消息后，向我询问有没有中文版，也让我意识到出版中文版的必要性因此，在NeurIPS2020论文提交截止后，我和李欢、方聪再次牺牲所有的业余时间，马上开始了翻译工作所幸数学公式占了绝大部分，文字翻译和全书校对得以在较短的时间内完成但是，中文版并不是英文版的逐字简单翻译，我们添加了少量内容（如增加了第21、22节和一致凸函数的定义，扩充了第23节），还更正了英文版中的一些细节错误完成了中文版，我才终于觉得这项工作功德圆满，故作小诗一首：
一朝意气兴， 两载苦劳形
若可追周髀， 千觥醉未名！
林宙辰
于北京 北京大学
2020 年 10 月
本书中文版主体译自：
Accelerated Optimization for Machine Learning: First-Order Algorithms by Zhouchen Lin, Huan Li and Cong Fang
Copyright Springer Nature Singapore Pte Ltd 2020 All Rights Reserved
建议引用本书英文版



英文版前言
在为北京大学开设的优化课程准备高级材料时，我发现加速算法是对工程专业学生最有吸引力和最实用的专题实际上，这也是当前机器学习会议的热门话题尽管有些书介绍了一些加速算法，例如[Beck,2017;Bubeck,2015;Nesterov,2018]，但它们不完整、不系统且不是最新的因此，在2018年年初，我决定写一本有关加速算法的专著我的目标是写一本有条理的书，其中包含足够的入门材料和详尽的证明，以便读者无须查阅分散四处的文献，不被不一致的符号所困扰，并且不被非关键内容包围而不知中心思想为何幸运的是，我的两个博士生李欢和方聪很乐意加入这项工作
事实证明，这项任务非常艰巨，因为我们必须在繁忙的工作日程中抽空进行写作最终，在李欢和方聪博士毕业之前，我们终于写完了一份粗糙但完整的初稿接下来，我们又花了四个月的时间来使本书读起来流畅并订正了各种不一致和错误最后，我们极为荣幸地收到MichaelIJordan教授、徐宗本教授和罗智泉教授写的序尽管这本书占用了我们近两年的所有闲暇时间，但当全书终于完成的时候，我们仍然觉得我们的努力是完全值得的
希望这本书能成为机器学习和优化领域研究人员的有价值的参考书，这将是对我们工作的最大认可
林宙辰
于北京 北京大学
2019 年 11 月
参 考 文 献
Beck Amir (2017) First-Order Methods in Optimization[M] volume 25 SIAM, Philadelphia
Bubeck Sébastien (2015) Convex optimization: Algorithms and complexity[J] Found Trends Math Learn, 8(3-4): 231-357
Nesterov Yurii (2018) Lectures on Convex Optimization[M] 2nd ed Springer