acceptodds
Under review as a conference paper at ICLR 2027

Provably Efficient Algorithm Configuration with Local Structure and Reuse of Observations

Abstract

We study the problem of algorithm configuration (AC) under realistic performance landscapes that exhibit local structure, but lack strong global regularity. While recent theoretically grounded AC methods provide PAC-style guarantees, they often rely on global exploration or restrictive assumptions on the reward distributions, limiting their practical efficiency. In this work, we introduce a new AC framework based on a relaxed structural assumption that captures local smoothness of the performance landscape. Under this assumption, we design an algorithm that identifies an -optimal configuration with probability of at least using predominantly local sampling. Our method efficiently reuses problem instances, narrowing the performance gap to heuristic AC methods. A key feature of our approach is the principled and consistent reuse of previously observed evaluations. In contrast to prior methods, this induces an implicit, data-dependent capping mechanism that reduces evaluation cost while preserving statistical guarantees. We provide theoretical bounds on the sample complexity of our algorithm and show that it improves over existing approaches under our structural assumptions. Empirical results further support our theory, demonstrating competitive or superior performance on benchmark configuration tasks. The code and experimental data are available at https://anonymous.4open.science/r/LoRe-AC-Band-045E.

Primary area:
optimization
Keywords:
Algorithm Configuration, Hyperparameter Optimization, Multi-Armed Bandits, AutoML

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_PAiCOpenReview ↗
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
  1. 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.

  2. 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
  1. 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 γ\gamma that carries over linearly to the probability bound for when LoRe-AC-Band is better than global sampling. If γ\gamma is small, then the provable benefit is only small. It would have been nice to see a discussion about the realism of such assumptions.

  2. 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.

  1. How realistic are the assumptions of the theoretical analysis? Why are there no guarantees for comparing LoRe-AC-Band to AC-Band?

  2. What is the overall merit of LoRe-AC-Band in the general AC context?

  3. 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?

  4. 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 ii is no longer quantified and thus dangling here. I suppose that the authors mean Θ‾\overline{\Theta} (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
AuthorsOpenReview ↗

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 ϵ\epsilon-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 γ\gamma)

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 γ\gamma is correct and the trade-off is intended: γ\gamma is the length scale on which the landscape is reliably Lipschitz; more structure gives a stronger statement, and as γ→0\gamma\to0 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 xx, not on γ\gamma. 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.

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?

AuthorsOpenReview ↗

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 γ\gamma 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.

Reviewer_F2wLOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper deals with algorithm configuration methods. The algorithm proposed by the authors is an extension of the AC-Band algorithm. The underlying idea is to use the Combinatorial Successive Elimination (CSE) method introduced in Brandt et al (2022) in the framework of Combinatorial Bandits. The authors give their version (LoRe-CSE), on which base their extension (LoRe-AC-Band). Their extension provides a provably efficient algorithm configuration method without requiring global (but only local) regularity, by reusing previous instances of the problem. The authors claim that their method is supported by theoretical guarantees as well as by practical advantages.

Critical strengths

The proposed algorithm obtain better results than other guarantee-based methods.

The reuse idea, which is one of the main points of the method, seems to be effective (Table 4).

New configurations are sampled near the current best (Theorem 3). This local sampling technique is close in spirit to heuristic techniques.

Critical weaknesses

The work is an incremental result over the AC-Band algorithm configuration method. While there is an improvement over AC-Band, the interest in guarantee-based is generally theoretical, so performance may be less relevant.

It is unclear how realistic are the assumptions, and how practical is to verify them. While the authors provide convincing support for (A1), there is no discussion about (A2), (A3). Same for Assumption 2 and Assumption 5.

Abstract/introduction mention the performance landscape, but it is unclear what is exactly (given that its local vs global regularity is one of the selling points of the paper). Is it the raw cost cc? or the limit statistics? This is unclear and plays a major role in Theorem 3.

No comparison with heuristic algorithms (SMAC, irace, ParamILS, etc), although the authors claim that their algorithm is able to ``narrowing the gap" (line 021) to such methods.

Main paper and supplementary material contain inconsistencies and should be carefully revised.

Questions for authors
  • I would expect that the value α\alpha in Assumption (A2) depends on ϵ\epsilon.
  • It is unclear where is the randomness in Definition 1. All the elements (ff, LL, xx, yy) in the event {∣f(x)−f(y)∣≤L∣x−y∣}\{|f(x)-f(y)|\leq L|x-y|\} are assigned.
  • It is unclear how Definition 1 (that deals with functions) is imposed on the search space Θ\Theta (a parameter space) in Theorem 3. Same in the proof. What is the function ff? It is definitely not the discard function.

Minor remarks:

  • l. 077: it is unclear what is the set Θˉ\bar\Theta. I recommend reformulating the sentence.
  • The statement of Theorem 7 is hard to read
  • Some lines in the pseudo-codes of algorithms 5 and 7 are struck through. Is it because they were included in AC-Band, but not in LoRe-AC-Band? In case, it would be useful to mention it at the beginning of Section A.
3 comments
AuthorsOpenReview ↗

Dear Reviewer F2wL

Thank you for the careful reading and the detailed, constructive comments. We address each point below.

W1: (incremental; relevance)

While retaining AC-Band's bandit-based successive-elimination framework, LoRe-AC-Band fundamentally changes candidate generation: instead of global random sampling, it exploits local information around the incumbent to identify promising configurations. This is a crucial difference when searching large configuration spaces, where identifying promising candidates is a major challenge with huge influence on the final performance.

Furthermore, we modify the evaluation procedure to reuse previously observed problem instances whenever possible. This preserves unbiased performance estimation while substantially reducing the number of instances required.

LoRe-AC-Band aims to narrow the gap between theoretically grounded methods and successful heuristic configurators by combining theoretical guarantees with locally guided exploration and efficient resource allocation.

W2 (assumptions)

We will add the following discussion.

(A2)/Assumption 2 is standard for infinitely many arms (de Heide et al., 2021; Brandt et al., 2023). For any ϵ\epsilon, α(ϵ)\alpha(\epsilon) is the measure of the ϵ\epsilon-optimal set; we only require α(ϵ)>0\alpha(\epsilon)>0, which excludes needle-in-a-haystack problems. Then ⌈log⁡1−αδ⌉\lceil\log_{1-\alpha}\delta\rceil uniform samples contain an ϵ\epsilon-optimal configuration with probability at least 1−δ1-\delta. Nothing has to be verified: the user chooses α\alpha and δ\delta and obtains a guarantee relative to the best α\alpha-fraction of configurations.

(A3) is taken from Brandt et al. 2023 and is needed because feedback may depend on the comparison set. It states that the more random comparison sets a configuration is ϵ\epsilon-best on, the more likely it is ϵ\epsilon-best globally. ψ(M)\psi(M) quantifies the remaining failure probability; such a ψ\psi exists whenever this probability decreases in MM.

(A5) concerns the reliability of performance estimates when observations from previous evaluations are reused. It ensures that the stored estimate of the incumbent becomes comparable to its underlying unbiased performance estimate as the number of observations increases.

W3 (performance landscape)

The landscape is the map θ↦Sθ\theta\mapsto S_\theta, i.e. the limit statistic (e.g. expected runtime over the instance distribution), not the raw cost c(i,θ)c(i,\theta) on a single instance. Def. 1 and Thm. 3 are applied to f=Sf=S.

W4 (heuristic configurators)

We agree that such comparisons would add context. but our current experiments compare against theoretically grounded configurators and COUP+; they do not establish superiority over the broader heuristic state of the art. We provide additional experimental results of irace (López-Ibáñez et al., 2016, Version 4.4.3) with a max runtime of 0.5/1 day(s). The irace experiments are run with 10 random seeds with the same EPM settings in our manuscript. In general, irace is a strong competitor to LoRe-AC-Band with comparable results in terms of the runtime of the best incumbent or runtime efficiency. See next response for details across scenarios. We believe that experiments of model-based methods (e.g., SMAC) may offer limited insight into this paper, as EPMs we used for simulations are essentially model-based.

W5 (inconsistencies)

We will cross-check the main text, appendix, notation, and algorithms and correct inconsistencies in the revision.

Q1 (α\alpha depends on ϵ\epsilon) Yes, the fraction of ϵ\epsilon-best configurations α\alpha is naturally related to ϵ\epsilon. In our bounds, we treat α\alpha as a problem-dependent lower bound on this proportion for a fixed ϵ\epsilon during a run of LoRe-AC-Band.

Q2 (randomness in Def 1)

The randomness lies in ff. The landscape is modelled as a random function, since the locations of its jumps are unknown. For fixed x,yx,y, the event ∣f(x)−f(y)∣≤Ld(x,y)|f(x)-f(y)|\le L d(x,y) is random through ff, and the probability is taken over the draw of the landscape. We will state this in the definition.

Q3 (Def 1 and Θ\Theta)

In Thm. 3, X=ΘX=\Theta with the metric of Sec. 5.1 and f=Sf=S, the ground-truth performance. We kept Def. 1 general, but agree that the link was unclear and that the symbol ff clashes with the discard function. We will rename it and state the instantiation.

Remark (Θˉ\bar{\Theta})

Θˉ\bar{\Theta} denotes an arbitrary subset of Θ\Theta to explain the notation cΘˉ(i,θ)c_{\bar{\Theta}}(i,\theta). We will reformulate the sentence to make this meaning explicit.

Remark (Thm 7)

We will introduce all quantities before the statement and add a simplified corollary.

Remark (pseudocode)

Yes, they are steps of AC-Band that LoRe-AC-Band no longer performs (partitioning or sampling fresh instances per round and epoch, replaced by instance reuse), while blue marks additions. We will say so at the start of Appendix A.

AuthorsOpenReview ↗

Comparison to irace

Runtime of the best incumbent on the test dataset for irace (max runtime) and LoRe-AC-Band (k=2k=2, δ=0.01\delta=0.01). Results reported with mean ±\pm std. Best per scenario in bold\textbf{bold}.

Scenarioirace (1/2 day)irace (1 day)LoRe-AC-Band (α=0.01\alpha=0.01)LoRe-AC-Band (α=0.05\alpha=0.05)
clasp_queens15.20 ±\pm 3.4414.92 ±\pm 2.8239.03 ±\pm 15.1549.30 ±\pm 28.42
clasp_weighted66.73 ±\pm 5.4365.43 ±\pm 8.8566.31 ±\pm 7.7173.90 ±\pm 3.54
cplex_rcw959.15 ±\pm 1043.70490.57 ±\pm 93.27165.29 ±\pm 52.90355.10 ±\pm 160.76
cplex_regions20012.14 ±\pm 9.108.67 ±\pm 7.625.00 ±\pm 0.618.96 ±\pm 4.23
lingeling_circuitfuzz73.09 ±\pm 1.5272.54 ±\pm 2.9797.60 ±\pm 9.35105.13 ±\pm 12.80
lpg_satellite3.99 ±\pm 0.463.90 ±\pm 0.615.06 ±\pm 0.286.40 ±\pm 0.98
lpg_zenotravel9.72 ±\pm 9.715.98 ±\pm 7.493.96 ±\pm 2.5913.92 ±\pm 9.24
minisat_randomk315.91 ±\pm 2.7815.65 ±\pm 2.1123.02 ±\pm 4.1422.46 ±\pm 5.84

Total runtime of irace (max runtime) and LoRe-AC-Band (k=2k=2, δ=0.01\delta=0.01) with mean ±\pm std. Units: 1×1031\times10^3 seconds.

Scenarioirace (1/2 day)irace (1 day)LoRe-AC-Band (α=0.01\alpha=0.01)LoRe-AC-Band (α=0.05\alpha=0.05)
clasp_queens39.8 ±\pm 4.182.3 ±\pm 7.2115.9 ±\pm 48.926.2 ±\pm 12.3
clasp_weighted35.3 ±\pm 1.572.0 ±\pm 2.8625.9 ±\pm 126.6133.1 ±\pm 34.3
cplex_rcw28.5 ±\pm 7.062.3 ±\pm 10.93,123.2 ±\pm 943.8670.7 ±\pm 191.9
cplex_regions20034.2 ±\pm 3.173.2 ±\pm 3.6773.9 ±\pm 120.6140.0 ±\pm 39.0
lingeling_circuitfuzz38.2 ±\pm 4.082.4 ±\pm 6.7328.9 ±\pm 66.758.1 ±\pm 17.2
lpg_satellite42.5 ±\pm 0.585.9 ±\pm 0.429.9 ±\pm 1.46.1 ±\pm 0.6
lpg_zenotravel34.6 ±\pm 2.782.4 ±\pm 5.8105.6 ±\pm 6.821.3 ±\pm 2.4
minisat_randomk334.3 ±\pm 3.461.6 ±\pm 5.450.9 ±\pm 39.817.1 ±\pm 15.1
AuthorsOpenReview ↗

Revised manuscript and appendix

Please note that we have already incorporated your valuable feedback into the revised manuscript. In particular, we have added:

  • a discussion about the realism of our assumptions behind each of it (e.g. l.106 following for (A2), l.117 for (A3), l.312 following for probabilistic Lipschitz-continuity)
  • the instantiation of the general Def. 1 with variables, like the performance landscape in our setting (l.316 following)
  • the randomness and underlying probability space in Def. 1 (l.303 following)
  • an experimental comparison of LoRe-AC-Band to irace (appendix p.17)

All changes are marked in blue.

As the experiments in the above tables demonstrate, LoRe-AC-Band achieves competitive performance compared to heuristic configurators such as irace, thereby providing empirical evidence that it narrows the performance gap between heuristic and theoretically grounded approaches. To the best of our knowledge, LoRe-AC-Band is the first theoretically grounded algorithm configuration method that provides PAC-style guarantees for the classical mean-runtime objective (unlike COUP) while also demonstrating competitive empirical performance against an established heuristic configurator such as irace.

Reviewer_QbVkOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces LORE-AC-BAND (an extension of AC-BAND), an algorithm configuration mmethod with some provable performance guarantees. One of the features of the algorithm is that it performs local sampling around a good incumbent solution rather than global sampling.

Theoretical results: Given strong assumptions on the underlying statistics profile of the algorithm on its parameter space, conditions are given under which searching for an epsilon-optimal solution within a local neighbourhood of the incumbent is faster than global sampling. Furthermore, sufficient sampling budgets are provided for finding epsilon-approximate solutions.

Due to time limitations, I have not had the opportunity to check the proofs in detail.

Empirical results: LORE-AC-BAND is compared with a range of baseslines. The experimental results do not clearly show that LORE-AC-BAND outperforms the baselines, except the predecessor algorithm AC-BAND.

Critical strengths

The paper is in overall well written and sound. It provides theoretical guarantees for an algorithm configuration method.

Critical weaknesses

The paper makes a number of strong assumptions about the performance profile of the underlying algorithm that is configured. It is unclear whether these hold in practice.

The theoretical statements are presented in vacuous way with a large number of parameters. I would recommend to state corollaries showing clear dependence on the core parameters (alpha, delta, m). Furthermore, state more clearly the difference between the statements in Theorem 6 and Theorem 7.

The analysis seems to assume that the underlying algorithm is deterministic. This assumption raraly holds in practical algorithm configuration.

Questions for authors

In the statement of Theorem 3, why does r appear on both sides of the equality? Is this a variable clash?

I would like to understand whether the theoretical guarantees give realistic runtimes for the algorithm. For the method to be practical, we should assume that m is large (large number of parameters), that alpha is small (perhaps in the order of 1/2^m), and that the number of samples required by the algorithm is polynomial in m. Is this the case?

Motivate further the assumption that the performance landscape lacks global structure. Often in optimisation, one makes the opposite assumption. The landscape has local irregularities, but a global structure.

When proposing making local changes to the incumbent solution, I would suggest to mention that this is very close to mutation in evolutionary algorithms. There may even be results from the theory of evolutionary computation that transfer directly to your setting.

The interpretation of Definition 1 is unclear if the configuration space consists of both continuous and categorical variables.

I would recommend to state the assumption of alpha as a function of m.

2 comments
AuthorsOpenReview ↗

Dear Reviewer QbVk

We sincerely thank the reviewer for the constructive feedback and the positive assessment. We address each point below.

W1 (strength of assumptions)

Our goal is to weaken what is usually assumed, thus making AC theory more applicable to practice. (A1)–(A3) are the standard assumptions of PAC-style AC and many-armed bandits (de Heide et al. 2021; Brandt et al. 2023). The only new assumption, γ\gamma-probabilistic Lipschitz continuity, relaxes Lipschitz continuity: every Lipschitz landscape satisfies it, but it also tolerates jumps between configurations with a specific probability. Local-search and evolutionary configurators (ParamILS, GGA) only work if neighbouring configurations tend to perform similarly, so they rely on such structure implicitly, and this is supported by the literature (Pushak & Hoos 2018).
Finally, the assumption is only used to show that local sampling is beneficial (Thm. 3, Cor. 4). The PAC guarantee of Thm. 7 rests on (A1)–(A3), Assumption 5 and the uniformly sampled fraction xx, so it remains valid if the structure is absent.

W2 (corollaries, Thm. 6 vs 7)

We agree and will add two corollaries. While we want to be as precise as possible, we understand that corollaries showing only the dependence on core parameters improve the readability, e.g. after Thm. 7: with n0=Θ(log⁡(1/δ)/α~)n_0=\Theta(\log(1/\delta)/\tilde\alpha) configurations, a budget B=O~(log⁡(1/δ)α~k,mLoRe-CSE)B=\tilde O\big(\tfrac{\log(1/\delta)}{\tilde\alpha k},m_{\text{LoRe-CSE}}\big) suffices; C1,C2,C3C_1,C_2,C_3 only contribute logarithmic factors.

Thm. 6 concerns the subroutine LoRe-CSE on a finite set of nn arms plus the dummy arm (one epoch). Thm. 7 lifts it to the infinite configuration space: it adds the number of configurations to sample, the budget split over EE epochs, and the step from local to global ϵ\epsilon-optimality via (A3).

W3 (deterministic algorithm)

We do not assume determinism. The cost c(i,θ)c(i,\theta) is explicitly allowed to be stochastic (Sec. 2). The non-stochastic bandit framework only requires that the statistic converges (A1), which holds for i.i.d. noisy runtimes by the law of large numbers. Assumption 5 treats the incumbent's observations as samples from a distribution. Def. 1 is imposed on the limit statistic (expected performance), not on single runs.

Q1 (rr in Thm 3)

This is not a variable clash: the optimal neighborhood radius is defined implicitly because the resulting equation has no convenient closed-form solution, as shown in the appendix. Consequently, rr is characterized implicitly and can be obtained numerically for given values of the relevant parameters. We will make this explanation more explicit.

Q2 (realistic runtimes)

The number of configurations is N≈ln⁡(1/δ)/α~N\approx\ln(1/\delta)/\tilde\alpha. It depends on mm only if α\alpha depends on mm, which is not necessarily the case. The budget is linear in NN up to logarithmic factors, so it is polynomial in mm whenever 1/α1/\alpha is. For α≈2−m\alpha\approx2^{-m} the problem is a needle in a haystack: Ω(1/α)\Omega(1/\alpha) uniform samples cannot be avoided without additional structure. However, in AC, near-optimal configurations are typically not that rare, because a few parameters dominate performance (Hutter et al., ICML 2014). In our experiments, α∈0.05,0.01\alpha\in{0.05,0.01} and δ=0.01\delta=0.01 give 94 and 463 configurations for spaces with 10 to 322 parameters, and the configurator's own overhead stays below 5 seconds on average (Table 3).

Q3 (global structure)

We do not assume that global structure is absent; we only do not require it. A landscape with global regularity also satisfies our assumption, so our results cover it. We will rephrase the abstract accordingly.

Q4 (mutation)

Local configuration changes are indeed closely related to mutation operators in evolutionary computation. Related results (Hall, Oliveto, Sudholt, 2019, 2020) provide valuable insights, but their guarantees rely on specific properties of the considered parameter landscapes and configurator settings. They therefore do not transfer directly to our general AC setting. Our contribution is complementary: we introduce a probabilistic continuity assumption and derive guarantees for locally guided configuration in a stochastic, bandit-based setting.

Q5: (mixed spaces)

Categorical parameters are represented one-hot and compared using Hamming distance; continuous and integer parameters use normalized distances. A weighted combination defines neighborhoods in mixed spaces. We will make this construction explicit in Definition 1.

Q6: (α\alpha as a function of mm).

We assume a fixed portion α\alpha in the space to be near-optimal, independent of the dimension mm of the space, but dependent on the desired performance quality ϵ\epsilon. However, α=α(m)\alpha = \alpha(m) can be substituted directly, since all bounds hold for arbitrary α\alpha.

I thank the author(s) for detailed answers to my questions, which are now mostly resolved. I have not made changes to the score.

The revision has changed Definition 1. As the authors remark in their rebuttal, f is now assumed to be random, and we have a probabilistic statement. Given this change, I am questioning whether other parts of the analysis need to take into account stochastic effects explicitly. Also, it would be good to add a discussion where the randomness in f comes from. Is it from random decisions made by the algorithm that is configured, or is it from randomness in the optimisation problem, or from some other source?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.