Research map / Learning theory and algorithms / Prediction and decision losses

Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination

ICML 2025 · Learning theory and algorithms › Prediction and decision losses · approach: Active learning and subset selection · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes objective-based feature selection and elimination criteria obtained by exactly solving the entry/exit subproblems of best subset selection, and plugs them into OMP, CoSaMP, and ABESS to yield OP, CoSaOP, and OP-(A)BESS with no extra asymptotic cost.

Problem

Classical greedy best subset selection criteria (correlation-based selection and Wald-T elimination) only capture the one-step objective change from support updates with fixed coefficients, ignoring feature interactions and coefficient refitting.

Approach

Reformulate feature entry and exit as exact optimization subproblems (solved via forward and backward block matrix inversion) yielding projection-based criteria that account for interactions with the current active set; substitute these criteria into existing greedy algorithms (meta-substitution).

Key results

• On synthetic data at measurement rate 0.25, OP achieves nearly 3x more successful recoveries than OMP, and CoSaOP outperforms CoSaMP by at least 4x in all scenarios.
• On AudioSet signals, OP-(A)BESS reduces NMSE versus (A)BESS by 30% to 91% across four audio clips (e.g., 91% on Audio 2).
• On sparse regression, OP and OP-(A)BESS give roughly 0.1 R^2 improvement, described as equivalent to selecting 10 more features.

Measured effects reported in the paper

Surprising findings

• CoSaMP fails in the sparse regression task, while the enhanced CoSaOP remains effective.
• A criterion similar to the proposed selection criterion (SMP) was independently published in a submodular-perspective paper.

Limitations

• Theoretical guarantees rely on RIP-type assumptions, which the authors note are invalid under high feature correlation.
• Criteria derived for least-squares objectives; extension to general objectives is left to future work.

Experimental setup

Datasets: AudioSet Boston Housing California Housing Superconductivity House 16H Prostate.v8.egenes Spectra

Benchmarks: AudioSet signal recovery (NMSE) synthetic sparse recovery (successful recovery counts) Boston Housing California Housing Superconductivity House 16H Prostate.v8.egenes Spectra

Metrics: number of successful recoveries NMSE R^2 runtime

Baselines: OMP CoSaMP (A)BESS MP LASSO

Builds on: ABESS OMP CoSaMP Gradient Pursuit

Closest papers by meaning

• A Probabilistic Derivation of LASSO and L12-Norm Feature Selections (AAAI 2019 · similarity 0.87)
• Optimal Sparse Recovery with Decision Stumps (AAAI 2023 · similarity 0.87)
• Most Influential Subset Selection: Challenges, Promises, and Beyond (NeurIPS 2024 · similarity 0.87)
• Improved Theoretically-Grounded Evolutionary Algorithms for Subset Selection with a Linear Cost Constraint (ICML 2025 · similarity 0.85)
• Differentially Private High-dimensional Variable Selection via Integer Programming (NeurIPS 2025 · similarity 0.84)
• Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Selection over Partition Constraints (ICML 2025 · similarity 0.83)