在線凸優(yōu)化：概念、架構(gòu)及核心算法

前言
致謝
第1章 導(dǎo)論 1
1.1 在線凸優(yōu)化模型 2
1.2 可以用OCO建模的例子 3
1.3 一個溫和的開始: 從專家建議中學(xué)習(xí) 8
1.3.1 加權(quán)多數(shù)算法 10
1.3.2 隨機加權(quán)多數(shù)算法 12
1.3.3 對沖 14
1.4 習(xí)題 16
1.5 文獻點評 17
第2章 凸優(yōu)化的基本概念 18
2.1 基本定義和設(shè)定 18
2.1.1 在凸集上的投影 20
2.1.2 條件簡介 21
2.2 梯度、次梯度下降法 23
2.3 非光滑和非強凸函數(shù)的歸約 27
2.3.1 光滑非強凸函數(shù)的歸約 28
2.3.2 強凸非光滑函數(shù)的歸約 29
2.3.3 一般凸函數(shù)的歸約 32
2.4 例子: 支持向量機訓(xùn)練 33
2.5 習(xí)題 35
2.6 文獻點評 37
第3章 在線凸優(yōu)化的一階算法 38
3.1 在線梯度下降法 39
3.2 下界 42
3.3 對數(shù)遺憾 43
3.4 應(yīng)用: 隨機梯度下降法 45
3.5 習(xí)題 49
3.6 文獻點評 50
第4章 二階方法 51
4.1 動機: 通用投資組合選擇 51
4.1.1 主流投資組合理論 51
4.1.2 通用投資組合理論 52
4.1.3 持續(xù)再平衡投資組合 54
4.2 exp-凹函數(shù) 55
4.3 在線牛頓步算法 57
4.4 習(xí)題 63
4.5 文獻點評 64
第5章 正則化 66
5.1 正則函數(shù) 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 應(yīng)用及特殊情形 78
5.4.1 在線梯度下降法的導(dǎo)出 79
5.4.2 乘法更新的導(dǎo)出 79
5.5 隨機正則化 81
5.5.1 對凸代價函數(shù)的擾動 82
5.5.2 對線性代價函數(shù)的擾動 86
5.5.3 專家建議中的擾動領(lǐng)袖追隨算法 87
5.6 正則化（選學(xué)） 90
5.7 習(xí)題 96
5.8 文獻點評 98
第6章 Bandit凸優(yōu)化 100
6.1 BCO設(shè)定 100
6.2 多臂賭博機問題 101
6.3 從有限信息到完整信息的歸約 107
6.3.1 第1部分: 使用無偏估計 107
6.3.2 第2部分: 點點梯度估計 110
6.4 不需要梯度的在線梯度下降算法 113
6.5 BLO遺憾算法（選學(xué)） 116
6.5.1 自和諧障礙 116
6.5.2 一個近優(yōu)算法 118
6.6 習(xí)題 121
6.7 文獻點評 122
第7章 無投影算法 123
7.1 回顧: 與線性代數(shù)相關(guān)的概念 123
7.2 動機: 矩陣補全與推薦系統(tǒng) 124
7.3 條件梯度法 126
7.4 投影與線性優(yōu)化 131
7.5 在線條件梯度算法 133
7.6 習(xí)題 138
7.7 文獻點評 139
第8章 博弈、對偶性和遺憾 140
8.1 線性規(guī)劃和對偶性 141
8.2 零和博弈與均衡 142
8.3 馮·諾伊曼定理的證明 146
8.4 近似線性規(guī)劃 148
8.5 習(xí)題 150
8.6 文獻點評 150
第9章 學(xué)習(xí)理論、泛化和OCO 152
9.1 統(tǒng)計學(xué)習(xí)理論的設(shè)定 152
9.1.1 過擬合 153
9.1.2 沒有免費