在線凸優化, 2/e Introduction to Online Convex Optimization, 2/e

普林斯頓大學計算機科學教授
谷歌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