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

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

塞巴斯蒂安·布貝克（Sébastien Bubeck）是微軟Redmond研究院理論組的首席研究員，曾擔任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的項目委員會成員，也是COLT的指導(dǎo)委員會成員。其研究興趣包括機器學(xué)習(xí)、凸優(yōu)化、統(tǒng)計網(wǎng)絡(luò)分析、隨機圖和隨機矩陣，以及信息論在學(xué)習(xí)、優(yōu)化和概率中的應(yīng)用。