機(jī)器學(xué)習(xí)是關(guān)于從數(shù)據(jù)中建立預(yù)測或描述模型,以提升機(jī)器解決問題能力的學(xué)科。在建立模型后,需要采用適當(dāng)?shù)膬?yōu)化算法來求解模型的參數(shù),因此優(yōu)化算法是機(jī)器學(xué)習(xí)的重要組成部分。但是傳統(tǒng)的優(yōu)化算法并不完全適用于機(jī)器學(xué)習(xí),因?yàn)橥ǔ碚f機(jī)器學(xué)習(xí)模型的參數(shù)維度很高或涉及的樣本數(shù)巨大,這使得一階優(yōu)化算法在機(jī)器學(xué)習(xí)中占據(jù)主流地位。
本書概述了機(jī)器學(xué)習(xí)中加速一階優(yōu)化算法的新進(jìn)展。書中全面介紹了各種情形下的加速一階優(yōu)化算法,包括確定性和隨機(jī)性的算法、同步和異步的算法,以求解帶約束的問題和無約束的問題、凸問題和非凸問題,對算法思想進(jìn)行了深入的解讀,并對其收斂速度提供了詳細(xì)的證明。
本書面向機(jī)器學(xué)習(xí)和優(yōu)化領(lǐng)域的研究人員,包括人工智能、信號處理及應(yīng)用數(shù)學(xué)特別是計(jì)算數(shù)學(xué)專業(yè)高年級本科生、研究生,以及從事人工智能、信號處理領(lǐng)域產(chǎn)品研發(fā)的工程師。
適讀人群:
機(jī)器學(xué)習(xí)和優(yōu)化領(lǐng)域的研究人員,包括人工智能、信號處理及應(yīng)用數(shù)學(xué)特別是計(jì)算數(shù)學(xué)專業(yè)高年級本科生、研究生,以及從事人工智能、信號處理領(lǐng)域產(chǎn)品研發(fā)的工程師
1、院士推薦。本書由Michael I. Jordan院士、徐宗本院士、羅智泉院士聯(lián)袂推薦。
2、作者知名。本書由機(jī)器學(xué)習(xí)和計(jì)算機(jī)視覺領(lǐng)域的國際知名專家,北京大學(xué)信息科學(xué)技術(shù)學(xué)院機(jī)器感知與智能重點(diǎn)實(shí)驗(yàn)室教授林宙辰領(lǐng)銜撰寫。
3、內(nèi)容前沿。概述了機(jī)器學(xué)習(xí)中加速一階優(yōu)化算法的新進(jìn)展,全面介紹了各種情形下的加速一階優(yōu)化算法。
4、主流熱門。以當(dāng)前機(jī)器學(xué)習(xí)會議的熱門話題加速算法為主線,涵蓋機(jī)器學(xué)習(xí)中常用的凸優(yōu)化、非凸優(yōu)化,以及隨機(jī)優(yōu)化和分布式優(yōu)化。
中文版前言
本書的英文版交稿后,對于是否要出版中文版,我的確糾結(jié)了一段時(shí)間.畢竟本書并非優(yōu)化算法的入門書,能夠關(guān)注它的人士一般都有較好的數(shù)學(xué)和英文基礎(chǔ),在此前提下,出版中文版似乎沒什么必要,而且會占用我們的科研時(shí)間,讓我們繼續(xù)在已知的范圍內(nèi)打圈圈,妨礙我們?nèi)ヌ綄の粗欢,庚子年突發(fā)新冠疫情,習(xí)近平總書記把論文寫在祖國大地上的號召越發(fā)深入人心.另外,不少好友在得知英文版將要出版的消息后,向我詢問有沒有中文版,也讓我意識到出版中文版的必要性.因此,在NeurIPS2020論文提交截止后,我和李歡、方聰再次犧牲所有的業(yè)余時(shí)間,馬上開始了翻譯工作.所幸數(shù)學(xué)公式占了絕大部分,文字翻譯和全書校對得以在較短的時(shí)間內(nèi)完成.但是,中文版并不是英文版的逐字簡單翻譯,我們添加了少量內(nèi)容(如增加了第2.1、2.2節(jié)和一致凸函數(shù)的定義,擴(kuò)充了第2.3節(jié)),還更正了英文版中的一些細(xì)節(jié)錯(cuò)誤.完成了中文版,我才終于覺得這項(xiàng)工作功德圓滿,故作小詩一首:
一朝意氣興, 兩載苦勞形.
若可追周髀, 千觥醉未名!
林宙辰
于北京 .北京大學(xué)
2020 年 10 月
本書中文版主體譯自:
Accelerated Optimization for Machine Learning: First-Order Algorithms by Zhouchen Lin, Huan Li and Cong Fang.
Copyright . Springer Nature Singapore Pte Ltd. 2020. All Rights Reserved.
建議引用本書英文版.
英文版前言
在為北京大學(xué)開設(shè)的優(yōu)化課程準(zhǔn)備高級材料時(shí),我發(fā)現(xiàn)加速算法是對工程專業(yè)學(xué)生有吸引力和實(shí)用的專題.實(shí)際上,這也是當(dāng)前機(jī)器學(xué)習(xí)會議的熱門話題.盡管有些書介紹了一些加速算法,例如[Beck,2017;Bubeck,2015;Nesterov,2018],但它們不完整、不系統(tǒng)且不是的.因此,在2018年年初,我決定寫一本有關(guān)加速算法的專著.我的目標(biāo)是寫一本有條理的書,其中包含足夠的入門材料和詳盡的證明,以便讀者無須查閱分散四處的文獻(xiàn),不被不一致的符號所困擾,并且不被非關(guān)鍵內(nèi)容包圍而不知中心思想為何.幸運(yùn)的是,我的兩個(gè)博士生李歡和方聰很樂意加入這項(xiàng)工作.
事實(shí)證明,這項(xiàng)任務(wù)非常艱巨,因?yàn)槲覀儽仨氃诜泵Φ墓ぷ魅粘讨谐榭者M(jìn)行寫作.終,在李歡和方聰博士畢業(yè)之前,我們終于寫完了一份粗糙但完整的初稿.接下來,我們又花了四個(gè)月的時(shí)間來使本書讀起來流暢并訂正了各種不一致和錯(cuò)誤.后,我們極為榮幸地收到MichaelI.Jordan教授、徐宗本教授和羅智泉教授寫的序.盡管這本書占用了我們近兩年的所有閑暇時(shí)間,但當(dāng)全書終于完成的時(shí)候,我們?nèi)匀挥X得我們的努力是完全值得的.
希望這本書能成為機(jī)器學(xué)習(xí)和優(yōu)化領(lǐng)域研究人員的有價(jià)值的參考書,這將是對我們工作的認(rèn)可.
林宙辰
于北京 .北京大學(xué)
2019 年 11 月
參 考 文 獻(xiàn)
Beck Amir. (2017). First-Order Methods in Optimization[M]. volume 25. SIAM, Philadelphia.
Bubeck Sébastien. (2015). Convex optimization: Algorithms and complexity[J]. Found. Trends Math. Learn., 8(3-4): 231-357.
Nesterov Yurii. (2018). Lectures on Convex Optimization[M]. 2nd ed. Springer.
林宙辰
機(jī)器學(xué)習(xí)和計(jì)算機(jī)視覺領(lǐng)域的國際知名專家,目前是北京大學(xué)信息科學(xué)技術(shù)學(xué)院機(jī)器感知與智能教育部重點(diǎn)實(shí)驗(yàn)室教授。他曾多次擔(dān)任多個(gè)業(yè)內(nèi)會議的領(lǐng)域主席,包括CVPR、ICCV、ICML、NIPS/NeurIPS、AAAI、 IJCAI和ICLR。他曾任IEEE Transactions on Pattern Analysis and Machine Intelligence編委,現(xiàn)任International Journal of Computer Vision和Optimization Methods and Software的編委。他是IAPR和IEEE的會士。
李 歡
于2019 年在北京大學(xué)獲得博士學(xué)位,專業(yè)為機(jī)器學(xué)習(xí)。目前是南開大學(xué)人工智能學(xué)院助理研究員,研究興趣包括優(yōu)化和機(jī)器學(xué)習(xí)。
方 聰
于2019 年在北京大學(xué)獲得博士學(xué)位,專業(yè)為機(jī)器學(xué)習(xí)。目前是北京大學(xué)助理教授,研究興趣包括機(jī)器學(xué)習(xí)和優(yōu)化。
推薦序一
推薦序二
推薦序三
中文版前言
英文版前言
致謝
作者介紹
符號表
第 1 章 緒論 1
1.1 機(jī)器學(xué)習(xí)中的優(yōu)化問題舉例 1
1.1.1 正則化的經(jīng)驗(yàn)損失模型 1
1.1.2 矩陣填充及低秩學(xué)習(xí)模型 3
1.2 一階優(yōu)化算法 3
1.3 加速算法中的代表性工作綜述 4
1.4 關(guān)于本書 7
參考文獻(xiàn) 7
第 2 章 無約束凸優(yōu)化中的加速算法 14
2.1 梯度下降法 14
2.2 重球法 15
2.3 加速梯度法 16
2.4 求解復(fù)合凸優(yōu)化問題的加速梯度法 23
2.4.1 種 Nesterov 加速鄰近梯度法 23
2.4.2 第二種 Nesterov 加速鄰近梯度法 27
2.4.3 第三種 Nesterov 加速鄰近梯度法 31
2.5 非精確加速鄰近梯度法 33
2.5.1 非精確加速梯度法 42
2.5.2 非精確加速鄰近點(diǎn)法 42
2.6 重啟策略 43
2.7 平滑策略 45
2.8 高階加速方法 50
2.9 從變分的角度解釋加速現(xiàn)象 55
參考文獻(xiàn) 60
第 3 章 帶約束凸優(yōu)化中的加速算法 63
3.1 線性等式約束問題的一些有用結(jié)論 63
3.2 加速罰函數(shù)法 66
3.2.1 一般凸目標(biāo)函數(shù) 71
3.2.2 強(qiáng)凸目標(biāo)函數(shù) 71
3.3 加速拉格朗日乘子法 72
3.3.1 原始問題的解 74
3.3.2 加速增廣拉格朗日乘子法 76
3.4 交替方向乘子法及非遍歷意義下的加速算法 77
3.4.1 情形 1:一般凸和非光滑目標(biāo)函數(shù) 82
3.4.2 情形 2:強(qiáng)凸非光滑目標(biāo)函數(shù) 83
3.4.3 情形 3:一般凸和光滑目標(biāo)函數(shù) 85
3.4.4 情形 4:強(qiáng)凸和光滑目標(biāo)函數(shù) 87
3.4.5 非遍歷意義收斂速度 88
3.5 原始對偶算法 98
3.5.1 情形 1:兩個(gè)函數(shù)均非強(qiáng)凸 100
3.5.2 情形 2:只有一個(gè)函數(shù)強(qiáng)凸 101
3.5.3 情形 3:兩個(gè)函數(shù)均強(qiáng)凸 103
3.6 Frank-Wolfe 算法 104
參考文獻(xiàn) 108
第 4 章 非凸優(yōu)化中的加速梯度算法 112
4.1 帶沖量的鄰近梯度法 112
4.1.1 收斂性理論 113
4.1.2 單調(diào)加速鄰近梯度法 120
4.2 快速收斂到臨界點(diǎn) 120
4.2.1 能夠檢測強(qiáng)凸性質(zhì)的 AGD 121
4.2.2 負(fù)曲率下降算法 123
4.2.3 非凸加速算法 125
4.3 快速逃離鞍點(diǎn) 128
4.3.1 幾乎凸的情形 128
4.3.2 完全非凸情形 130
4.3.3 非凸加速梯度下降法 131
參考文獻(xiàn) 136
第 5 章 加速隨機(jī)算法 138
5.1 各自凸情況 139
5.1.1 加速隨機(jī)坐標(biāo)下降算法 140
5.1.2 方差縮減技巧基礎(chǔ)算法 147
5.1.3 加速隨機(jī)方差縮減方法 152
5.1.4 黑盒加速算法 158
5.2 各自非凸情況 160
5.3 非凸情況 166
5.3.1 隨機(jī)路徑積分差分估計(jì)子 167
5.3.2 沖量加速 173
5.4 帶約束問題 174
5.5 無窮情況 197
參考文獻(xiàn) 200
第 6 章 加速并行算法 202
6.1 加速異步算法 202
6.1.1 異步加速梯度下降算法 203
6.1.2 異步加速隨機(jī)坐標(biāo)下降算法 215
6.2 加速分布式算法 227
6.2.1 中心化模式 227
6.2.2 去中心化模式 232
參考文獻(xiàn) 243
第 7 章 總結(jié) 246
參考文獻(xiàn) 247
附錄 A 數(shù)學(xué)基礎(chǔ) 249
A.1 代數(shù)與概率 249
A.2 凸分析 250
A.3 非凸分析 257
參考文獻(xiàn) 259
縮略語表 260
索引 262