機器學習中的加速一階優化算法

林宙辰

機器學習和計算機視覺領域的國際知名專家，
目前是北京大學信息科學技術學院機器感知與智能教育部重點實驗室教授。
他曾多次擔任多個業內頂級會議的領域主席，包括CVPR、ICCV、
ICML、NIPS/NeurIPS、AAAI、 IJCAI和ICLR。
他曾任IEEE Transactions on Pattern Analysis and Machine Intelligence編委，
現任International Journal of Computer Vision和Optimization Methods and Software的編委。他是IAPR和IEEE的會士。

李 歡

於2019 年在北京大學獲得博士學位，專業為機器學習。
目前是南開大學人工智能學院助理研究員，研究興趣包括優化和機器學習。

方 聰

於2019 年在北京大學獲得博士學位，專業為機器學習。
目前是北京大學助理教授，研究興趣包括機器學習和優化。

目錄
推薦序一 
推薦序二 
推薦序三 
中文版前言 
英文版前言 
致謝 
作者介紹 
符號表 
第 1 章 緒論 1 
11 機器學習中的優化問題舉例 1 
111 正則化的經驗損失模型 1 
112 矩陣填充及低秩學習模型 3 
12 一階優化算法 3 
13 加速算法中的代表性工作綜述 4 
14 關於本書 7 
參考文獻 7 

第 2 章 無約束凸優化中的加速算法 14 
21 梯度下降法 14 
22 重球法 15 
23 加速梯度法 16 
24 求解複合凸優化問題的加速梯度法 23 
241 第一種 Nesterov 加速鄰近梯度法 23 
242 第二種 Nesterov 加速鄰近梯度法 27 
243 第三種 Nesterov 加速鄰近梯度法 31 
25 非精確加速鄰近梯度法 33 
251 非精確加速梯度法 42 
252 非精確加速鄰近點法 42 
26 重啟策略 43 
27 平滑策略 45 
28 高階加速方法 50 
29 從變分的角度解釋加速現象 55 
參考文獻 60 

第 3 章 帶約束凸優化中的加速算法 63 
31 線性等式約束問題的一些有用結論 63 
32 加速罰函數法 66 
321 一般凸目標函數 71 
322 強凸目標函數 71 
33 加速拉格朗日乘子法 72 
331 原始問題的解 74 
332 加速增廣拉格朗日乘子法 76 
34 交替方向乘子法及非遍歷意義下的加速算法 77 
341 情形 1：一般凸和非光滑目標函數 82 
342 情形 2：強凸非光滑目標函數 83 
343 情形 3：一般凸和光滑目標函數 85 
344 情形 4：強凸和光滑目標函數 87 
345 非遍歷意義收斂速度 88 
35 原始–對偶算法 98 
351 情形 1：兩個函數均非強凸 100 
352 情形 2：只有一個函數強凸 101 
353 情形 3：兩個函數均強凸 103 
36 Frank-Wolfe 算法 104 
參考文獻 108 

第 4 章 非凸優化中的加速梯度算法 112 
41 帶衝量的鄰近梯度法 112 
411 收斂性理論 113 
412 單調加速鄰近梯度法 120 
42 快速收斂到臨界點 120 
421 能夠檢測強凸性質的 AGD 121 
422 負曲率下降算法 123 
423 非凸加速算法 125 
43 快速逃離鞍點 128 
431 幾乎凸的情形 128 
432 完全非凸情形 130 
433 非凸加速梯度下降法 131 
參考文獻 136 

第 5 章 加速隨機算法 138 
51 各自凸情況 139 
511 加速隨機坐標下降算法 140 
512 方差縮減技巧基礎算法 147 
513 加速隨機方差縮減方法 152 
514 黑盒加速算法 158 
52 各自非凸情況 160 
53 非凸情況 166 
531 隨機路徑積分差分估計子 167 
532 衝量加速 173 
54 帶約束問題 174 
55 無窮情況 197 
參考文獻 200 

第 6 章 加速並行算法