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

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