Corgi^2: A Hybrid Offline-Online Approach To Storage-Aware Data Shuffling For SGD

Etay Livne, Gal Kaplun, Eran Malach, Shai Shalev-Schwatz

Abstract

Corgi² addresses the challenge of training deep learning models on massive cloud-stored datasets where random data access is prohibitively expensive. By introducing a hybrid shuffling strategy that combines a lightweight offline "pre-mix" with an online buffer-based shuffle, Corgi² achieves the convergence performance of a full random shuffle while preserving the I/O efficiency of sequential block reads. Experimental results on datasets up to 27TB demonstrate that Corgi² significantly reduces block-wise variance, allowing models to reach peak accuracy faster and more cost-effectively than existing partial shuffling methods.

The Challenge of Large-Scale Data Shuffling

Training modern deep learning models requires massive datasets, often stored in cloud environments. For Stochastic Gradient Descent (SGD) to converge correctly, the model must access data in an independent and identically distributed (i.i.d.) manner. However, accessing individual random examples from cloud storage incurs a significant "Cloud Storage Tax" due to high latency and cost.

To mitigate this, data is typically stored in large "shards" or blocks and read sequentially. The primary drawback is that these shards are often highly homogeneous (e.g., frames from a single video clip). Training on one shard at a time causes the model to overfit to specific local features before moving to the next, leading to poor overall performance. While existing solutions like CorgiPile attempt to fix this by shuffling shards in an online memory buffer, they struggle when the original shards are extremely non-diverse.

The Corgi² Hybrid Approach

Corgi² introduces a two-step shuffling pipeline designed to break up extreme homogeneity without the overhead of a full global shuffle:

  1. OfflineCorgiShuffle (The "Pre-mix"): Before training, a partial shuffle is performed. The algorithm loads a small number of blocks into a buffer, shuffles the examples, and writes them back into new blocks. This targeted pre-mixing is designed to de-homogenize the shards.
  2. CorgiPile (The "Online Shuffle"): During training, the model applies the standard CorgiPile method to the pre-mixed data, loading blocks into a buffer and performing a final shuffle before the data reaches the model.
The Corgi² workflow: (1)-(2) OfflineCorgiShuffle pre-mixes data blocks, and (3)-(4) CorgiPile performs online shuffling during training.

Crucially, this process can be implemented "in-place," avoiding the need for double storage capacity while adding only a minimal, one-time cost to total data access queries.

Experimental Evaluation

The researchers evaluated Corgi² across three distinct scales:

  • Proprietary Mobileye Dataset: A 27TB dataset of real-world autonomous driving images.
  • ImageNet: The standard benchmark for image classification using ResNet-50.
  • CIFAR-100: A smaller dataset used to test algorithmic limits with extremely small buffer sizes.

Key Results and Visual Uniformity

Corgi² demonstrated parity with a full random shuffle on the 27TB Mobileye dataset while using a memory buffer only 0.25% the size of the total dataset. On ImageNet, it significantly outperformed the original CorgiPile and matched the performance of a full offline shuffle.

Visual comparison of data distribution over time: Corgi² achieves a near-uniform distribution similar to a full shuffle, whereas CorgiPile exhibits visible clumping.

The core insight behind this success is the reduction of "block-wise variance." The authors mathematically proved that SGD quality depends on how much the average gradient of a single block differs from the dataset average. By de-homogenizing shards offline, the subsequent online shuffle becomes exponentially more effective.

Conclusion and Future Directions

While Corgi² provides a robust solution for large-scale training, it faces challenges in extreme edge cases. On CIFAR-100 with artificially small buffers (0.2% of data), the model occasionally encountered buffers lacking certain classes, slightly slowing convergence. Future work may focus on optimizing in-place logic for specific cloud architectures and providing more automated hyperparameter tuning for block and buffer sizes to balance storage costs and convergence speed.

Summary updated

Abstract

When using Stochastic Gradient Descent (SGD) for training machine learning models, it is often crucial to provide the model with examples sampled at random from the dataset. However, for large datasets stored in the cloud, random access to individual examples can be costly and inefficient. A recent work proposed an online shuffling algorithm called CorgiPile, which greatly improves efficiency of data access, at the cost of some performance loss, which becomes particularly apparent for large datasets stored in homogeneous shards (e.g., video datasets). In this paper, we extend CorgiPile by adding an efficient offline iteration, transforming it into a hybrid two-step partial data shuffling strategy. We show through comprehensive theoretical analysis that our approach performs similarly to SGD with random access (even for homogenous data) without compromising on the data access efficiency of CorgiPile, and demonstrate its practical advantages through experimental results.
BibTeX
@misc{livne2023corgi,
  author = {Etay Livne and Gal Kaplun and Eran Malach and Shai Shalev-Schwatz},
  title = {{Corgi^2: A Hybrid Offline-Online Approach To Storage-Aware Data Shuffling For SGD}},
  year = {2023},
  eprint = {2309.01640},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2309.01640},
}
Figure