Delay-Tolerant Algorithms for Asynchronous Distributed Online Learning

H. Brendan McMahan, Matthew J. StreeterNeurIPS 2014

Introduction

In large-scale machine learning, distributed systems are essential. Typically, "Readers" (which make predictions and compute gradients) and "Updaters" (which maintain the model parameters) operate on different machines. This architecture introduces a significant challenge: stale gradients. By the time a Reader calculates a gradient and sends it to the Updater, the central model has often been updated many times by other concurrent threads.

While standard asynchronous algorithms like Hogwild! perform well with moderate parallelism (around 100 threads), their performance degrades sharply as the number of threads—and consequently, the delay—scales to 1,000 or more. Existing adaptive learning rate methods, such as AdaGrad, adjust to the sequence of data but fail to account for the asynchronous, delayed nature of the system itself.

To address this, researchers have introduced AdaptiveRevision, a novel online gradient descent algorithm designed specifically for distributed systems with high communication delays.

The AdaptiveRevision Methodology

The core innovation of this paper is the shift toward "Delay-Tolerant" algorithms. Instead of relying on a learning rate that only considers past gradients, AdaptiveRevision accounts for the forward gradient sum—the sum of all updates that were "in flight" while a specific gradient was being computed.

The authors conceptualize this through a progression of algorithms:

  1. HypFwd & HypBack: These are theoretical models. HypFwd perfectly sets the learning rate by "cheating" and looking at future gradients. HypBack approximates this ideal state using only the information available at the time of the update.
  2. AdaptiveRevision: This is the practical, deployable algorithm. It maintains a running sum of gradients for each coordinate. When a delayed update arrives, the algorithm calculates how much the learning rate should have been adjusted given the exact delay that occurred, and applies a retroactive "revision" to the model.
  3. Coordinate-Wise Updates: To maintain efficiency and avoid heavy synchronization locks, the algorithm operates on each feature coordinate independently. This is highly effective for the sparse data typically found in web-scale problems.

Key Insights

  • Delay as a First-Class Citizen: Rather than treating delay as noise or an error to be minimized, AdaptiveRevision treats the precise delay of each update as valuable data used to optimize the learning rate.
  • The Power of Revision: Traditional algorithms apply an update and move on. AdaptiveRevision retroactively improves the step size taken for a stale gradient because it knows exactly how many updates occurred during the lag.
  • Linearization and Sparsity: By leveraging convexity, the authors demonstrate that handling delays for simple linear functions provides guarantees for complex convex loss functions (like Logistic Regression). Furthermore, in high-dimensional sparse data, concurrent updates to the same feature are rare, which simplifies the analysis and boosts performance.

Experimental Results

The researchers evaluated AdaptiveRevision on two massive real-world datasets: Web Search Ads (~3.1 million examples predicting click-through rates) and Malicious URLs (~2.4 million examples identifying dangerous websites).

Performance across datasets and delay patterns

The results demonstrate superior accuracy at scale. When delays reach 1,000 updates or more, AdaptiveRevision significantly outperforms standard asynchronous AdaGrad (AsyncAda-DA and AsyncAda-GD).

Remarkably, the experiments revealed a 10x speedup potential. AdaptiveRevision achieved better accuracy with a massive delay of 10,000 than standard methods did with a delay of only 1,000. This implies that engineering teams can utilize 10x more machines to train models significantly faster without sacrificing predictive quality. The algorithm also proved highly robust across various delay patterns, including constant lag, minibatch-style updates, and purely random delays.

Limitations and Future Directions

While highly effective, the approach has a few limitations:

  • The "InOrder" Assumption: The strongest theoretical proofs assume that updates arrive at the Updater in the exact order the Readers initiated them. While the algorithm performs exceptionally well in practice even when this is violated, a theoretical gap remains.
  • Memory Overhead: AdaptiveRevision requires storing three numbers per model coefficient (weight, gradient sum, and revision tracker), compared to two for standard methods. This increases the memory footprint on the parameter server.
  • Scope: The current research focuses on Online Gradient Descent (OGD). Future work could extend these delay-tolerant techniques to other frameworks, such as Dual Averaging, or algorithms involving complex constraints.

Summary updated

BibTeX
@inproceedings{mcmahan2014delay,
  author = {H. Brendan McMahan and Matthew J. Streeter},
  title = {{Delay-Tolerant Algorithms for Asynchronous Distributed Online Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
}
Figure