Title :
Asynchronous incremental block-coordinate descent
Author :
Aytekin, Arda ; Feyzmahdavian, Hamid Reza ; Johansson, Mikael
Author_Institution :
Dept. of Autom. Control, R. Inst. of Technol. (KTH), Stockholm, Sweden
fDate :
Sept. 30 2014-Oct. 3 2014
Abstract :
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.
Keywords :
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;
Conference_Titel :
Communication, Control, and Computing (Allerton), 2014 52nd Annual Allerton Conference on
Conference_Location :
Monticello, IL
DOI :
10.1109/ALLERTON.2014.7028430