We study the problem of minimizing the sum of a smooth convex function and a convex block-separable regularizer and propose a new randomized coordinate descent method, which we call ALPHA. Our method at every iteration updates a random subset of coordinates, following an arbitrary distribution. No coordinate descent methods capable to handle an arbitrary sampling have been studied in the literature before for this problem. ALPHA is a remarkably flexible algorithm: in special cases, it reduces to deterministic and randomized methods such as gradient descent, coordinate descent, parallel coordinate descent and distributed coordinate descent -- both in nonaccelerated and accelerated variants. The variants with arbitrary (or importance) sampling are new. We provide a complexity analysis of ALPHA, from which we deduce as a direct corollary complexity bounds for its many variants, all matching or improving best known bounds.

研究了平滑凸函数和凸块可分正则化项求和的最小化问题，提出了一种新的随机坐标下降算法，称为ALPHA，其维护了一个随机的坐标集，可以处理任意的采样，在特殊情况下可以变成梯度下降法，坐标下降法和并行坐标下降法等多种算法，还提供了复杂度分析，可以匹配或改善最佳已知边界。

任意采样协同下降I:算法与复杂度