Distributed Block Coordinate Descent for Minimizing Partially Separable Functions

Jakub Marecek, Peter Richtárik, Martin TakácSpringer Proceedings in Mathematics & Statistics 2015 · DOI · arXiv · OpenAlex

Introduction

In the landscape of modern large-scale optimization, the "Big Data" paradigm presents a fundamental challenge: datasets often exceed the RAM capacity of individual machines. Problems such as training Support Vector Machines (SVM) with millions of features or solving LASSO problems with billions of variables necessitate distributed architectures. However, moving from a single-machine setup to a cluster introduces two primary obstacles: communication bottlenecks, where network latency often dwarfs computation time, and step-size dilemmas, where simultaneous updates from multiple nodes can lead to instability or divergence.

This work addresses these challenges by introducing a distributed randomized block coordinate descent method. By exploiting the "partial separability" of objective functions, the authors provide a theoretical framework that bridges the gap between high-level optimization theory and the practical constraints of distributed hardware.

Methodology: Distributed Block Coordinate Descent

The proposed algorithm distributes the variables (blocks) across $C$ computers in a cluster. The core of the approach lies in how these nodes interact and update their local variables.

Partial Separability and ESO

The fundamental assumption is that the objective function $f(x)$ is partially separable. This means $f(x)$ can be expressed as a sum of functions, each depending only on a small subset of coordinates. The degree of overlap between these subsets is captured by a parameter $\omega$.

To ensure convergence in a distributed setting, the authors derive the Expected Separable Overapproximation (ESO). The ESO provides a step-length parameter, $\beta$, which dictates how far the algorithm can safely move along a gradient direction during a parallel update. Unlike standard methods that might require conservative, slow steps to avoid "overshooting" the minimum, the ESO-derived $\beta$ is optimized based on the number of computers, the number of updates per iteration ($\tau$), and the inherent sparsity of the data.

Communication Strategies

A significant contribution of this work is the departure from traditional synchronous communication patterns. Standard "ReduceAll" (RA) strategies require every node to wait for a global synchronization before proceeding, which often leads to significant idle time. The authors propose:

  • Asynchronous StreamLined (ASL): A ring-based topology where updates flow asynchronously between neighboring nodes. This allows computation to continue while data is in transit.
  • Asynchronous Torus (AST): A more complex topology designed for massive clusters, further reducing the communication overhead by organizing nodes in a multi-dimensional grid.

Experimental Evaluation

The framework was tested on two primary benchmarks:

  1. WebSpam: A real-world SVM training task involving 16.6 million features and 350,000 observations (approx. 25 GB).
  2. Artificial LASSO: A massive synthetic sparse least squares problem designed to test the limits of the implementation. This problem featured 1 billion rows and 500 million columns, requiring 3 TB of storage.

The experiments were conducted on the HECToR high-performance computing cluster, allowing the authors to observe the algorithm's behavior across hundreds of cores.

Key Insights and Results

The empirical results validate the theoretical framework, particularly regarding the impact of data sparsity on performance.

  • Efficiency at Scale: On the 3 TB LASSO problem, the algorithm successfully reduced the loss function by 25 orders of magnitude in less than 30 minutes. This demonstrates the capability of the ESO framework to handle problems that are traditionally computationally prohibitive.
  • Linear Speedup: The authors observed that as the problem becomes more "separable" (sparser), the system achieves nearly linear speedup. For data with a sparsity of $\eta = 0.001$, the method scaled efficiently up to 1,000 parallel updates per iteration.
  • Communication Performance: The ASL-FP (Fully Parallel) implementation consistently outperformed the standard RA-FP approach. By removing the need for global synchronization, the ASL strategy significantly reduced the wall-clock time required for convergence.
  • Theoretical Safety: The analysis shows that the "cost of distribution" is bounded. In the worst-case scenario, distributing the task across $C$ machines only roughly doubles the number of iterations compared to a single machine performing the same total number of updates, providing a reliable performance floor for large-scale deployments.

Conclusion and Future Directions

This work provides a robust foundation for scaling coordinate descent to massive datasets. By leveraging partial separability and the ESO framework, it is possible to achieve significant speedups on distributed clusters without sacrificing theoretical convergence guarantees.

While the current analysis relies on the objective function being convex, future work could explore extending these principles to non-convex regimes, such as deep learning. Additionally, while the ASL and AST patterns are highly effective, further research into hardware-specific interconnect optimizations could yield even greater performance gains. The ability to calculate the degree of separability $\omega$ efficiently remains a practical consideration for applying this method to novel, unstructured datasets.

Summary updated

BibTeX
@inproceedings{marecek2015distributed,
  author = {Jakub Marecek and Peter Richtárik and Martin Takác},
  title = {{Distributed Block Coordinate Descent for Minimizing Partially Separable Functions}},
  booktitle = {Springer Proceedings in Mathematics \& Statistics},
  year = {2015},
  doi = {10.1007/978-3-319-17689-5\_11},
}
Figure