By Nivedita Bhaskhar - September 3, 2021
Variable selection with error control: another look at stability selection by R.D. Shah and R.J. Samworth.
Why CPSS ?
The original stability selection procedure (SS), broadly speaking, improves the performance of a base variable selection procedure () by aggregating the results of applying to subsamples of the dataset. However the guarantee of an upper bound on the expected number of noise variables which get selected by SS holds only under the following assumptions on the base procedure - a) that is better than random guessing and b) a strong exchangeability condition on the selection of noise variables holds. Further, the guaranteed upper bound tends to be weak and often, a precise calculation of the estimator used in SS is impossible because it involves running over all subsets of size from a dataset of size .
Complementary Pairs Stability Selection (CPSS) introduced in this paper is a closely related variant of stability selection. Instead of segregating variables into noise and signal, they are split into two disjoint groups - variables that have low (resp. high) probability of getting selected by base procedure . The authors derive upper bounds without any further assumptions on for a) the average number of low selection (by M) probabilities variables which are selected by CPSS and b) the average number of high selection (by M) probabilities variables which are NOT selected by CPSS where guarantee a) can be further strengthened under reasonable shape restrictions. Finally, the estimator used in the CPSS procedure involves the number of splits and the guarantees derived above hold for any .
Assumptions and notations:
Fix a and fix a .
We call feature to be a low selection probability feature if the probability that it gets selected by procedure is at most . If not, we call it a *high selection probability feature.*Thus the features are segregated into two disjoint subsets of low selection probability features () and high selection probability features ()
Broadly speaking, if , we have a guarantee that the average number of low selection probability features picked by the CPPS procedure is upper bounded by a quantity proportional to the average number of low selection probability features picked by . More formally,
Similarly, if , we have a guarantee that the average number of high selection probability features NOT picked by the CPPS procedure is upper bounded by a quantity proportional to the average number of high selection probability features NOT picked by . More formally,
In fact, if the assumptions needed for the original stability selection (SS) guarantee actually hold, then the CPSS guarantee (a) recovers the original SS guarantee.
Stronger CPSS guarantees for restricted distributions: