In this paper, we consider solving the 2 -norm regularized empirical loss minimization problem which is arising ubiquitously in supervised machine learning and data mining problems:
We let f (w) = 1 n n i=1 φ i (w) and w ∈ R d be the linear predictor to be optimized. There are many applications falling into this formulation, such as classification, regression, and principal component analysis (PCA). In classification, given features x i ∈ R d and labels y i ∈ {1, -1}, we obtain Support Vector Machine (SVM) when we let φ i (w) = max{0, 1y i x T i w}. In regression, given features x i ∈ R d and response y i ∈ R, we have Ridge Regression problem if φ i (w) = (y ix T i w) 2 . Recently, [1], [2] showed that the problem of PCA can be solved through convex optimization. Supposing C = 1 n n i=1 x i x T i be normalized covariance matrix, [1] showed that approximating the principle component of A is equivalent to minimizing f (w) = 1 2 w T (µI -C)w-b T w given µ > 0 and b ∈ R d . Defining φ i (w) = 1 2 w T ((µ -λ 2 )I -x i x T i )w -b T w and µ > σ 1 (C) + λ 2 where σ 1 (C) denotes the largest singular value of C, it also falls into problem (1). In this case, f (w) is convex while each φ i (w) is probably non-convex.
Distributed machine learning and data mining methods are required to solve the problem (1) when the data are distributed over multiple machines. In [3], the authors proposed communication-efficient distributed dual coordinate ascent (CoCoA) for primal-dual distributed optimization. In each iteration, the CoCoA framework allows workers to optimize subproblems independently at first. After that, it calls "Reduce" operation to collect local solution from all workers, and updates global variable and broadcasts the up-to-date global variable to workers in the end. It uses stochastic dual coordinate ascent (SDCA) as the local solver which is one of the most successful methods proposed for solving the problem (1) [4], [5]. In [6], the authors proved that SDCA has linear convergence if the convex function φ i (w) is smooth, which is much faster than stochastic gradient descent (SGD). [7], [8] also proposed distributed SDCA and analyzed the tradeoff between computation and communication. [9], [10] accelerated the CoCoA by allowing for more aggressive updates, and proved that CoCoA has linear primal-dual convergence for the smooth convex problem and sublinear convergence for the non-smooth convex problem. However, there are two issues for these primal-dual distributed methods. Firstly, all of them use SDCA as the local solver. SDCA is not applicable when the dual problem is unknown, e.g. φ i is non-convex. Therefore, the applications of these primal-dual distributed methods are limited. Secondly, all of these methods assume that the workers have similar computing speed, which is not true in practice. Straggler problem is an unavoidable practical issue in the distributed data mining. Thus, the computing time of CoCoA and distributed SDCA is dependent on the slowest worker. Even if there is only one bad worker, they will work far slower than expectation.
In [11], [12], the authors proposed dual free stochastic dual coordinate ascent (dfSDCA). It was proved to admit similar convergence rate to SDCA while it did not rely on duality at all. However there is no distributed machine learning method using dfSDCA, and its convergence analysis is still unknown yet.
In this paper, we solve the above two challenging issues in previous primal-dual distributed machine learning methods by proposing novel Distributed Dual Free Stochastic Dual Coordinate Ascent (Dis-dfSDCA). We use dfSDCA as the local solver such that Dis-dfSDCA can be applied to the nonconvex problem easily. We alleviate the effect of straggler Fig. 1: Distributed asynchronous dual free stochastic dual coordinate ascent for parameter server framework. In iteration t, the server receives gradient message v k from worker k, and sends the up-to-date w t back to the worker k. Global variables in other workers are stale. For example worker 1 and K store stale global variables w t-2 and w t-5 respectively.
problem by allowing asynchronous communication between server and workers. As shown in Figure 1, the server does not wait and workers may store the stale global variable in the local. We also analyze the convergence rate of our method and prove that it admits linear convergence rate even if the individual losses (φ i ) are non-convex, as long as the sum of losses f is convex. Finally, we conduct simulation on the distributed system with straggler problem. Experimental results verify our theoretical conclusions and show that our method works well in practice.
To optimize the primal problem (1), we often derive and optimize its dual problem alternatively:
where φ * i is the convex conjugate function to φ i , A = [x 1 , x 2 , ...x n ] ∈ R d×n denotes data matrix and α ∈ R n denotes dual variable. We can use stochastic gradient descent (SGD) to optimize primal problem (1), however, there are always two issues: (1) SGD is too aggressive at the beginning of the optimization; (2) it does not have a clear stopping criterion. One of the biggest advantages of optimizing the dual problem is that we can keep tracking the duality gap G(α) to monitor the progress of optimization. Duality gap is defined as: G(α) = P (w(α)) -D(α), where P (w(α)) and D(α) denote objective values of primal problem and dual problem respectively. If w * is the optimal solution of primal problem (1) and α * is the optimal solution of dual problem (2), the primal-dual relation always holds that:
In [6], the authors proposed stochastic dual coordinate ascent (SDCA) to optimize the dual problem (2). The pseudocode of SDCA is presented in Algorithm 1. In iteration t, given sample i and other dual variables α j =i fixed, we maximize the following subproblem:
(4) e i denotes coordinate vector of size n, where element i is 1 and other elements are 0. In their paper, the authors proved that SDCA admits linear convergence rate for smooth loss, which is much faster than stochastic gradient descent (SGD).
An accelerated SDCA was also proposed in [5]. However, SDCA is not applicable when it is difficult to derive the dual problem, e.g. φ i are non-convex. Randomly sample i from {1, 2, ..., n};
4:
Find ∆α i to maximize the subproblem (4);
To address the limitation of SDCA, [11] proposes Dual Free Stochastic Coordinate Ascent (dfSDCA) which has similar convergence property to SDCA. The pseudocode of dfSDCA is presented in Algorithm 2. Although we keep vector α ∈ R n in the optimization, the derivation of dual problem is not necessary for dfSDCA. According to the update rule of α and w in the algorithm, the primal-dual relation (3) also holds for dfSDCA. The drawback of dfSDCA is that it is spaceconsuming to store α, whose space complexity O(nd). We can reduce it to O(n) if ∇φ i (w) can be written as ∇φ i (x T i w)x i . In [13], the authors accelerated dfSDCA by using non-uniform sampling strategy in each iteration and proved that it admits faster convergence.
Algorithm 2 Dual Free SDCA 1: Initialize dual variable α 0 = (α 0 0 , ..., α 0 n ) where ∀i, α 0 i ∈ R d , primal variable w 0 = w(α 0 ); 2: for t = 0, 1, 2, . . . , T -1 do
Randomly sample i from {1, 2, ..., n}; In this section, we propose Distributed Asynchronous Dual Free Stochastic Coordinate Ascent (Dis-dfSDCA) for distributed optimization. Dis-dfSDCA fits for any parameter server framework, where the star-shape network is used. We assume that there are n samples in the dataset, and they are evenly distributed over K workers. In worker k, there are n k samples. It is satisfied that n = K k=1 n k . Different from sequential dfSDCA, we split the update of dual variable and primal variable into different nodes. The pseudocodes of Dis-dfSDCA for server node and worker nodes are presented in Algorithm 3 and Algorithm 4 respectively.
The up-to-date global variable w ∈ R d is stored and updated on the server. Initially, w is set to be vector zero. At the beginning of each iteration, the server receives gradient message v k from arbitrary worker k and let v t = v k . Then it updates the global variable through:
Finally, it sends the up-to-date global variable back to the worker k for further computation. Asynchronous method is robust to straggler problem because it allows for updating the global variable when receiving from only one worker. However, if the w in the worker is too stale, it may lead the algorithm to diverge. Therefore, we induce two loops in our algorithm. Server broadcasts the latest global variable w to all workers after every T iterations. In this way, we prevent the problem of divergence and keep the advantage of asynchronous communication at the same time. Algorithm 3 summarizes the pseudocode on the server.
Update global variable w s+1,t+1 through: w s,t+1 ← w s,t -ηv s,t ; Send w s,t+1 back to worker k ; end for w s+1,0 = w s,T Broadcast the up-to-date global variable w s+1,0 to all workers. end for
In Algorithm 3, we use the update of vanilla dfSDCA in the server. [12] proposed accelerated dfSDCA by using "Catalyst" algorithm of [14]. It is proved to admit faster convergence rate by a constant factor. Our Algorithm 3 can also be extended to the accelerated version easily. In our paper, we only consider the vanilla version and analyze the convergence rate of our algorithm.
In the distributed optimization, workers are responsible for the gradient computation which is the main workload during the optimization. We take arbitrary worker k as an example. Dual variable α [k] ∈ R n k is only stored and updated in the worker k, each α i is corresponding to sample i. Initially, local variable α [k] is set to be vector zero. After receiving stale global variable w s,d(t) ∈ R d from the server, worker k computes the dual residue κ and updates local variable α i and gradient message v k for H iterations. Samples I t are randomly selected in the local dataset, and we set
Receive global variable w s,d(t) from server; Initialize gradient message:
Send gradient message v k to server; until Termination iteration, worker k selects a sample i randomly and computes the dual residue κ for coordinate i of the dual variable through:
Dual residue can also be viewed as the gradient in Stochastic Gradient Descent. When we obtain optimal dual variable α * and primal variable w * , κ should be 0. Therefore, it is satisfied that α * i = -∇φ i (w * ). Then worker k updates local dual variable α i and gradient message v k separately through:
Because there is only one α i in the cluster, it is always up-todate. After H iterations, the worker k sends gradient message v k to the server. From the update rule in our algorithm, it is easy to know that the well-known primal-dual relation in the equation ( 3) is always satisfied. The pseudocode of Dis-dfSDCA in worker node k is described in Algorithm 4.
In Algorithm 4, we use vanilla dfSDCA in the worker which samples with uniform distribution. There are also other sampling techniques proposed to accelerate dfSDCA. As per the sampling strategy in [11], [13], [12], [15], there are three options: uniform sampling, importance sampling, and adaptive sampling. In importance sampling strategy [12], it first computes the fixed probability distribution p i using smoothness parameter of each function φ i , then selects samples following this probability. In adaptive sampling strategy [13], it computes the adaptive probability distribution p i using dual residue κ for each sample every iteration, then selects samples following this probability. Both of them are proved to admit faster convergence than vanilla dfSDCA with uniform sampling. We only consider the uniform sampling strategy, and analyze its corresponding convergence rate in our paper. However, other sampling techniques are straightforward to be applied to our distributed method.
In this section, we provide the theoretical convergence analysis of Dis-dfSDCA. For the case of convex losses φ i , we prove that Dis-dfSDCA admits linear convergence rate. If losses φ i are non-convex, we also prove linear convergence rate as long as the sum-of-non-convex objectives f is convex.
We make the following assumptions for the primal problem (1) for further analysis. All of them are common assumptions in the theoretical analysis for the asynchronous stochastic methods.
Assumption 1 (Lipschitz Constant): We assume ∇φ i is Lipschitz continuous, and there is Lipschitz constant L such that ∀x, y ∈ R d :
We can also know that P is (L + λ)-smooth:
Assumption 2 (Maximum Time Delay): We assume that the maximum time delay of the global variable in each worker is upper bounded by τ , such that:
τ is relevant to the number of workers K in the system. We can also control τ through inner iteration T in our algorithm.
In this section, we assume that the losses φ i are convex, and prove that our method admits linear convergence.
Assumption 3 (Convexity): We assume losses φ i are convex, such that ∀x, y ∈ R d :
In our algorithm, dual variables α [1] , ..., α . For brevity, we write v s,t , w s,t and α s,t as v t , w t and α t . According to our algorithm, we know that:
where
). In our analysis, we also assume that there are no duplicate samples in I t . To analyze the convergence rate of our method, we need to prove the following Lemma 1 at first.
Lemma 1: Let w * be the global solution of P (w), and α * i = -∇φ i (w * ). Following the proof in [11], we define A t and B t as follows:
According to our algorithm, we can prove that A t+1 and B t+1 are upper bounded:
)
Theorem 1: Suppose losses φ i are convex and ∇φ i are Lipschitz continuous. Let w * be the optimal solution to P (w), and
We can prove that as long as:
the following inequality holds:
Proof sketch: 1 Substituting A t+1 and B t+1 according to Lemma 1, the following inequality holds that:
Adding the above inequality from t = 0 to t = T -1, we have:
where the inequality follows from Assumption 2 and ηL ≤ 1.
1 We provide the proof sketch here, please check the Appendix for details.
we have the following inequality:
Because C t ≥ 0, then we complete the proof that
Because ∇P (w) is Lipschitz continuous, we know that:
Theorem 2: We consider the outer iteration s, and write C t as C s,t . According to Algorithm 3, we know C s+1,0 = C s,T . Following Theorem 1 and applying (19) for S iterations, it is satisfied that:
In particular, to achieve E[P (w S,0 ) -P (w * )] ≤ ε, it suffices to set η = 1 4HLτ 2 +λn+2L and
From Theorem 1 and 2, we know that our Dis-dfSDCA admits linear convergence if losses φ i are convex. According to Theorem 2, we observe that τ affects the speed of our convergence, if τ → ∞, it may lead our algorithm to diverge. Therefore, it is important to keep τ within a reasonable bound. In our algorithm, τ is relevant to the number of workers and less than T . When we let H = 1 and τ = 0, S is relevant to O( L λ + n). It is compatible with the convergence analysis of sequential dfSDCA in [11].
In this section, we assume that the losses φ i are non-convex, while the sum-of-non-convex objectives f is convex. We also prove that Dis-dfSDCA admits linear convergence rate for this case. Firstly, we get the following Lemma 2.
Lemma 2: Let w * be optimal solution to P (w), and α * i = -∇φ i (w * ). Following the definition of A t and B t in Lemma 1, we prove that A t+1 and B t+1 are upper bounded:
Theorem 3: Suppose f is convex and ∇φ i is Lipschitz continuous. Let w * be the optimal solution to P (w), and
We can prove that as long as:
the following inequality holds:
Proof sketch: Substituting A t+1 and B t+1 according to Lemma 2, the following inequality holds that:
Adding the above inequality from t = 0 to t = T -1, we have:
where the inequality follows from Assumption 2 and ηL ≤ 1.
we have the following inequality:
Because C t ≥ 0, then we complete the proof that
Theorem 4: We consider the outer iteration s, and write C t as C s,t . According to Algorithm 3, we know C s+1,0 = C s,T . Following Theorem 3 and applying (29) for S iterations, it is satisfied that:
In particular, to achieve E[P (w S,0 ) -P (w * )] ≤ ε, it suffices to set η = λ 2 2HLτ 2 λ 2 +8HLτ 2 (L+λ) 2 +4λL 2 +nλ 3 and
From Theorems 3 and 4, we know that our Dis-dfSDCA admits linear convergence even if losses φ i are non-convex, as long as the sum-of-non-convex objectives is convex. Comparing Theorems 2 with 4, we can observe that our method needs more iterations to converge to the similar accuracy when φ i are non-convex. It is reasonable because non-convex problem is known to be harder to be optimized than convex problem. When we let H = 1 and τ = 0, S is relevant to O( L 2 λ 2 + n). It is also compatible with the convergence analysis of sequential dfSDCA in [11].
In this section, we conduct two simulated experiments on the distributed system with straggler problem. There are mainly three goals, firstly, we want to verify that our Dis-dfSDCA has linear convergence rate for the convex and smooth problem; secondly, we would like to make sure that our method has better speedup property than other primal-dual methods; thirdly, we would like to show that our method is also fit for non-convex losses.
Our algorithm is implemented using C++, and the point-topoint communication between worker and server is handled by openMPI [16]. We use Armadillo library [17] for efficient matrix computation. Experiments are performed on Amazon Web Services, and each node is a t2.medium instance which has two virtual CPUs. In our distributed system, we simulate the straggler problem by forcing one selected worker node to the delaying state for m times as long as the normal computing time of other normal workers with probability p.
In our experiments, we set p = 0.2 and m is selected from [0, 10] randomly. In practice, all nodes have a tiny possibility of being delayed. The setting in our experiments is to verify that our algorithm is robust to straggler problem, even in the extreme situation.
In our experiment, we optimize quadratic loss with 2 regularization term to solve binary classification problem:
where λ = 0.1. Datasets in our experiments are from LIBSVM [18]. Table I shows brief details of each dataset. In this problem, because ∇φ i (w) can be written as ∇φ i (x T i w), we just need to store α ∈ R n , and recover α ∈ R d×n through a i = x i αi . Therefore the space complexity is O(n).
We compare our method with CoCoA+ [9], which is the state-of-the-art distributed primal-dual optimization framework. We reimplement CoCoA+ framework using C++, and use SDCA as the local solver. Learning rate η in our method is selected from η = {1, 0.1, 0.001, 0.0001}.
1) Convergence of Duality Gap: We compare the duality gap convergence of compared methods in terms of time and epoch number respectively, where duality gap is well defined in [6]. Experimental results are presented in Figure 2. We distribute IJCNN1 dataset over 4 workers. Figures 2a in the . Results show that our method is faster than CoCoA+ method in both two cases. The reason is that CoCoA+ is affected by the straggler problem in the distributed system. We also optimize problem (36) with COVTYPE dataset using 8 workers, and RCV1 dataset using 16 workers. We can draw the similar conclusion from the results of other two datasets.
2) Speedup: In this section, we evaluate the scaling up ability of compared methods. The first row of Figure 3 presents the speedup of compared methods on IJCNN1 and COVTYPE datasets. Speedup is defined as follows:
Running time for serial computation Running time of using K workers (37)
Figure in the second row shows the convergence of duality gap on RCV1 on multiple machines. It is obvious that Dis-dfSDCA always converges faster than CoCoA+ when they have the same number of workers. Experimental results verify that Dis-dfSDCA has better speedup property than CoCoA+ when there is straggler problem.
In this experiment, we optimize the following convex objective, which is an essential step for principal component analysis in [1]:
We conduct the experiment on synthetic data and generate n = 500, 000 random vectors {x 1 , ..., x 500,000 } ∈ R 500 which are mean subtracted and normalized to have Euclidean norm
x i x T i denotes covariance matrix, b ∈ R d denotes a random vector and we let µ = 100, λ = 10 -4 in the experiment. Because each φ i is probably non-convex, CoCoA is not able to solve this problem. In this experiment, we compare with Distributed asynchronous SVRG [19].
In Figure 4, it is obvious that Dis-dfSDCA runs faster than Distributed SVRG when there are 4 workers. We can observe the similar phenomenon when there are 8 workers. This observation is reasonable because Distributed SVRG needs to compute two gradients in each inner iteration and full gradient in each outer iteration. Dis-dfSDCA is faster because it only needs to compute one gradient in each iteration. However, Dis-dfSDCA needs O(nd) space for storing α , because ∇φ i (w) cannot be written as ∇φ i (x T i w)x i in this problem.
In this paper, we proposed Distributed Asynchronous Dual Free Coordinate Ascent (Dis-dfSDCA) method for distributed machine learning. We addressed two challenging issues in previous primal-dual distributed optimization methods: firstly, Dis-dfSDCA does not rely on the dual formulation, and can be used to solve the non-convex problem; secondly, Dis-dfSDCA uses asynchronous communication and can be applied on the complicated distributed system where there is straggler problem. We also analyze the convergence rate of Dis-dfSDCA and prove linear convergence even if the loss functions are non-convex, as long as the sum of non-convex objectives is convex. We conduct experiments on the simulated distributed system with straggler problem, and all experimental results consistently verify our theoretical analysis.
Proof to Lemma 1 Proof sketch: In our proof, we suppose that there are no duplicate samples in I t . According to our algorithm, we know that:
where
). Following the proof in [11], we define A t and B t as follows:
Defining β = ηλn, so in iteration t, α t+1 i = (1 -β)α t i + β(-∇φ i (w d(t) )), we have: where the last inequality follows from that i∈It
Because α * i = -∇φ i (w * ), we have the following inequality:
where the first inequality follows from Lemma 4, the second inequality follows from Lemma 5, the third and the last inequalities follow from the Assumption 2. In addition, it also follows that:
We can know E w t -w * , v t is lower bounded that:
where the equality follows form that v t i is not relevant to the variable before w t+1 and the inequality follows from the convexity of P (w).
Proof sketch: We define C t+1 = c a A t+1 + c b B t+1 and set c a = 1 2λL , c b = 1. Inputting Lemma 1 in equation, we have:
where the last inequality follows from the L-smooth of P (w):
Adding the above inequality from t = 0 to t = T -1, we have that:
where the last inequality follows from Assumption 2 and ηL ≤ 1. If 2Hη 2 τ 2 + η 2 λn 2L + η 2 -η 2L ≤ 0 such that:
Therefore, we have:
We complete the proof.
Proof to Lemma 2 Proof sketch: As per the smoothness of φ i , we have:
We can also bound -E w t -w * , v t as follows:
-E w t -w * , v t = -HE w t -w * , ∇P (w where the first inequality follows from the strong convexity of P such that w t -w * , ∇P (w t ) ≥ P (w t ) -P (w * ) + λ 2 w t -w * 2 and P (w t ) -P (w * ) ≥ λ 2 w t -w * 2 . Defining γ = λ 2 and substituting above two inequalities into (42) and (43) respectively, we complete the proof. where γ = λ 2 . Adding the above inequality from t = 0 to t = T -1, we have that: