A Partition-insensitive Parallel Framework for Distributed Model Fitting

Xiaofei Wu, Rongmei Liang, Fabio Roli, Marcello Pelillo, Jing YuanarXiv 2024 · DOI · arXiv

TL;DR

Researchers have developed a new parallel framework for distributed model fitting called PIPADMM that is "partition-insensitive." Unlike traditional consensus-based methods that struggle with high-dimensional data and varying numbers of computing nodes, this framework maintains a consistent solution path regardless of how data is split and significantly reduces the computational burden by eliminating redundant auxiliary variables.

What Problem Does This Paper Address?

In the era of Big Data, we often can't fit a model on a single machine. We use distributed computing, where data is sharded across multiple "slave" nodes. The industry standard for this is Consensus ADMM (Alternating Direction Method of Multipliers).

However, Consensus ADMM has a major flaw: it forces every node to maintain its own local copy of the entire model parameter vector. If you have a model with $n$ features and $D$ nodes, you end up managing $(D+1)n$ variables. For high-dimensional datasets (where $n$ is huge), this creates massive memory overhead, slow communication, and sluggish convergence. Furthermore, the way you partition the data (how many nodes you use or how much data each node gets) can actually change the optimization behavior of the algorithm.

Methods

The authors introduce the Partition-insensitive Parallel ADMM (PIPADMM). Its core innovation lies in how it structures the optimization problem:

  1. Variable Splitting over Consensus: Instead of forcing local variables to equal a global "consensus" variable ($x = z_d$), they use a constraint based on the data itself ($A_d x = r_d$).
  2. Linearization Trick: To ensure the "master" node doesn't need to see the raw data (which would defeat the purpose of distributed computing), they use a linearization technique. This allows the master node to update the global model using only small, aggregated vectors ($\xi_d$) sent by the slave nodes.
  3. Succinctness: This approach reduces the number of variables to $m + n$ (total samples + features), making it independent of the number of nodes $D$.

The authors mathematically prove that if you keep the step size ($\eta$) consistent, the algorithm will follow the exact same iterative path regardless of whether you split your data across 2 nodes or 200 nodes.

Datasets

The framework was evaluated using:

  • Synthetic Data: A high-dimensional heteroscedastic regression model with 10,000 samples and 20,000 features.
  • Real-world Data: The rcv1.binary dataset, a well-known benchmark for text classification containing 47,236 features and over 677,000 testing samples.

Key Insights and Ideas

  • Partition Insensitivity: This is the "aha" moment. In most distributed systems, the hardware configuration (number of workers) affects the math. Here, the hardware is decoupled from the optimization logic, ensuring stability and reproducibility across different cluster sizes.
  • Communication Efficiency: Because the master node only receives a single vector from each slave and doesn't manage $D$ copies of the model, the communication overhead is significantly lower than traditional consensus methods.
  • Linear Convergence: The authors provide a theoretical guarantee that the algorithm achieves a worst-case linear convergence rate, providing confidence in its speed for practical applications.
  • Universal Applicability: The framework isn't just for one type of model; the paper demonstrates its use for Lasso, Ridge regression, Logistic Regression, and Support Vector Machines (SVMs).

Key Results

The performance gains over standard Consensus ADMM (CPADMM) are striking:

  • Speed: In a Lasso regression test with 10 nodes, PIPADMM finished in ~9.6 seconds, while the consensus version took ~496 seconds.
  • Accuracy and Sparsity: PIPADMM was much better at "feature selection" (identifying which coefficients should be zero). In synthetic tests, it achieved zero False Positives (FP) in coefficient estimation, whereas the consensus method often struggled with "noisy" non-zero estimates.
  • Scalability: As shown in the paper's figures, PIPADMM's training time remains relatively flat or decreases efficiently as more nodes are added, whereas consensus methods are heavily penalized by the increasing number of auxiliary variables.

Limitations and Future Work

  • Convexity Assumptions: The current theoretical proofs for convergence rely on the loss functions and regularization terms being convex. While the algorithm works in practice for many problems, non-convex optimization remains a challenge.
  • Parameter Tuning: The algorithm requires choosing an augmentation parameter ($\mu$) and a linearization constant ($\eta$). While the paper provides a method to calculate $\eta$ using the power method, finding the optimal $\mu$ still requires some cross-validation.
  • Future Directions: The authors suggest exploring "over-relaxation" techniques to further accelerate convergence and investigating how to generalize the framework for non-convex loss functions.

Summary updated

Abstract

Distributed model fitting refers to the process of fitting a mathematical or statistical model to the data using distributed computing resources, such that computing tasks are divided among multiple interconnected computers or nodes, often organized in a cluster or network. Most of the existing methods for distributed model fitting are to formulate it in a consensus optimization problem, and then build up algorithms based on the alternating direction method of multipliers (ADMM). This paper introduces a novel parallel framework for achieving a distributed model fitting. In contrast to previous consensus frameworks, the introduced parallel framework offers two notable advantages. Firstly, it exhibits insensitivity to sample partitioning, meaning that the solution of the algorithm remains unaffected by variations in the number of slave nodes or/and the amount of data each node carries. Secondly, fewer variables are required to be updated at each iteration, so that the proposed parallel framework performs in a more succinct and efficient way, and adapts to high-dimensional data. In addition, we prove that the algorithms under the new parallel framework have a worst-case linear convergence rate in theory. Numerical experiments confirm the generality, robustness, and accuracy of our proposed parallel framework.
BibTeX
@misc{wu2024partition,
  author = {Xiaofei Wu and Rongmei Liang and Fabio Roli and Marcello Pelillo and Jing Yuan},
  title = {{A Partition-insensitive Parallel Framework for Distributed Model Fitting}},
  year = {2024},
  eprint = {2406.00703},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2406.00703},
}
Figure