On the complexity of parallel coordinate descent

In this work we study the parallel coordinate descent method (PCDM) proposed by Richtarik and Taka [Parallel coordinate descent methods for big data optimization, Math. Program. Ser. A (2015), pp. 1-52] for minimizing a regularized convex function. We adopt elements from the work of Lu and Xiao [On the complexity analysis of randomized block-coordinate descent methods, Math. Program. Ser. A 152(1-2) (2015), pp. 615-642], and combine them with several new insights, to obtain sharper iteration complexity results for PCDM than those presented in [Richtarik and Taka, Parallel coordinate descent methods for big data optimization, Math. Program. Ser. A (2015), pp. 1-52]. Moreover, we show that PCDM is monotonic in expectation, which was not confirmed in [Richtarik and Taka, Parallel coordinate descent methods for big data optimization, Math. Program. Ser. A (2015), pp. 1-52], and we also derive the first high probability iteration complexity result where the initial levelset is unbounded.