Near Optimal Coded Data Shuffling for Distributed Learning

Mohamed Adel Attia, Ravi Tandon

TL;DR

This paper tackles the communication bottleneck in distributed machine learning caused by data shuffling between training epochs. The authors establish fundamental information-theoretic limits on the trade-off between local worker storage and communication overhead, proposing a novel "Aligned Coded Shuffling" scheme that is nearly optimal—and in some cases, perfectly optimal—at reducing the data transfer load.

What Problem Does This Paper Address?

In large-scale distributed learning, data is often shuffled across a cluster of worker nodes at the start of every "epoch" (a full pass through the dataset). This randomization is crucial for the statistical convergence of algorithms like Stochastic Gradient Descent (SGD). However, moving massive amounts of data from a master node to workers creates a massive communication bottleneck that often outweighs the time spent on actual computation.

The central question is: If we give worker nodes a little bit of extra memory (storage), how much can we reduce the communication cost? While previous work explored this, a rigorous understanding of the optimal trade-off and a practical scheme to achieve it across any number of workers were missing.

Methods

The authors approach this as an information-theoretic problem, treating data shuffling as a specialized version of the "index coding" problem. Their methodology involves three main pillars:

  1. Information-Theoretic Lower Bounds: They use a novel bounding methodology (inspired by recent work in web caching) to formulate the minimum possible communication rate as a Linear Program (LP).
  2. Structural Invariant Placement and Update: To ensure that coding opportunities exist in every epoch, the authors propose a specific way to partition data across workers. Crucially, they developed a "structural invariant" update rule: as data is shuffled, workers update their local cache in a way that preserves the mathematical structure needed for coded delivery in the next epoch.
  3. Interference Alignment: For more complex scenarios, they introduce "Aligned Coded Shuffling." This technique, borrowed from wireless communication theory, forces the "interference" (data a worker receives but doesn't need) to occupy the smallest possible "dimensions," allowing the master node to pack more useful information into fewer transmissions.

Datasets

As this is a theoretical paper focused on fundamental limits and coding theory, no empirical datasets were used. The results are derived mathematically and hold for any dataset of $N$ points and $K$ workers, assuming the data points are independent and identically distributed (i.i.d.).

Key Insights and Ideas

  • Storage is the Lever: Even a small amount of "excess" storage (beyond what is needed to hold the current training batch) can be used to store parts of other data points, creating "coded broadcasting" opportunities.
  • The Power of XOR: Instead of sending a data point $D_1$ to Worker A and $D_2$ to Worker B, the master can send $D_1 \oplus D_2$. If Worker A already has $D_2$ in its cache and Worker B has $D_1$, both can decode their needed data from a single transmission.
  • Vanishing Gaps: The authors discovered that the gap between their proposed scheme and the theoretical "perfect" limit vanishes as the number of workers ($K$) increases. Specifically, the scheme is within a factor of $K/(K-1)$ of the lower bound.
  • Symmetry is Key: By maintaining a symmetric storage structure across shuffles, the master node can treat every shuffle as a "worst-case" scenario and still provide a guaranteed communication rate.

Key Results

  • Characterized the Trade-off: The paper provides the first closed-form expressions for the storage-vs-communication rate for any number of workers $K$.
  • Near-Optimality: They proved that their coded communication scheme is within a multiplicative factor of at most $K/(K-1)$ from the information-theoretic lower bound. For a 10-node cluster, the scheme is within ~11% of the absolute physical limit.
  • Optimal for Small Clusters: The "Aligned Coded Shuffling" scheme was shown to be perfectly optimal (closing the gap entirely) for clusters with fewer than 5 workers.
  • Improved Bounds: For larger clusters ($K \ge 5$), they reduced the maximum multiplicative gap to $\frac{K-1/3}{K-1}$, further tightening the performance guarantees.

Limitations and Future Work

  • Uncoded Storage Assumption: The authors assume that the "excess" storage at workers is used to store uncoded fragments of data. While this simplifies the update process, it's possible that storing coded fragments locally could further reduce communication.
  • Master-Worker Topology: The current work focuses on a centralized master node. Future research could extend these "structural invariant" ideas to decentralized, worker-to-worker (MapReduce-style) shuffling.
  • Stragglers: While the paper mentions "stragglers" (slow nodes) in the introduction, the primary focus is on communication volume rather than the temporal latency caused by heterogeneous hardware. Integrating these coded shuffling schemes with straggler-mitigation codes (like MDS codes) remains an open challenge.

Summary updated

Abstract

Data shuffling between distributed cluster of nodes is one of the critical steps in implementing large-scale learning algorithms. Randomly shuffling the data-set among a cluster of workers allows different nodes to obtain fresh data assignments at each learning epoch. This process has been shown to provide improvements in the learning process (via testing and training error). However, the statistical benefits of distributed data shuffling come at the cost of extra communication overhead from the master node to worker nodes, and can act as one of the major bottlenecks in the overall time for computation. There has been significant recent interest in devising approaches to minimize this communication overhead. One approach is to provision for extra storage at the computing nodes. The other emerging approach is to leverage coded communication to minimize the overall communication overhead. The focus of this work is to understand the fundamental tradeoff between the amount of storage and the communication overhead for distributed data shuffling. In this paper, we first present an information theoretic formulation for the data shuffling problem, accounting for the underlying problem parameters (number of workers, K, number of data points, N, and available storage, and S per node). We then present an information theoretic lower bound on the communication overhead for data shuffling as a function of these parameters. We next present a novel coded communication scheme and show that the resulting communication overhead of the proposed scheme is within a multiplicative factor of at most K-1 from the lower bound (which is upper bounded by 2 for K/K ≥ 2). Furthermore, we present new results towards closing this gap through a novel coded communication scheme, which we call the aligned coded shuffling. This scheme is inspired by the ideas of coded shuffling and interference alignment. In particular, we show that the aligned scheme achieves the optimal storage vs communication trade-off for K <; 5, and further reduces the K-1 maximum multiplicative gap down to K-1/3/k-1, for K ≥ 5.
BibTeX
@article{attia2019near,
  author = {Mohamed Adel Attia and Ravi Tandon},
  title = {{Near Optimal Coded Data Shuffling for Distributed Learning}},
  journal = {IEEE Trans. Information Theory},
  year = {2019},
  url = {https://openreview.net/forum?id=Lahqv40dU7G},
}

Loading related content...

Figure