Unifying the Subset Selection Problem in Machine Learning

Many machine learning tasks, including feature and data selection, ensemble pruning, and circuit discovery, reduce to maximizing an expensive set function over a finite ground set. Existing methods exploit structural properties such as modularity, submodularity, or low degree; we develop certificates that quantify these properties and find that none hold exactly for any of the 321 set functions in our benchmark. Likelihood-free Bayesian optimization (LFBO) offers a natural alternative when such assumptions fail by adaptively learning improvement above a threshold, but it was developed primarily for continuous hyperparameter optimization rather than exponentially large Boolean search spaces. We adapt LFBO to subset selection using tree-ensemble surrogates, which can efficiently represent the sparse, low-degree, and hierarchical interactions we find in these set functions. Across all four domains, our method ranks first in three at equal query budget and second in circuit discovery, where it achieves quality comparable to the strongest Gaussian-process BO baseline at substantially lower computational cost.