Distributed Sparse Multicategory Discriminant Analysis

Hengchao Chen, Qiang SunAISTATS 2022 · OpenReview

Abstract

This paper proposes a convex formulation for sparse multicategory linear discriminant analysis and then extends it to the distributed setting when data are stored across multiple sites. The key observation is that for the purpose of classification, it suffices to recover the discriminant subspace which is invariant to orthogonal transformations. Theoretically, we establish statistical properties ensuring that the distributed sparse multicategory linear discriminant analysis performs as well as the centralized version after a few rounds of communications. Numerical studies lend strong support to our methodology and theory.

Introduction

Linear Discriminant Analysis (LDA) is a cornerstone of statistical classification and dimensionality reduction. However, modern data environments present two significant challenges: high dimensionality ($d \gg N$) and distributed storage. In high-dimensional settings, standard LDA fails because covariance matrices become singular and noise accumulation leads to poor predictive performance. Furthermore, when data is scattered across multiple servers due to privacy concerns or sheer scale, centralizing raw data is often impractical due to bandwidth and time constraints.

While sparse LDA (SLDA) addresses high dimensionality, existing multicategory extensions are frequently non-convex—making them difficult to solve—or lack scalability for distributed systems. This paper introduces dmSLDA, a communication-efficient, convex approach for multicategory classification in high-dimensional distributed environments.

Methodology: The dmSLDA Framework

The proposed Distributed Sparse Multicategory Discriminant Analysis (dmSLDA) leverages several key innovations to achieve centralized-level performance with minimal communication overhead.

Subspace Recovery and Convexity

A central insight of this work is that classification does not require recovering specific "Fisher vectors." Instead, it is sufficient to identify any set of vectors that span the same discriminant subspace. This realization allows the authors to transform the typically non-convex multicategory LDA problem into a convex optimization task, ensuring computational efficiency and the guarantee of finding a global optimum.

Regularization and Distribution

The algorithm employs $\ell_{1,1}$ regularization (element-wise sparsity) rather than row-sparsity ($\ell_{2,1}$). This choice facilitates easier distribution across multiple machines. The framework utilizes a Communication-Efficient Surrogate Likelihood (CSL) approach: a master node broadcasts the current model to worker nodes, which compute gradients based on their local data. These gradients are returned to the master to update the global model.

This iterative refinement typically converges in 3 to 5 rounds. The communication cost is $O(dKM)$, where $K$ is the number of classes and $M$ is the number of machines. Since $K$ is usually very small compared to the number of samples or features, this is significantly cheaper than sending raw data.

Experimental Results

The authors evaluated dmSLDA using synthetic datasets simulating high-dimensional ($d=400$), multicategory ($K=3$) scenarios across $M=20$ to $60$ machines.

Performance in Multicategory Settings

Numerical results demonstrate that the dmSLDA estimator achieves estimation accuracy and misclassification rates (MCR) nearly identical to the centralized and theoretical "Oracle" models. It significantly outperforms "Local" models trained on isolated data subsets, which suffer from limited sample sizes.

Estimation error and misclassification rate (mcr.mean) for dmSLDA compared to local, centralized, and oracle models across different noise levels (sigma).

As shown in the figure above, dmSLDA maintains robustness across varying noise levels ($\sigma = 0, 0.5, 0.8$), indicating its ability to handle complex feature dependencies effectively. The MCR of dmSLDA consistently tracks the Oracle performance, proving its effectiveness in practical classification tasks.

Binary Classification Comparison

In binary classification tests ($d=200$, $M \le 30$), dmSLDA was compared against distributed Support Vector Machines (dSVM) and specialized distributed sparse LDA (dSLDA).

Comparison of misclassification rates in a binary classification task between dmSLDA, dSLDA, dSVM, and centralized SLDA.

The results indicate that dmSLDA performs on par with specialized binary dSLDA methods and consistently outperforms dSVM, highlighting its versatility even in the simplest classification scenarios.

Conclusion and Future Work

The dmSLDA algorithm provides a robust, communication-efficient solution for high-dimensional multicategory classification. By focusing on subspace recovery and utilizing a convex formulation, it achieves the statistical convergence rates of centralized estimators without the need for massive data transfers.

Future research may address current limitations, such as the assumption of sub-Gaussian distributions and the focus on balanced class sizes. Extending the framework to handle heavy-tailed data or adversarial conditions remains a promising direction for enhancing the robustness of distributed discriminant analysis in real-world applications.

Summary updated

Abstract

This paper proposes a convex formulation for sparse multicategory linear discriminant analysis and then extend it to the distributed setting when data are stored across multiple sites. The key observation is that for the purpose of classification it suffices to recover the discriminant subspace which is invariant to orthogonal transformations. Theoretically, we establish statistical properties ensuring that the distributed sparse multicategory linear discriminant analysis performs as good as the centralized version after a few rounds of communications. Numerical studies lend strong support to our methodology and theory.
BibTeX
@inproceedings{chen2022distributed,
  author = {Hengchao Chen and Qiang Sun},
  title = {{Distributed Sparse Multicategory Discriminant Analysis}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2022},
  url = {https://openreview.net/forum?id=aFgKrp9_87},
}
Figure