Anytime Minibatch with Delayed Gradients
| Autor: | Stark C. Draper, Haider Al-Lawati |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
Mathematical optimization Speedup Computer Networks and Communications Computer science 05 social sciences Regret 010501 environmental sciences 01 natural sciences Range (mathematics) Variable (computer science) Rate of convergence Transmission (telecommunications) Computer Science - Distributed Parallel and Cluster Computing Asynchronous communication Optimization and Control (math.OC) 0502 economics and business Signal Processing FOS: Mathematics Distributed Parallel and Cluster Computing (cs.DC) 050207 economics Mathematics - Optimization and Control 0105 earth and related environmental sciences Information Systems |
| DOI: | 10.48550/arxiv.2012.08616 |
| Popis: | Distributed optimization is widely deployed in practice to solve a broad range of problems. In a typical asynchronous scheme, workers calculate gradients with respect to out-of-date optimization parameters while the master uses stale (i.e., delayed) gradients to update the parameters. While using stale gradients can slow the convergence, asynchronous methods speed up the overall optimization with respect to wall clock time by allowing more frequent updates and reducing idling times. In this paper, we present a variable per-epoch minibatch scheme called Anytime Minibatch with Delayed Gradients (AMB-DG). In AMB-DG, workers compute gradients in epochs of a fixed time while the master uses stale gradients to update the optimization parameters. We analyze AMB-DG in terms of its regret bound and convergence rate. We prove that for convex smooth objective functions, AMB-DG achieves the optimal regret bound and convergence rate. We compare the performance of AMB-DG with that of Anytime Minibatch (AMB) which is similar to AMB-DG but does not use stale gradients. In AMB, workers stay idle after each gradient transmission to the master until they receive the updated parameters from the master while in AMB-DG workers never idle. We also extend AMB-DG to the fully distributed setting. We compare AMB-DG with AMB when the communication delay is long and observe that AMB-DG converges faster than AMB in wall clock time. We also compare the performance of AMB-DG with the state-of-the-art fixed minibatch approach that uses delayed gradients. We run our experiments on a real distributed system and observe that AMB-DG converges more than two times. Comment: Accepted for publication in the IEEE Transaction on Signal and Information Processing over Networks |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|