A more efficient method for large-sample model-free feature screening via multi-armed bandits
Xiaxue Ouyang, Xinlai Kang, Mengyu Li, Zhenxing Dou, Jun Yu, Cheng Meng · 2025
Read A more efficient method for large-sample model-free feature screening via multi-armed bandits by Xiaxue Ouyang, Xinlai Kang, Mengyu Li, Zhenxing Dou, Jun Yu, Cheng Meng (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-16085.txt.
Introduction
Screening thousands of traits for the few that matter is a core step in large data work, but the standard screen scans every row for every trait. Xiaxue Ouyang, Kejun He, and Cheng Meng speed it up with a method that grows its sample bit by bit, in the spirit of bandit problems. Traits with weak links to the outcome are dropped early, which saves work.
Their method cuts the scan cost sharply while keeping the trait-finding promise of the older screen. Clear theory shows how sample size trades against accuracy. On made-up and real data, results match the standard screen at much lower run time.
Catalog record
| CREATOR | Xiaxue Ouyang, Xinlai Kang, Mengyu Li, Zhenxing Dou, Jun Yu, Cheng Meng |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 55 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-16085
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A more efficient method for large-sample model-free feature screening via multi-armed bandits Xiaxue Ouyang, Xinlai Kang, Mengyu Li, Zhenxing Dou, Jun Yu, Cheng Meng Abstract We consider the model-free feature screening in large-scale ultrahigh-dimensional data analysis. Existing feature screening methods often face substantial computational challenges when dealing with large sample sizes. To alleviate the computational burden, we propose a rank-based model-free sure independence screening method (CR-SIS) and its efficient variant, BanditCR-SIS. The CR-SIS method, based on Chatterjee’s rank correlation, is as straightforward to implement as the sure independence screening (SIS) method based on Pearson correlation introduced by Fan and Lv 2008 , but it is significantly more powerful in detecting nonlinear relationships between variables. Motivated by the multi-armed bandit (MAB) problem, we reformulate the feature screening procedure to significantly reduce the computational complexity of CR-SIS. For a predictor matrix of size n × p n\times p , the computational cost of CR-SIS is O ( n log ( n ) p ) O(n\log(n)p) , while BanditCR-SIS reduces this to O ( n log ( n ) p + n log ( n ) ) O(\sqrt{n}\log(n)p+n\log(n)) . Theoretically, we establish the sure screening property for both CR-SIS and BanditCR-SIS under mild regularity conditions. Furthermore, we demonstrate the effectiveness of our methods through extensive experimental studies on both synthetic and real-world datasets. The results highlight their superior performance compared to classical screening methods, requiring significantly less computational time. Keywords: Big data; Variable selection; Sure independence screening; Chatterjee’s Rank 1 Introduction In recent years, rapid advances in science and technology have led to explosive growth in high-dimensional data, which has become increasingly common in various academic and industrial domains. Some fields have pushed this trend even further, giving rise to ultrahigh-dimensional data, particularly in areas such as bioinformatics, medical imaging, computer vision, and social network analysis ( Fan and Ren 2006 ; Weinberger et al. 2009 ; Pang et al. 2018 ; Ghorbani et al. 2020 ) . In such datasets, the number of features often far exceeds the available sample size, with dimensionality reaching thousands or even millions-several magnitudes larger. For example, thousands of gene expression profiles are used for disease classification ( Chen et al. 2020 ) , while millions of single nucleotide polymorphisms (SNP) are analyzed in genome-wide association studies to explore the relationship between genotypes and phenotypes (dbGaP Study Accession: phs000368.v1.p1 ). While these ultrahigh-dimensional datasets offer unprecedented opportunities for discovery, they also present significant challenges for traditional statistical and machine learning algorithms. Analyzing and modeling functional relationships in the presence of redundant and noisy features can be quite challenging due to computational burden, memory cost, statistical accuracy, and algorithmic stability ( Fan et al. 2009 ; Hall and Miller 2009 ; Lv and Liu 2014 ) . To address the challenges posed by ultrahigh dimensionality, Fan and Lv 2008 highlighted the importance of feature screening and introduced a widely adopted method known as sure independence screening (SIS) within the framework of the linear regression model. Feature screening aims to use some marginal utility measures to efficiently reduce the dimensionality of data, scaling it down from an extremely high dimension to a moderate size. For example, the SIS method eliminates redundant features in the linear regression model by ranking the absolute values of marginal Pearson correlations with the response and attempts to retain all the important features at the same time. This is referred to as the sure screening property, which states that the selected features will contain all the informative ones with probability approaching one when the sample size goes to infinity. SIS has demonstrated a significant impact in the study of ultrahigh-dimensional data. However, it relies on the linear regression model, which poses substantial limitations. To address these, SIS has been extended beyond the simple linear model to more diverse model settings, including generalized linear models ( Fan and Song 2010 ) , nonparametric regression models such as additive models ( Fan et al. 2011 ) , and varying coefficient models ( Fan et al. 2014 ) , as well as applications to the categorical response ( Fan and Fan 2008 ) . Although these model-based methods are effective under the assumption that the specified model closely approximates the true underlying relationship, they can perform poorly when this assumption is violated, especially in cases where the relationship between variables is complex or unknown. These limitations have prompted researchers to explore model-free approaches. Examples include sure independent ranking and screening (SIRS) ( Zhu et al. 2011 ) , distance correlation-based screening (DC-SIS) ( Li et al. 2012 ) , and projection correlation-based screening (PC-SIS) ( Xu et al. 2020 ) , among others. In situations where the number of features is large and little prior information is available about the true model, model-free methods become particularly valuable. Although these model-free methods have already shown great performance and enjoy strong theoretical properties, they may suffer from huge computational costs in practice. For a predictor matrix of size n\times p , the computational cost of SIRS is at the order of O(n\log(n)p) . The computational costs of the other two methods, DC-SIS and PC-SIS, are even higher, with complexities of O(n^{2}p) and O(n^{3}p) , respectively. Such high computational costs limit the practicality of model-free methods for large-scale datasets, when both the sample size n and the number of features p are considerable, especially in the case where n has several millions. In this paper, we propose a new model-free feature screening framework based on Chatterjee’s rank correlation ( Chatterjee 2021 ) , a recently proposed rank-based marginal utility measure that has attracted great attention. Like distance correlation, Chatterjee’s rank correlation measures the dependence between the predictor and the response, taking a value of zero if and only if the variables are independent. However, applying Chatterjee’s rank correlation for feature screening also comes with a computational cost of O(n\log(n)p) , which can be burdensome for large datasets. To alleviate the computational burden mentioned above, we propose a more efficient method based on CR-SIS for a large-sample case. Inspired by the multi-arm bandit problem ( Even-Dar et al. 2006 ; Bubeck et al. 2009 ; Audibert and Bubeck 2010 ; Jamieson and Nowak 2014 ) , we reformulate the feature screening process as a best-arm identification task. In the standard best-arm identification problem, a multi-arm bandit machine is equipped with p arms, where pulling a given arm yields a reward drawn from an unknown corresponding distribution. One goal is to identify the arm with the highest expected reward within a specified accuracy and probability. Analogously, in our framework, the p features are treated as p arms, the marginal Chatterjee’s rank correlation serves as the rewards, and the task is to identify the top d most important features (the best d arms). This approach aims to efficiently eliminate features with the smallest marginal utilities while retaining the most significant ones with an overwhelming probability. Using this bandit-inspired methodology, our proposed method significantly reduces computational overhead, making it suitable for large-scale feature screening tasks. Our major contributions are summarized as follows. First, we introduce a novel rank-based marginal utility measure for feature screening (CR-SIS)