凸優(yōu)化 : 算法與復(fù)雜性

本書介紹了凸優(yōu)化中的主要復(fù)雜性定理及其相應(yīng)的算法。從黑箱優(yōu)化的基本理論出發(fā)，內(nèi)容材料是朝著結(jié)構(gòu)優(yōu)化和隨機(jī)優(yōu)化的新進(jìn)展。我們對(duì)黑箱優(yōu)化的介紹，深受Nesterov的開創(chuàng)性著作和Nemirovski講稿的影響，包括對(duì)切割平面方法的分析，以及（加速）梯度下降方案。我們還特別關(guān)注非歐幾里德的情況（相關(guān)算法包括Frank Wolfe、鏡像下降和對(duì)偶平均法），并討論它們?cè)跈C(jī)器中的相關(guān)性學(xué)習(xí)。我們慢慢的介紹了FISTA（優(yōu)化一個(gè)光滑項(xiàng)和一個(gè)簡(jiǎn)單的非光滑項(xiàng)的和）、鞍點(diǎn)鏡像代理（Nemirovski平滑替代Nesterov的光滑）和一個(gè)對(duì)內(nèi)點(diǎn)方法的簡(jiǎn)明描述。在隨機(jī)優(yōu)化中，我們討論了隨機(jī)梯度下降、小批量、隨機(jī)坐標(biāo)下降和次線性算法。我們還簡(jiǎn)單地討論了組合問題的凸松弛和隨機(jī)性對(duì)取整（四舍五入）解的使用，以及基于隨機(jī)游動(dòng)的方法。

塞巴斯蒂安·布貝克（Sébastien Bubeck）是微軟Redmond研究院理論組的首席研究員，曾擔(dān)任COLT 2013、COLT 2014的聯(lián)席主席，NIPS 2012、NIPS 2014、NIPS 2016、COLT 2013、COLT 2014、COLT 2015、COLT 2016、ICML 2015、ICML 2016、ALT 2013、ALT 2014的項(xiàng)目委員會(huì)成員，也是COLT的指導(dǎo)委員會(huì)成員。其研究興趣包括機(jī)器學(xué)習(xí)、凸優(yōu)化、統(tǒng)計(jì)網(wǎng)絡(luò)分析、隨機(jī)圖和隨機(jī)矩陣，以及信息論在學(xué)習(xí)、優(yōu)化和概率中的應(yīng)用。