acceptodds
Under review as a conference paper at ICLR 2027

Unifying the Subset Selection Problem in Machine Learning

Abstract

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.

Primary area:
optimization
Keywords:
subset selection, data shapley, bayesian optimization, feature selection, data selection

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_srBXOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper unifies feature selection, data selection, ensemble pruning, and circuit discovery as subset selection problems. It finds that common structural assumptions, such as submodularity, do not hold exactly in its benchmark. The authors propose S-LFBO, which combines tree-based models of improvement with warm-started simulated annealing. Across 321 objectives, it performs strongly under limited evaluation budgets and achieves competitive results at lower computational cost than Gaussian-process Bayesian optimization.

Critical strengths

The paper provides a unified formulation of four important subset selection tasks. Its structural analysis offers a clear motivation for using tree-based surrogates to learn improvement targets. The evaluation is extensive, covering 321 objectives under both query and runtime budgets, and demonstrates strong empirical performance with relatively low computational overhead.

Critical weaknesses

Relative to LFBO, the method mainly modifies the initial sampling, surrogate model, and candidate search while retaining the core learning objective. The distinct contribution of these modifications and their applicability should be clarified.

Questions for authors
  1. The paper examines additive, pairwise, MTM, monotone, submodular, and supermodular structures. Given that function evaluations are noisy in some tasks, how do the authors distinguish genuine structural violations from apparent violations caused by evaluation noise? Were the identified counterexamples evaluated repeatedly?
  2. How does S-LFBO perform on problems that strictly satisfy these structural properties? How does it compare, in solution quality and computational cost, with methods that exploit the corresponding structure and have theoretical guarantees?
  3. Could replacing the current hard thresholding with a smooth approximation improve surrogate learning and optimization performance? Have the authors considered such a comparison?
  4. Do the authors plan to release the code and experimental configurations upon acceptance?
2 comments

We thank the reviewer for their time and effort put into the review. We appreciate their recognition of our “unified formulation of four important subset selection tasks”. We address the remaining concerns below.

[R1] Differences between S-LFBO and LFBO ([W1])

The distinct contribution of these modifications and their applicability should be clarified. ([W1])

Thank you for highlighting this point. The impact of these modifications are shown in Figure 9 and Appendix E.2, and we have updated the caption of Figure 3 to reference those ablations. At 100 queries, the maximizer contributes the most; with LFBO's random-candidate search, S-LFBO falls behind across all domains. Boosted trees in place of the random forest close part of the gap to LFBO, and the size-uniform design helps mainly at small budgets and in data selection.

[R2] Noisy evaluation. ([Q1])

Given that function evaluations are noisy in some tasks, how do the authors distinguish genuine structural violations from apparent violations caused by evaluation noise? Were the identified counterexamples evaluated repeatedly?

The object of interest is the estimated (noisy) utility. In our experiments, we use a fixed seed, so each utility is a deterministic function of SS. Replacing it with its expectation over ten training seeds changes none of the findings (mean over 18 enumerated TabPFN utilities):

MonotoneSubmod.Supermod.AdditivePairwiseMTM
Fixed seed (Table 5).89.70.30.80.97.91
Expectation over ten seeds.89.70.30.80.97.91
Largest change across utilities.012.014.014.003.011.003

The linear programs still reject MTM and degree two on every expected utility. The counterexamples were not evaluated repeatedly because the function is not noisy. Under the expected utility, the same holds: each of monotonicity, submodularity, and supermodularity stays rejected.

[R3] How does S-LFBO perform on problems that strictly satisfy these structural properties? ([Q2])

Good point! We investigated this in Appendix F.3 (Figure 17), which, for each property, compares S-LFBO performance against the methods developed for that property. For each property, we split the utilities into three groups, and showcase the relative improvement of S-LFBO over that method at 100 queries (x% is median; median property score in parentheses):

Property (its method)Lowest thirdMiddle thirdHighest third
MTM (Data Shapley)2.4% (.59)1.0% (.83)0.5% (.90)
Monotone (take everything)3.7% (.51)3.9% (.74)0.7% (.95)
Submodular (double greedy)3.1% (.58)0.7% (.68)0.1% (.86)
Additive (Data Shapley)1.4% (.55)1.1% (.78)0.7% (.87)
Pairwise (BOCS)0.0% (.78)0.0% (.92)0.0% (.97)
Supermodular (min-cut)0.2% (.17)1.5% (.36)2.8% (.50)

As the property score increases, the domain's baseline reaches S-LFBO performance.

In response to [R2] from reviewer b9Ww, we have also added a controlled experiment (Mirzasoleiman et al., 2020) that is submodular by construction.

[R4] Could replacing the current hard thresholding with a smooth approximation improve surrogate learning and optimization performance?([Q3])

We replaced the hard weights [y−τ]+[y-\tau]_+ with the softplus βlog⁡(1+e(y−τ)/β)\beta\log(1+e^{(y-\tau)/\beta}) (Ament et al., 2023), with β\beta the median of y−τy-\tau over the evaluations above τ\tau. The table gives the gain of softplus over the hard weights in mean rank percentile (positive means softplus is better):

20 queries50 queries100 queries
Feature selection.007.026.006
Data selection.016.004.004
Ensemble pruning.068−.005−.007
Circuit discovery.001.050.032

Smooth weights help at 20 and 50 queries, and at 100 queries the difference is small. We keep the hard weights for their simplicity and because Propositions 1, 3, and 4 apply to them (Appendix E.3, Figure 12b).

[R5] Do the authors plan to release the code and experimental configurations upon acceptance? ([Q4])

The code link was provided in Appendix C.5, and we have additionally added the link to Section 4 for better visibility. Upon acceptance, all necessary resources (in particular, the experimental configurations) will be released to GitHub.

The rebuttal strengthens my positive assessment of the paper. I will maintain my original rating of Weak Accept.

Reviewer_b9WwOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper formulates feature selection, data selection, ensemble pruning, and circuit discovery as expensive set-function maximization. It proposes S-LFBO, an adaptation of likelihood-free Bayesian optimization that learns improvement above a threshold using a tree-ensemble classifier. Its main design choices are sampling across subset sizes and optimizing the surrogate with warm-started simulated annealing. The authors evaluate the method on 321 utility functions and report competitive solution quality with lower computational cost than a Gaussian-process BO baseline.

Critical strengths

A useful common formulation. Bringing four selection tasks into one benchmark makes it possible to compare domain-specific methods with general black-box optimizers under consistent query budgets.

Careful empirical investigation. The paper examines structural properties of the objectives, includes strong baselines, reports both query-limited and time-limited results, and provides ablations of the initial design, surrogate, target, and search procedure.

A practical method. S-LFBO is generally competitive with GP-BO while being faster to refit. The ablations give a credible explanation for why warm-started surrogate optimization matters.

Critical weaknesses
  1. Limited optimization guarantees. The propositions characterize how thresholding affects Fourier and tree representations, but they do not provide a query-complexity bound, regret bound, or approximation guarantee for S-LFBO. The tree-preservation result applies to a single decision tree and does not directly extend to the boosted ensemble used by the method. As S-LFBO treats ff as a black box, an optimization guarantee would require additional assumptions on ff; none is established here.

  2. Limited evidence for generality. Three of the four domains reuse the same pool of 51 tabular datasets, and circuit discovery uses only seven synthetic transformers. Structured subset-selection problems, such as cardinality-constrained log-det maximization, are not evaluated. The results therefore support the method on the selected benchmarks more strongly than they support its effectiveness across subset-selection problems generally.

  3. Modest quality gains over the strongest baseline. At 100 queries, S-LFBO and GP-BO achieve similar average utility in the tabular domains, while GP-BO achieves higher average gains in data selection and circuit discovery. The rank-based results should be presented alongside effect sizes and per-utility distributions so readers can assess the practical size and consistency of the improvement.

Questions for authors

1. Ambiguous “first in 9 of 12 columns” claim. Appendix C.4 states that, for ensemble pruning at 100 queries, a hill-climbing method included in the aggregated others row outranks the gold-marked method in Table 2. The claim therefore appears to refer only to individually displayed methods. Please report the rankings of the methods in others and clarify or revise the 9-of-12 statement.

2. Performance on known(e.g. submodular) objectives is unclear. The benchmark focuses on objectives that violate the structural assumptions examined in the paper. Results on controlled synthetic submodular functions, such as coverage or facility-location objectives, would show how S-LFBO compares with methods designed to exploit that structure. Varying the degree of departure from submodularity would be especially informative.

3. Downstream generalization is not established. In the tabular tasks, subsets are selected and their gains are reported using validation AUC or R2R^2. Please report the selected subsets’ performance on the separate test split to assess whether those gains persist beyond the data used to guide selection.

4. Sensitivity to the threshold is untested. S-LFBO fixes τ\tau at the 2/32/3 quantile, although the paper shows that thresholding changes the structure of the learning target. An ablation across several quantiles would establish whether performance is robust to this choice.

5. Templete is not correct.

4 comments

We would like to thank the reviewer for their time and detailed feedback. We appreciate that the reviewer found our work a “useful common formulation” and highlighted the “careful empirical investigation”. We address the concerns below.

[R1] The propositions characterize how thresholding affects Fourier and tree representations, but they do not provide [...] guarantee for S-LFBO. ([W1])

We agree with the reviewer that an optimization guarantee would require structural assumptions on ff, and we have shown that none of the standard assumptions holds exactly. Our propositions instead address which surrogate class can represent the LFBO target: Thresholding makes the target dense in the Fourier basis, while preserving a compact tree. They motivate the choice of surrogate and target, and are not intended as an optimization guarantee. Identifying novel properties that give an approximation guarantee is interesting future work, though at budgets of 20 to 100 queries a worst-case bound is unlikely to be informative.

[R2] Structured subset-selection problems, such as cardinality-constrained log-det maximization, are not evaluated. (...) / Results on controlled synthetic submodular functions (...). ([W2]/[Q2])

Thank you for the suggestion. We added a submodular benchmark from a practical ML setting: the CRAIG coreset objective (Mirzasoleiman et al., 2020), a facility-location function, on all 51 datasets (new Appendix F.4 and Figure 18).

Share of runs that find the exact optimum (\lambda=.03):

Queries2050100
S-LFBO6%34%60%
GP-BO5%27%54%
Greedy2%37%37%
Data Shapley1%3%3%

S-LFBO is best at 20 and 100 queries, while greedy is best at 50.

We then gradually break submodularity by mixing in the model's validation performance (100 queries):

Submodular share1.00.80.6
S-LFBO60%72%74%
GP-BO54%65%56%
Greedy37%8%4%

[R3] Modest quality gains over the strongest baseline. ([W3])

The rank-based results should be presented alongside effect sizes and per-utility distributions so readers can assess the practical size and consistency of the improvement

Thank you for this suggestion. We added Appendix F.2 (Table 8, Figures 13 and 14) and referenced it in Section 4.1, which presents effect sizes and per-utility distributions. Summary at 100 queries:

Feature sel.Data sel.Ensemble pruningCircuit disc.
Gain over the full set
S-LFBO3.0%2.4%1.8%23.7%
GP-BO2.9%2.5%1.8%25.8%
Data Shapley1.6%0.9%1.1%4.1%
Best known subset4.0%3.2%1.8%28.7%
S-LFBO vs. GP-BO per utility
Wins / ties / losses23 / 50 / 1747 / 67 / 545 / 45 / 11 / 0 / 6
Runtime
Speed-up of S-LFBO over GP-BO2.3x8.1x3.2x4.7x

Our main claims remain unchanged: S-LFBO is a fast, optimized method for the selection problem in machine learning, closely matching the performance of “strong baselines” at lower runtime, outperforming attribution methods.

[R4] Please report the rankings of the methods in others and clarify or revise the 9-of-12 statement. ([Q1])

Table 2 now lists hill climbing and the other strongest baselines separately, and we added Table 9 (Appendix F.6) to report the ranking without the runtime tie-break. Hill climbing ranks first in ensemble pruning at 100 queries solely because of the tie-break; by value alone, it ranks behind S-LFBO. S-LFBO is first in 8 of 12 columns with tie-break by runtime and in 7 of 12 by value. We have updated the manuscript to state 8 of 12.

[R5] Please report the selected subsets’ performance on the separate test split (...). ([Q3])

Thank you for this suggestion, we added test results for all four domains (new Appendix F.7).

The subsets obtained on the validation set do not transfer their gains to the test set in the tabular domains, where all methods end slightly below the full set. This is expected and known as overtuning (Schneider et al., 2025; Loughrey & Cunningham, 2005; Cawley & Talbot, 2010). It is due to a misalignment of the utilities on validation and test sets, which can affect the ranking of optimizers:

Domain (utilities)Method20 queries50 queries100 queries
Feature selectionS-LFBO−0.41−0.32−0.44
Data Shapley−0.05−0.08−0.10
GP-BO−0.51−0.50−0.52
Data selectionS-LFBO−0.27−0.31−0.39
Data Shapley−0.12−0.09−0.18
GP-BO−1.07−0.99−0.97
Ensemble pruningS-LFBO−0.03−0.35−0.42
Data Shapley−0.23−0.34−0.45
GP-BO−0.09−0.37−0.38
Circuit discoveryS-LFBO+8.87+18.60+23.01
Data Shapley0.00+1.12+3.85
GP-BO−5.77+18.89+25.12

In particular for feature and data selection, Data Shapley optimizes the least on the validation utility and loses the least.

There are different strategies to mitigate overtuning (Cawley & Talbot 2010, Nagler et al. 2024, Schneider et al. 2025). A simple method is to increase the validation split from 25% to 50% (Cawley & Talbot 2010, Schneider et al. 2025):

MethodTest gain, 20Test gain, 50Test gain, 100Mean rank, 20Mean rank, 50Mean rank, 100Run time, 20Run time, 50Run time, 100
S-LFBO+0.37+0.62+0.95.39.39.376 s15 s30 s
GP-BO+0.11+0.16+0.63.50.51.5013 s53 s242 s
Data Shapley0.000.00+0.60.42.47.463 s7 s15 s
Data Banzhaf−0.89−0.31+0.25.62.59.554 s9 s16 s
Random search−0.49−0.06−0.19.57.55.614 s9 s17 s

Whether gains on the utility transfer therefore depends on how well the utility estimates test performance, and among the methods compared, S-LFBO transfers best once it does.

[R6] Sensitivity to the threshold is untested. ([Q4])

An ablation across several quantiles would establish whether performance is robust to this choice.

We added this ablation to 244 utilities across all four domains (Appendix E.3, Figure 12). Here τ=1−γ\tau = 1- \gamma quantile of the observed value, and we ablate across several choices of γ\gamma. We compare the mean rank percentile relative to our default at γ=1/3\gamma = 1/3 at 100 queries (positive is worse):

γ\gammaFeature sel.Data sel.Ensemble pruningCircuit disc.
0.1+.043+.014−.001.000
0.2+.028.000.000−.011
1/3 (default)0000
0.5−.006−.007+.006+.020

A stricter threshold (γ<1/3\gamma < 1/3) costs in feature selection at both settings and in data selection at γ=0.1\gamma = 0.1, and is level elsewhere. Those results are supported by Propositions 1 and 4, as the share of Fourier coefficients carrying 95% of the energy of aa goes from 3.5% at γ=0.5\gamma = 0.5 to 20% at γ=0.1\gamma = 0.1. As a looser threshold does not yield large differences, we keep γ=1/3\gamma = 1/3, as also shown to be a sensible default in Song et al., 2022 (Figure 9).

[R7] Template is not correct. ([Q5])

Thanks for catching this. We switched to the 2027 template, which does not affect the page limit.

Dear Reviewer b9Ww,

Thank you for your review.

The authors have posted their response. Could you please let us know whether your main concerns have been addressed?

Your feedback would be appreciated.

Regards, AC

Thanks for your response—it addresses my concerns. I've raised my score to weak acceptance.

Reviewer_6PGVOpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies feature/data selection, ensemble pruning and circuit discovery as subset search. It aims to find a high utility subset with a limited number of utility evaluations. S-lfbo adapts likelihood free BO with a tree ensemble model. Instead of fitting the utility directly, it learns improvement above a threshold. The model guides which subset to evaluate next, then updates with the new result. The analysis looks at how thresholding changes Fourier sparsity and tree size. The search also uses different subset sizes and warm starts from promising subsets.

Critical strengths

(1) It is good to see that fourier sparsity and tree size are treated separately, since after thresholding, a simple utility can have many fourier coefficients and still allow a small tree. Also the ensemble result uses the combined prediction rather than clipping each tree separately; this gives a reason to model improvement directly.

(2) Keeping the loop fixed is good design choice in the restart comparison (App. E2). Seeding all 5 chains loses exact optima, while mixed starts help on wide data selection. The wide feature results do not show a clear difference between the search methods.

(3) App. C3 checks LP infeasibility because a poor MTM fit could still miss better weights. With exact utility values, infeasibility on a slice also rules out the global property.

Critical weaknesses

(1) The advantage over Gp-bo seems less clear than the main ranking suggests. On the tabular tasks, utility values are close. App. C4 breaks ties using time affected by a shared cache. Hill climbing is grouped under others despite its better ensemble rank at 100 queries. It would be good to check which ranking results still hold without breaking ties by time.

(2) Fig. 4 scales tabular time after startup from a 100 query measurement. gp refitting gets slower with more observations. It would be good to separate measured/estimated times in the equal time comparison.

(3) The structural statement for all 321 utilities seems to cover more cases than the checks shown. Table 5 covers 244 utilities. Section 3 also assumes exact evaluations despite the reported refit noise. It would be good to explain the missing coverage and whether the checks use a fixed random seed or an expected utility. A noisy violation alone would not reject a property of the expectation.

Questions for authors

please see weakness part.

3 comments

We thank the reviewer for the time and effort spent in the review of our manuscript. We appreciate the reviewer highlighting our separate treatment of Fourier sparsity and tree size, and finding that the ensemble result “gives a reason to model improvement directly”.

[R1] Advantage over GP-BO. ([W1])

The advantage over Gp-bo seems less clear than the main ranking suggests. On the tabular tasks, utility values are close. App. C4 breaks ties using time affected by a shared cache. Hill climbing is grouped under others despite its better ensemble rank at 100 queries. It would be good to check which ranking results still hold without breaking ties by time.

Thank you for highlighting these points. We have further investigated them and added the results to the paper.

  • Without the time tie-break (new Table 9). S-LFBO is first in 7 of 12 columns (8 of 12 with tie-break). For all other columns, GP-BO is first, with S-LFBO being second and not statistically distinguishable from GP-BO.

  • Utility values are close for S-LFBO and GP-BO (new Figure 16). We confirm this: at equal queries (100), the mean difference to GP-BO is at most 0.11 points. Importantly, S-LFBO achieves that quality much faster, namely 2.3x to 8.1x.

  • Shared cache is already accounted for. We have updated the wording in Appendix C.4, as Table 2 already addressed cache memorization in both enumerated and larger games.

  • Hill climbing removed from others. Thank you for catching this. Hill climbing is now listed in Table 2 and leads ensemble pruning at 100 queries, so we revised our claim: S-LFBO leads in 8 of 12 columns (previously 9 of 12).

[R2] Figure 4 scaling on x-Axis. ([W2])

Fig. 4 scales tabular time after startup from a 100 query measurement. gp refitting gets slower with more observations. It would be good to separate measured/estimated times in the equal time comparison.

We agree with this observation and have now added the exact measured time for the GP-BO baseline below 100 queries, thereby improving its runtime. The main insights from the experiment remain unchanged: S-LFBO is still 1.3x faster at feature selection and 1.5x faster at data selection. We have updated Figure 4 and the numbers reported in Section 4.2 and Appendix C.4.

[R3] Inconsistent number of utilities. ([W3])

The structural statement for all 321 utilities seems to cover more cases than the checks shown. Table 5 covers 244 utilities.

Thanks for catching this. Table 5 was missing two lines, which we have added. Our experiments and the results of Figure 2 are not affected by this.

[R4] Noisy evaluations. ([W3])

Section 3 also assumes exact evaluations despite the reported refit noise. It would be good to explain the missing coverage and whether the checks use a fixed random seed or an expected utility. A noisy violation alone would not reject a property of the expectation.

The checks use a fixed seed, and we have adjusted the wording in Section 3. We agree with the reviewer that a rejection of the property from a noisy estimate does not reject the property of the expectation. However, our goal is to investigate the properties of the practical utility (cf. Wang et al. 2024, Wang & Jia 2023, Ghorbani & Zou 2019) used for the selection task, rather than the theoretical one, which is intractable.

To further address the reviewer’s concern, we have re-run a TabPFN model across ten seeds on 18 enumerated utilities and scored the averaged (noise-reduced) utility:

MonotoneSubmod.Supermod.AdditivePairwiseMTM
Fixed seed (Table 5).89.70.30.80.97.91
Average of ten seeds.89.70.30.80.97.91
Largest change across utilities.012.014.014.003.011.003

The scores remain mostly unchanged, and the properties remain rejected.

Dear Reviewer 6PGV,

Thank you for your review.

The authors have posted their response. Could you please take a look and let us know whether their response addresses your main concerns?

Your feedback would be appreciated.

Regards, AC

Thanks for the detailed response and reminder. authors response address my concerns, and I have raised my score to accept accordingly.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response

We thank the anonymous reviewers for the time and effort they put into their reviews. We are glad they appreciated our work, and we found their feedback valuable for improving it. We have updated our paper as follows and indicate the changes in blue\color{blue}{\text{blue}}:

New experiments:

  • App. E.3 now shows ablations of the quantile thresholding, including a soft-thresholding variant. Neither change substantially affects the results, so we keep the original design. [srBX, b9Ww].
  • App. F.2 gives more insights into effect sizes and per-utility distributions. S-LFBO is on par with GP-BO but is much faster [b9Ww].
  • App. F.4 shows a new controlled benchmark using the submodular CRAIG function. S-LFBO outperforms greedy and is not negatively affected by the submodularity mass of the underlying objective, unlike greedy. [b9Ww, srBX].
  • App. F.7 shows downstream application on test-set: increasing validation set size mitigates overtuning and generalizes our insights to test data. We updated our limitations section accordingly [b9Ww].

Presentation:

  • Table 2 now lists Hill climbing separately and S-LFBO wins in 8 of 12 settings (previously 9 of 12) [6PGV, b9Ww].
  • Table 9 shows ranking without tie-breaking, and S-LFBO wins in 7 of 12 settings (8 of 12 with tie-break) [6PGV, b9Ww].
  • Figure 4 now shows re-measured GP-BO times. S-LFBO remains faster than GP-BO for the same achieved performance [6PGV].
  • We clarified that our utilities are deterministic (fixed seed), and found that properties remain rejected with multiple seeds [6PGV, srBX].
  • Added three missing rows to Table 5. Figure 2 remains unchanged [6PGV, srBX].

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.