Most distributed machine learning (ML) systems store a copy of the model parameters locally on each machine to minimize network communication. In practice, in order to reduce synchronization waiting time, these copies of the model are not necessarily updated in lock-step, and can become stale. Despite much development in large-scale ML, the effect of staleness on the learning efficiency is inconclusive, mainly because it is challenging to control or monitor the staleness in complex distributed environments. In this work, we study the convergence behaviors of a wide array of ML models and algorithms under delayed updates. Our extensive experiments reveal the rich diversity of the effects of staleness on the convergence of ML algorithms and offer insights into seemingly contradictory reports in the literature. The empirical findings also inspire a new convergence analysis of SGD in non-convex optimization under staleness, matching the best-known convergence rate of O(1/\sqrt{T}). With the advent of big data and complex models, there is a growing body of works on scaling machine learning under synchronous and non-synchronous 1 distributed execution BID8 BID11 BID29 . These works, however, point to seemingly contradictory conclusions on whether non-synchronous execution outperforms synchronous counterparts in terms of absolute convergence, which is measured by the wall clock time to reach the desired model quality. For deep neural networks, BID2 ; BID8 show that fully asynchronous systems achieve high scalability and model quality, but others argue that synchronous training converges faster BID1 BID5 . The disagreement goes beyond deep learning models: ; BID49 ; BID26 ; BID31 ; BID41 empirically and theoretically show that many algorithms scale effectively under non-synchronous settings, but BID36 ; ; demonstrate significant penalties from asynchrony.The crux of the disagreement lies in the trade-off between two factors contributing to the absolute convergence: statistical efficiency and system throughput. Statistical efficiency measures convergence per algorithmic step (e.g., a mini-batch), while system throughput captures the performance of the underlying implementation and hardware. Non-synchronous execution can improve system throughput due to lower synchronization overheads, which is well understood BID1 BID4 BID2 . However, by allowing various workers to use stale versions of the model that do not always reflect the latest updates, non-synchronous systems can exhibit lower statistical efficiency BID1 BID5 . How statistical efficiency and system throughput trade off in distributed systems, however, is far from clear.The difficulties in understanding the trade-off arise because statistical efficiency and system throughput are coupled during execution in distributed environments. Non-synchronous executions are in general non-deterministic, which can be difficult to profile. Furthermore, large-scale experiments 2 RELATED WORK Staleness is reported to help absolute convergence for distributed deep learning in BID2 ; BID8 ; and has minimal impact on convergence BID31 BID6 BID51 BID32 . But BID1 ; BID5 show significant negative effects of staleness. LDA training is generally insensitive to staleness BID44 BID47 BID7 , and so is MF training BID48 BID33 BID4 BID49 . However, none of their evaluations quantifies the level of staleness in the systems. By explicitly controlling the staleness, we decouple the distributed execution, which is hard to control, from ML convergence outcomes.We focus on algorithms that are commonly used in large-scale optimization BID11 BID1 BID8 , instead of methods specifically designed to minimize synchronization BID39 BID43 BID20 . Non-synchronous execution has theoretical underpinning BID30 BID49 BID31 BID41 . Here we study algorithms that do not necessarily satisfy assumptions in their analyses. In this work, we study the convergence behaviors under delayed updates for a wide array of models and algorithms. Our extensive experiments reveal that staleness appears to be a key governing parameter in learning. Overall staleness slows down the convergence, and under high staleness levels the convergence can progress very slowly or fail. The effects of staleness are highly problem 10 Cosine similarity is closely related to the coherence measure in Definition 1. 11 Low gradient coherence during the early part of optimization is consistent with the common heuristics to use fewer workers at the beginning in asynchronous training. BID31 also requires the number of workers to follow DISPLAYFORM0 where K is the iteration number.dependent, influenced by model complexity, choice of the algorithms, the number of workers, and the model itself, among others. Our empirical findings inspire new analyses of non-convex optimization under asynchrony based on gradient coherence, matching the existing rate of O(1/ √ T ).Our findings have clear implications for distributed ML. To achieve actual speed-up in absolute convergence, any distributed ML system needs to overcome the slowdown from staleness, and carefully trade off between system throughput gains and statistical penalties. Many ML methods indeed demonstrate certain robustness against low staleness, which should offer opportunities for system optimization. Our results support the broader observation that existing successful nonsynchronous systems generally keep staleness low and use algorithms efficient under staleness.
Empirical and theoretical study of the effects of staleness in non-synchronous execution on machine learning algorithms.
{"src": "scitldr-AIC_train", "paper_id": "BylQV305YQ"}