On the complexity of parallel coordinate descent. (4th March 2018)

• Record Type: Journal Article
• Authors: Tappenden, Rachael; Takáč, Martin; Richtárik, Peter
• Is Part Of: Optimization methods and software. Volume 33:Number 2(2018)
• Page Start: 372
• Page End: 395
• Publication Date: 2018-03-04
• Subjects: block coordinate descent -- parallelization -- iteration complexity -- composite minimization -- convex optimization -- rate of convergence -- unbounded levelset -- monotonic algorithm; 65K05 -- 90C05 -- 90C06 -- 90C25; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2017.1392517
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : 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.