PaperlayerView exact revision on arXiv

Source-linked AI summary

Distributed Learning over Unreliable Networks

Chen Yu, Hanlin Tang, Cedric Renggli, Simon Kassing, Ankit Singla, Dan Alistarh, Ce Zhang, Ji Liu

arXiv:1810.07766v4cs.DCcs.LG

TL;DR

The paper asks whether distributed learning can converge when worker–server communications may be dropped. It adapts Reduce-Scatter and All-Gather for unreliable links and analyzes the resulting algorithm. Under certain parameter values, the analysis gives the same convergence rate as standard algorithms, while the paper also describes a potential benefit for colocated applications.

  • Problem

    The paper asks whether distributed learning can converge, and at what rate, when communication between workers and servers can be dropped.

    Source: §1 · p. 2

  • Method

    RPS uses uniform random subsets of machines for block averaging in Reduce-Scatter and for receiving updates in All-Gather.

    Source: §1 · p. 3

  • Results

    For certain parameter values, RPS with unreliable communication admits the same convergence rate as standard algorithms.

    Source: §5 · p. 8

  • Takeaways & Limitations

    Lost model updates can allow colocated applications to receive prioritized network traffic, potentially lowering their latency at the expense of some update losses.

    Source: §7 · p. 11

    With a constant learning rate, the algorithm converges only to a ball centered at a critical point; a decayed learning rate can yield convergence to a critical point at the same rate.

    Source: §5 · p. 10

Abstract

from arXiv · show

Most of today's distributed machine learning systems assume {\em reliable networks}: whenever two machines exchange information (e.g., gradients or models), the network should guarantee the delivery of the message. At the same time, recent work exhibits the impressive tolerance of machine learning algorithms to errors or noise arising from relaxed communication or synchronization. In this paper, we connect these two trends, and consider the following question: {\em Can we design machine learning systems that are tolerant to network unreliability during training?} With this motivation, we focus on a theoretical problem of independent interest---given a standard distributed parameter server architecture, if every communication between the worker and the server has a non-zero probability $p$ of being dropped, does there exist an algorithm that still converges, and at what speed? The technical contribution of this paper is a novel theoretical analysis proving that distributed learning over unreliable network can achieve comparable convergence rate to centralized or distributed learning over reliable networks. Further, we prove that the influence of the packet drop rate diminishes with the growth of the number of \textcolor{black}{parameter servers}. We map this theoretical result onto a real-world scenario, training deep neural networks over an unreliable network layer, and conduct network simulation to validate the system improvement by allowing the networks to be unreliable.

1 Introduction

The paper studies distributed learning when worker–server communications can be dropped, and introduces RPS, which adapts Reduce-Scatter and All-Gather to unreliable links. It analyzes RPS theoretically and uses network simulations to study its effect on learning and a colocated Web service.

1 Introduction

  • The paper studies distributed learning when communication between workers and servers has a nonzero probability of being dropped.The illustrated setting has three parameter servers and four workers; each server serves a model partition, and each worker holds a full-model replica.Source: §1 · p. 2, Figure 1 · p. 2
  • RPS averages each model block over a uniform random subset of machines during Reduce-Scatter, then sends the average to a uniform random subset during All-Gather.Machines omitted from Reduce-Scatter do not contribute; machines omitted from All-Gather do not receive that block's update.Source: §1 · p. 3
  • The main technical contribution is a convergence analysis of RPS for this faulty communication model.The authors describe the analysis as novel to the best of their knowledge.Source: §1 · p. 3
  • With a 10% learning-traffic drop rate, network simulations find up to 1.2× faster emulated Web service performance without affecting convergence rates across a range of machine-learning applications.The applications cited include image classification and natural language processing.Source: §1 · p. 3

2 Related Work

Prior work studies distributed learning through system designs, communication strategies, and robustness settings. This paper focuses on unreliable communication and analyzes a model intended to cover both Parameter Server and AllReduce strategies.

2 Related Work

  • Distributed-learning research includes optimization and scaling methods, communication-saving approaches, asynchronous training, and Byzantine-robust algorithms.Examples include sparse methods for reducing communication and work on delay-tolerant asynchronous learning.Source: §2 · pp. 3–4
  • Centralized parallel training commonly aggregates worker models through Parameter Server systems or AllReduce implementations.The paper describes model partitioning as a key design choice for communication performance.Source: §2 · p. 4
  • Decentralized-learning work studies fixed or changing communication topologies, including gossip-based approaches.The cited work includes convergence bounds for fixed regular graphs and empirical results for GossipGrad.Source: §2 · p. 4
  • This paper analyzes communication uncertainty in a general model covering Parameter Server and AllReduce strategies, and finds that the system can handle additional packet drops as worker nodes increase.The paper frames this as a distinction from prior work on distributed learning.Source: §2 · p. 4

3 Problem Setup

The setup allows workers to have different local data distributions and models unreliable communication through packet drops. It assumes independent drops with a common probability across communications.

3 Problem Setup

  • Workers may have distinct local data distributions, and each worker's loss function depends on its model and local data.The setup denotes worker i's data distribution by D_i and its local loss by F_i(x; ξ).Source: §3 · p. 5
  • Every communication can be dropped with probability p, with drop events assumed independent and identically likely across communications.The paper distinguishes packet drop rate from the phrase “packet loss rate” because “loss” refers to the loss function.Source: §3 · p. 5
  • The notation uses ∇f for a gradient, λ_i for a matrix's ith-largest eigenvalue, and 1_n for the full-one vector.Source: §3 · p. 5

4 Algorithm

RPS adds communication-efficient model averaging and sharing to local SGD so workers can operate despite packet loss. Its global analysis represents communication outcomes with time-varying matrices and coefficients α1 and α2.

4.1 Our Algorithm: RPS

  • RPS alternates each worker’s regular SGD step with a communication procedure intended to reliably average workers’ intermediate models.The algorithm initializes workers with the same model and runs for a specified number of iterations.Source: §4.1 · p. 5, §4.2 · p. 7
  • Reduce-Scatter divides each intermediate model into n blocks and assigns workers to average blocks from the packets they receive.The division parallelizes averaging and reduces communication cost.Source: §4.1 · pp. 5–6
  • AllGather shares averaged blocks, and workers that miss a block use the original block instead.Workers replace corresponding blocks of their intermediate models with received averaged blocks.Source: §4.1 · p. 6

4.2 RPS From a Global Viewpoint

  • The coefficient matrix indicates the communication outcome at time step t and is time-varying; constants α1 and α2 satisfy 0 < α2 < α1 < 1.Source: §4.2 · pp. 6–7

5 Theoretical Guarantees and Discussion

Under common stochastic-optimization assumptions, RPS can match the O(1/nT) convergence-rate scaling of centralized and decentralized SGD. Its analysis also indicates that packet-drop effects diminish as the number of workers and parameter servers grows.

5 Theoretical Guarantees and Discussion

  • The guarantee assumes Lipschitz gradients and bounded stochastic-gradient variance, and initializes X1 = 0 for simplicity.The zero initialization is stated to be without loss of generality.Source: §5 · p. 8
  • The dominant O(1/nT) convergence-rate term matches the rate reported for centralized and decentralized SGD.Theorem 1 states the guarantee under Assumption 1 for a sufficiently small learning rate.Source: §5 · p. 9
  • The convergence rate has a linear speedup with the number of workers n.The discussion identifies the leading term as proportional to 1/(nT).Source: §5 · p. 9
  • At fixed packet-drop rate p, the drop-rate effect diminishes as the number of workers and parameter servers increases.The discussion attributes this to α2 = O(p(1 − p)/n).Source: §5 · p. 9
  • With a constant learning rate, convergence is to a ball around a critical point; a decayed rate such as O(1/√t) can give critical-point convergence at the same rate.The paper describes constant learning rate as a simplifying choice.Source: §5 · p. 10

6 Experiments: Convergence of RPS

The experiments evaluate RPS on image-classification and natural-language-understanding tasks under packet loss. Model averaging largely preserves training-loss convergence, while gradient averaging is more sensitive to lost messages.

6.1 Experimental Setup

  • The evaluation uses ResNet models on CIFAR-10 and a single-layer LSTM on ATIS, with packet losses simulated in CNTK and RPS implemented using MPI.Training used 16 TITAN Xp GPUs connected by Gigabit Ethernet; momentum and regularization were omitted to match the analyzed algorithm.Source: §6.1 · p. 10
  • With 90% message arrival, training loss was 0.03 for ResNet110 and 0.11 for ResNet20; at 5% loss, ResNet110 matched baseline and ResNet20 increased by 0.02.The 100%-delivery baselines were 0.02 for ResNet110 and 0.09 for ResNet20; 1% loss did not increase training loss after 160 epochs.Source: §6.1 · p. 11
  • On ATIS with a single-layer LSTM, dropping 1%, 5%, or 10% of communicated partial vectors increased training loss by 0.01 from the 0.01 baseline.Source: §6.1 · p. 11
  • With 1% communication loss, gradient averaging converged worse in accuracy than model averaging on both CIFAR-10 ResNet architectures.The authors attribute this to packet-drop error accumulating across iterations without decaying, and suggest favoring model averaging on unreliable networks.Source: §6.1 · p. 11, Figure 5 · p. 11

7 Case study: Speeding up Colocated Applications

The case study simulates learning traffic sharing a network with a Web service. Prioritizing the Web service can improve its performance as learning updates are dropped, while the paper reports that small loss levels do not deteriorate convergence.

7 Case study: Speeding up Colocated Applications

  • The proposed use case is to de-prioritize learning updates so colocated, delay-sensitive services can receive priority and achieve lower latency.The paper concludes that tolerating small amounts of update loss can benefit colocated services without deteriorating convergence.Source: §7 · pp. 11–12
  • The simulation sends ResNet110-on-CIFAR-10 learning traces unreliably over 16 servers with 1 Gbps links, alongside an emulated Web service.The learning workload translates to 2.4 Gbps; Web-service messages are sent reliably.Source: §7 · pp. 11–12
  • With 10% learning-update loss, the Web service can be sped up by more than 20% (1.2×) at fixed message arrival rates.Figure 6 varies learning-update losses while holding λ at 2000, 5000, or 10000 messages per second.Source: Figure 6 · p. 12, §7 · p. 12
  • At target average transmission times of 2, 5, or 10 ms, accommodating higher Web-service arrival rates over the same infrastructure reduces its running cost as learning-update losses rise.Figure 7 presents the cost reduction against increasing message arrival rate and resulting learning-update loss.Source: Figure 7 · p. 12, §7 · p. 12

8 Conclusion

The conclusion presents a theoretical analysis of distributed learning with unreliable communication, evaluates it on image and language tasks, and illustrates application collocation as a practical use case.

8 Conclusion

  • The paper presents a novel analysis of a general distributed-learning model under unreliable communication.Source: §8 · p. 13
  • The analysis is evaluated while training neural networks on image and natural-language datasets.Source: §8 · p. 13
  • An application-collocation case study illustrates potential benefits from allowing learning algorithms to use unreliable communication channels.Source: §8 · p. 13

Supplemental Materials

The supplement defines notation used in the analysis and outlines a proof of a convergence property for local models. Its proof strategy uses relations among weighted-matrix quantities and intermediate lemmas.

A Notations

  • The supplement sets notation for gradients and packet-drop rate p, then introduces identity and averaging matrices.Source: A Notations · p. 17

A.1 Matrix Notations

  • The appendix organizes vectors and model-related quantities into matrix, averaged, block, and aggregated-block notation, with relations among the resulting quantities.Source: §A.1 · p. 17, §A.2 · p. 17, §A.3 · p. 18

A.6 Expectation Notations

  • The proof distinguishes expectations over stochastic gradients, packet drops, an iteration's procedures, and all history.Source: §A.6 · p. 19

B Proof to Theorem 1

  • The proof to Theorem 1 first establishes that local models converge toward their average, then proceeds through lemmas using properties of weighted matrices.Source: B Proof to Theorem 1 · p. 19

B.1 Proof of Lemma 3

  • The proof of Lemma 3 combines update-rule and assumption-based inequalities, propagating a bound across iterations using factors defined in Theorem 1.Source: §B.1 · pp. 19–21

B.2 Proof to Theorem 1

The proof derives the expected update from blockwise changes, uses lemmas based on the update rule and Assumption 1, and combines further lemmas in the proof of Theorem 1.

B.2 Proof to Theorem 1

  • Lemmas 4 and 5 derive inequalities from update rule (4) and Assumption 1.The proof then applies norm inequalities and combines intermediate bounds.Source: §B.2 · pp. 22, 24, 25, 26
  • The blockwise expected change yields E_t,P[∆x_t] = −γg(X_t; Ξ_t).The proof first computes the expected change for each block.Source: §B.2 · pp. 23–24
  • The proof of Theorem 1 combines Lemmas 6 and 8 and takes expectation over the whole history.It also sums intermediate inequalities and invokes Lemma 3.Source: §B.2 · pp. 26, 28, 29

C Proof to Corollary 2

The appendix proves Corollary 2 and examines properties of the weighted matrix W(j) under the updating rule.

C Proof to Corollary 2

  • The Corollary 2 proof begins by setting an expression involving T, n, σ², ζ², and α².The supplied expression also includes terms combining these quantities.Source: C Proof to Corollary 2 · pp. 29–30

D Properties of Weighted Matrix W(j)

  • The appendix studies three properties of W(j), including lemmas that bound its behavior under updating rule (4).The matrix entries are discussed in connection with Xt+1 = VtW.Source: D Properties of Weighted Matrix W(j) · pp. 30, 34
  • For W(j), expected entries are equivalent among off-diagonal pairs and among diagonal pairs, but the two groups need not match.The proof attributes the distinction to a node retaining its own portion when it is both sender and receiver.Source: D Properties of Weighted Matrix W(j) · p. 30

Related papers

Loading 1810.07766v4…