Shotgun: Parallel CD for L1-LR

1. Abstract

单机多核并行，near-linear speedup

2. Intro

  • L1 regularization适合sparse高维大数据
  • CD: 本文称为Shooting，每轮迭代只更新一个坐标
  • 并行SGD：单机多核 and 分布式，切分samples，但是L1应用一般feature比sample数量多，因此切分数据不合适
  • 因此选用一种相反的方式，切分features，并行化L1-regularized CD
  • Shotgun：多核算法，让P个维度并行地更新
  • 证明了Shotgun的convergence bound，near-linear in P，同时提供了P的最佳的估计

3. Parallel CD

  • 从所有weights中平均地选择P个weights，然后用同样的更新规则更新它们
  • 并行地更新可能增加divergence的风险。如果features不相关，那么并行更新会加快收敛；如果features相关，那么并行更新就可能会增加objective value

4. Experiment

  • Shotgun的实现：pathwise 优化方法；atomic compare-and-swap opearation
  • 对LR，比较Shotgun和SGD variants
  • Shotgun CDN(Coordinate Descent Newton)的实现：使用backtrack line-search策略寻找step size
  • SGD适合大数据(large n)，Shotgun适合大维度(large d)
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容