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

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.