Trading Computation for Communication: Distributed Stochastic Dual Coordinate Ascent

Tianbao YangNeurIPS 2013 · OpenReview

Introduction

In the era of "Big Data," machine learning models are routinely trained on billions of data points. To handle this immense scale, researchers rely on distributed optimization, spreading the computational workload across many CPU cores or networked machines. This paper introduces DisDCA, a distributed version of the Stochastic Dual Coordinate Ascent (SDCA) algorithm designed to solve large-scale regularized loss minimization problems. By performing multiple local updates before communicating across the network, DisDCA effectively "trades" local CPU cycles for reduced network latency, achieving faster convergence than distributed SGD or ADMM without requiring complex parameter tuning.

The Bottleneck in Distributed Optimization

The standard tools for distributed machine learning are Stochastic Gradient Descent (SGD) and the Alternating Direction Method of Multipliers (ADMM). However, both come with significant drawbacks in a distributed setting:

  • Distributed SGD requires frequent communication to synchronize gradients across machines. In networks with high latency or low bandwidth, this synchronization quickly becomes a severe bottleneck.
  • ADMM can be faster and requires less frequent communication, but it is notoriously sensitive to its "penalty parameter" ($\rho$). Finding the right parameter requires tedious manual tuning, making it cumbersome for production environments.

The authors aim to bring the benefits of SDCA—an algorithm known for strong theoretical guarantees and high efficiency in sequential settings—into the distributed world to overcome these limitations.

Introducing DisDCA

The authors propose DisDCA (Distributed Stochastic Dual Coordinate Ascent), which operates in a "star network" topology where multiple worker machines communicate with a central master node.

The Basic vs. Practical Variants

In the Basic Variant (DisDCA-b), each worker machine holds a local subset of the data. During each iteration, a worker randomly selects $m$ local data points and updates their corresponding "dual variables" (mathematical proxies for how much each data point contributes to the final model). Afterward, the workers perform an AllReduce operation to synchronize their local updates into a global weight vector.

Observing that the basic version is somewhat conservative, the authors introduced a Practical Variant (DisDCA-p). Instead of using the global weights from the previous round for all $m$ local updates, DisDCA-p leverages up-to-date local information by updating its local model estimate after every single coordinate update. This minor adjustment significantly accelerates convergence in practice.

The Computation-Communication Tradeoff

A core contribution of the paper is the rigorous theoretical analysis of the relationship between $m$ (local computation) and $K$ (number of machines). The authors define an "effective region" for these parameters. They demonstrate that as long as the parameters stay within certain bounds determined by the regularization strength ($\lambda$), increasing local work ($m$) directly reduces the number of expensive communication rounds needed. In distributed systems, the network is usually the bottleneck, not the CPU. By doing more "mini-batches" of work locally, DisDCA drastically cuts down on network overhead.

Experimental Results

The algorithm was evaluated on two large-scale datasets commonly used in machine learning benchmarks: covtype (581,012 examples, 54 features) and the massive kdd dataset (over 19 million examples, nearly 30 million features). The tasks focused on solving Support Vector Machine (SVM) problems using both $L_1$ and $L_2$ formulations.

Performance of DisDCA variants across different parameters ($m$, $K$) and against baseline algorithms.

Key findings from the experiments include:

  • Superior Speed: On the covtype dataset, the practical variant (DisDCA-p) reached a target duality gap in under 1 second, vastly outperforming the basic variant.
  • Scaling on Huge Data: On the 30-million-feature kdd dataset, DisDCA-p outperformed distributed versions of SAG (Stochastic Average Gradient) and Pegasos (a popular SGD-based SVM solver).
  • Robustness vs. ADMM: While ADMM can perform well if its penalty parameter is perfectly tuned, its performance deteriorates significantly if the parameter is off. DisDCA is essentially "parameter-free" (beyond standard ML hyperparameters like $\lambda$) and produced comparable or better results without any tuning.

Furthermore, the experiments confirmed the theoretical "effective region": the wider the regularization parameter $\lambda$, the more the model benefits from distributed parallelization and local computation.

Limitations and Future Work

While DisDCA presents a strong step forward, the authors note a few limitations. First, there is a theoretical gap: while the "Practical Variant" performed best empirically, proving its specific convergence bound remains an open problem (current proofs apply primarily to the basic variant). Second, the study assumes a synchronous "star network" or an AllReduce framework; exploring asynchronous network topologies where machines do not wait for each other is a promising direction for future research. Finally, the current analysis focuses on smooth or Lipschitz continuous loss functions, leaving the extension to non-convex problems as a future challenge.

Summary updated

Abstract

We present and study a distributed optimization algorithm by employing a stochastic dual coordinate ascent method. Stochastic dual coordinate ascent methods enjoy strong theoretical guarantees and often have better performances than stochastic gradient descent methods in optimizing regularized loss minimization problems. It still lacks of efforts in studying them in a distributed framework. We make a progress along the line by presenting a distributed stochastic dual coordinate ascent algorithm in a star network, with an analysis of the tradeoff between computation and communication. We verify our analysis by experiments on real data sets. Moreover, we compare the proposed algorithm with distributed stochastic gradient descent methods and distributed alternating direction methods of multipliers for optimizing SVMs in the same distributed framework, and observe competitive performances.
BibTeX
@inproceedings{yang2013trading,
  author = {Tianbao Yang},
  title = {{Trading Computation for Communication: Distributed Stochastic Dual Coordinate Ascent}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2013},
  url = {https://openreview.net/forum?id=H1-btLZuWB},
}
Figure