Communication-efficient Distributed Sparse Linear Discriminant Analysis

Lu Tian, Quanquan GuAISTATS 2017 · OpenReview

Abstract

We propose a communication-efficient distributed estimation method for sparse linear discriminant analysis (LDA) in the high dimensional regime. Our method distributes the data of size $N$ into $m$ machines, and estimates a local sparse LDA estimator on each machine using the data subset of size $N/m$. After the distributed estimation, our method aggregates the debiased local estimators from $m$ machines, and sparsifies the aggregated estimator. We show that the aggregated estimator attains the same statistical rate as the centralized estimation method, as long as the number of machines $m$ is chosen appropriately. Moreover, we prove that our method can attain the model selection consistency under a milder condition than the centralized method. Experiments on both synthetic and real datasets corroborate our theory.

Introduction

Linear Discriminant Analysis (LDA) is a fundamental technique for classification and dimensionality reduction. In the era of "Big Data," LDA faces two primary challenges: the curse of dimensionality and the computational bottleneck of massive datasets. When the number of features ($d$) exceeds the sample size ($n$), the sample covariance matrix becomes singular, necessitating sparse LDA approaches. However, when data is distributed across multiple machines, naive aggregation of sparse estimators fails. Sparse estimators like Lasso or Dantzig-type selectors are inherently biased; while averaging reduces variance, it does not mitigate this bias, leading to suboptimal performance.

This paper introduces a communication-efficient, "one-shot" distributed framework for sparse LDA. By incorporating a debiasing step before aggregation, the proposed method achieves statistical accuracy comparable to centralized approaches with minimal communication overhead.

Methodology

The proposed method follows a four-step "one-shot" process:

  1. Local Estimation: Each worker machine computes a local sparse LDA estimator using its data subset.
  2. Debiasing: To counteract the shrinkage bias inherent in sparse penalties, workers perform a debiasing step. This involves using a CLIME estimator to approximate the precision matrix (inverse covariance matrix) and adjusting the local estimate to "undo" the bias.
  3. Communication: Workers transmit only a $d$-dimensional debiased vector to a master machine, avoiding the high cost of sending $d \times d$ matrices.
  4. Aggregation & Sparsification: The master machine averages the received vectors and applies hard thresholding to produce the final sparse discriminant vector.

A key theoretical insight is the $\sqrt{N}$ limit: as long as the number of machines $m$ is less than approximately $\sqrt{N}$ (where $N$ is the total sample size), the distributed model performs as well as the centralized one. Furthermore, the distributed method can achieve model selection consistency under milder conditions than centralized LDA.

Experimental Results

The method was evaluated on synthetic high-dimensional data ($d=200$) and the UCI Heart Disease dataset.

Synthetic Data Performance

On synthetic tests, the proposed distributed LDA method demonstrated statistical parity with the centralized approach. As shown in Figure 1, the $F_1$ score for support recovery and estimation errors ($\ell_2$ and $\ell_\infty$ norms) for the distributed method closely track the centralized benchmark, whereas naive averaging performance degrades significantly as the number of machines increases.

Performance comparison on synthetic data showing F1 scores and estimation errors.

Real-World Application: Heart Disease Dataset

The Heart Disease dataset, comprising 920 patient records across four hospitals, naturally fits a distributed setting. The proposed method achieved a misclassification rate of 0.220, which is remarkably close to the centralized result (0.208) and significantly better than the naive average (0.329), as detailed in Table 1.

Misclassification rates on the Heart Disease dataset (m=4).

Beyond accuracy, the method offers substantial computational gains. In large-scale experiments ($10^6$ samples), the distributed version with 100 machines completed in ~10 seconds, compared to ~863 seconds for the centralized approach.

Conclusion and Future Work

The proposed distributed sparse LDA method effectively balances communication efficiency and statistical precision. While it currently focuses on binary classification, future work will extend the framework to multi-class LDA. Other areas for exploration include automated hyperparameter tuning in distributed environments and relaxing the Gaussian data assumption to accommodate heavy-tailed distributions.

Summary updated

Abstract

We propose a communication-efficient distributed estimation method for sparse linear discriminant analysis (LDA) in the high dimensional regime. Our method distributes the data of size N into m machines, and estimates a local sparse LDA estimator on each machine using the data subset of size N/m. After the distributed estimation, our method aggregates the debiased local estimators from m machines, and sparsifies the aggregated estimator. We show that the aggregated estimator attains the same statistical rate as the centralized estimation method, as long as the number of machines m is chosen appropriately. Moreover, we prove that our method can attain the model selection consistency under a milder condition than the centralized method. Experiments on both synthetic and real datasets corroborate our theory.
BibTeX
@inproceedings{tian2017communication,
  author = {Lu Tian and Quanquan Gu},
  title = {{Communication-efficient Distributed Sparse Linear Discriminant Analysis}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2017},
  url = {https://openreview.net/forum?id=a0CsiNMgP5},
}
Figure