1. Abstract
- 解决分布式大规模稀疏优化问题
- prox linear 算法的分布式实现
- GRock：并行贪心的coordinate-block descent算法
2. Introduction
2.1 稀疏优化问题的两个结构特征：
- 目标函数可分
- 数据近似正交性
2.2 ADMM的可扩展性不好：
- 将数据切分到不同节点并不能减少ADMM的计算时间
- 因为数据块的增加会导致需要的迭代数增加
- 小数据块节省的时间会被迭代数的增加而抵消
2.3. 并行Coordinate descent：
- Shotgun:Parallel coordinate descent for l1-regularized loss minimization
- Scaling up coordinate descent algorithms for large l1 regularization problems. 并行CD算法的框架
- Feature clustering for accelerating parallel coordinate descent. 迭代和随机地选择多个block，在正交条件下，本文的方法需要更少的迭代轮数，而且每轮迭代的开销也几乎不变
3. Problem formulation和数据并行
3.1 三种分布式策略
- 行block分布式
- 列block分布式
- 通用block分布式，行和列都切分
4. Prox-linear的分布式实现
- 分布式Lasso
- 分布式稀疏逻辑回归
5. 并行贪心CD
4.1. CD
- 每轮迭代只更新一个coordinate(或者block)，其他保持不变
- Cyclic CD：轮流更新
- Random CD：随机选择coordinate，分析基于期望的目标值
- Greedy CD. 选择merit value最大的coordinates，比如梯度向量中绝对值最大的坐标
- Mixed CD. 混合上面几种
4.2. GRock
- 贪心的coordinate-block descent方法
- P个block中最好的坐标被选中
4.3. GRock在稀疏优化的优点
- CD每次只更新很少的坐标，因此与prox-linear和梯度算法相比，需要更多的迭代
- 但是稀疏优化问题中，Greedy CD的坐标选择经常发生在非0的区域
5. 计算复杂度分析
- 几种算法每轮迭代的开销基本差不多
6. Conclusion
- prox-linear算法的分布式实现
- GRock：解决大规模稀疏优化问题
- 利用稀疏优化问题的两个结构特点：目标函数可分，数据大部分正交
