	In this paper, we propose the Asynchronous Accelerated Nonuniform Randomized Block Coordinate Descent algorithm (A2BCD). We prove A2BCD converges linearly to a solution of the convex minimization problem at the same rate as NU_ACDM, so long as the maximum delay is not too large. This is the first asynchronous Nesterov-accelerated algorithm that attains any provable speedup. Moreover, we then prove that these algorithms both have optimal complexity. Asynchronous algorithms complete much faster iterations, and A2BCD has optimal complexity. Hence we observe in experiments that A2BCD is the top-performing coordinate descent algorithm, converging up to 4-5x faster than NU_ACDM on some data sets in terms of wall-clock time. To motivate our theory and proof techniques, we also derive and analyze a continuous-time analog of our algorithm and prove it converges at the same rate. In this paper, we propose and prove the convergence of the Asynchronous Accelerated Nonuniform Randomized Block Coordinate Descent algorithm (A2BCD), the first asynchronous Nesterovaccelerated algorithm that achieves optimal complexity. No previous attempts have been able to prove a speedup for asynchronous Nesterov acceleration. We aim to find the minimizer x * of the unconstrained minimization problem: DISPLAYFORM0 f (x) = f x (1) , . . . , x (n) ( FORMULA52 where f is σ-strongly convex for σ > 0 with L-Lipschitz gradient ∇f = (∇ 1 f, . . . , ∇ n f ). x ∈ R d is composed of coordinate blocks x (1) , . . . , x (n) . The coordinate blocks of the gradient ∇ i f are assumed L i -Lipschitz with respect to the ith block. That is, ∀x, h ∈ R d : DISPLAYFORM1 where P i is the projection onto the ith block of R d . LetL 1 n n i=1 L i be the average block Lipschitz constant. These conditions on f are assumed throughout this whole paper. Our algorithm can also be applied to non-strongly convex objectives (σ = 0) or non-smooth objectives using the black box reduction techniques proposed in BID1 . Hence we consider only the coordinate smooth, strongly-convex case. Our algorithm can also be applied to the convex regularized ERM problem via the standard dual transformation (see for instance Lin et al. (2014) ): DISPLAYFORM2 Hence A2BCD can be used as an asynchronous Nesterov-accelerated finite-sum algorithm.Coordinate descent methods, in which a chosen coordinate block i k is updated at every iteration, are a popular way to solve equation 1.1. Randomized block coordinate descent (RBCD, Nesterov (2012) ) updates a uniformly randomly chosen coordinate block i k with a gradient-descent-like step: DISPLAYFORM3 The complexity K( ) of an algorithm is defined as the number of iterations required to decrease the error E(f (x k ) − f (x * )) to less than (f (x 0 ) − f (x * )). Randomized coordinate descent has a complexity of K( ) = O(n(L/σ) ln(1/ )).Using a series of averaging and extrapolation steps, accelerated RBCD Nesterov (2012) improves RBCD's iteration complexity K( ) to O(n L /σ ln(1/ )), which leads to much faster convergence whenL σ is large. This rate is optimal when all L i are equal Lan & Zhou (2015) . Finally , using a special probability distribution for the random block index i k , the non-uniform accelerated coordinate descent method BID2 (NU_ACDM) can further decrease the complexity to O( DISPLAYFORM4 L i /σ ln(1/ )), which can be up to √ n times faster than accelerated RBCD, since some L i can be significantly smaller than L. NU_ACDM is the current state-of-the-art coordinate descent algorithm for solving equation 1.1.Our A2BCD algorithm generalizes NU_ACDM to the asynchronous-parallel case. We solve equation 1.1 with a collection of p computing nodes that continually read a shared-access solution vector y into local memory then compute a block gradient ∇ i f , which is used to update shared solution vectors (x, y, v) . Proving convergence in the asynchronous case requires extensive new technical machinery.A traditional synchronous-parallel implementation is organized into rounds of computation: Every computing node must complete an update in order for the next iteration to begin. However , this synchronization process can be extremely costly, since the lateness of a single node can halt the entire system. This becomes increasingly problematic with scale, as differences in node computing speeds, load balancing, random network delays, and bandwidth constraints mean that a synchronous-parallel solver may spend more time waiting than computing a solution.Computing nodes in an asynchronous solver do not wait for others to complete and share their updates before starting the next iteration. They simply continue to update the solution vectors with the most recent information available, without any central coordination. This eliminates costly idle time, meaning that asynchronous algorithms can be much faster than traditional ones, since they have much faster iterations. For instance, random network delays cause asynchronous algorithms to complete iterations Ω(ln(p)) time faster than synchronous algorithms at scale. This and other factors that influence the speed of iterations are discussed in Hannah & Yin (2017a) . However, since many iterations may occur between the time that a node reads the solution vector, and the time that its computed update is applied, effectively the solution vector is being updated with outdated information. At iteration k, the block gradient ∇ i k f is computed at a delayed iterateŷ k defined as 1 : DISPLAYFORM5 for delay parameters j(k, 1), . . . , j(k, n) ∈ N. Here j(k, i) denotes how many iterations out of date coordinate block i is at iteration k. Different blocks may be out of date by different amounts, which is known as an inconsistent read. We assume 2 that j(k, i) ≤ τ for some constant τ < ∞.Asynchronous algorithms were proposed in Chazan & Miranker (1969) to solve linear systems.General convergence results and theory were developed later in BID5 ; Bertsekas & Tsitsiklis (1997); Tseng et al. (1990); Luo & Tseng (1992; 1993); Tseng (1991) There is also a rich body of work on asynchronous SGD. In the distributed setting, Zhou et al. (2018) showed global convergence for stochastic variationally coherent problems even when the delays grow at a polynomial rate. In Lian et al. (2018) , an asynchronous decentralized SGD was proposed with the same optimal sublinear convergence rate as SGD and linear speedup with respect to the number of workers. In Liu et al. (2018) , authors obtained an asymptotic rate of convergence for asynchronous momentum SGD on streaming PCA, which provides insight into the tradeoff between asynchrony and momentum. In Dutta et al. (2018) , authors prove convergence results for asynchronous SGD that highlight the tradeoff between faster iterations and iteration complexity. Further related work is discussed in Section 4.
We prove the first-ever convergence proof of an asynchronous accelerated algorithm that attains a speedup.
{"src": "scitldr-AIC_train", "paper_id": "rylIAsCqYm"}