机器学习与数据科学中的优化算法

本书由威斯康星大学Stephen J. Wright与加州大学伯克利分校Benjamin Recht教授联袂撰写，内容源自两所名校机器学习与优化课程讲义，经多年教学实践打磨而成。全书系统阐述数据分析与机器学习中的优化理论，涵盖梯度法、随机梯度法、坐标下降法等核心算法，并深入讲解深度学习中的梯度计算方法。每章配备习题，理论与实践紧密结合，既适合作为高年级本科生及低年级研究生教材，也适合作为机器学习工程师与科研人员的重要参考资料。译本由Airbnb和Meta资深机器学习工程师精心翻译，著译双馨。

在人工智能与大数据时代，优化算法已成为机器学习与数据科学的核心支柱。本书以独特的应用视角，将抽象的数学理论与实际工程问题紧密结合，为读者架起了一座从理论到实践的桥梁。
本书由优化领域权威学者Stephen J. Wright和Benjamin Recht撰写，旨在为读者提供一本条理清晰、系统全面的优化技术指南，尤其聚焦数据科学与机器学习领域的核心优化技术。书中详细阐述了基本优化算法，并分析了它们的收敛性和复杂度。全书共11章，第1章通过典型案例阐释优化在现代数据分析中的应用；第2~10章深入剖析多种核心算法，包括加速梯度法、随机梯度法（机器学习的核心算法）、坐标下降法（高效处理高维问题的利器）、简单约束问题的梯度法、具有非平滑项的凸优化问题的理论和算法，以及约束优化问题的对偶方法；第11章拓展至深度学习与控制领域的梯度计算方法（如自动微分、反向传播的优化视角）。

斯蒂芬·J. 赖特

（Stephen J. Wright）

现任威斯康星大学麦迪逊分校George B. Dantzig教授、 Sheldon Lubar讲席教授，以及 Amar和Balinder Sohi计算机科学教授，同时担任威斯康星州发现研究所（Wisconsin Institute for Discovery）的研究员。他主要研究计算优化及其在数据科学和科学工程其他领域的应用。他是美国工业与应用数学学会（SIAM）会士，曾获2014年IEEE W. R. G. Baker杰出论文奖、2020年INFORMS优化学会Khachiyan终身成就奖以及2020年NeurIPS时间检验奖。他著有多部优化领域经典教材与参考书，包括Primal Dual Interior-Point Methods（1987）和Numerical Optimization（2006）。

本杰明·雷希特

（Benjamin Recht）

加州大学伯克利分校电气工程与计算机科学系副教授。其研究团队致力于通过运用优化、统计和动力系统的数学工具，提升机器学习系统在动态不确定环境中的稳健性。他曾获总统科学家与工程师早期职业奖、Alfred P. Sloan研究奖、2012年SIAM/MOS拉格朗日连续优化奖、2014年Jamon奖、2015年William O. Baker研究倡议奖，以及2017年和2020年NeurIPS时间检验奖。

译者序

前言

第1章概述1

1.1数据分析和优化1

1.2最小二乘法3

1.3矩阵因子分解问题4

1.4支持向量机5

1.5逻辑回归8

1.6深度学习9

1.7重点11

注释和参考12

第2章平滑优化的基础13

2.1优化问题的解的分类13

2.2泰勒定理14

2.3刻画平滑函数的最小值16

2.4凸集和函数18

2.5强凸函数20

注释和参考22

习题22

第3章下降法24

3.1下降方向24

3.2最速下降法25

3.2.1一般情况26

3.2.2凸函数情况27

3.2.3强凸函数情况28

3.2.4收敛速率的比较30

3.3下降法：收敛性31

3.4线搜索法：方向选择33

3.5线搜索法：步长选择35

3.6?收敛到近似的二阶必要点40

3.7镜像下降42

3.8KL和PL属性47

注释和参考48

习题48

第4章使用动量的梯度法51

4.1来自微分方程的启发52

4.2Nesterov法：凸二次方程53

4.3强凸函数的收敛性58

4.4弱凸函数的收敛性61

4.5共轭梯度法64

4.6收敛速率的下界66

注释和参考67

习题68

第5章随机梯度法71

5.1示例与启发72

5.1.1噪声梯度72

5.1.2增量梯度法73

5.1.3分类和感知器73

5.1.4经验风险最小化74

5.2随机性和步长：深入分析75

5.2.1示例：计算均值76

5.2.2随机Kaczmarz法77

5.3收敛分析的关键假设80

5.3.1案例1：有界梯度(Lg=0)81

5.3.2案例2：随机Kaczmarz(B=0,Lg=0)81

5.3.3案例3：加性高斯噪声82

5.3.4案例4：增量梯度82

5.4收敛分析83

5.4.1案例1：Lg=084

5.4.2案例2：B=086

5.4.3案例3：B和Lg都非零87

5.5实施方面的问题89

5.5.1轮次89

5.5.2迷你批量处理89

5.5.3使用动量加速90

注释和参考90

习题91

第6章坐标下降法95

6.1机器学习中的坐标下降法96

6.2平滑凸函数的坐标下降法98

6.2.1利普希茨常数98

6.2.2随机坐标下降法：有放回抽样99

6.2.3循环坐标下降法105

6.2.4随机排列坐标下降法：无放回抽样107

6.3块坐标下降法107

注释和参考109

习题110

第7章约束优化的一阶方法112

7.1最优性条件112

7.2欧几里得投影114

7.3投影梯度算法116

7.3.1一般情况：一种短步法117

7.3.2一般情况：回溯法118

7.3.3平滑强凸情形119

7.3.4动量变体120

7.3.5其他搜索方向120

7.4条件梯度（Frank-Wolfe）法121

注释和参考123

习题124

第8章非平滑函数和次梯度126

8.1次梯度和次微分127

8.2次微分和方向导数131

8.3次微分运算134

8.4凸集和凸约束优化137

8.5复合非平滑函数的最优性条件139

8.6近端算子和莫罗包络141

注释和参考143

习题143

第9章非平滑优化方法145

9.1次梯度下降146

9.2次梯度法148

9.3正则化优化的近端梯度法151

9.4结构化非平滑函数的近端坐标下降法156

9.5近端点法158

注释和参考159

习题159

第10章对偶性和算法161

10.1二次惩罚函数161

10.2拉格朗日函数和对偶性162

10.3一阶最优性条件165

10.4强对偶168

10.5对偶算法170

10.5.1对偶次梯度170

10.5.2增广拉格朗日函数法170

10.5.3交替方向乘数法172

10.6对偶算法的一些应用173

10.6.1共识优化173

10.6.2效用最大化175

10.6.3线性和二次规划176

注释和参考177

习题178

第11章微分和伴随179

11.1向量函数嵌套组合的链式法则179

11.2伴随法181

11.3深度学习中的伴随182

11.4自动微分183

11.5通过拉格朗日函数和隐函数定理推导185

11.5.1渐进式函数的约束优化公式186

11.5.2无约束和约束公式的一般观点187

11.5.3扩展：控制188

注释和参考188

习题189

附录一些背景信息190

参考文献209