Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination

Zhihan Zhu, Yanhao Zhang, Yong Xia
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:80398-80426, 2025.

Abstract

This paper introduces two novel criteria: one for feature selection and another for feature elimination in the context of best subset selection, which is a benchmark problem in statistics and machine learning. From the perspective of optimization, we revisit the classical selection and elimination criteria in traditional best subset selection algorithms, revealing that these classical criteria capture only partial variations of the objective function after the entry or exit of features. By formulating and solving optimization subproblems for feature entry and exit exactly, new selection and elimination criteria are proposed, proved as the optimal decisions for the current entry-and-exit process compared to classical criteria. Replacing the classical selection and elimination criteria with the proposed ones generates a series of enhanced best subset selection algorithms. These generated algorithms not only preserve the theoretical properties of the original algorithms but also achieve significant meta-gains without increasing computational cost across various scenarios and evaluation metrics on multiple tasks such as compressed sensing and sparse regression.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-zhu25ad, title = {Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination}, author = {Zhu, Zhihan and Zhang, Yanhao and Xia, Yong}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {80398--80426}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/zhu25ad/zhu25ad.pdf}, url = {https://proceedings.mlr.press/v267/zhu25ad.html}, abstract = {This paper introduces two novel criteria: one for feature selection and another for feature elimination in the context of best subset selection, which is a benchmark problem in statistics and machine learning. From the perspective of optimization, we revisit the classical selection and elimination criteria in traditional best subset selection algorithms, revealing that these classical criteria capture only partial variations of the objective function after the entry or exit of features. By formulating and solving optimization subproblems for feature entry and exit exactly, new selection and elimination criteria are proposed, proved as the optimal decisions for the current entry-and-exit process compared to classical criteria. Replacing the classical selection and elimination criteria with the proposed ones generates a series of enhanced best subset selection algorithms. These generated algorithms not only preserve the theoretical properties of the original algorithms but also achieve significant meta-gains without increasing computational cost across various scenarios and evaluation metrics on multiple tasks such as compressed sensing and sparse regression.} }
Endnote
%0 Conference Paper %T Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination %A Zhihan Zhu %A Yanhao Zhang %A Yong Xia %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-zhu25ad %I PMLR %P 80398--80426 %U https://proceedings.mlr.press/v267/zhu25ad.html %V 267 %X This paper introduces two novel criteria: one for feature selection and another for feature elimination in the context of best subset selection, which is a benchmark problem in statistics and machine learning. From the perspective of optimization, we revisit the classical selection and elimination criteria in traditional best subset selection algorithms, revealing that these classical criteria capture only partial variations of the objective function after the entry or exit of features. By formulating and solving optimization subproblems for feature entry and exit exactly, new selection and elimination criteria are proposed, proved as the optimal decisions for the current entry-and-exit process compared to classical criteria. Replacing the classical selection and elimination criteria with the proposed ones generates a series of enhanced best subset selection algorithms. These generated algorithms not only preserve the theoretical properties of the original algorithms but also achieve significant meta-gains without increasing computational cost across various scenarios and evaluation metrics on multiple tasks such as compressed sensing and sparse regression.
APA
Zhu, Z., Zhang, Y. & Xia, Y.. (2025). Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:80398-80426 Available from https://proceedings.mlr.press/v267/zhu25ad.html.

Related Material