在线凸优化(第2版)

第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