Asynchronous COMID: the theoretic basis for transmitted data sparsification tricks on Parameter Server

Daning Cheng, Shigang Li, Yunquan ZhangarXiv 2017 · arXiv

TL;DR

This paper introduces asynchronous COMID, a theoretical framework that provides a rigorous mathematical proof for popular "tricks" used to speed up distributed machine learning. By proving that methods like asynchronous FTRL-proximal and server-side L2 regularization are special cases of asynch-COMID, the authors demonstrate that these techniques reduce network traffic through data sparsification without sacrificing convergence speed or final model accuracy.

What Problem Does This Paper Address?

In large-scale distributed machine learning, the Parameter Server architecture is a standard choice. However, as the number of worker nodes increases, the network often becomes a bottleneck. To combat this, engineers frequently use "tricks" to reduce the amount of data sent over the wire.

Two widely used techniques are:

  1. Asynchronous FTRL-proximal: A method effective at producing sparse, accurate models.
  2. Server-side L2 Regularization: Moving the computation of the L2 norm gradient from the workers to the server. Since L2 gradients are typically dense, computing them on the server allows workers to send only sparse loss gradients, significantly reducing network load.

While these tricks are effective in practice, they lacked rigorous mathematical proofs of convergence in an asynchronous setting. This paper fills that gap, providing the theoretical "safety net" that researchers and engineers need to use these optimizations confidently.

Methods

The authors propose asynchronous Composite Objective Mirror Descent (asynch-COMID). Standard COMID is a variant of Stochastic Gradient Descent (SGD) that doesn't linearize the regularization term, making it well-suited for regularized loss minimization.

The key innovation here is adapting COMID for an asynchronous environment where updates are based on "delayed" information from workers. The authors:

  • Formulate the Update: They split the update into two parts: a worker-side computation (scanning data and computing sparse loss gradients) and a server-side computation (computing regularization gradients and updating parameters "lazily").
  • Prove Convergence: They derive a general regret bound for asynch-COMID, showing that the error (regret) converges to zero as training progresses, even with delayed updates.
  • Establish Equivalence: They mathematically prove that the popular FTRL-proximal and L2 norm tricks are actually specific applications of the asynch-COMID framework.
Algorithm 1: Implementation of asynch-FTRL-Proximal on a Parameter Server

Datasets

The researchers validated their theory using several large-scale datasets known for their high dimensionality and sparsity:

  • Avazu's Click-through Prediction: The primary dataset for experiments, featuring 1,000,000 features.
  • KDD 2010 (algebra): Over 20 million features.
  • MNIST8m: 780 features.
  • Webspam: Over 16 million features.
  • KDD 2012: Over 54 million features.

Key Insights and Ideas

  • The Power of Sparsity: The "aha moment" is realizing that the common thread between these disparate tricks is the strategic separation of sparse and dense computations. By keeping dense regularization updates on the server, the system avoids clogging the network with dense vectors.
  • Theoretical Umbrella: Asynch-COMID acts as a unifying theory. Instead of proving every new optimization trick from scratch, researchers can now check if a trick fits within the COMID framework to guarantee its convergence.
  • Minimal Impact of Delay: The theory and experiments show that the "staleness" of gradients in an asynchronous system (the delay $\tau(t)$) is manageable and doesn't fundamentally break the optimization process, provided the learning rate is chosen appropriately.

Key Results

The paper successfully bridges the gap between empirical "tricks" and rigorous theory:

  • Regret Bound: The authors established a general regret bound for asynch-COMID, proving it is mathematically sound.
  • Experimental Validation: Using the Avazu dataset, they showed that asynch-FTRL-proximal maintains a very similar convergence path regardless of the number of workers (from 1 to 32).
Figure 1(a): Convergence of asynch-FTRL-proximal with varying worker counts
  • L2 Trick Efficiency: Experiments confirmed that the L2 norm trick (computing L2 on the server) results in virtually no loss in convergence speed compared to traditional methods, while significantly reducing network overhead.
Figure 3. Impact of multi-worker: The convergence speed of using different number of workers, with η = 0.0001, λ = 0.001

Limitations and Future Work

While the paper provides a strong theoretical foundation, the authors note a few areas for further exploration:

  • Beyond Regret: Future work will look into other mathematical properties of asynch-COMID beyond just regret bounds.
  • Dataset Sensitivity: The authors want to investigate how specific characteristics of a dataset (like the distribution of features) influence the "gap" in convergence speed between different algorithms.
  • More Tricks: There are many other unproven optimization tricks in the wild; the authors aim to expand their framework to cover more of them.

Summary updated

Abstract

Asynchronous FTRL-proximal and L2 norm done at server are two widely used tricks in Parameters Server which is an implement of delayed SGD. Their commonness is leaving parts of updating computation on server which reduces the burden of network via making transmitted data sparse. But above tricks' convergences are not well-proved. In this paper, based on above commonness, we propose a more general algorithm named as asynchronous COMID and prove its convergence. We prove that asynchronous FTRL-proximal and L2 norm done at server are applications of asynchronous COMID, which demonstrates the convergences of above two tricks. Then, we conduct experiments to verify theoretical results. Experimental results show that compared with delayed SGD on Parameters Server, asynchronous COMID reduces the burden of the network without any harm on the mathematical convergence speed and final output.
BibTeX
@misc{cheng2017asynchronous,
  author = {Daning Cheng and Shigang Li and Yunquan Zhang},
  title = {{Asynchronous COMID: the theoretic basis for transmitted data sparsification tricks on Parameter Server}},
  year = {2017},
  eprint = {1709.02091},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1709.02091},
}
Figure