机器学习中的一阶与随机优化方法

本书对优化算法的理论和研究进展进行了系统的梳理，旨在帮助读者快速了解该领域的发展脉络，掌握必要的基础知识，进而推进前沿研究工作。本书首先介绍流行的机器学习模式，对重要的优化理论进行回顾，接着重点讨论已广泛应用于优化的算法，以及有潜力应用于大规模机器学习和数据分析的算法，包括一阶方法、随机优化方法、随机和分布式方法、非凸随机优化方法、无投影方法、算子滑动和分散方法等。
本书适合对机器学习、人工智能和数学编程感兴趣的读者阅读参考。

蓝光辉（Guanghui Lan） 佐治亚理工学院工业与系统工程学院教授，之前曾任教于佛罗里达大学工业与系统工程系。研究方向为随机优化和非线性规划的理论、算法与应用。曾获NSF CAREER奖、INFORMS青年教师论文奖一等奖、INFORMS Computing Society（ICS）奖等。目前担任Computational Optimization and Applications、Mathematical Programming和SIAM Journal on Optimization等期刊的副主编。博士毕业于佐治亚理工学院。

优化方法的研究面临着数据的高维度、不确定性和非凸性等问题，同时，实时求解、分布式处理等需求的日益增多也给优化方法的应用带来了困难。
近年来，优化方法的研究已取得了重要进展，本书对这些工作进行了系统的梳理，旨在帮助读者快速了解该领域的发展脉络，掌握必要的基础知识，进而推进前沿研究工作。
本书首先介绍流行的机器学习模式，对重要的优化理论进行回顾，接着重点讨论已广泛应用于优化的算法，以及有潜力应用于大规模机器学习和数据分析的算法，包括一阶方法、随机优化方法、随机和分布式方法、非凸随机优化方法、无投影方法、算子滑动和分散方法等。全书从基础知识开始讲解，逐步进阶到为机器学习精心设计的复杂算法，涵盖适用于不同场景的算法方案，适合对机器学习、人工智能和数学编程感兴趣的读者参考。

前　言Firstorder and Stochastic Optimization Methods for Machine Learning在数据科学中，优化从一开始就扮演着重要的角色，许多统计和机器学习模型的分析与求解方法都依赖于优化。近年来学界对计算数据分析中的优化兴趣激增，相关研究也面临着一些重大挑战：在所研究的问题中，常常会遇到高维度、庞大的数据量、固有的不确定性以及几乎不可避免的非凸性等问题；同时，越来越多的问题有实时求解的需求，还有许多问题有在分布式环境下处理的需求。所有这些都成为当前优化方法论发展中面临的重大障碍。
在过去10年左右的时间里，人们在设计和分析优化算法来解决这些挑战方面取得了重要的进展。然而，相关工作分散在大量不同学科和方向的文献中。由于对这些进展缺乏系统的梳理，年轻的研究人员要涉足这一领域也就十分困难。他们需要建立必要的基础，了解相关发展的现状，进而推动这一令人兴奋的研究领域的前沿工作。在本书中，我试图把最近的这些进展以一种比较有条理的方式展现出来，主要关注的是已被广泛应用于优化的算法，或（在我看来）未来有潜力应用于大规模机器学习和数据分析的算法。这些算法包括相当多的一阶方法、随机优化方法、随机和分布式方法、非凸随机优化方法、无投影方法以及算子滑动和分散方法等。我的目的是介绍能够在不同场合提供最佳性能保证的基本算法方案。在讨论这些算法之前，先简要介绍了一些流行的机器学习模型以启发读者，同时，也对一些重要的优化理论进行了回顾，为读者特别是初学者提供良好的理论基础。
本书适合对优化方法及其在机器学习或机器智能中的应用感兴趣的研究生和高年级本科生阅读，也可以供资深的研究人员参考。这本书的初稿已被佐治亚理工学院用作高年级本科生和博士生的参考资料。对于高年级本科生一个学期的课程，我建议学习内容涵盖1.1、1.2、1.4～1.7、2.1、2.2、3.1、3.2、4.1和7.1节，并鼓励学生完成一个课程项目。对于博士生一个学期的课程，我建议包括1.1～1.7、2.1～2.4、3.1～3.6、4.1～4.3、5.1、5.3、5.4、6.1～6.5和7.1～7.4节，并鼓励学生阅读和讨论本书中或文献中未涉及的材料。
本书中所选的很多材料都来自我们在过去几年里的研究工作。非常感谢我的博士导师、已毕业的博士生、博士后和其他合作者。衷心感谢Arkadi Nemirovski，他指导我走过了学术生涯的不同阶段，成就了今天的我。Alex Shapiro对本书的写作提供了很多指导，并不断提醒我进度。如果没有他的鼓励，我可能已经放弃了这一努力。非常感谢Renato Monteiro的善良和支持。本书的写作过程也让我重温了与合作者共同工作时的愉快记忆，包括一些非常敬业的同事，如Yunmei Chen和Hongchao Zhang，还有一些非常有才华的已毕业的学生和博士后，如Cong Dang、Qi Deng、Saeed Ghadimi、Soomin Lee、Yuyuan Ouyang、Wei Zhang和Yi Zhou。非常幸运的是，我现在的学生也抽出时间来帮助我做了一些工作。

Guanghui Lan
2019年5月于亚特兰大

目　录Firstorder and Stochastic Optimization Methods for Machine Learning译者序
前言第1章　机器学习模型 1　1.1　线性回归1
　1.2　逻辑回归3
　1.3　广义线性模型5
　　1.3.1　指数分布族5
　　1.3.2　模型构建5
　1.4　支持向量机8
　1.5　正则化、Lasso回归和
岭回归11
　1.6　群体风险最小化11
　1.7　神经网络12
　1.8　练习和注释14第2章　凸优化理论15　2.1　凸集15
　　2.1.1　定义和例子15
　　2.1.2　凸集上的投影16
　　2.1.3　分离定理17
　2.2　凸函数20
　　2.2.1　定义和例子20
　　2.2.2　可微凸函数21
　　2.2.3　不可微凸函数21
　　2.2.4　凸函数的Lipschitz
连续性23
　　2.2.5　凸优化的最优性条件24
　　2.2.6　表示定理与核25
　2.3　拉格朗日对偶26
　　2.3.1　拉格朗日函数与
对偶性26
　　2.3.2　强对偶性的证明27
　　2.3.3　鞍点29
　　2.3.4　KarushKuhnTucker
条件29
　　2.3.5　对偶支持向量机31
　2.4　LegendreFenchel共轭对偶32
　　2.4.1　凸函数的闭包32
　　2.4.2　共轭函数33
　2.5　练习和注释35第3章　确定性凸优化37　3.1　次梯度下降法37
　　3.1.1　一般非光滑凸问题38
　　3.1.2　非光滑强凸问题39
　　3.1.3　光滑凸问题41
　　3.1.4　光滑强凸问题42
　3.2　镜面下降法43
　3.3　加速梯度下降法46
　3.4　加速梯度下降法的博弈论
解释50
　3.5　非光滑问题的光滑方案52
　3.6　鞍点优化的原始-对偶方法54
　　3.6.1　一般双线性鞍点问题57
　　3.6.2　光滑双线性鞍点问题57
　　3.6.3　光滑强凸双线性鞍点
问题58
　　3.6.4　线性约束问题59
　3.7　乘子交替方向法61
　3.8　变分不等式的镜面-邻近
方法63
　　3.8.1　单调变分不等式64
　　3.8.2　广义单调变分不等式66
　3.9　加速水平法68
　　3.9.1　非光滑、光滑和弱光滑
问题68
　　3.9.2　鞍点问题76
　3.10　练习和注释81第4章　随机凸优化83　4.1　随机镜面下降法83
　　4.1.1　一般非光滑凸函数84
　　4.1.2　光滑凸问题87
　　4.1.3　准确性证书90
　4.2　随机加速梯度下降法95
　　4.2.1　无强凸性问题100
　　4.2.2　非光滑强凸问题103
　　4.2.3　光滑强凸问题104
　　4.2.4　准确性证书109
　4.3　随机凹凸鞍点问题111
　　4.3.1　通用算法框架112
　　4.3.2　极小极大随机问题115
　　4.3.3　双线性矩阵博弈117
　4.4　随机加速原始-对偶方法119
　　4.4.1　加速原始-对偶方法121
　　4.4.2　随机双线性鞍点问题129
　4.5　随机加速镜面-邻近方法140
　　4.5.1　算法框架141
　　4.5.2　收敛性分析142
　4.6　随机块镜面下降方法154
　　4.6.1　非光滑凸优化155
　　4.6.2　凸复合优化164
　4.7　练习和注释171第5章　凸有限和及分布式
优化173　5.1　随机原始-对偶梯度法173
　　5.1.1　多人共轭空间博弈的
重新表述176
　　5.1.2　梯度计算的随机化177
　　5.1.3　强凸问题的收敛性179
　　5.1.4　随机化方法的复杂度
下界189
　　5.1.5　对非强凸性问题的
推广193
　5.2　随机梯度外插法197
　　5.2.1　梯度外插方法198
　　5.2.2　确定性有限和问题204
　　5.2.3　随机有限和问题213
　　5.2.4　分布式实现218
　5.3　降低方差的镜面下降法220
　　5.3.1　无强凸性的光滑问题223
　　5.3.2　光滑和强凸问题225
　5.4　降低方差加速梯度下降法226
　　5.4.1　无强凸性的光滑问题229
　　5.4.2　光滑和强凸问题233
　　5.4.3　满足错误界条件的
问题238
　5.5　练习和注释240第6章　非凸优化241　6.1　无约束非凸随机优化法241
　　6.1.1　随机一阶方法243
　　6.1.2　随机零阶方法251
　6.2　非凸随机复合优化法260
　　6.2.1　邻近映射的一些性质261
　　6.2.2　非凸镜面下降法263
　　6.2.3　非凸随机镜面下降法264
　　6.2.4　复合问题的随机零阶
方法275
　6.3　非凸随机块镜面下降法279
　6.4　非凸随机加速梯度下降法286
　　6.4.1　非凸加速梯度下降法287
　　6.4.2　随机加速梯度下降法298
　6.5　非凸降低方差镜面下降法310
　　6.5.1　确定性问题的基本
求解方案310
　　6.5.2　随机优化问题的推广313
　6.6　随机化加速邻近点方法316
　　6.6.1　非凸有限和问题317
　　6.6.2　非凸多块问题327
　6.7　练习和注释337第7章　无投影方法 338　7.1　条件梯度法338
　　7.1.1　经典条件梯度