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

在人工智能与大数据时代，优化算法已成为机器学习与数据科学的核心支柱。本书以独特的应用视角，将抽象的数学理论与实际工程问题紧密结合，为读者架起了一座从理论到实践的桥梁。 本书由优化领域权威学者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.8　KL和PL属性47 注释和参考48 习题48 第4章　使用动量的梯度法51 4.1　来自微分方程的启发52 4.2　Nesterov法：凸二次方程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