在線凸優化：概念、架構及核心算法（簡體書）

谷歌人工智能普林斯頓公司的聯合創始人、普林斯頓大學計算機科學教授撰寫，系統闡釋在線凸優化理論及應用

本書可用作大量在線凸優化（OnlineConvexOptimization,OCO）理論的導論它是一本針對研究生課程的基礎內容設計的高等教材,可作為深入優化與機器學習交叉領域的研究人員的參考書
這一課程於2010～2014年在Technion開設,每一年都有一些小的變化,之後於2015～2016年在普林斯頓大學開設這些課程中的核心材料在本書中均有涉及,同時本書也附帶了習題以便學生完成部分計算和證明,還有一些具有啟發性和發人深省的內容多數材料是以應用實例的形式給出的,這些例子貫穿不同的主題,包括來自專家建議的預測（predictionfromexpertadvice）、投資組合選擇（portfolioselection）、矩陣補全（matrixcompletion）和推薦系統（recommendationsystem）、支援向量機（SupportVectorMachine,SVM）的訓練等
希望本書可以為讀者、教師和研究人員提供幫助
請將本書置於機器學習的圖書館中
近年來,在機器學習廣闊領域的子學科,如在線學習（onlinelearning）、提升方法（boosting）、博弈中的遺憾值最小化方法（regretminimizationingames）、通用預測方法（universalprediction）和其他相關主題中出現了大量的入門文獻在本書中,很難對所有這些內容進行取捨,但它們也許指出了本書在讀者擁有的虛擬圖書館中的位置
緊挨著本書的應當是Cesa-Bianchi和Lugosi[29]的精彩教材,正是它啟迪了本書的撰寫事實上,它啟迪了博弈論中學習方法的整個領域另外,有著無數有關凸優化和凸分析的入門文獻,包括[23,78,76,77,21,92]有關機器學習的文獻太多了,不可能在此一一給出
本書的主要目的是為在線凸優化和凸優化與機器學習相結合的課程提供教材在線凸優化已經在很多綜述和入門文獻（例如[53,97,85,87]）中產生了足夠大的影響希望本書能進一步豐富這些文獻
本書的結構
本書旨在為計算機科學、電氣工程、運籌學、統計學及相關領域的研究生提供自學課程的參考因此,本書遵循了在Technion講授的“決策分析”課程的架構
根據課程的深度和廣度,每一章都應講授一周或兩周第1章為導論,因此沒有其他部分那麼嚴格
全書可以粗略地分成兩個部分:第一部分從第2章到第5章,包括在線凸優化的基本概念、架構和核心算法;第二部分從第6章到第9章,旨在處理更高級的算法、更困難的設定和與著名的機器學習範式之間的關係

前言
致謝
第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 沒有免費