前    言

本书是在线凸优化(Online Convex Optimization，OCO)扩展理论的导论。它是为研究生基础课程编写的高等教材，可作为深入优化与机器学习交叉领域的研究人员的参考书。

Technion于2010—2014年开设了这门课程，每年略有变化，普林斯顿大学于2015—2020年开设了这门课程。本书全面涵盖了这些课程的核心材料，并给出让学生完成部分证明的练习，或者参加课程的人觉得具有启发性和发人深省的练习。大部分材料都给出了应用实例，这些应用实例穿插在各个主题中，包括专家建议的预测、投资组合选择、矩阵补全和推荐系统，以及支持向量机(Support Vector Machine，SVM)的训练。

我们希望这份材料和练习纲要对研究人员和教育工作者有用。

把这本书放在机器学习图书馆中

机器学习的广阔领域，如在线学习(online learning)、提

升(boosting)、博弈中的遗憾最小化(regret minimization in games)、通用预测(universal prediction)和其他相关主题的子学科，近年来已经出现了大量的入门书籍。在此，我们很难对所有这些进行公正的评价，但也许可以列出与机器学习、博弈学习和优化主题最相关的书籍，它们的交集是我们的主要关注点。

最密切相关的书是Cesa-Bianchi and Lugosi (2006)，它对整个博弈学习领域起到了启发作用。在数学优化理论的文献中，有许多关于凸优化和凸分析的介绍性文章，例如以下作者的文章：Boyd andVandenberghe, 2004; Nesterov, 2004; Nemirovski and Yudin, 1983; Nemirovski, 2004; Borwein and Lewis, 2006; Rockafellar, 1997。作者推荐了自己学习数学优化理论的书籍(Nemirovski, 2004)。关于机器学习的书籍太多了，在这里无法一一列举。

本书的主要目的是作为OCO和机器学习凸优化方法专门课程的教科书。在线凸优化已经产生了足够的影响，出现在多个综述和导论文献中(Hazan, 2011; Shalev-Shwartz, 2011; Rakhlin, 2009; Rakhlin and Sridharan, 2014)。我们希望这份材料和练习的汇编将进一步丰富这些文献。

本书结构

本书旨在作为计算机科学/电气工程/运筹学/统计学及相关领域研究生独立课程的参考。因此，它的组织遵循了在Technion教授的“决策分析”课程的结构，以及后来在普林斯顿大学教授的“理论机器学习”课程的结构。

每章应该花费一到两周的课时，具体取决于课程的深度和广度。

第1章为该领域的导论，不像本书其他部分那么严谨。

粗略地说，本书可以分成三个部分。第一部分是第2章到第4章，包含了在线凸优化的基本定义、框架和核心算法。第二部分是第5章到第7章，包含更高阶的算法、框架的深入分析以及其他计算和信息访问模型的扩展。本书的其余部分(即第三部分)涉及更高级的算法、更困难的设置以及与知名机器学习范式的关系。

本书可以帮助教育工作者设计关于在线凸优化主题的完整课程，也可以作为机器学习综合课程的组成部分。

第2版新增

本书第2版的主要增补内容如下：

•

在第2章中扩大了优化范围，对Polyak步长进行了统一的梯度下降分析。

•

在第9章中扩展了学习理论的涵盖范围，介绍了压缩及其在泛化理论中的应用。

•

扩展的第4章，增加了指数(exp)凹损失函数的指数加权优化器。

•

修订后的第5章，增加了镜像下降分析，自适应梯度方法(5.6节)也进行了修订。

•

新的第10章包括自适应遗憾的概念和面向具有近似最优自适应遗憾界的OCO算法。

•

新的第11章包括Boosting(提升)及其与在线凸优化的关系。从遗憾最小化推导Boosting算法。

•

新的第12章包括在线 Boosting。

•

新的第13章包括Blackwell可接近性及其与在线凸优化的紧密联系。