- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper proposes an improvement to an existing algorithm configuration (AC) method known as AC-Band. This new approach, coined LoRe-AC-Band, reuses the performance of promising configurations from earlier during the optimization process. For a specific local smoothness assumption, LoRe-AC-Band comes with theoretical guarantees that show that it performs better than global sampling. In empirical tests, LoRe-AC-Band compares favorably against its predecessor AC-Band, and LoRe-AC-Band is comparable to another existing comparable in terms of performance.
Critical strengths
-
General theoretical guarantees. The performance guarantees for LoRe-AC-Band are provided under rather general, problem-agnostic assumptions. This suggests that the algorithm performs preferably if the assumptions are met. Since they are of stochastic nature, the assumptions themselves are reasonably flexible.
-
Decent evaluation. LoRe-AC-Band comes with various parameters. The appendix analyzes the robustness of the algorithm with respect to the parameter choices in reasonable detail, showing that it is generally robust with respect to such choices. It is just a pity that these considerations are deferred to the appendix.
Critical weaknesses
-
Unclear merit of LoRe-AC-Band. The new approach is theoretically compared to global sampling, which itself is neither defined in the paper nor in the appendix. This is a bit unfortunate as LoRe-AC-Band is an improvement over an existing method, namely, AC-Band. Hence, comparing theoretical guarantees of these two approaches would seem more reasonable to me. However, since this paper introduces a novel AC setting, there are no theoretical guarantees for AC-Band for this new setting. This paper should have provided such bounds in order to have a more direct comparison, but it does not do so.
Moreover, it is not clear how realistic the assumptions for the new setting are. For example, for the probabilistic Lipschitz continuity, the probability bound scales in a value that carries over linearly to the probability bound for when LoRe-AC-Band is better than global sampling. If is small, then the provable benefit is only small. It would have been nice to see a discussion about the realism of such assumptions.
-
The empirical performance of LoRe-AC-Band is not too particular. The paper shows that the performance of LoRe-AC-Band is overall decently comparable to that of the competitor COUP+. This begs the question whether LoRe-AC-Band is necessary. While it does outperform its predecessor, other approaches could be already sufficient. Data in the appendix elaborates on this comparison, but despite the more positive interpretation in the appendix, the overall performance still seems mostly interchangeable. Due to the lack of statistical tests, it is hard to say if a benefit exists.
Honorable mention. This paper is missing the AI use statement, which theoretically means that this submission is violating the ICLR submission rules. This is fine by me, but I highly advise the authors to be more careful the next time. If such a statement is present, I was unable to find it.
Questions for authors
I would like the authors to respond to my two numbered points above that I perceive as critical weaknesses. Furthermore, I have additional questions that I would like to see addressed. All my questions are listed below.
-
How realistic are the assumptions of the theoretical analysis? Why are there no guarantees for comparing LoRe-AC-Band to AC-Band?
-
What is the overall merit of LoRe-AC-Band in the general AC context?
-
The authors are missing important related work, most prominently, papers by George T. Hall, Pietro S. Oliveto, and Dirk Sudholt, for example, [1]. These theoretical considerations use specific benchmarks, which is different from the PAC-style approach in this work. Nonetheless, they qualify as theoretical guarantees for algorithm configurators. Could the authors please look more thoroughly into potential other related work and provide a statement about the implications of such papers for the current work?
-
Why did the authors choose the parameters that they used for the runs stated in the paper?
Additional comments. The following points are mere suggestions, and I do not know where else to put them. They did not impact my rating of the paper.
-
In the second line of (A3), index is no longer quantified and thus dangling here. I suppose that the authors mean (without the index).
-
Figure 2 is immensely hard to read at a normal zoom level. In particular, the legend is hard to read, but also the axis labels are of a questionable size. I highly recommend increasing the font size of these quantities. For the legend, two columns should also work.
[1] George T. Hall, Pietro S. Oliveto, Dirk Sudholt: On the impact of the cutoff time on the performance of algorithm configurators. In Proceedings of GECCO 2019, pages 907–915.
Update During the Rebuttal
Since the authors addressed all my concerns satisfactorily, I increased my rating to a weak accept.
4 comments
I thank the authors for their response. All my issues have been satisfactorily addressed.
Given that the ICLR rebuttal period allows to upload new PDF versions and that some of my remarks have been addressed by proposing changes to the paper, is it perhaps possible that the authors upload an updated version of their submission, highlighting the changes to the current version?
Revised manuscript uploaded
Thank you for your quick response. As promised, we have now incorporated the clarifications above into the manuscript. In particular, we have added:
- the clarification of the merit and comparison to AC-Band in the Introduction (l.54 following)
- a discussion about the realism of our assumptions behind each of it (e.g. l.312 following)
- a discussion about the influence of on the theory after our results (l. 419 following)
- the AI use statement in the end (l.527 following)
- a comparison to the approach of Hall, Oliveto, Sudholt 2019 and 2020 in the related work (l. 152 following)
- an explanation about our parameter choices in the empirical evaluation section (l. 442 following)
All changes are marked in blue.
I thank the authors for the quick update. The updated version looks good to me. Since all my concerns have been adequately addressed, I will increase my rating to weak accept.
Dear Reviewer PAiC
Thank you for the thorough review and the helpful pointers. We address each point below.
W1/Q2 (merit, comparison to AC-Band)
The central contribution of LoRe-AC-Band is to make local structure in configuration spaces amenable to theoretical analysis without requiring classical continuity. In AC, practically successful heuristic methods often exploit local information, whereas theoretically grounded methods need strong global structural assumptions that permit rigorous analysis. Our probabilistic continuity condition provides a way to relax these strong assumptions and formalize a local structure that still allows jumps in the performance landscape.
This motivates a fundamentally different candidate-generation strategy: instead of global random sampling, we use the incumbent to guide local exploration. Theorem 3 isolates the benefit of this change by comparing local and global candidate sampling and identifying when local sampling is more likely to find an ϵ-best configuration. Theorems 6 and 7 then establish guarantees for LoRe-AC-Band and its subroutine, with Theorem 7 providing an overall sufficient-budget-bound that is compared to AC-Band.
Beyond candidate generation, LoRe-AC-Band reuses previously evaluated instances to reduce the number of unique instances required for evaluation while maintaining unbiased estimates.
W2/Q1 (assumptions, role of γ)
Local-search and evolutionary configurators (ParamILS, GGA) only work if neighbouring configurations tend to perform similarly; they rely on this implicitly. Lipschitz continuity makes it explicit but is too strong for AC, e.g. because switching a categorical parameter can change performance abruptly. Def. 1 relaxes it: continuity must hold reliably only at small distances and may fail between distant configurations. Empirically, Pushak & Hoos (PPSN 2018) found AC landscapes of SAT, MIP and TSP solvers to be largely unimodal and often convex.
Your reading of γ is correct and the trade-off is intended: γ is the length scale on which the landscape is reliably Lipschitz; more structure gives a stronger statement, and as γ→0 Thm. 3 gives no advantage. Nothing breaks in that case: the PAC guarantee of Thm. 7 rests on (A1)–(A3), Assumption 5 and the uniformly sampled fraction x, not on γ. A wrong structural assumption costs efficiency, not the guarantee. However, the empirical success of many heuristic approaches that exploit local structure show that such assumptions seem to be realistic in many applications. We will add this discussion.
W3 (empirical performance)
We agree that the results do not establish universal superiority over COUP+ or other configurators. Rather, LoRe-AC-Band achieves competitive solution quality while improving resource efficiency in the evaluated settings. In the supplement, it uses approximately 13 unique instances across the eight scenarios; the reported algorithm-side runtime comparison with COUP+ without a prediction model favors LoRe-AC-Band. We will report statistical tests between LoRe-AC-Band and COUP+.
AI use statement
The authors used generative AI tools to assist with coding and to copyedit the manuscript. We take responsibility for the final content of this work, including text, claims or artifacts produced with the aid of generative AI. We will add this to the revised manuscript.
Q3 (related work)
Hall et al. 2019, 2020 demonstrate that rigorous theoretical analyses of local and mutation-based algorithm configurators are possible, and we do not intend to suggest otherwise. Their analyses focus on particular configurator designs and benchmark landscapes. Our work addresses a complementary question: how can locally guided configuration be supported by guarantees under a probabilistic structural assumption that allows irregularities in the performance landscape? In addition, we integrate this analysis into a stochastic, bandit-based AC framework with multi-fidelity evaluation and instance reuse. We will add this discussion.
Q4 (parameter choices)
The instance budget is chosen mainly according to the number of samples needed per LoRe-CSE round; in practice, 2--3 samples per round are usually sufficient. The remaining budget can be used to increase instance diversity, although a larger budget comes at the cost of higher runtime. The neighborhood radius depends on several factors: (a) the configuration space of the target algorithm; (b) the relative importance of individual parameters; and (c) the desired exploration-exploitation trade-off. Our experiments indicate that no single setting works for all scenarios. We use 0.1 throughout, as smaller values may yield too few qualified local samples. The capping quantile is selected based on runtime statistics, which can be obtained from random or initial runs. We use the median or an upper quantile to avoid overly greedy behavior in early rounds.
Comments You are right, we will correct it.