Interaction Screening for Ultra-High Dimensional Data.
In ultra-high dimensional data analysis, it is extremely challenging to identify important interaction effects, and a top concern in practice is computational feasibility. For a data set withnobservations andppredictors, the augmented design matrix including all linear and order-2 terms is of sizen× (p2+ 3p)/2. Whenpis large, say more than tens of hundreds, the number of interactions is enormous and beyond the capacity of standard machines and software tools for storage and analysis. In theory, the interaction selection consistency is hard to achieve in high dimensional settings. Interaction effects have heavier tails and more complex covariance structures than main effects in a random design, making theoretical analysis difficult. In this article, we propose to tackle these issues by forward-selection based procedures called iFOR, which identify interaction effects in a greedy forward fashion while maintaining the natural hierarchical model structure. Two algorithms, iFORT and iFORM, are studied. Computationally, the iFOR procedures are designed to be simple and fast to implement. No complex optimization tools are needed, since only OLS-type calculations are involved; the iFOR algorithms avoid storing and manipulating the whole augmented matrix, so the memory and CPU requirement is minimal; the computational complexity islinearinpfor sparse models, hence feasible forp≫n. Theoretically, we prove that they possess sure screening property for ultra-high dimensional settings. Numerical examples are used to demonstrate their finite sample performance.
Assistant Professor, Department of Mathematics, University of Arizona, Tucson, AZ 85721.
Ning
N
Hao
Associate Professor, Department of Mathematics, University of Arizona, Tucson, AZ 85721.
Hao Helen
HH
Zhang
Forward selection; GWAS; Heredity condition; Interaction; Sure Screening