Asynchronous incremental block-coordinate descent
2014 (English)In: 52nd Annual Allerton Conference on Communication, Control, and Computing (Allerton), IEEE conference proceedings, 2014, 19-24 p.Conference paper (Refereed)
This paper studies a flexible algorithm for minimizing a sum of component functions, each of which depends on a large number of decision variables. Such formulations appear naturally in “big data” applications, where each function describes the loss estimated using the data available at a specific machine, and the number of features under consideration is huge. In our algorithm, a coordinator updates a global iterate based on delayed partial gradients of the individual objective functions with respect to blocks of coordinates. Delayed incremental gradient and delayed coordinate descent algorithms are obtained as special cases. Under the assumption of strong convexity and block coordinate-wise Lipschitz continuous partial gradients, we show that the algorithm converges linearly to a ball around the optimal value. Contrary to related proposals in the literature, our algorithm is delay-insensitive: it converges for any bounded information delay, and its step-size parameter can be chosen independently of the maximum delay bound.
Place, publisher, year, edition, pages
IEEE conference proceedings, 2014. 19-24 p.
Big Data, gradient methods, asynchronous incremental block-coordinate descent, big data applications, block coordinate-wise Lipschitz continuous partial gradients;bounded information delay, component function sum minimization, delayed partial gradients, global iterate, maximum delay bound, step-size parameter, Algorithm design and analysis, Color, Convergence, Delays, Servers, Standards, Vectors
IdentifiersURN: urn:nbn:se:kth:diva-164288DOI: 10.1109/ALLERTON.2014.7028430ScopusID: 2-s2.0-84946692347OAI: oai:DiVA.org:kth-164288DiVA: diva2:805300
52nd Annual Allerton Conference on Communication, Control, and Computing (Allerton),Sept. 30 2014-Oct. 3 2014,Monticello, IL
QC 201505112015-04-152015-04-152015-05-11Bibliographically approved