Distributed optimization is vital in solving large-scale machine learning problems. A widely-shared feature of distributed optimization techniques is the requirement that all nodes complete their assigned tasks in each computational epoch before the system can proceed to the next epoch. In such settings, slow nodes, called stragglers, can greatly slow progress. To mitigate the impact of stragglers, we propose an online distributed optimization method called Anytime Minibatch. In this approach, all nodes are given a fixed time to compute the gradients of as many data samples as possible. The result is a variable per-node minibatch size. Workers then get a fixed communication time to average their minibatch gradients via several rounds of consensus, which are then used to update primal variables via dual averaging. Anytime Minibatch prevents stragglers from holding up the system without wasting the work that stragglers can complete. We present a convergence analysis and analyze the wall time performance. Our numerical results show that our approach is up to 1.5 times faster in Amazon EC2 and it is up to five times faster when there is greater variability in compute node performance. The advent of massive data sets has resulted in demand for solutions to optimization problems that are too large for a single processor to solve in a reasonable time. This has led to a renaissance in the study of parallel and distributed computing paradigms. Numerous recent advances in this field can be categorized into two approaches; synchronous Dekel et al. (2012) ; Duchi et al. (2012) ; Tsianos & Rabbat (2016) ; Zinkevich et al. (2010) and asynchronous Recht et al. (2011); Liu et al. (2015) . This paper focuses on the synchronous approach. One can characterize synchronization methods in terms of the topology of the computing system, either master-worker or fully distributed. In a master-worker topology, workers update their estimates of the optimization variables locally, followed by a fusion step at the master yielding a synchronized estimate. In a fully distributed setting, nodes are sparsely connected and there is no obvious master node. Nodes synchronize their estimates via local communications. In both topologies, synchronization is a key step.Maintaining synchronization in practical computing systems can, however, introduce significant delay. One cause is slow processing nodes, known as stragglers Dean et al. (2012) ; Yu et al. (2017) ; Tandon et al. (2017) ; Lee et al. (2018) ; Pan et al. (2017) ; S. Dutta & Nagpurkar (2018) . A classical requirement in parallel computing is that all nodes process an equal amount of data per computational epoch prior to the initiation of the synchronization mechanism. In networks in which the processing speed and computational load of nodes vary greatly between nodes and over time, the straggling nodes will determine the processing time, often at a great expense to overall system efficiency. Such straggler nodes are a significant issue in cloud-based computing systems. Thus, an important challenge is the design of parallel optimization techniques that are robust to stragglers.To meet this challenge, we propose an approach that we term Anytime MiniBatch (AMB). We consider a fully distributed topologyand consider the problem of stochastic convex optimization via dual averaging Nesterov (2009); Xiao (2010) . Rather than fixing the minibatch size, we fix the computation time (T ) in each epoch, forcing each node to "turn in" its work after the specified fixed time has expired. This prevents a single straggler (or stragglers) from holding up the entire network, while allowing nodes to benefit from the partial work carried out by the slower nodes. On the other hand, fixing the computation time means that each node process a different amount of data in each epoch. Our method adapts to this variability. After computation, all workers get fixed communication time (T c ) to share their gradient information via averaging consensus on their dual variables, accounting for the variable number of data samples processed at each node. Thus, the epoch time of AMB is fixed to T + T c in the presence of stragglers and network delays.We analyze the convergence of AMB, showing that the online regret achieves O( √m ) performance, which is optimal for gradient based algorithms for arbitrary convex loss Dekel et al. (2012) . In here, m is the expected sum number of samples processed across all nodes. We further show an upper bound that, in terms of the expected wall time needed to attain a specified regret, AMB is O( √ n − 1) faster than methods that use a fixed minibatch size under the assumption that the computation time follows an arbitrary distribution where n is the number of nodes. We provide numerical simulations using Amazon Elastic Compute Cloud (EC2) and show that AMB offers significant acceleration over the fixed minibatch approach. We proposed a distributed optimization method called Anytime MiniBatch. A key property of our scheme is that we fix the computation time of each distributed node instead of minibatch size. Therefore, the finishing time of all nodes are deterministic and does not depend on the slowest processing node. We proved the convergence rate of our scheme in terms of the expected regret bound. We performed numerical experiments using Amazon EC2 and showed our scheme offers significant improvements over fixed minibatch schemes. A AMB ALGORITHM In this section, we present additional details regarding the numerical results of Section 6 of the main paper as well as some new results. In Appendix I.1, we detail the network used in Section 6 and, for a point of comparison, implement the same computations in a master-worker network topology. In Appendix I.2, we model the compute times of the nodes as shifted exponential random variables and, under this model, present results contrasting AMB and FMB performance for the linear regression problem. In Appendix I.3 we present an experimental methodology for simulating a wide variety of straggler distributions in EC2. By running background jobs on some of the EC2 nodes we slow the foreground job of interest, thereby simulating a heavily-loaded straggler node. Finally, in Appendix I.4, we present another experiment in which we also induce stragglers by forcing the nodes to make random pauses between two consecutive gradient calculations. We present numerical results for both settings as well, demonstrating the even greater advantage of AMB versus FMB when compared to the results presented in Section 6.
Accelerate distributed optimization by exploiting stragglers.
{"src": "scitldr-AIC_train", "paper_id": "rkzDIiA5YQ"}