123,123,123

在人工智能與大數(shù)據(jù)時(shí)代，優(yōu)化算法已成為機(jī)器學(xué)習(xí)與數(shù)據(jù)科學(xué)的核心支柱。本書以獨(dú)特的應(yīng)用視角，將抽象的數(shù)學(xué)理論與實(shí)際工程問題緊密結(jié)合，為讀者架起了一座從理論到實(shí)踐的橋梁。
本書由優(yōu)化領(lǐng)域權(quán)威學(xué)者Stephen J. Wright和Benjamin Recht撰寫，旨在為讀者提供一本條理清晰、系統(tǒng)全面的優(yōu)化技術(shù)指南，尤其聚焦數(shù)據(jù)科學(xué)與機(jī)器學(xué)習(xí)領(lǐng)域的核心優(yōu)化技術(shù)。書中詳細(xì)闡述了基本優(yōu)化算法，并分析了它們的收斂性和復(fù)雜度。全書共11章，第1章通過典型案例闡釋優(yōu)化在現(xiàn)代數(shù)據(jù)分析中的應(yīng)用；第2～10章深入剖析多種核心算法，包括加速梯度法、隨機(jī)梯度法（機(jī)器學(xué)習(xí)的核心算法）、坐標(biāo)下降法（高效處理高維問題的利器）、簡(jiǎn)單約束問題的梯度法、具有非平滑項(xiàng)的凸優(yōu)化問題的理論和算法，以及約束優(yōu)化問題的對(duì)偶方法；第11章拓展至深度學(xué)習(xí)與控制領(lǐng)域的梯度計(jì)算方法（如自動(dòng)微分、反向傳播的優(yōu)化視角）。

前言
優(yōu)化公式和算法長期以來一直在數(shù)據(jù)分析和機(jī)器學(xué)習(xí)中發(fā)揮著核心作用. 極大似然的概念可以追溯到18世紀(jì)后期高斯和拉普拉斯的研究，這類問題推動(dòng)了20世紀(jì)下半葉無約束優(yōu)化問題研究的發(fā)展. Mangasarian在20世紀(jì)60年代發(fā)表的關(guān)于使用線性規(guī)劃進(jìn)行模式分離的論文，在機(jī)器學(xué)習(xí)這一學(xué)科誕生初期就明確了機(jī)器學(xué)習(xí)和優(yōu)化之間的聯(lián)系. 在20世紀(jì)90年代，優(yōu)化技術(shù)（尤其是二次規(guī)劃和對(duì)偶）是支持向量機(jī)和核學(xué)習(xí)發(fā)展的關(guān)鍵. 在19972010年間，正則化/稀疏優(yōu)化、變量選擇和壓縮感知之間出現(xiàn)了許多協(xié)同效應(yīng). 在當(dāng)前深度學(xué)習(xí)時(shí)代，兩種優(yōu)化技術(shù)，即隨機(jī)梯度和自動(dòng)微分（又名反向傳播）是十分重要的.
本書是對(duì)連續(xù)優(yōu)化基礎(chǔ)知識(shí)的介紹，著重講解與數(shù)據(jù)分析和機(jī)器學(xué)習(xí)有關(guān)的技術(shù). 我們主要（但不完全）針對(duì)凸問題討論了基本算法，并分析了它們的收斂性和復(fù)雜度. 第1章概述了優(yōu)化在現(xiàn)代數(shù)據(jù)分析中的應(yīng)用. 第2～10章討論了梯度法，包括加速梯度法和隨機(jī)梯度法、坐標(biāo)下降法、簡(jiǎn)單約束問題的梯度法、具有凸非平滑項(xiàng)的優(yōu)化問題的理論和算法，以及約束優(yōu)化問題的對(duì)偶方法. 第11章從多個(gè)角度探討了深度學(xué)習(xí)和控制領(lǐng)域中出現(xiàn)的函數(shù)梯度計(jì)算方法. 本書適合作為高年級(jí)本科生或低年級(jí)研究生一個(gè)季度或一個(gè)學(xué)期的課程教材. 我們和同事已經(jīng)在低年級(jí)研究生的課程中廣泛使用了本書內(nèi)容的初稿.
本書的寫作可追溯至2010年左右，當(dāng)時(shí)我們著手改革優(yōu)化課程體系，試圖在實(shí)用優(yōu)化技術(shù)和對(duì)優(yōu)化算法的非漸近性分析之間建立平衡. 那時(shí)，優(yōu)化算法分析的風(fēng)格正在轉(zhuǎn)變?yōu)楦訌?qiáng)調(diào)最壞情況的復(fù)雜性. 但人們更多的是根據(jù)算法的最壞情況界限來評(píng)估算法的優(yōu)劣，而不是考慮它們?cè)趹?yīng)用科學(xué)實(shí)踐中的表現(xiàn). 本書介于分析和實(shí)踐之間.
從威斯康星大學(xué)的CS726和CS730課程開始，我們著手撰寫講義、習(xí)題和本書初稿. Benjamin 2013年到加州大學(xué)伯克利分校后，這些講義成為EECS227C課程的核心內(nèi)容. 本書的內(nèi)容很大程度上來自優(yōu)化算法理論的前沿發(fā)展成果. 例如，在文中的多個(gè)部分，我們利用了Lieven Vandenberghe多年來為加州大學(xué)洛杉磯分校ECE236C課程編寫并經(jīng)過多年完善的優(yōu)秀課件. 我們對(duì)加速法的介紹反映了將優(yōu)化算法視為動(dòng)態(tài)系統(tǒng)的趨勢(shì)，并且深受與Laurent Lessard和 Andrew Packard合作研究的影響. 在選擇本書要包含的內(nèi)容時(shí)，我們盡量不被那些在實(shí)踐中未廣泛使用的方法所干擾，同時(shí)強(qiáng)調(diào)理論如何指導(dǎo)應(yīng)用研究人員選擇和設(shè)計(jì)算法.
我們感謝許多其他同事，他們的意見優(yōu)化了本書的內(nèi)容. 在我們于2013年秋季在西蒙斯研究所大數(shù)據(jù)計(jì)劃的訓(xùn)練營中介紹了有關(guān)優(yōu)化算法的綜述后，Moritz Hardt最初啟發(fā)我們編寫本書. 他隨后就本書初稿的呈現(xiàn)方式和組織結(jié)構(gòu)提供了反饋. Ashia Wilson曾是 Benjamin教授EECS227C課程的助教，她的意見和筆記在多個(gè)方面幫助我們厘清了教學(xué)信息. 最近，Martin Wainwright教授了EECS227C課程并提供了寶貴的反饋，Jelena
Diakonikolas在教授 CS726課程后對(duì)前幾章進(jìn)行了校正. André Wibisono提供了關(guān)于加速梯度法的見解，Ching?pei Lee提供了關(guān)于坐標(biāo)下降法的有用建議. 我們還要感謝在威斯康星大學(xué)選修CS726和CS730課程以及在加州大學(xué)伯克利分校學(xué)習(xí) EECS227C課程的眾多學(xué)生，他們發(fā)現(xiàn)了書中的錯(cuò)別字，試做了課后習(xí)題，他們的支持讓教授這門課程變得非常愉快. 最后，我們要感謝西蒙斯研究所多次給予我們的支持，包括2017年秋季，我們兩人共同參與了西蒙斯優(yōu)化領(lǐng)域的研究項(xiàng)目.

斯蒂芬·J. 賴特
（Stephen J. Wright）
現(xiàn)任威斯康星大學(xué)麥迪遜分校George B. Dantzig教授、 Sheldon Lubar講席教授，以及 Amar和Balinder Sohi計(jì)算機(jī)科學(xué)教授，同時(shí)擔(dān)任威斯康星州發(fā)現(xiàn)研究所（Wisconsin Institute for Discovery）的研究員。他主要研究計(jì)算優(yōu)化及其在數(shù)據(jù)科學(xué)和科學(xué)工程其他領(lǐng)域的應(yīng)用。他是美國工業(yè)與應(yīng)用數(shù)學(xué)學(xué)會(huì)（SIAM）會(huì)士，曾獲2014年IEEE W. R. G. Baker杰出論文獎(jiǎng)、2020年INFORMS優(yōu)化學(xué)會(huì)Khachiyan終身成就獎(jiǎng)以及2020年NeurIPS時(shí)間檢驗(yàn)獎(jiǎng)。他著有多部?jī)?yōu)化領(lǐng)域經(jīng)典教材與參考書，包括Primal Dual Interior-Point Methods（1987）和Numerical Optimization（2006）。
本杰明·雷希特
（Benjamin Recht）
加州大學(xué)伯克利分校電氣工程與計(jì)算機(jī)科學(xué)系副教授。其研究團(tuán)隊(duì)致力于通過運(yùn)用優(yōu)化、統(tǒng)計(jì)和動(dòng)力系統(tǒng)的數(shù)學(xué)工具，提升機(jī)器學(xué)習(xí)系統(tǒng)在動(dòng)態(tài)不確定環(huán)境中的穩(wěn)健性。他曾獲總統(tǒng)科學(xué)家與工程師早期職業(yè)獎(jiǎng)、Alfred P. Sloan研究獎(jiǎng)、2012年SIAM/MOS拉格朗日連續(xù)優(yōu)化獎(jiǎng)、2014年Jamon獎(jiǎng)、2015年William O. Baker研究倡議獎(jiǎng)，以及2017年和2020年NeurIPS時(shí)間檢驗(yàn)獎(jiǎng)。

張璐，2021年7月至今于愛彼迎任算法工程師，此前曾在Facebook、eBay任軟件工程師。2011年12月于密歇根州立大學(xué)獲電子工程專業(yè)理學(xué)碩士學(xué)位，2009年7月于中國科學(xué)技術(shù)大學(xué)電子信息工程學(xué)院獲工學(xué)學(xué)士學(xué)位。

目錄
譯者序
前言
第1章　概述 1
1.1　數(shù)據(jù)分析和優(yōu)化 1
1.2　最小二乘法 3
1.3　矩陣因子分解問題 4
1.4　支持向量機(jī) 5
1.5　邏輯回歸 8
1.6　深度學(xué)習(xí) 9
1.7　重點(diǎn) 11
注釋和參考 12
第2章　平滑優(yōu)化的基礎(chǔ) 13
2.1　優(yōu)化問題的解的分類 13
2.2　泰勒定理 14
2.3　刻畫平滑函數(shù)的最小值 16
2.4　凸集和函數(shù) 18
2.5　強(qiáng)凸函數(shù) 20
注釋和參考 22
習(xí)題 22
第3章　下降法 24
3.1　下降方向 24
3.2　最速下降法 25
3.2.1　一般情況 26
3.2.2　凸函數(shù)情況 27
3.2.3　強(qiáng)凸函數(shù)情況 28
3.2.4　收斂速率的比較 30
3.3　下降法：收斂性 31
3.4　線搜索法：方向選擇 33
3.5　線搜索法：步長選擇 35
3.6?收斂到近似的二階必要點(diǎn) 40
3.7　鏡像下降 42
3.8　KL和PL屬性 47
注釋和參考 48
習(xí)題 48
第4章　使用動(dòng)量的梯度法 51
4.1　來自微分方程的啟發(fā) 52
4.2　Nesterov法：凸二次方程 53
4.3　強(qiáng)凸函數(shù)的收斂性 58
4.4　弱凸函數(shù)的收斂性 61
4.5　共軛梯度法 64
4.6　收斂速率的下界 66
注釋和參考 67
習(xí)題 68
第5章　隨機(jī)梯度法 71
5.1　示例與啟發(fā) 72
5.1.1　噪聲梯度 72
5.1.2　增量梯度法 73
5.1.3　分類和感知器 73
5.1.4　經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化 74
5.2　隨機(jī)性和步長：深入分析 75
5.2.1　示例：計(jì)算均值 76
5.2.2　隨機(jī)Kaczmarz法 77
5.3　收斂分析的關(guān)鍵假設(shè) 80
5.3.1　案例1：有界梯度(Lg=0) 81
5.3.2　案例2：隨機(jī)Kaczmarz
(B=0, Lg=0) 81
5.3.3　案例3：加性高斯噪聲 82
5.3.4　案例4：增量梯度 82
5.4　收斂分析 83
5.4.1　案例1：Lg=0 84
5.4.2　案例2：B=0 86
5.4.3　案例3：B和Lg都非零 87
5.5　實(shí)施方面的問題 89
5.5.1　輪次 89
5.5.2　迷你批量處理 89
5.5.3　使用動(dòng)量加速 90
注釋和參考 90
習(xí)題 91
第6章　坐標(biāo)下降法 95
6.1　機(jī)器學(xué)習(xí)中的坐標(biāo)下降法 96
6.2　平滑凸函數(shù)的坐標(biāo)下降法 98
6.2.1　利普希茨常數(shù) 98
6.2.2　隨機(jī)坐標(biāo)下降法：有放回
抽樣 99
6.2.3　循環(huán)坐標(biāo)下降法 105
6.2.4　隨機(jī)排列坐標(biāo)下降法：無放回抽樣 107
6.3　塊坐標(biāo)下降法 107
注釋和參考 109
習(xí)題 110
第7章　約束優(yōu)化的一階方法 112
7.1　最優(yōu)性條件 112
7.2　歐幾里得投影 114
7.3　投影梯度算法 116
7.3.1　一般情況：一種短步法 117
7.3.2　一般情況：回溯法 118
7.3.3　平滑強(qiáng)凸情形 119
7.3.4　動(dòng)量變體 120
7.3.5　其他搜索方向 120
7.4　條件梯度（Frank-Wolfe）法 121
注釋和參考 123
習(xí)題 124
第8章　非平滑函數(shù)和次梯度 126
8.1　次梯度和次微分 127
8.2　次微分和方向?qū)?shù) 131
8.3　次微分運(yùn)算 134
8.4　凸集和凸約束優(yōu)化 137
8.5　復(fù)合非平滑函數(shù)的最優(yōu)性條件 139
8.6　近端算子和莫羅包絡(luò) 141
注釋和參考 143
習(xí)題 143
第9章　非平滑優(yōu)化方法 145
9.1　次梯度下降 146
9.2　次梯度法 148
9.3　正則化優(yōu)化的近端梯度法 151
9.4　結(jié)構(gòu)化非平滑函數(shù)的近端坐標(biāo)
下降法 156
9.5　近端點(diǎn)法 158
注釋和參考 159
習(xí)題 159
第10章　對(duì)偶性和算法 161
10.1　二次懲罰函數(shù) 161
10.2　拉格朗日函數(shù)和對(duì)偶性 162
10.3　一階最優(yōu)性條件 165
10.4　強(qiáng)對(duì)偶 168
10.5　對(duì)偶算法 170
10.5.1　對(duì)偶次梯度 170
10.5.2　增廣拉格朗日函數(shù)法 170
10.5.3　交替方向乘數(shù)法 172
10.6　對(duì)偶算法的一些應(yīng)用 173
10.6.1　共識(shí)優(yōu)化 173
10.6.2　效用最大化 175
10.6.3　線性和二次規(guī)劃 176
注釋和參考 177
習(xí)題 178
第11章　微分和伴隨 179
11.1　向量函數(shù)嵌套組合的鏈?zhǔn)椒▌t 179
11.2　伴隨法 181
11.3　深度學(xué)習(xí)中的伴隨 182
11.4　自動(dòng)微分 183
11.5　通過拉格朗日函數(shù)和隱函數(shù)定理
推導(dǎo)185
11.5.1　漸進(jìn)式函數(shù)的約束優(yōu)化
　公式 186
11.5.2　無約束和約束公式的一般
　觀點(diǎn) 187
11.5.3　擴(kuò)展：控制 188
注釋和參考 188
習(xí)題 189
附　　錄　一些背景信息 190
參考文獻(xiàn) 209

你還可能感興趣

我要評(píng)論