Robust Screening and Partitioning for Feature Selection: A Binary Simulation Optimization Problem

Feature selection is the process of eliminating irrelevant or redundant covariates in a dataset to construct generalizable interpretable predictions. It is an NP-hard combinatorial problem with only heuristic or model-dependent greedy solution methods. To improve robustness, previous work proposed a zero-one simulation optimization by independently replicating model construction and out-of-sample error calculation. Genetic algorithms were used to solve feature selection showing improved robustness compared to existing techniques, albeit being slow, sensitive to hyperparameters, and lacking convergence guarantees. We propose a stochastic binary search method based on nested partitioning informed by an initial rapid screening phase. With new mechanisms for sampling, we propose steps to efficiently reduce the feature space and obtain an intelligent partitioning scheme. Our experiments show that our proposed algorithm finds fewer irrelevant features, is less sensitive to the data size, and is faster than competing methods.