High Dimensional Linear Discriminant Analysis: Optimality, Adaptive Algorithm and Missing Data

Tommaso Cai, Linjun ZhangJournal of the Royal Statistical Society Series B (Statistical Methodology) 2019 · DOI

TL;DR

This paper introduces novel, data-driven algorithms (AdaLDA and ADAM) for high-dimensional linear discriminant analysis, both with complete and missing data. These algorithms achieve theoretically optimal classification rates, adapting to data sparsity and signal-to-noise ratio, and outperform existing methods in simulations and real-world datasets.

What Problem Does This Paper Address?

Linear Discriminant Analysis (LDA) is a powerful classification technique, but its traditional form struggles in high-dimensional settings where the number of features (p) far exceeds the number of samples (n). In such scenarios, the sample covariance matrix becomes unstable and even non-invertible, rendering standard LDA unusable. While existing methods have attempted to address this, they often require careful tuning of parameters or lack theoretical guarantees of optimality. Furthermore, real-world data frequently contains missing values, posing an additional challenge for high-dimensional classification. This paper aims to bridge these gaps by developing theoretically sound, adaptive, and robust LDA methods for high-dimensional data, including scenarios with missing observations.

Methods

The authors propose two main algorithms:

  • AdaLDA (Adaptive Linear Discriminant Analysis): For complete data, AdaLDA is a three-step, data-driven approach that adapts to the variability of individual features. It uses an $l_1$-minimization framework but crucially, the constraints are made entry-dependent, accounting for the heteroscedasticity of the data. This makes it "tuning-free," meaning it doesn't require manual parameter selection like cross-validation.
  • ADAM (Adaptive Linear Discriminant Analysis with randomly Missing data): This algorithm extends AdaLDA to handle data with missing values under the Missing Completely at Random (MCR) model. It employs "generalized sample means" and "generalized sample covariance matrices" to estimate the necessary parameters from incomplete data. A key technical contribution is a large deviation result for these generalized estimators, which is crucial for theoretical analysis.

Both algorithms are designed to be computationally efficient, cast as linear programs. The theoretical contributions include establishing minimax lower bounds and proving that AdaLDA and ADAM achieve these optimal rates, demonstrating their adaptivity to data characteristics.

Datasets

The paper uses two real-world datasets for evaluation:

  • Lung Cancer Data: This dataset consists of 181 tissue samples with 12,533 genes, used to classify malignant pleural mesothelioma (MPM) from adenocarcinoma (ADCA).
  • Leukemia Data: This dataset comprises 72 tissue samples with 7,129 genes, used to distinguish between acute myeloid leukemia (AML) and acute lymphoblastic leukemia (ALL).

These datasets are standard benchmarks in high-dimensional classification research. The authors also conduct extensive simulations using three different models for the covariance matrix (Erdős-Rényi random graph, Block sparse model, and AR(1) model) to evaluate performance under various data structures.

Key Insights and Ideas

  • Adaptive Constraints are Key: The core innovation for complete data (AdaLDA) is making the $l_1$-minimization constraints adaptive to individual feature variability. This is a significant improvement over methods that use uniform constraints, allowing the algorithm to better handle heteroscedasticity.
  • Tuning-Free is Achievable: The proposed AdaLDA algorithm is "tuning-free," meaning it automatically determines necessary parameters from the data. This simplifies practical application and avoids the potential variability and theoretical uncertainty associated with cross-validation.
  • Missing Data is Tractable: The ADAM algorithm demonstrates that robust and theoretically sound LDA is possible even with missing data, by carefully defining generalized estimators and proving their statistical properties.
  • Theoretical Optimality: The paper provides rigorous theoretical guarantees, showing that both AdaLDA and ADAM achieve minimax optimal rates of convergence. This means they perform as well as any possible algorithm under the given assumptions.
  • Large Deviation for Generalized Covariance: A significant technical tool developed is a large deviation result for generalized sample covariance matrices, which is crucial for analyzing the missing data case and may be useful for other high-dimensional inference problems.

Key Results

  • Simulation Performance: In simulations, AdaLDA and ADAM consistently outperformed existing methods (LPD, SLDA, FAIR, NSC, Naive Bayes) in terms of misclassification error across various models and missingness proportions. For instance, in Model 2, ADAM achieved misclassification rates as low as 0.20% with 5% missing data, significantly better than other methods.
  • Real Data Performance: On the Lung Cancer dataset, AdaLDA achieved a testing error of 3.22% (with 5% missing data for ADAM at 5.53%), outperforming LPD, FAIR, and NSC. For the Leukemia dataset, AdaLDA achieved a misclassification error of 2.94%, comparable to LPD and FAIR, while ADAM also showed satisfactory accuracy (7.53% with 5% missing data).
  • Theoretical Guarantees: The paper establishes minimax lower bounds for both estimation and classification risks and proves that AdaLDA and ADAM attain these bounds, demonstrating their adaptive optimality.

Limitations and Future Work

  • MCR Assumption: The ADAM algorithm relies on the Missing Completely at Random (MCR) assumption. While this is a standard assumption, real-world missingness mechanisms can be more complex (e.g., Missing Not At Random - MNAR). Extending the methods to handle such cases would be a valuable future direction.
  • Computational Cost: While the algorithms are cast as linear programs, the theoretical analysis involves complex bounds. The paper mentions that computational costs were reduced in real data analysis by selecting a subset of genes, but further optimization for extremely large datasets might be explored.
  • Generalization to Other Models: The theoretical optimality is established for Gaussian distributions. Investigating the performance and optimality of these methods for non-Gaussian data distributions would be a natural extension.

Summary updated

Abstract

Summary The paper develops optimality theory for linear discriminant analysis in the high dimensional setting. A data-driven and tuning-free classification rule, which is based on an adaptive constrained l1-minimization approach, is proposed and analysed. Minimax lower bounds are obtained and this classification rule is shown to be simultaneously rate optimal over a collection of parameter spaces. In addition, we consider classification with incomplete data under the missingness completely at random model. An adaptive classifier with theoretical guarantees is introduced and the optimal rate of convergence for high dimensional linear discriminant analysis under the missingness completely at random model is established. The technical analysis for the case of missing data is much more challenging than that for complete data. We establish a large deviation result for the generalized sample covariance matrix, which serves as a key technical tool and can be of independent interest. An application to lung cancer and leukaemia studies is also discussed.
BibTeX
@article{cai2019high,
  author = {Tommaso Cai and Linjun Zhang},
  title = {{High Dimensional Linear Discriminant Analysis: Optimality, Adaptive Algorithm and Missing Data}},
  journal = {Journal of the Royal Statistical Society Series B (Statistical Methodology)},
  year = {2019},
  doi = {10.1111/rssb.12326},
}
Figure