凸優化

本書介紹了凸優化中的主要複雜性定理及其相應的算法。從黑箱優化的基本理論出發，內容材料是朝着結構優化和隨機優化的新進展。我們對黑箱優化的介紹，深受Nesterov的開創性著作和Nemirovski講稿的影響，包括對切割平面方法的分析，以及（加速）梯度下降方案。我們還特別關注非歐幾里德的情況（相關算法包括Frank Wolfe、鏡像下降和對偶平均法），並討論它們在機器中的相關性學習。我們慢慢的介紹了FISTA（優化一個光滑項和一個簡單的非光滑項的和）、鞍點鏡像代理（Nemirovski平滑替代Nesterov的光滑）和一個對內點方法的簡明描述。在隨機優化中，我們討論了隨機梯度下降、小批量、隨機座標下降和次線性算法。我們還簡單地討論了組合問題的凸鬆弛和隨機性對取整（四捨五入）解的使用，以及基於隨機遊動的方法。

譯者序

致謝

第1章緒論1

11機器學習中的若干凸優化問題1

12凸性的基本性質3

13凸性的作用5

14黑箱模型7

15結構性優化8

16結果的概述和免責聲明9

第2章有限維的凸優化12

21重心法12

22橢球法14

23Vaidya割平面法18

231體積障礙19

232Vaidya算法20

233Vaidya方法分析20

234限制條件和體積障礙22

24共軛梯度26

第3章維度無關的凸優化30

31Lipschitz函數的投影次梯度下降31

32光滑函數的梯度下降33

33條件梯度下降39

34強凸性43

341 強凸函數和Lipschitz函數44

342強凸光滑函數45

35下限47

36幾何下降52

361熱身賽：梯度下降的幾何學替代方案53

362加速度55

363幾何下降法56

37Nesterov加速梯度下降58

371光滑強凸情況58

372光滑的情況62

第4章非歐氏空間幾乎維度無關的凸優化65

41鏡像映射66

42鏡像下降67

43鏡像下降的標準設置70

44惰性鏡像下降72

45鏡像代理74

46關於MD、DA和MP的向量場觀點76

第5章超越黑箱模型78

51光滑項與簡單非光滑項之和78

52非光滑函數的光滑鞍點表示80

521鞍點計算81

522鞍點鏡像下降82

523鞍點鏡像代理83

524應用84

53內點法87

531障礙法87

532牛頓法的傳統分析88

533自和諧函數90

534ν自和諧障礙92

535路徑跟蹤方案95

536線性規劃和半定規劃的內點法96

第6章凸優化與隨機性98

61非光滑隨機優化99

62光滑隨機優化與小批量SGD100

63光滑函數與強凸函數的和103

64隨機座標下降107

641座標平滑優化的RCD算法108

642用於光滑和強凸優化的RCD110

65鞍點的隨機加速112

66凸鬆弛與隨機取整113

67基於隨機遊動的方法117

參考文獻120

塞巴斯蒂安·布貝克（Sébastien Bubeck）是微軟Redmond研究院理論組的首席研究員，曾擔任COLT 2013、COLT 2014的聯席主席，NIPS 2012、NIPS 2014、NIPS 2016、COLT 2013、COLT 2014、COLT 2015、COLT 2016、ICML 2015、ICML 2016、ALT 2013、ALT 2014的項目委員會成員，也是COLT的指導委員會成員。其研究興趣包括機器學習、凸優化、統計網絡分析、隨機圖和隨機矩陣，以及信息論在學習、優化和概率中的應用。