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.
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).
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