在线凸优化（第2版）

近年来，随着机器学习和计算机技术的不断发展，以及在Web上收集大量数据的普及，在线广告优化、在线投资组合、在线博弈学习等应用已成为工业和学术界关注的热点。而在线凸优化是一种专门用于处理在线学习过程中凸优化问题的优化理论。我们非常高兴介绍由普林斯顿大学教授埃拉德●哈赞(Elad Hazan)撰写的《在线凸优化(第2版)》，书中包括了在线凸优化的基本概念和方法，并详细讨论了在线凸优化的性能保证问题，还介绍了一些最新的在线凸优化算法。本书涵盖了在线凸优化领域的许多关键问题，为我们提供了一份全面的指南。

　　《在线凸优化(第２版)》全面更新，深入探索优化和机器学习交叉领域，详细介绍日常生活中许多系统和模型的优化过程。
●　第2版亮点: 增加了关于提升、自适应遗憾和可接近性的章节
●　扩大了优化和学习理论的覆盖面
●　应用实例包含专家建议投资组合选择、矩阵补全推荐系统和支持向量机训练等
●　指导学生完成练习

普林斯顿大学计算机科学教授
谷歌AI普林斯顿实验室的联合创始人和主任
Elad Hazan教授主要研究学习机制的自动化及其高效的算法实现。研究领域集中在机器学习，并涉及数学优化、博弈论、统计学和计算复杂性。

第1章　导论       1
1.1　在线凸优化设置     2
1.2　可用OCO建模的问题示例    3
1.2.1　从专家建议中预测   3
1.2.2　在线垃圾邮件过滤   4
1.2.3　在线最短路径    5
1.2.4　投资组合选择    6
1.2.5　矩阵补全和推荐系统    7
1.3　混合的开始：从专家建议中学习   7
1.3.1　加权多数算法    9
1.3.2　随机加权多数    10
1.3.3　Hedge     12
1.4　文献评述     13
1.5　练习      14
第2章　凸优化基本概念     17
2.1　基本定义和设置     17
2.1.1　凸集上的投影    19
2.1.2　最优条件介绍    20
2.2　梯度下降     21
2.2.1　Polyak 步长    23
2.2.2　度量与最优值之间的距离    24
2.2.3　Polyak 步长分析    25
2.3　约束梯度/次梯度下降   27
2.4　非光滑和非强凸函数的归约   30
2.4.1　光滑且非强凸函数的归约    30
2.4.2　强凸非光滑函数的归约    31
2.4.3　一般凸函数的归约    34
2.5　示例：支持向量机训练   34
2.6　文献评述     37
2.7　练习      38
第3章　在线凸优化一阶算法     41
3.1　在线梯度下降     42
3.2　下界      44
3.3　对数遗憾     46
3.4　应用：随机梯度下降    48
3.5　文献评述     51
3.6　练习      51
第4章　二阶方法      53
4.1　动机：通用投资组合选择    53
4.1.1　主流投资组合理论    53
4.1.2　通用投资组合理论    54
4.1.3　持续再平衡投资组合    55
4.2　指数凹函数    56
4.3　指数加权OCO     58
4.4　在线牛顿步算法     60
4.5　文献评述     66
4.6　练习      67
第5章　正则化       69
5.1　正则化函数    70
5.2　RFTL算法及其分析    71
5.2.1　元算法定义     72
5.2.2　遗憾界     73
5.3　在线镜像下降     75
5.3.1　懒惰版在线镜像下降与RFTL的等价性  77
5.3.2　镜像下降的遗憾界    78
5.4　应用与特例    79
5.4.1　推导在线梯度下降    79
5.4.2　推导乘法更新    80
5.5　随机正则化    81
5.5.1　凸损失扰动    82
5.5.2　线性代价函数扰动    86
5.5.3　专家建议的FPL算法    87
5.6　自适应梯度下降     89
5.7　文献评述     95
5.8　练习      96
第6章　赌博机凸优化     99
6.1　赌博机凸优化设置     99
6.2　多臂赌博机问题    100
6.3　从有限信息归约至完全信息   105
6.3.1　第一部分：使用无偏估计   105
6.3.2　第二部分：逐点梯度估计   107
6.4　无需梯度在线梯度下降    110
6.5　赌博机线性优化的最优遗憾算法  112
6.5.1　自和谐势垒    113
6.5.2　一个近似最优算法    114
6.6　文献评述     117
6.7　练习      118
第7章　无投影算法       121
7.1　回顾：线性代数的相关概念   121
7.2　动机：推荐系统     122
7.3　条件梯度法     124
7.4　投影与线性优化    128
7.5　在线条件梯度算法    130
7.6　文献评述     134
7.7　练习      134
第8章　博弈，对偶与遗憾     137
8.1　线性规划与对偶    138
8.2　零和博弈与均衡    139
8.3　冯 • 诺依曼定理证明    142
8.4　近似线性规划     144
8.5　文献评述     146
8.6　练习      146
第9章　学习理论，泛化性与在线凸优化    149
9.1　统计学习理论     149
9.1.1　过拟合      150
9.1.2　免费午餐     151
9.1.3　学习问题示例    152
9.1.4　定义泛化性与可学习性   153
9.2　使用在线凸优化的不可知学习   155
9.2.1　余项：度量集中和鞅    156
9.2.2　归约的分析    158
9.3　学习与压缩     160
9.4　文献评述     161
9.5　练习      162
第10章　在变化的环境中学习      165
10.1　一个简单的开始：动态遗憾    166
10.2　自适应遗憾的概念    167
10.3　跟踪最好的专家     169
10.4　在线凸优化的有效自适应遗憾   172
10.5　计算高效的方法     174
10.6　文献评述    179
10.7　练习     180
第11章　Boosting与遗憾     183
11.1　Boosting 的问题     184
11.2　基于在线凸优化的 Boosting   185
11.2.1　简化设置    185
11.2.2　算法与分析    186
11.2.3　AdaBoost     188
11.2.4　补全路线图    189
11.3　文献评述    190
11.4　练习     191
第12章　在线Boosting     193
12.1　动机：向大量专家学习     193
12.1.1　示例：Boosting在线二进制分类   194
12.1.2　示例：个性化文章配置   195
12.2　情境学习模型     195
12.3　延拓算子    196
12.4　在线 Boosting方法    198
12.5　文献评述    202
12.6　练习     202

本书是在线凸优化(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可接近性及其与在线凸优化的紧密联系。