Asynchronous Stochastic Gradient Descent for Extreme-Scale Recommender Systems

Lewis Liu, Kun ZhaoAAAI 2021 · DOI

Abstract

Training recommendation models on petabytes of data requires massive parallelization via Asynchronous Stochastic Gradient Descent (ASGD). However, ASGD faces significant challenges with gradient staleness and optimizer stalling when scaled to thousands of workers. We propose a framework featuring Staleness Normalization, Local Data Normalization, and SWAP (Samples Weighted According to Period). Our methods enable stable training with 3,000 workers, achieving a 5 percentage point increase in AUC on Alibaba's industrial CTR datasets compared to standard asynchronous baselines.

Introduction

Industrial recommender systems process billions of samples daily, necessitating highly distributed training environments. ASGD is the standard approach, allowing thousands of workers to update a central parameter server independently. However, as the number of workers grows, the "staleness" of gradients—the delay between parameter retrieval and update submission—increases. This staleness often leads to model divergence or suboptimal performance, particularly in sparse, high-dimensional feature spaces.

Staleness and Normalization

A critical finding of this work is that gradient staleness scales linearly with the number of workers. As shown in the distribution analysis below, increasing the worker count from 1,000 to 3,000 significantly shifts the staleness distribution, nearly tripling the mean staleness and increasing variance.

Distribution of update staleness for 1,000 and 3,000 workers, demonstrating linear scaling.

To address this, we introduced Staleness Normalization. By modeling the update arrival as a Poisson process, we developed a formula to discount the learning rate for older updates, preventing stale gradients from destabilizing the global model. This is complemented by Local Data Normalization at the worker level, which smooths the optimization landscape and reduces the impact of data distribution variance across the cluster.

SWAP: Maintaining Model Freshness

Adaptive optimizers like Adagrad can lose sensitivity to new data over time as historical gradient sums grow to extreme magnitudes. We introduced SWAP, a periodic recession method that decays accumulated history. This ensures the optimizer remains responsive to the latest user behavior trends in high-velocity data streams, preventing the performance plateaus common in long-running incremental training sessions.

Experimental Results

We evaluated our framework on Alibaba’s E-Commercial CTR dataset, which features 7 billion daily samples and over 30 billion sparse features.

Performance at Scale

Our framework successfully scaled to 3,000 workers while maintaining convergence. As illustrated in the normalization tests, the proposed staleness normalization significantly outperforms both unnormalized ASGD and naive linear normalization strategies, providing a stable path to convergence even at high worker counts.

Test AUC performance across different normalization strategies, highlighting the effectiveness of the proposed staleness normalization.

Impact on Accuracy and Stability

The combination of staleness and data normalization resulted in a total AUC improvement of over 5 percentage points compared to standard ASGD. Furthermore, SWAP allowed the model to continue learning from new data trends after 10 days of continuous training, whereas standard Adagrad implementations typically plateaued much earlier.

Conclusion

This work demonstrates that with proper staleness normalization and periodic history decay, ASGD can be scaled to thousands of workers for extreme-scale recommendation tasks. These techniques provide the stability and freshness required for modern, petabyte-scale e-commerce engines.

Summary updated

BibTeX
@inproceedings{liu2021asynchronous,
  author = {Lewis Liu and Kun Zhao},
  title = {{Asynchronous Stochastic Gradient Descent for Extreme-Scale Recommender Systems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i1.16108},
}
Figure