1. Abstract

• 解決分布式大規(guī)模稀疏優(yōu)化問題
• prox linear 算法的分布式實(shí)現(xiàn)
• GRock：并行貪心的coordinate-block descent算法

2. Introduction

2.1 稀疏優(yōu)化問題的兩個結(jié)構(gòu)特征：

1. 目標(biāo)函數(shù)可分
2. 數(shù)據(jù)近似正交性

2.2 ADMM的可擴(kuò)展性不好：

1. 將數(shù)據(jù)切分到不同節(jié)點(diǎn)并不能減少ADMM的計(jì)算時間
2. 因?yàn)閿?shù)據(jù)塊的增加會導(dǎo)致需要的迭代數(shù)增加
3. 小數(shù)據(jù)塊節(jié)省的時間會被迭代數(shù)的增加而抵消

2.3. 并行Coordinate descent：

1. Shotgun:Parallel coordinate descent for l1-regularized loss minimization
2. Scaling up coordinate descent algorithms for large l1 regularization problems. 并行CD算法的框架
3. Feature clustering for accelerating parallel coordinate descent. 迭代和隨機(jī)地選擇多個block，在正交條件下，本文的方法需要更少的迭代輪數(shù)，而且每輪迭代的開銷也幾乎不變

3. Problem formulation和數(shù)據(jù)并行

3.1 三種分布式策略

• 行block分布式
• 列block分布式
• 通用block分布式，行和列都切分

4. Prox-linear的分布式實(shí)現(xiàn)

• 分布式Lasso
• 分布式稀疏邏輯回歸

5. 并行貪心CD

4.1. CD

• 每輪迭代只更新一個coordinate(或者block)，其他保持不變
• Cyclic CD：輪流更新
• Random CD：隨機(jī)選擇coordinate，分析基于期望的目標(biāo)值
• Greedy CD. 選擇merit value最大的coordinates，比如梯度向量中絕對值最大的坐標(biāo)
• Mixed CD. 混合上面幾種

4.2. GRock

• 貪心的coordinate-block descent方法
• P個block中最好的坐標(biāo)被選中

4.3. GRock在稀疏優(yōu)化的優(yōu)點(diǎn)

• CD每次只更新很少的坐標(biāo)，因此與prox-linear和梯度算法相比，需要更多的迭代
• 但是稀疏優(yōu)化問題中，Greedy CD的坐標(biāo)選擇經(jīng)常發(fā)生在非0的區(qū)域

5. 計(jì)算復(fù)雜度分析

• 幾種算法每輪迭代的開銷基本差不多

6. Conclusion

• prox-linear算法的分布式實(shí)現(xiàn)
• GRock：解決大規(guī)模稀疏優(yōu)化問題
• 利用稀疏優(yōu)化問題的兩個結(jié)構(gòu)特點(diǎn)：目標(biāo)函數(shù)可分，數(shù)據(jù)大部分正交