TY - JOUR

T1 - On the complexity of parallel coordinate descent

AU - Tappenden, Rachael

AU - Takáč, Martin

AU - Richtárik, Peter

N1 - Funding Information:
The work of this author was supported by the NSF Grants CCF-1618717 and CMMI-1663256. The work of all authors was supported by the EPSRC grant EP/I017127/1 (Mathematics for Vast Digital Resources) and by the Centre for Numerical Algorithms and Intelligent Software (funded by EPSRC grant EP/G036136/1 and the Scottish Funding Council).
Publisher Copyright:
© 2017 The Author(s). Published by Informa UK Limited, trading as Taylor & Francis Group.

PY - 2018/3/4

Y1 - 2018/3/4

N2 - In this work we study the parallel coordinate descent method (PCDM) proposed by Richtárik and Takáč [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 [Richtárik and Takáč, 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 [Richtárik and Takáč, 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.

AB - In this work we study the parallel coordinate descent method (PCDM) proposed by Richtárik and Takáč [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 [Richtárik and Takáč, 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 [Richtárik and Takáč, 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.

KW - block coordinate descent

KW - composite minimization

KW - convex optimization

KW - iteration complexity

KW - monotonic algorithm

KW - parallelization

KW - rate of convergence

KW - unbounded levelset

UR - http://www.scopus.com/inward/record.url?scp=85032803982&partnerID=8YFLogxK

U2 - 10.1080/10556788.2017.1392517

DO - 10.1080/10556788.2017.1392517

M3 - Article

AN - SCOPUS:85032803982

VL - 33

SP - 372

EP - 395

JO - Optimization Methods and Software

JF - Optimization Methods and Software

SN - 1055-6788

IS - 2

ER -