凸優化:算法與復雜性 Convex Optimization: Algorithms and Complexity

Sébastien Bubeck

買這商品的人也買了...

商品描述

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

作者簡介

Sebastien Bubeck

是微軟Redmond研究院理論組的首席研究員,曾擔任COLT 2013、COLT 2014的聯席主席,
NIPS 2012、NIPS 2014、NIPS 2016、COLT 201 3、COLT 201 4 、COLT 201 5、COLT 201 6、
ICML 201 5、ICML 201 6、ALT2013、ALT 2014的項目委員會成員,也是COLT的指導委員會成員。
其研究興趣包括:機器學習、凸優化、統計網絡分析、隨機圖和隨機矩陣,
以及信息論在學習、優化和概率中的應用。

目錄大綱

目錄
譯者序
致謝
第1章緒論
1.1機器學習中的若干凸優化問題
1.2凸性的基本性質
1.3凸性的作用
1.4黑箱模型
1.5結構性優化
1.6結果的概述和免責聲明

第2章有限維的凸優化
2.1重心法
2.2橢球法
2.3 Vaidya割平面法
2.3.1體積障礙
2.3.2 Vaidya算法
2.3.3 Vaidya方法分析
2.3.4限制條件和體積障礙
2.4共軛梯度

第3章維度無關的凸優化
3.1 Lipschitz函數的投影次梯度下降
3.2光滑函數的梯度下降
3.3條件梯度下降
3.4強凸性
3.4.1強凸函數和upschitz函數
3.4.2強凸光滑函數
3.5下限
3.6幾何下降
3.6.1熱身賽:梯度下降的幾何學替代方案
3.6.2加速度
3.6.3幾何下降法
3.7 Nesterov加速梯度下降
3.7.1光滑強凸情況
3.7.2光滑的情況

第4章非歐氏空間幾乎維度無關的凸優化
4.1鏡像映射
4.2鏡像下降
4.3鏡像下降的標准設置
4.4惰性鏡像下降
4.5鏡像代理
4.6關於MD、DA和MP的向量場觀點

第5章超越黑箱模型
5.1光滑項與簡單非光滑項之和
5.2非光滑函數的光滑鞍點表示
5.2.1鞍點計算
5.2.2鞍點鏡像下降
5.2.3鞍點鏡像代理
5.2.4應用
5.3內點法
5.3.1障礙法
5.3.2牛頓法的傳統分析
5.3.3自和諧函數
5.3.4 v一自和諧障礙
5.3.5路徑跟踪方案
5.3 .6線性規劃和半定規劃的內點法

第6章凸優化與隨機性
6.1非光滑隨機優化
6.2光滑隨機優化與小批量SGD
6.3光滑函數與強凸函數的和
6.4隨機坐標下降
6.4.1坐標平滑優化的RCD算法
6.4.2用於光滑和強凸優化的RCD
6.5鞍點的隨機加速
6.6凸鬆弛與隨機取整
6.7基於隨機遊動的方法
參考文獻