On optimal probabilities in stochastic coordinate descent methods

详细信息    查看全文

• 作者：Peter Richtárik ; Martin Takáč
• 刊名：Optimization Letters
• 出版年：2016
• 出版时间：August 2016
• 年：2016
• 卷：10
• 期：6
• 页码：1233-1243
• 全文大小：502 KB
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Optimization
  Operation Research and Decision Theory
  Numerical and Computational Methods in Engineering
  Numerical and Computational Methods
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1862-4480
• 卷排序：10

文摘

We propose and analyze a new parallel coordinate descent method—NSync—in which at each iteration a random subset of coordinates is updated, in parallel, allowing for the subsets to be chosen using an arbitrary probability law. This is the first method of this type. We derive convergence rates under a strong convexity assumption, and comment on how to assign probabilities to the sets to optimize the bound. The complexity and practical performance of the method can outperform its uniform variant by an order of magnitude. Surprisingly, the strategy of updating a single randomly selected coordinate per iteration—with optimal probabilities—may require less iterations, both in theory and practice, than the strategy of updating all coordinates at every iteration.KeywordsCoordinate descentArbitrary samplingFirst order methodComplexity