- 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
- 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?
- 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?
- Could replacing the current hard thresholding with a smooth approximation improve surrogate learning and optimization performance? Have the authors considered such a comparison?
- Do the authors plan to release the code and experimental configurations upon acceptance?
2 comments
The rebuttal strengthens my positive assessment of the paper. I will maintain my original rating of Weak Accept.
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])
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])
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 S. Replacing it with its expectation over ten training seeds changes none of the findings (mean over 18 enumerated TabPFN utilities):
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):
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−τ]+ with the softplus βlog(1+e(y−τ)/β) (Ament et al., 2023), with β the median of y−τ over the evaluations above τ. The table gives the gain of softplus over the hard weights in mean rank percentile (positive means softplus is better):
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.