在線凸優化：概念、架構及核心算法 Introduction to Online Convex Optimization

本書可作為在線凸優化大量理論的導論教程。
第2~5章主要介紹在線凸優化的基本概念、架構和核心算法。
本書其餘部分則處理更為高級的算法、更為困難的設定和與著名的機器學習範式之間的關係。

[美] 埃拉德·哈贊（Elad Hazan） 著：埃拉德·哈贊（Elad Hazan） 普林斯頓大學計算機科學教授，谷歌人工智能普林斯頓公司的聯合創始人和董事。
他專注於機器學習和優化中基本問題的算法設計和分析的研究，曾獲得貝爾實驗室獎、2008年度和2012年度IBM Goldberg最佳論文獎、歐洲研究理事會獎、瑪麗·居里獎學金和谷歌研究獎。
他曾在計算學習協會指導委員會任職，並擔任COLT 2015程序委員會主席，2017年與他人共同創建了致力於高效優化和控制的In8公司。

前言
致謝
第1章 導論 1
1.1 在線凸優化模型 2
1.2 可以用OCO建模的例子 3
1.3 一個溫和的開始: 從專家建議中學習 8
1.3.1 加權多數算法 10
1.3.2 隨機加權多數算法 12
1.3.3 對沖 14
1.4 習題 16
1.5 文獻點評 17

第2章 凸優化的基本概念 18
2.1 基本定義和設定 18
2.1.1 在凸集上的投影 20
2.1.2 條件簡介 21
2.2 梯度、次梯度下降法 23
2.3 非光滑和非強凸函數的歸約27
2.3.1 光滑非強凸函數的歸約 28
2.3.2 強凸非光滑函數的歸約 29
2.3.3 一般凸函數的歸約 32
2.4 例子: 支持向量機訓練 33
2.5 習題 35
2.6 文獻點評 37

第3章 在線凸優化的一階算法 38
3.1 在線梯度下降法 39
3.2 下界 42
3.3 對數遺憾 43
3.4 應用: 隨機梯度下降法 45
3.5 習題 49
3.6 文獻點評 50

第4章 二階方法 51
4.1 動機: 通用投資組合選擇 51
4.1.1 主流投資組合理論 51
4.1.2 通用投資組合理論 52
4.1.3 持續再平衡投資組合 54
4.2 exp-凹函數 55
4.3 在線牛頓步算法 57
4.4 習題 63
4.5 文獻點評 64

第5章 正則化 66
5.1 正則函數 67
5.2 RFTL 算法及其分析 69
5.2.1 元算法的定義 70
5.2.2 遺憾界 70
5.3 在線鏡像下降法 74
5.3.1 遲緩型OMD算法與RFTL 算法的等價性75
5.3.2 鏡像下降的遺憾界 76
5.4 應用及特殊情形 78
5.4.1 在線梯度下降法的導出 79
5.4.2 乘法更新的導出 79
5.5 隨機正則化 81
5.5.1 對凸代價函數的擾動 82
5.5.2 對線性代價函數的擾動 86
5.5.3 專家建議中的擾動領袖追隨算法 87
5.6 正則化（選學） 90
5.7 習題 96
5.8 文獻點評 98

第6章 Bandit凸優化 100
6.1 BCO設定 100
6.2 多臂賭博機問題 101
6.3 從有限信息到完整信息的歸約 107
6.3.1 第1部分: 使用無偏估計 107
6.3.2 第2部分: 點點梯度估計 110
6.4 不需要梯度的在線梯度下降算法113
6.5 BLO遺憾算法（選學）116
6.5.1 自和諧障礙 116
6.5.2 一個近優算法 118
6.6 習題 121
6.7 文獻點評 122

第7章 無投影算法 123
7.1 回顧: 與線性代數相關的概念 123
7.2 動機: 矩陣補全與推薦系統 124
7.3 條件梯度法 126
7.4 投影與線性優化 131
7.5 在線條件梯度算法 133
7.6 習題 138
7.7 文獻點評 139

第8章 博弈、對偶性和遺憾 140
8.1 線性規劃和對偶性 141
8.2 零和博弈與均衡 142
8.3 馮·諾伊曼定理的證明 146
8.4 近似線性規劃 148
8.5 習題 150
8.6 文獻點評 150

第9章 學習理論、泛化和OCO 152
9.1 統計學習理論的設定 152
9.1.1 過擬合 153
9.1.2 沒有免費的午餐 154
9.1.3 學習問題的例子 156
9.1.4 泛化和可學習性的定義 157
9.2 使用OCO的不可知學習 159
9.2.1 餘項: 度量集中和鞅 160
9.2.2 對歸約的分析 162
9.3 習題 165
9.4 文獻點評 166
參考文獻 167