Abstract: Detecting the interaction effects among the predictors on the response variable is a crucial step in numerous applications. We first propose a simple method for sure screening interactions (SSI). Although its computation complexity is O(p²n), the SSI method works well for problems of moderate dimensionality (e.g., p = 10³ ~ 104), without the heredity assumption. For ultrahigh-dimensional problems (e.g., p = 106), motivated by a discretization associated Boolean representation and operations and a contingency table for discrete variables, we propose a fast algorithm, called “BOLT-SSI.” The statistical theory is established for SSI and BOLT-SSI, guaranteeing their sure screening property. We evaluate the performance of SSI and BOLT-SSI using comprehensive simulations and real case studies. Our numerical results demonstrate that SSI and BOLT-SSI often outperform their competitors in terms of computational efficiency and statistical accuracy. The proposed method can be applied to fully detect interactions with more than 300,000 predictors. Based on our findings, we believe there is a need to rethink the relationship between statistical accuracy and computational efficiency. We have shown that the computational performance of a statistical method can often be greatly improved by exploring the advantages of computational architecture with a tolerable loss of statistical accuracy.

Key words and phrases: Discretization, package “BOLTSSIRR”, sure independent screening for interaction detection, trade-off between statistical efficiency and computational complexity, ultra-high dimensionality.