Generalization Bounds for Model-based Algorithm Configuration
Authors: Zhiyang Chen
Hailong Yao
Xia Yin
Venue: NeurIPS 2025 poster ()
Keywords: generalization bound
data-driven algorithm design
theory of algorithm configuration
algorithmic stability
Primary area: theory
TL;DR: We present the first generalization bound for algorithm configuration that closely approximates practical model-based algorithm configurators.

Abstract: Algorithm configuration, which involves selecting algorithm parameters based on sampled problem instances, is a crucial step in applying modern algorithms such as SAT solvers. Although prior work has attempted to understand the theoretical foundations of algorithm configuration, we still lack a comprehensive understanding of why practical algorithm configurators exhibit strong generalization performances in real-world scenarios. In this paper, through the lens of machine learning theory, we provide an algorithm-dependent generalization bound for the widely used model-based algorithm configurators under mild assumptions. Our approach is based on the algorithmic stability framework for generalization bounds. To the best of our knowledge, this is the first generalization bound that applies to a model closely approximating practical model-based algorithm configurators.

Generalization Bounds for Model-based Algorithm Configuration
Zhiyang Chen' Hailong Yao Xia Yin'
'Tsinghua University University of Science and Technology Beijing
Key Laboratory of Advanced Materials and Devices for Post-Moore Chips, Ministry of Education of China
Abstract
Algorithm configuration, which involves selecting algorithm parameters based on sampled problem instances, is a crucial step in applying modern algorithms such as SAT solvers. Although prior work has attempted to understand the theoretical foun- dations of algorithm configuration, we still lack a comprehensive understanding why practical algorithm configurators exhibit strong generalization performances in real-world scenarios. In this paper, through the lens of machine learning the- ory, provide algorithm-dependent generalization bound for the widely used model-based algorithm configurators under mild assumptions. Our approach is based on the algorithmic stability framework for generalization bounds. To the best of our knowledge, this is the first generalization bound that applies to model closely approximating practical model-based algorithm configurators.
Introduction
Many algorithms used in practice contain large number of parameters that need to be tuned by users. For example, modern SAT and mixed-integer programming solvers generally have dozens of parameters that define the search strategy. A set of carefully tuned parameters may provide over 1000 performance improvement compared with default settings []. Therefore, selecting algorithm parameters, a.k.a., algorithm configuration (AC), crucial step in applying parameterized algorithms.
Tuning parameters manually is usually time-consuming and highly dependent the user's experience. Much prior work has been devoted to designing automatic AC methods. Due to the high intrinsic complexities of modern algorithms,, these methods generally treat AC black-box optimization problem. The AC problem can be formally stated as follows: Given a parameterized" |algriihmm A with parameter space θ, a of problem instances J,.... Im independently sampled from some probabilistic distribution DD and a metric function u(0, I) that measures the performance of parameter 0 θ on instance I (e.g., running time), find a parameter configuration Ø Q that optimizes 1 >"' u(O, 1,). Here, D can be regarded as an application-specine model of problem instances, e.g.. uniform distribution over mixeddintegee programs formulating facility location instances. We hope the found configuration 0 performs well on distribution D, i.e., with optimized E,~D[u I)].
One of the most popular methods is the so-called sequential model-basee optimization (SMBO), which exploits surrogate model to fit the landscape of the performance metric function, and iteratively samples configurations with promising predicted performances. See Schede al. [ for comprehensive survey.
Various AC methods have been proposed to tackle this problem 2
Corresponding author. E-mail: hailongyaodustb.. edu. en
By parameterized algorithms, mean the algorithms contain tunable parameters (a.k.a. hyper-parameters machine learning), instead of algorithms in the context of parameterized complexity theory.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Although state-of- of-the-art art model-based methods yield good performances on practical algorithmic problems, an interesting theoretical question remains unsolved:
The parameters found by algorithm configurators are only evaluated on sampled problem instances from distribution D. Why do they perform well on other unseen instances from D?
In this work, we answer this question by presenting generalization bounds for mosed algorithm configurators through the lens of statistical learning theory. A generalization bound provides a guar- antee that upper bounds the gap between training and testing performances of the learned parameter, iee. [E ( r)] 1 E== u(0, I:)l. From the practical view, tight generalization bound for AC important since it implies the number of data samples such that the learned configuration does not overfit training data and exhibits strong generalization abilities.
1.1 Limitations of previous work
Several studies have been devoted to generalization guarantees of AC. Previous work can be generally categorized into two classes: Problem-dependent and problem-independent guarantees.
Problem-dependent dependent guarantees, a.k.a., data-driven algorithm design [6), provide generalization bounds for specific families of parameterized algorithms. This line of research exploits the structures of the problem instances and the parameterized algorithms, instead of studying the algorithm configu- rators. Gupta and Roughgarden [7] initially propose the framework of data-driven algorithm design, and present generalization bounds for tuning greedy heuristics, tuning local search, and learning the step size for gradient descent, etc. Subsequent work provides generalization bounds for learning the branch strategy for branch-and-bound [8] [9, learning cutting plane parameters for branch-and- cut [10), tuning cooling parameters for simulated annealing [1], tuning dynamic programming for string alignment [12], tuning multi-objective optimization
[33 and VLSI design [14 [5] etc.
Although these studies are highly non-trivial, they suffer from two limitations:
These generalization guarantees problem-dependent. We need to analyze parameterized algorithms in practice one by one. It is hard to establish a general result for AC following this line of research.
These results are generally limited to single family of parameters, which are incompatible with practice. For example, the work of Balcan et al. [ and Balcan et al. [0] studies generalization bounds of branch policies and cut policies for integer program (IP) solvers, respectively. However, there is no known method to combine these two results to obtain guarantee for the joint space of branch and cut parameters. In contrast, modern solver has dozens of parameters (c.g.. 135 parameters for CPLEX). It seems intractable to prove a problem-dependent generalization bound for the entire parameter space of IP solvers.
Problem-independent guarantees provide generalization bounds that are independent of the parame- terized algorithm. Thus, this kind of guarantee treats the algorithm to be configured black-box and provides results that are more general. To the hest of our knowledge, the only prohlem-independent generalization bound is due to Liu et al. [16]. However, their result only applies to discrete parameters (which is technically easy to obtain by union bounds), while in practice, an algorithm may contain continuous parameters. Although their result can be extended to the continuous case by assuming that the performance metric is Lipschitz on the parameters, the Lipschitzness assumption is too strong to be compatible with practice: As discussed in previous work [8 9. the landscape of the performance metric in AC is usually piecewise structured, with many non smooth discontinuities.
To summarize, it remains an open question whether can provide generalization guarantees for general AC problems (with multiple and continuous parameters). Note that all previously discussed work derives generalization bounds using uniform convergence. Uniform convergence bounds imply that the generalization upper bound holds for any learned parameter in the parameter space. Thus, they are independent from the algorithm configurator. Due to the black-box nature of AC, it is impossible to derive a general problem-indepenndnt uniform convergence bound. To overcome this barrier, we instead consider algorithmmddependen wtw.:/eaddnnneeggeaaaaaiaaaioooi generalization bounds, which utilize the properties of the algorithm configurator:
'The Aggorith--depeneer term is borrowed from statistical learning theory. In generalization bounds of neural networks, an algorithu dependent bound depends on the learning algorithm (e.g.. gradient descent). In

---

Table 1: A comparison with previous generalization bounds for AC
Reference
AC Problem
#Parameters
Parameter Space
Configurator
Proof Technique
Gupta and Roughgarden ?
Greedy & Local search
Contimoous
Any
Uniform convergence
Gupta Roughearden
Gradient deseent Branch policy for MIP
Continuous
Any
Uniform convergence
Balcun al. 9
Several
Continuous
Unitorm convergence
Balean et al. 10
Cutting plane MIP Simulatedd annealing
Several
Contimaous
Any
Uniform convergence
Blum al.
Multiple Several
Continuous
Uniform convergence
Balcan et [2]
String aligument
Continoous
Any
Uniform convergence
Balcan
Clustering beuristics Regularized regression
Continoous
Any
Uniform convergence
Balcan al. T++ [8]
Continoous
Any
Uniform convergence
Balcan and Sharma
Decision tree heuristics
$ 3
Continuous
Any
Uniform convergence
Chen al.
Multi obj. opiimication
Contimuous
Unilorm convergence
Liu et al.
16
Prohlem-indes indeee-nnddeeeedent
Multiple
Discrete only
Any
Uniform convergence
Ours (Theorem
Problem-indeeendent
Multiple
Continuons
Model-based
Algorichmic stability
1.2 Our contributions
Main results. In this work, we present the first generalization bound for the general AC problem using model-bases algorithm configurators. Model-based AC is popular framework in practice, which applies a Bayesian optimization framework to configure the parameterized algorithm. In Bayesian optimization, random forests are often used as surrogate mode With a few assumptions on the algorithm configurator (these assumptions are generally realistic, as we will show in experiments), we prove a generalization bound for the learned parameter in Theorem []
To the best of our knowledge, this is the first generalization bound for general AC with continuous and multiple parameters, and the first generalization bound that applies to a model closely approximating practical model- based algorithm configurators. See Table I for a comparison with previous work. An informal version of our bound as follows.
Theorem (Informally, Theorem 5)
The generalization error of model-based algorithm configura- tors with random forest surrogate models is upper bounded by
(17
d Q
T
m
in expectation, where T is the iteration number of the configurator, is the number of sampled instances, Q is the number of decision trees in the random forest surrogate model, n. is the number of parameters, and d is the number of instance features.
Note that our bound converges with a rate of m 1122 with respect to the number of training samples, but with an additive term of ((n + 2)/4) This term is related to the stability of the random forest model. Intuitively, the model becomes more stable as we increase the number of decision trees in the forest. In fact, this term comes from the Rademacher complexity of the dual decision tree class. We will numerically show that this term is very small for a mild number of trees Q in experiments. To compute this data-dependent empirical Rademacher complexity term, propose divide-and-conquer algorithm in Appendix
Our techniques. Different from previous uniform convergence results for AC, our generalization bound is aggorthmm-dependen which exploits the properties of the algorithm configurator. Our technical approach relies on the algorithmic stability framework [20). We show that the model-based algorithm configurator with random forest surrogate models stable, i.c., small change in the training data to the configurator does not change the learned configuration much. Note that the algorithm configurator
randomized algorithm. Thus, we bound the difference between the distributions of the output configuration two training datasets with only one different instance. To achieve this, two building blocks are required to bound the stability of random forest model
our work. by algorithm adgoridhin-dependent we mean the bound depends on the algorithm configurator, instead of the parameterized algorithm be contigured.
"Although Gaussian processes are popular in Bayesian optimization, model based algorithm contigurators usually use random forests since (1) random forests are faster compared with Gaussian processes; (2) random forests integrate the features of problem instances achieve accurate predictions. See, e.g.. Hutter et al. [2]

---

Black-box optimization
Algorichm configurator (Training)
Parameterized algorithm (e.g., SAT solver)
Parumeter configuration e
Application (Inference)
Parumeter configuration 2
Generulization error
Parameter space &
Performance metric 1(0,1,5)
Problem instance I
Problem instance
Problem instance I
Real-world instances
Problem instance
(A probabilistic distribution)
.**..*
sampling
Parameterized algorithm
Problem instance Im
sumpling
Problem instance Im
Performance metric
Problem instances
Training data
Evaluation data
Figure 1: The framework of algorithm configuration and generalization guarantees.
and the local search sampling method in the configurator, respectively, which may be of independent interest.
The stability of random forests has been studied in previous work, such Soloff et al. [21 and Wang et al. [22]. However, in our analysis, we need (1) a uniform upper bound on the stability, while previous work focuses on the stability of single point; (2) stability bound for both the empirical mean and the variance estimations, while previous work only considers the mean. Therefore, we derive upper bounds Rademacher complexity of the mean and the variance of the dual decision tree class to achieve these targets. For the local search sampling method, we assume the configurator applies a aatlaateddannnalin--syyyy rule, and study its convergence using the theory of Monte-Cate Markov Chains (MCMC). Different from classic mixing-time bounds for MCMC that consider additive errors (23], we consider the convergence using the multiplicative error.
1.3
Organization
The rest of this paper is organized as follows: Section 2 introduces the problem formulation and technical preliminaries. Section|introduues introouuess the framework of model-based algorithm configurators and presents our generalization bound. Section 4 concludes the paper and discusses future work. Proofs are omitted to the appendix. Appendix A presents some technical lemmas. Appendix B gives the proof of our main theorem. Appendix CrpeenixxCproviiii provides the data-dependent bound and numerical experiments.
2 Preliminaries
2.1 Problem formulation
Notations. Throughout this paper, use [n]] to denote the set (1,...,m). For asymptotic symbols, we use ((f(n) f(n) poly logn hide logarithmic factors and f(n) g(n) denote f(n) A 0(1) g(n).
Formulation of algorithm configuration. Figure T iillustrates overview of AC and generalization bounds. Let be an algorithm with parameters # (c.g., a SAT solver). In this paper, we consider algorithms with bounded continuous parameters. Without loss of generality, we assume 0 E [0, 1)"
Let u0, 00 T, denote the performance metric (e.g., running time) algorithm A using parameters on instance I. Notice that algorithm A may be stochastie. Thus, u(0, (, may be random variable.

---

We use to denote the random seed to characterize the randommess of A. Given a pair (6. I). the algorithm configurator can only access u(8, -.-) by randomly sampling a seed E and observing m(0, e). Without loss of generality, we assume u(::.:)) E [O, 11, since we can always normalize the performance metric (e.g., represents the running time, we can set a time limit 1, and divide the running time by t).
Let be probabilistic distribution of problem instances. Given independently sampled instances /,...., Im D. algorithm configurator finds 0 minimize the loss function ((0) = EL.D.--E[E(( [) Since the configurator only observes the sampled instances I1.... ,......,mm..... Im- it instead minimizes the empirical loss function E(6) ness of the evaluation on instance I,.
m Ei= u(0, Ei). where & is the random-
We are interested in providing generalization guarantees for ((0) of the learned 0. A generalization guarantee is in the form of
((()) -(()) S Earr:
where Cer is called the generalization error or generalization gap of the learned configuration.
2.2 Algorithmic stability
Algorithmic stability is algorithn-dependent approach generalization bounds. If learning algorithm (i.e., the algorithm configurator in our setting) produces similar models (i.e., algorithm parameters) under slight perturbations to training data (i.e., sampled instances), then, the learned model has strong generalization guarantees. The following result can be found in most learning theory textbooks, e.g., Shalev-Shwartz and Ben-David (20).
Definition 2 (Stability). Let Ø1, ... Im, I'm X be + samples from some distribution D. Let S == {x1..... Fm } and S' = {01.... Im-1; xmm be two datasets with only one different sample. inputs, and outputs a parameter L(S) θ
Suppose L is learning algorithm that takes dataset Let u0, x) denote the loss function on data x E X using parameter E O. We say L e-stable,
[Erlu(((S) =>] E, (((((")) x)]l s E, E
where the expectation E is taken over the randomness of learning algorithm L (since the learned parameter L(S) may be stochastic).
Theorem 3. Let be an s-stable learning algorithm. Suppose S {a1...., Imn ~ Dmm are m independent samples from some distribution D. and u(0,z) be the loss function. Then, the expected generalization error is upper bounded by
1 Σ
EL B DoLpD[u((SSS (u(L(S),
c(L((S),
Se.
Therefore, to prove generalization guarantees for AC, suffices to show that the algorithm configurator is stable.
Remark 4. Theorem 3 provides generalization bound that holds in expectation. Feldman and Von- drák (24) show that such results can also be turned into high-probability bounds: For e-stable learning algorithms, the generalization error log(m) log(m/6) + Vlog(L/0)/m with probability at least 1 5. Thus, in the following, we only consider generalization bounds in expectation.
3 Generalization Guarantees
In this section, we formally present our generalization guarantee. We first introduce the model-based AC framework studied in our setting. Then, we present the main generalization bound and discuss the implications of our result.
3.1 Model-based algorithm configuration
The framework of model-based algorithm configuration is illustrated in Algorithm D The configurator uses the outcomes of sampled runs of algorithm A to train surrogate model that predicts the
5

---

Algorithm The algorithmic framework of model-based algorithm configurator
Input: The sampled instances I1,...y . Im ~ D.
Output: A parameter configuration 0 E [0, 1 for algorithm A.
Sample intt initial parameters 0, for E [iiit]
2: Evaluate parameters Opgma on m instances to obtain dzy that estimates 15 [u( E).
3: for t I..... init Titer do
4: Build dataset D = {((0,, Qj), أay) hee(t- [jj(m=) where $3 is the feature vector of problem
instance Ij.
5: Use D train surrogate model that predicts the performance metric function Eg [u( I, E)].
6: Use local search heuristic to find 0g that maximizes the acquisition function.
7: Evaluate parameter Og to obtain Mej for j E [m]] and update the incumbent parameter.
8: end for
9: return OT
OTme+ + Time
performance metric function Eg [u(0, I, [)] for any parameter 0 and instance I. Based on this model, the configurator searches for promising parameter, and evaluates this parameter to obtain new data. The surrogate model and the parameters are iteratively updated incorporate new training data.
In the following, we introduce the algorithmic details of the configurator in our analysis. We emphasize that our setting is generally consistent with algorithm configurators in practice [2], but with some slight modifications to make the generalization error analysis possible. In experiments, we will show that our modifications negligibly affect the performance of the configurator.
Sampling initial parameters. The configurator initially samples Tinit parameters to "warm- start" the surrogate model. Our analysis works for arbitrary sampling methods: It could be uniform distribution over the entire parameter space [0, 1]",, or any other distributions based on prior knowledge (e.g., applying large language models enhance the initial samplings (25)), long the distribution is fixed conditioning on the instances Jı...., Tm.
Building datasets. In the t-th iteration, the configurator has collected the outcomes of A on parameters OI.... Oz-1. Suppose for each instance In and parameter 0,, algorithm A is evaluated and the outcomes are u(0,, Eiz). The configurator may use úsj w(O,, Ij. to estimate Be[u [)]
Moreover, configurators in practice may also predict the algorithmic performance based on the features of problem instances. We use o; denote the feature vector of instance 4, Let d denote the number of features (i.c., d; E Id... The configurator trains surrogate model to predict Ee [u(0, E)] based on training data {(0,, ,)), ( [e((-1).dE[m)-
Surrogate models. In Bayesian optimization, many machine learning models are utilized as surrogate models, such as Gaussian processes and random forests. Algorithm configurators in practice usually use the random forest as the surrogate model, due to its low training time complexity. Random forests can be built in almost linear time, while standard Gaussian processes require O(N3) time to fit N data points.
In analysis. we assume the configurator adopts random forests the surrogate model. The random forest is a classic learning model, which applies the bagging heuristic to decision trees. A random forest consists of Q independently built decision trees. Each tree is trained with randomly sampled subset of the entire dataset. The most common bagging strategy is sub-bagging, which uniformly samples Mbag out of m instances without replacement and learns the decision tree with data related to these instances in D. In practice, the number of samples for each decision tree is not very large prevent overfitting. We assume Mabg constant as we increase the total number of instances m.
Note that in model-based AC, the surrogate model is required to predict both the expectation and the variance. The random forest predicts the expectation by averaging the outputs, and predicts the variance by computing the empirical variance of all trees. Suppose Q is even and Tree; is the output of the i-th tree. We predict the empirical variance by
Q/2
RF
Treee:--- - Tr
Q
i=1

---

We assume the predicted empirical variance is lower bounded by small constant miin since in practice, RFy cannot arbitrarily small due to the randomness of random forests. The variance ensures that the configurator will explore new parameters instead of purely exploiting.
Acquisition functions. After training surrogate model for the metric function, the algorithm configurator finds promising parameter by maximizing an acquisition function. In our analysis, we consider the widely used expected improvement (EI) function: Suppose the surrogate model predicts the mean and the variances of u(0, I, to be f and o², and the empirical estimation of the incumbent parameter (with currently the best mean) is ú'. The expected improvement of is defined as
EI( ((.--N(1,,2)) [max (u' û, 0}}
Sampling promising parameters with local search. In each iteration, the configurator finds parameter configuration with maximized El acquisition. Model-based algorithm configurators, such as SMAC 21 apply local search heuristic to solve this optimization problem. Concretely, suppose the incumbent parameter 0. The configurator iteratively samples 6' A > 0, and updates 0 +- 0' if 6' has better EI.
N(0, A In) for some
However, due its greedy nature, it is hard analyze the convergence properties of this local search algorithm. In our analysis, we instead assume applying an MCMC-based algorithm. Concretely, starting from a uniformly sampled initial parameter 0, the algorithm iteratively samples 0' (0,
In). The difference is that accept 0 0' with probability min
1, exp
This adaptation reasonable since it is equivalent applying the Metropolis- Hasttnng algorithm to sample 9 with probability proportional to exp(El(0)/T). We can also regard it as simulated- annealing version of local search with fixed temperature т. This assumption allows convergence rate analysis of the sampling algorithm, and negligibly affects the empirical performance we will show in experiments.
Selecting the best configuration. The algorithm configurator performs Ther iterations in total. In modern algorithm configurators, the configurator maintains an incumbent parameter in each iteration using so-called intensification method. Intensification adaptively allocates algorithm runs to different parameters to boost the accuracy of parameter evaluations. This makes our analysis hard since different configurations may be evaluated with different numbers of runs. In this paper, initial samplings, we select parameter 0 E {fI...., , } with minimized - Miy as the initial incumbent. In subsequent iterations, we update the incumbent if the latest parameter 6, has a better empirical metric value.
we simplify the configurator for ease of analysis.
Let Trotal Tinit + Titer be the total number of sampled configurations. A modification to the algorithm configurator in our analysis is that we let the configurator output &rewn instead of the incumbent parameter. We make this modification ensure that the trajectory of the configurator (i.e., the sequence 0,, .2....) is fixed, the output parameter is also fixed. This negligibly affects the performance long as the configurator finally converges promising region of the parameter space.
3.2 The main theorem
Now, we are ready present our main generalization bound.
Theorem 5. Let v(0, I,E) be the performance metric function instance I with parameter 0 and algorithmic randomness E. Let S = (I,,.... Im,) ~ DDm be m independent problem instances sampled
from from some distribution DD, and Ei....,Em, denote the independent random seeds of m. calls. Let 0 denote the parameter configuration learned by the model-basede algorithm configurator. The expected generalization error of is upper bounded by
1 Σ
E
E
(0,,1)))
(0. E.Ei))
S /Titer (EStab + EMH),
5,0
I~DRE~
m
where
Mbag m
(n + d) (Qg(Q
T Tiotal 1bgg)
EStab
+
T Fmin
Q
7

---

and
TMH
1
1
MH exp
exp
+
(2TA)
24
7
Remark 6. We make some comments on this bound:
The notations A, min: T, Magg can be regarded as constants, We focus on the asymptotic behavior with respect to the sample number m, the surrogate model size Q, the number of iterations Titer and TMH, and the dimension n and of the AC problem considered.
The generalization bound grows linearly with respect to the root of the total iteration number Viter. The generalization gap larger the training time grows longer. This is similar to stability bounds of (stochastic) gradient descent in the classic machine learning literature (26).
The Ô ((nn+d///) term in Estab comes from the Rademacher complexity of the dual decision tree class. We can numerically compute the empirical Rademacher complexity (see Appendix C to obtain a tighter data-dependent bound.
The EMH term comes from the convergence of the local search process for sampling promis- ing parameters in Algorithm| [ We study its convergence by treating as a Metropolis- Hastings sampling algorithm, and derive a geometric convergence rate. This term can be almost neglected numerically by selecting large enough TMH (e.g., SMAC [2] performs TMH 10000 steps) since it converges zero exponentially.
We sketch the proof of Theorem The complete proof is in Appendix B due the page limit. Required technical lemmas are listed in Appendix A
Proof sketch of Theorem Our analysis is based the algorithmic stability framework of general- ization bounds as introduced in Section Thus, throughout our analysis, we define $ = [J,,..., mm) and S .L....., Am-11 I'mm as two sets of problem instances, with only one different instance. Let 0, and 0g denote the sampled parameters for datasets S and S'. Recall that ü.j = u(0,, Eiy) the empirical estimation of I,
for parameter O, and instance I5. We also have i(0.) = Σm= ü(O;, J Eiy) be the empirical estimation of the performance metric. Similarly, we define ú', i' for dataset 5". To analyze the stability, we fix the randomness of evaluations such that S.j Ely for any j. Thus, ü.j = ikly for any j * m.
Our proof consists of four steps: Firstly, the configurator samples Linit parameters before the main loop. In this step, the distribution of initial parameters is fixed. Secondly, we analyze the stability of the random forest surrogate model. We present uniform stability bound for both the mean and the variance estimation of the random forest. Thirdly, we turn the stability bound of the surrogate model into the stability of the acquisition function, and study the convergence of the local search sampling process that maximizes the acquisition function. Finally, we put the building blocks together to obtain an algorithmic stability bound for the complete algorithm configuration method by bounding the KI. divergence between two search paths on S and S'. This leads to a generalization bound via Theorem
Step 1: Sampling initial parameters. In Lines 1-2 of Algorithm I Tinit initial configurations are randomly sampled to form the initial dataset. Since the initial samplings are only based on prior knowledge, the distributions of (O,,..., OT... and (0',... T are the same. Moreover, since S differs 5" by only one instance, it is easy to show that the difference between the empirical estimations (i.e., i(0mm) - i' (6inc)) of the incumbent parameter for S and S' is at most 1/m.
Step 2: Uniform stability of surrogate models. In this step, aim to show that the prediction of the surrogate model is cnntuurbaion-rrsillicn when one instance modified the dataset, conditioned on the randomness of the algorithm and the model.
Suppose the configurator is working the I-th iteration (Timit < L S Timit + Tite). The configuration trains the random forest model using D {((0,, Φ5), Kny) Je(())JE( for S, and similarly D' for S'.
8

---

Let (f, 6) denote the prediction of the i-th decision tree in the random forest for S. The random forest model predicts the mean and the variance by RF x) 2 E Tree, (0, and RF Φ) Q E (Treez:-1 (0, Φ) Tree2; x))². We similarly define Tree', RF' for 5'.
We consider the stability of the random forest prediction, i.e., Gapg () RF (0. Φ) - g (0. Φ) and (f +) (f, RF (0.gg Φ). It is easy show that for fixed pair of (0, の), we have El|Gap= (0, [) - /abag// mm and E| Gapy( +}]] S. 2mbbag m, where the expectation is taken over the randomness of the bagging process in random forests.
However, this bound only holds for a single parameter. To derive a stability bound for the complete configurator, we require uniform bounds, i.c., upper bounds for supe.6 Gap Φ) and supo.a (0 Φ). For Gapz(".), +), we can directly apply the Rademacher complexity tool to achieve this. Note that the supremum is taken over the input of the random forest. Thus, different from results in classic learning theory, we bound the Rademacher complexity of the dual decision tree class. For Gapy(t,)) (t, we apply a similar bound to Massart's ' lemma to obtain an upper bound in Appendix A..3
Step 3: An analysis of the Metropolis- Hastinggs sampling. In model-based algorithm configurators. local search heuristic is applied to sample promising parameters with high acquisition function value.
apply a Metropolis- Hastings-style method to sample 0g in Line 7 of Algorithm [ This method samples a parameter such that the target distribution has a density proportional exp(EI(0)/T). To analyze the stability of Metropolis-Hasting, two building blocks are required. We first analyze the stability of the target distribution, i.e., the difference between El(0) for S and S". Then, we analyze the convergence rate of the sampling method.
As discussed in Section 3.1
Let μı and o² denote the mean and the variance predictions of the surrogate model for S. Let iine denote the incumbent performance for S. We similarly define μ', o' and l'ne for S'. By showing that EI( o) is 2nr -Lppschitzz w.r.t. a, we have El(H, o) (y',,, o')l | I |line - lnnel + |p - n'l + - o /2(T)) In Step we have already obtained stability bounds on ||- μ² and la a'). Moreover, we directly have line - !ine S 1/m. Thus, we have a stability bound on the expected improvement acquisition function.
Next, by applying a convergence bound Appendix A.4 we have convergence rate of the Metropolis- Hastings method. Note that, unlike the classic mixing time analysis in Markov chains, our analysis requires a convergence bound on the ratio of the sampling distribution and the target distribution. Combining the above two bounds yields an upper bound on the ratio of the probability densities of 0g for S and S
Step 4: Putting things together. Finally, we consider the complete algorithm configurator. Let 0 and 0' denote the output of the configurator on S and S", respectively. Let θ = (0)): and O' = (0)), denote the search paths of the configurator. Let p(-) denote the probability density. We show that
[1()] - -10')] 0,0
/ 1(x) 1(00= = x)) -p(0' m7) dr
< 22TV(0,
p(0 x) p = x
S V2KL(0)110)
log
by Pinsker's incquality. To upper-bound the KL divergence, it suffices to bound the density ratio between two paths. Fixing a path x = (xz)c. we have
e = L) e x)
Tenal
p(O= = Ez 101001-11 = =[ 11) p(0' xz 0/-1) 2[(-1)
II
T
Plugging in the bounds in Steps 2 and 3 yields the desired bound for the stability of the algorithm configurator.
D

---

4 Conclusion and Future Research
In this paper, we present an algorithm-depende generalization bound for model- algorithm configurators, based the algorithmic stability framework. To the best of our knowledge, this is the first generalization bound that applies to a model closely approximating practical model-based algorithm configurators.
We briefly discuss some directions for future research. A limitation our work is that the generaliza- tion bound is still loose compared with practice. In practice, small number of instances is sufficient to learn a good parameter configuration. Sometimes, even single instance works for algorithm configuration 22. It would be interesting to establish connections between algorithm configuration and few-shot learning. To tighten the generalization bound, we may need to find novel characteriza- tions of the performance metric landscape to derive more sophisticated data-dependent bounds. It is also interesting to extend our results to other advanced surrogate models, e.g., tree-structured Parzen estimators [27]-
Another significant line of research involves providing theoretical guarantees for the empirical risk minimization problem of algorithm configuration, i.e., explaining why model-based algorithm configurators can find nearly optimal parameters in real-world scenarios. Due the black-box nature of algorithm configuration, this question is extremely difficult, and may require stronger assumptions and sophisticated beyond-worst-case worst-case analysis to answer it.
Acknowledgements
We thank anonymous NeurIPS reviewers for the helpful comments on this paper. This work is supported by the Key Program of National Natural Science Foundation of China (No. 62034005).
References
[1] Frank Hutter, Marius Lindauer, Adrian Balint, Sam Bayless, Holger Hoos, and Kevin Leyton- Brown. The configurable SAT solver challenge (CSSC), arXiv preprint arXiv 1505.01221, 2015.
[2] Frank Hutter, Holger H. Hoos, and Kevin Sreyton-Brown. Sequential model-based optimization for general algorithm configuration. In Proceedings of the International Conference Learning and Intelligent Optimization, page 507-523, 2005.
[3] Belarmino Alenso-Díaz and Manuel Laguna. Fine-tuning of algorithms using fractional experimental designs and local search. Operations Research, 54(1):99-114 2006.
[4] Frank Hutter, Holger H. Hoos, and Thomas Stützle. Automatic algorithm configuration based on local search. In Proceedings of the National Conference Artificial Intelligence (AAAI), page 1152-1157, 2007.
[5] Elias Schede, Jasmin Brandt, Alexander Tornede, Marcel Wever, Viktor Bengs, Eyke Huller- meier, and Kevin Tiemey. A survey of methods for automated algorithm configuration. Journal of Artificial Intelligence Research, 75:425-487, 2022.
[6] Maria-Florina Balcan. Data-driven algorithm design. arXiv preprint arXiv 201 1007177 2020.
[7] Rishi Gupta and Tim Roughgarden. A PAC approach to application-specifcc algorithm selection. SIAM Journal on Computing, 46(3):992-1017, 2017.
[8] Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning to branch. In Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 344-353. PMLR, 2018
[9] Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. Refined bounds for algorithm configuration: The knife-edge of dual class approximability. In Proceedings of the 37th International Conference on Machine Learning. volume 119, pages 580-590, 2020.
[10] Maria-Florina Balcan, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik. Structural analysis of branch-and-cu and the learnability of Gomory mixed integer cuts. Advances in Neural Information Processing Systems, volume 35, pages 33890-33903, 2022.
10

---

[11] Avrim Blum, Chen Dan, and Saeed Seddighin. Learning complexity of simulated annealing. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130, pages 1540-1548, 2021.
[12] Maria-Florina Balcan, Dan DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik. How much data is sufficient learn high perffrrrfnnnng algorithms? Generalization guarantees for data-driven algorithm design. In Proceedings of the 53rd Anmual ACM SIGACT Symposium Theory of Computing, page 919-932, 2021.
[13] Zhiyang Chen, Hailong Yao, and Xia Yin. Learning configurations for data-driven multi- objective optimization. In Proceedings of the 42nd International Conference on Machine Learning, volume 267, pages 9642-9663. PMLR, 2025.
[14] Zhiyang Chen, Hailong Yao, and Xia Yin. Learning a provably good wirelength model for analytical placement. In International Symposium of Electronics Design Automation (ISEDA), pages 358-363, 2023.
[15] Zhiyang Chen, Tsung- Yi Ho, Ulf Schlichtmann, Datao Chen, Mingyu Liu, Hailong Yao, and Xia Yin. NeuroEscape: Ordered escape routing via Monte-Carlo tree search and neural network. In IEEE/ACM International Conference Computer Aided Design (ICCAD), pages 01-09,
2023.
[16] Shengeai Liu, Ke Tang, Yunwen Lei, and Xin Yao. On performance estimation in automatic algorithm configuration. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, pages 3384-2391, AAAI Press, 2020.
[17] Maria-Flone Maria-Florina Balcan, Mikhail Khodak, Dravyansh Sharma, and Ameet Talwalkar. Provably tuning the ElasticNet across instances. In Proceedings of the 36th International Conference on Neural Information Processing Systems, 2022.
[18] Maria-Florina Balcan, Anh Tuan Nguyen, and Dravyansh Sharma. New bounds for hyperparam- eter tuning of regression problems across instances. In Proceedings of the 37th International Conference on Neural Information Processing Systems, 2023.
[19]
Maria-Florina Balcan and Dravyansh Sharma. Learning accurate and interpretable decision trees. In The 40th Conference on Uncertainty in Artificial Intelligence, 2024.
[20] Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
[21] Jake A. Soloff, Rina Foygel Barber, and Rebecca Willett. Bagging provides assumption- stability. Journal of Machine Learning Research, 25(131):1-35, 2024.
[22] Yan Wang. Huaiqing Wu, and Dan Nettleton. Stability of random forests and coverage of random-forest prediction intervals. In Advances in Neural Information Processing Systems, volume 36, pages 31558-31569, 2023.
[23] Austin Brown and Galin L. Jones. Convergence rates of Metropolis -astponss- algorithms. WIRES Computational Statistics, 1605):770002, 2024.
[24] Vitaly Feldman and Jan Vondrák. High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. In Proceedings of Conference on Learning Theory, pages 1270-1279, 2019.
[25] Tennison Liu, Nicolás Astorga, Nabeel Seedat, and Mihaela van der Schaar. Large language models enhance Bayesian optimization. In The Twelfth International Conference on Learning Representations, 2024.
[26] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar, Foundations of Machine Learning. The MIT Press, 2nd edition, 2018.
(27] James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for hyper- parameter optimization. In Proceedings of the 25th International Conference on Neural Infor- mation Processing Systems, page 2546-2554, 2011.
[28] Eric Brochu, Vlad M. Cora, and Nando de Freitas. A tutorial on Bayesian optimization of expensive cost functions, with application to active user modeling and hierarchical reinforcement learning. Xiviv preprint arXiv 1012.2599, 2010.
[29] Tai-Hsuan Wu, Azadeh Davoodi, and Jeffrey T. Linderoth. GRIP: Global routing via integer programming. IEFE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 30(1):22-84 2011.
11

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We claim all the contributions of this work in the abstract and the introduction section.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of this work in Section 4
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
12

---

Justification: All theoretical assumptions are provided in Section 3.1 All proofs are provided in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
The experimental details are presented in Appendix C
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
13

---

Answer:
[No]
Justification:
We will release the codes upon the acceptance of the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ccpppp.ccppulli//guiii wwwtc//ggui////eeeeceoocc CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The experimental details are presented in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Error bars are given in Table
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
14

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We discuss the experimental environment in Appendix
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We conform with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work generally focuses on the theoretical foundations of algorithm
configuration. There no societal impact that we feel obliged to discuss here.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
15

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: There is no data or model that have risk for misuse in this work.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We state all assets well as their authors in this paper.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
16

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We release no new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
17

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: This work is not relevant LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy for what should or should not be described.
18

---

A Technical Lemmas
In this section, we review and prove some technical lemmas that useful in the proof of the main theorem. Results in Appendices A. and A.2 can be found in most learning theory textbooks, c.g., Mohri al. 26
A.1
Information theory
Definition (Total variation distance and Kullback-Leibler divergence). Suppose P and Q are two distributions over the same domain. Let p(-) and g(-) denote their probability density functions, respectively. The total variation distance between P and Q is defined as
1
TV(P, Q)
p(x)) g(x))dr.
The KL divergence of P over Q is defined as
p(æ) ((x)
KL(PIIQ)
E zmp
log
Theorem 8 (Pinsker inequality). Suppose P and Q are two distributions over the same domain, We have TV(P,Q) S (AKL(PIIQ)
A.2
Rademacher complexity
Definition 9 (Rademacher complexity). Let H. denote set of functions from domain X to
10. The empirical Rademacher complexity of H for a finite set S {I1,..., Im C X is
Rs(H)
IE a-d 1,1)
sup NEW 77
a.h((sa))
where each o; is independently and uniformly sampled from 1-1,1]. The Rademacher complexity
of H is RD (H) ES (H)) where each S is independently sampled from some
distribution D.
Theorem 10 (Uniform convergence). Given i..dd samples S = fx1..... Fm from distribution D. for a function class H. from to [0, 1), we have
)]
E SmDD
sup
1 Σ MZ.)) 77
aND DDD ((x)))
< 2RD(H).
KER
Thus, Rademacher complexity can be applied obtain uniform convergence concentration for empirical means. To obtain an upper bound of Rademacher complexity, the following Massart's lemma is popular.
Lemma 11 (Massart). Let A C R be finite sel, and . Fm be the Rademacher variables. We have
||0|||2 22 AA
E
sup m aEA
S max zEA
-~1-1.11m
m
1=1
Corollary 12. For a function class H frommm % to [0, 1}, and S (I1,..., Fm X. we have
2 log IA
Rs(H)
where = ((h())())........ M(m)) h E H} is the set of all possible values of h E H on S.
A.3 Rademacher complexity for empirical variances
The classic Rademacher complexity is proposed to study the expectation of an empirical process. In this work, we also need to analyze the empirical variance estimation. To address this problem, we make small modification the definition of Rademacher complexity.
19

---

Definition 13 (Rademacher complexity). Let H denote set of functions from some domain X² to [0. and m be an even number. The empirical Rademacher complexity of H. for finite set S = [11, , Fm S X is
m2/2 Σ 2=1
Rs (H) =
E
sup hEH m
o, (1h 12.)
a~1-1,1mm//
where each o; independently and uniformly sampled from {-1,1}. The Rademacher complexity of RD(H) = ES-DD [R(H)] where each z; is independently sampled from distribution D.
Similar to Theorem T0l we also have a uniform convergence theorem. The proof is similar to Theorem 10 which applies the classic symmetrization technique. We provide the proof for the sake of completeness.
Theorem 14. Given m i.idd samples S = fII,..., [mm] from a distribution D, for a symmetric function class H from x² to [0, 11, we have
m/2
]
E
sup NEW
Σ m =1
1
h(02--1,
ax axat _ (12,22222)
< 2R (HL)
S~D"
Proof. For simplicity of notations, we define
m/2 Es [M]
m (x22-1,
and use Ex, [h] to denote Ez, (h(x,, r')] for brevity. Let S' fIi...., and be an independent
copy of S and {-1, mm/2 be the Rademacher variables. We have
Es
sup bEH
Es(h) B [1)]
Es
sup NEW
[Bs(h) D'. Bs(h))
Egg,
sup
(R.((h) B.s (1))
m/2
Eg,s
sup
(h(22)11, 121) -1 xbee
778
1 m/2
Eg,s
sup h
(h(22
a
((222--12222))
m
2RD(H),
where the second line is due to Jensen's inequality, and the fourth line is due to the fact that S' is identically distributed to S.
We upper bound the modified Rademacher complexity by the following theorem. The proof is simply by applying Massart's 's lemma. The only difference is the constant, since we only have m//2 Rademacher variables here.
Theorem 15. For a symmetric function class H. from x² to |o, 1]. S (a Imd S X with m being even, we have
4 log IA
(s) S
m
where = (1((212)))) h H) is the set of all possible values of h E H. on S.
20

---

A.4 Metropolis-Haase sampling
Metropolis- Hastings algorithm generates a Markov chain (ze)s20 such that 2t converges
given distribution II. The algorithm chooses a proposal distribution Q(.), and an initial distribution
Qo- Starting with 2g Qo. we independently generate 1/+1 [e Q(x+) and random variable
6 ~ Unif[0, 1] that is uniformly sampled over [0. 1j. The Markov chain is defined by
#/41: if S T T(x)) ((2))
It+1
Øt, otherwise,
where x--) is the probability density of the target distribution IT, and q(-) is the density of the proposal distribution Q. Note that the proposal distribution is usually symmetric (i.e., q(alb) = ((bla), as is the case of Gaussian proposals in this work). Thus, the acceptance probability can be reduced to the ratio the target density.
In this work, we are interested in the convergence rate of the SestropoiisHHastinn algorithm, i.e., how fast the Markov chain 2, converges II. Previous work [23] has been devoted studying the mixing time of Metropolis- Hastings,,, i.e., the number of iterations such that the total variation distance between 2; and II is small enough. However, in the proof of our main theorem, KL divergence bound is required. Instead, we need uniform convergence bound on the probability density ratio of the sample and the target distribution.
Definition 16 (Minorization (23)) We say the proposal distribution satisfies the global minorization condition, if g( (Te) 2 am (Iz) for some a E (0, 1).
Theorem 17. Suppose the proposal probability density q(-) symmetric and satisfies the global minorization condition. Let q:).) denote the probability density of ae and qu(-) is the density of the initial distribution. for any x,
(0( π(x)
1- I
$ 1 $1+0 ao
then, for any x, we also have
qt
1 0r (1 (1-a) a)²
< 1 00
a)).
It is easy to note that min(T(x), o ((²)){())))))))))))))) = = c0z,, x')))")) Throughout this proof, we use f to denote the integral over the support of the distribution 11. By definition, we have
Proof. Let x0((,x)) min {1. )|))
90-12x)= = (ʃ (ole) 2)dx / (0(2))) o(z,2'))da)
= = (an()))old
qi (2)))((( /((o))//eatdddd
If T( 2 T(2), we have
/ (((())((z' xt)
a(ad) / (r(xx) - (1(2²) x(x)
(((or) a(a' (()))
/
(((x)) gc(x²)
p6 x') (=())) ())..
((x) ((x')
If T(x(²) < (()), we have
/ (()()))pox' a (n(x')(lx x²)) ala (x))
(x(x)) ((x") -
u(a')) g(a'l
<(x)
/
(e(x)) 9c(x²)
T(x) ((x²)
21

---

Combining the above two cases, we have
9(+1(x') 2e(x²)+ / (2((z)) 2c(x')
<(x²) a(a11a) min(f(()) (( )dz.
Let Ex)x) [((2) T(x) L. We have
Fe(x') g(<(|a) min(f((), (x'))
E2+1(x') = Ex(x') +
dr
((x2)
=E((z') 1 ((()))) + 2')
Since (p+, :) S we have 1 - (0xx, x2)g(()))))))))))))))))))))))))) 2 0. Therefore, we have
Ee41 (2') S sup Er (z0) 1 pla, (l (((()()))()( (a(r))(a,, d' da
sup E, (zo) - / sup E, (20) Ex(x)) min { ((()))). (
x(x") f dx ((x)
)
I sup Eú (zo) a / (uup Er (x00) - Ei(()) T(z)dx
20
= (1 - a) sup Eg (xa)) + /
(9((() ( -1 x ((r)dr
Tσz)
= (1 a) sup F (zn).
ab
Since this bound holds for any s', we have
sup 1 s (1 a) sup Ex(o)), 20
zo
which yields the desired bound by induction.
B Proof of Theorem 5
In this section, we prove the main theorem. We first introduce the necessary notations for our proof. Then, prove some building blocks in Sections B.2 to B.4 Finally, we put things together to obtain the desired bound.
B.1 Step Notation preparations
Our analysis is based on the algorithmic stability framework of generalization bounds. Thus, through- out our analysis, we define instances, with only one different instance. We study the difference between the behaviors of the algorithm configurator on and S".
(J,,..., I and S = (J,..... mm rn are two sets of
problem
8 Let f1.... PYm. and .1...., denote the sampled parameters using datasets S and S'. Let úij u(0;, Eiy) denote the empirical estimation of Be[u(0,, for S and i(0,) Eド i(0,, II Eiz) be the empirical metric function of S. Similarly, we define Vyy. Elg. and I' for
fix the randomness of evaluations such that &ú = Eg for any i,j. Thus, if j + m, we have u. = ily. This helps us analyze the stability the configurator under stochasticity.
B.2 Step Sampling initial parameters
Initially, the algorithm configurator randomly samples Tini parameters and selects the best one as the incumbent. Since the initial samplings are only based on prior knowledge, we directly have the following claim.
22

---

Claim 18. The parameters (f1..... Oi....,,rm.i mm)) and (0',.... ........... ) an identical distribution.
Moreover, since S differs S' by only one instance, the empirical estimations of incumbents are close each other, conditioned on the evaluation randomness. Let Oine and fine denote the best parameter among
and Lemma 19. If = for any i [Tinis]. we have [((inc) (((((nn)) S m
Hmmm) respectively. We have the following lemma.
Proof. Since üys = Bly for any E [ E [m 1], we have [((0.) - [(0)))
1 úim - im/m S
1 for any i E [Tinit]- Thus, we have
i(Oinc) & (0inc) + < max ((,))((0,) + = ((( +
772
m
Similarly, we also have (f(m))) S 2(0me) + 1 m bound.
Combining these two inequalities yields the desired
B.3 Step 2: Uniform stability of surrogate models
Now, we consider the stability of the surrogate model. We aim to show that the prediction of the surrogate model is perturbation-resilient when one instance is modified in the dataset, conditioned on the randomness of the algorithm and the model.
Suppose the configurator is working on the t-th iteration for some t E [Tin + 1iit + Therl- We study the learned surrogate model using datasets {((0,, o,), d.z)) and D' {((0%, df),, (ly) (ell
Since we fix the randomness of the algorithm configurator, we assume the sampled parameters (01, ....... 0,) (61 ..... 0.). Since and S' differs by only one instance, have Φ, = 6/. ü., d/ for any i it] and j [m 1]. Suppose the random forest surrogate model consists of Q decision trees. We use Tree; (0, Φ) to denote the output of the i-th decision tree on parameter and instance feature & using training data D. We
RFx(0,
Σ Q
1
Tree; (0, Φ)
and
Q/2
(0,
Σ
1
(Treezi (0, (0,
Q 1=1
to denote the empirical expectation and the variance prediction, respectively, Similarly, we define Tree RF's and RF, for D'.
Let Gap (9, Φ) = (F Φ) - RF Φ) and Gapy(0, (b) = RFv -F
RF (0, d). We can bound
the stability of the prediction follows.
Lemma 20. For any parameter 0 and instance feature 6, we have
M&bag
2mbag
El]Gap (0,+))
m
m
where the expectation taken over randomness of the bagging.
Proof. Note that [Gapz 6)) S Ee Tree, Φ) (6, Q)). Since and S' differs by only instance Im and Tn,. have T0, G[] o) < 2 mbag/ = -mag//nnn mm.
(0, () # Tree' Φ) with probability mba/ Thus,
Similarly, [Gapy(0, +)) S -0 |02/2((TTeeee) [(Treez- (0, Tree (0, (Tree'x-1(0,)) (B, d. With probability 1 (1 mbag/ /m) < 2mbbg/ m,, have that Tr,e, 0) * (O,e o) (0, o) o Tree' (0, Φ) holds. Thus, Gl]Gap Ø) - 2mbbag m
23

---

However, this bound only holds for a single parameter in expectation. The subsequent analysis requires a uniform bound that holds for any We can use the classic tool of Rademacher complexity to achieve this.
Let Gap
(6) (0, = Tr, +) (0, We regard Gap (::))
(4)
i.i.d. samples of
E[Gape( }] Note that Gap (8) a function that maps a pair of f and ø to the stability gap on fixed
decision tree i. We define the dual function of Gap as DualGapg (0.6), T Treer(0, Φ) - Φ).
where T is bagging sequence of the random forest that induces decision tree. For the i-th decision tree in the random forest,
DualGape (9.d) (i) to denote Gap (4) (0,
Let GE {DualGap (9.4) T T0e .) Tree (0, Φ) (0, Φ)} (T is an arbitrary valid decision tree model, including Trees,... ..... Treeq) be the set of dual functions of Gap that maps decision trees to prediction values. The empirical Rademacher complexity of GE is
Q
R(GR)= 1011
sup (0,00
DuDulGapp (0,0) (i))
sup (8,0)
Gap (7) (0)
(11
i=1
Lemma 21. have
R(Ge) I 22 (n + d)(1 + log(2Q t mmbgg))))
Q
where is the current iteration of the configurator.
Proof. Massart's 's lemma shows that for a function class H. for a finite set {#1...., Im we have [A| where ((h(1))) ... ()(m)) h H). To apply Massart's lemma, need to bound the number of possible values of GGap (1) ( ( for all (0, Φ). Note that each decision tree Tree, is built upon t mibg data points. Each decision tree has at most mbbg leaves. Each leaf of decision tree is a hyper-rectangle in (n + dd-dimension space, where is the number of parameters and d is the number of features (i.e., (0, Φ) Rm+dd. Altogether, there are at most 2Q L. --bbaag hyper-rectangles. Since the VC-dimension of d-dimensional hyper-rectangles 2d, these hyper-rectangles divide the TRa+ space into most (2eQtmaag) 22++2d regions by Sauer's lemma. Plugging this bound into Massart's lemma yields the desired result.
R(H) 2logg m
Corollary 22. We have
sup E
Gap=
(0, Φ)1
mbag m
(n d) log t mbag)
8.0
Q
Proof. Note that by symmetry,
E
sup (0, Φ)
S
sup (O, d) 8.0
+E
sup( G0
0,0
9.0
2E
sup Gapz Φ))
0,6
suffices to consider E (sup9,6 G0 })] The result holds by applying Lemma and Theo-
rem 10
L
( Next, we consider the upper bound of Gapy. Similarly, we define Gap (8, 6) = (Tree - (0, 6)
Treez; d²)²
(Tree'y-1(0,44 Tree (0, 6))2 and the dual function DualGap, (0.0)
(i)
Gapy (4) (),
Let Gy S (8.0)
(1) (i) + Gapy (0, o)} be the dual class. By Definition 13 the empirical
Rademacher complexity of Gy
Q/2
R(Gr) =
E
sup (0.6)
o, Gap (0,
Q
a~ (1.-1
24

---

Lemma 23. We have
(n+ d) log (Q t. mbag
R(Gv)= S
The proof of this lemma identical to that Lemma since the number possible values of (Gapy (6) (8, ()) has the same upper bound as the number of (Gapg (0, ø)), The only difference
is that apply Theorem 15 instead of Massart's lemma. By Theorem 14 we have the following corollary.
Corollary 24. We have
E sup x)1
Gapy
maag x
(n d) log(Q t mbag)
0.0
m
Q
B.4 Step 3: An analysis of the Setrroooli--Hasting sampling
In this step, we analyze the stability of the local search sampling. In our framework, we apply the Seropoolis-Hastinge sampling method to sample a configuration where the distribution is relevant to the expected improvement acquisition function.
Let Iine and f denote the incumbent parameter for and S' for some iteration t, respectively. With a little abuse of notation, we use line [(Ome) and ii = ('(iine) to denote their empirical losses. Let p. and μ', a²2 denote the mean and the variance for S and S' on parameter 0. The expected improvement for (u, is thus El((,o) (Eu-)(H mmax(/ie u, 03 and we similarly define El'(p' o') for (u',o'²) Lemma 25. have
[EI(, - ( & 1inc Pinc + 110 - 1'l + 2TT 10 - 0'1.
Proof. Note that max 0H S |1-11,, and max 1oxxxll-10 u1 0) 10a0-aaa---o0 00| s Iu w/). Thus, suffices to consider the case such that linc Yn and n²,
Recall that 28 the expected improvement be computed by
(Z= lice H
(z
El(H,,) = (linc - μ) 2(Z) + -
where (.)) and se()) are the c.d.f. and the p.d.f. of Gaussian distribution A/0 1). Note that for (/ 1), we have (p()) s 2. Now, fix and in.. The derivative of El w.r.t. is
dEl (iic 4) d$
dip
x(Z)
do
do
do
Note that
dZ
iice p1 de
dZ d$
dz do
-Z (z))
((Z)
do
σ2 do
do do
Thus,
dEI
-Z + + t + -2
Za (z)
do
1
|x(2)
2
which indicates that El is -Lipschitz with respect to Therefore, have [El(u, El( <
0 a-aal
25

---

Now, we are ready to prove stability bound for El. The mean is estimated by
m
(F p²
m Σ
RF (0,
Since and 5' differs by only one instance, we have
E
sup
1'1
+
Gapa o,)
1=1
Mbag
R(GE)
m
Mbagg
(n c)) log(Q L 1/bag
m
Q
In practice, the variance is usually estimated by sum of the mean of the variance and the variance of the mean, i.e.,
(Fv + m(m
Σ
(RFB(0, 0.) - RFg(0,
1gicjsm
and similarly for o²2. We have
E
sup 2a2
02
(0,
m
m
Σ
(Gapz(0. + GO o,))
m(m - 1)
1gicjsm-1
Tllbag
+ R(Gv) + R(GE)
m
Mibag
(n + d) log(Q t mbag)
+
Moreover, by identical argument to Lemma 19 have Dine i/cll S 1. Applying Lemma 25 yields
1
EI(,,)) El' ,')l < 1iicc -Yncl 111
2T 1 a'l 1r'l
0² o²²
1iicc Mncl
+
110 n/|
+
4x
m
After obtaining a stability bound for El, we analyze the convergence the local search heuristic. The local search method can be regarded Metropolis-Hoe Hastings sampling process approximate distribution II where the density (.)) x ((EEE(((())))))))))))) and the proposal distribution Q with density (-)10) is the Gaussian distribution (e0,, A I.). Let 9.(+) denote the density of the sampling variable after iterations.
Lemma 26. Let TMH denote the number of iterations the sampling. We have
1 (exp(1/r) -1) (1- (1- (2TA)"
Tim
@Tiu (x) T TT))
1
exp
2A
for any 10.
Proof. Note that the expected improvement satisfies 0 < EI(..) < 1. Thus, EI(;,)/T E [0. 1/7]. This indicates that the target density x(.) E (x(_111)))x((///))) The initial sample is uniformly sampled over the parameter space, which means go (-) 1.
26

---

The proposal distribution is 2= -N(0, A In). The density is
(())
exp
|
01
v(2Ta)a
2A
11
exp
V (2T
2A
exp
n
T(x).
(2TA)"
2A
Therefore, we can apply Theorem 17 to obtain the desired convergence rate.
B.5 Step Putting things together
Finally, we apply the algorithmic stability framework to prove the main theorem.
Proof Theorem Recall that 1(0) TEI.D (u( T) denote the loss of parameter and
θ = (01. Toul and O' = (8%,..... H' denote the iteration paths of the algorithm configurator
Ticeal
on dataset S and S'. For simplicity, we use 0 = 6 reai and O'
6' to denote the final configuration. Treeal
Note that 8 and 0' are stochastic depending on the randomness of the configurator. We use p(O x)
and p(0' 2) to denote the probability densities of é and 0'.
Note that the randomness of the configurator consists of two parts: The bagging randomness of the random forest model, and the randomized sampling of the parameters 0,. Let RF denote the randomness of the bagging (i.e., we assume we determine the bagging instances of each iteration before running the configurator). To apply the algorithmic stability framework, we need to bound
E 0
[1())
(100)-1(0))
1(00]]
=
E RF
E 0.0
|1(0) - ((0)
RF
Now, we fix RF and consider Egge [1(0 - 1(0')
RF
For brevity, we use dr(s) to denote
dz dzid0z- dr in the integral. Fixing RF, we have
E [1(] - -(00 = / (xx) 1p10 pp(0=2) x) -x)-p(0 -p(0' xx) dx
0.0
/ p(0 x)) p(00'= =0){ dr
p(O = xz)dz Teai
p(O'= = =))d
dr
Jajyietal 1)
F|Freel 11
Ip(0 = x) p(0' = =x)) doTpimal
2TV(e, 0') /2KL(e)Ie).
The first inequality is due to ((0) 1]. the second inequality is due to If, f(z)dz| S S2 (f()))zz, and the last inequality is due to Pinsker's 's inequality (Theorem Therefore, it suffices to upper- upper-bound the KL divergence between two iteration paths. By definition,
p(O x)
O = EE log
p(O' = xz)
We aim to bound the ratio between the densities of ② and O'. In the following, for simplicity of notations, we use p(z), (æ) to denote p(O ( z), and use p(z,), (xx)) to denote
27

---

p(0 = =.). = z;). Note that
Piotsl
p(x)
pla1,... Tia
T=
p((x)
pl (011 Ti
Puaa
Tiut1 pl (x' 01.....;(-11
I1== +1 plzz 11, ((111)
I1 Tmatt +1 p/ (Ie I1,, ; xt-1)
Tina
II
Tt-1)
( F4-1)
1=
where the second equality due Claim 18 Now, fix iteration number t, bound the ratio between p(z, Ft-1) and
It-1).
Since condition on the same F1, ...-... Tt- the previously sampled parameters for S and S' are
the same. Let ga (x4) denote the sampled parameter for 2 using Sectropoiis-Hasting Thus, 9lmm (z²) = p(2a) #1...... 21-1). Let I (2;) denote the target distribution of Metropolli-Hastinng,. We similarly define VT and T' for S" By definition,
plza| I1-1)
@Tam (1xx)
π (xx))
9Tum (2x)
p' ( Te-1)
&no (x1)
xxx1)
Dram (2z))
We bound each term respectively. We have
(xx)
exp(Elu((z)) (())))))) ((
ex((E((((())) (
T' T'(x))
J, exp(El(tt))
(l(((())) El' (I J [x)p (2 sup EI(u(z), (r((' T
exp
I exp
Note that (xx) and T'
('xx) (x)) are actually random variables depending on the bagging randomness of the random forest. Now, consider the randomness of RF. We have
T(x;)
ERF
log T' T'xx))
<
ERF
sup
EI(u(z). - El
ERF
sup
[linc - l'ne + |10 pll
4TO 102 - o(8)
iibag +
(n + d) log ((tmaag)
T
m
Q
Moreover, by Lemma 26 we have
Tum
Timm (xt)
(1) - - -1)
1
log
< log
1+ exp
exp
π (Ix)
((2AA)"
2A
1 = -1)
1
< exp
1
exp
((2TA)"
2A
V2
1
exp
TMHH
exp
π
1
(2TA)
2A
28

---

where the second inequality is due to log + 2) S and the last one is due to (1 11-z)//a = 1/e for small enough x > O. We also have
log (2s)) 9TmI (20))
- -1)
1
72
< log
1
1 2
exp
exp
V (2TA)"
22
Tim
1 + -1) (1
1
exp
exp
A2
2A
-1)
TMH
24 exp
exp
exp
((2AA)"
2A
for sufficiently large THH since - S 1 2x for (0,0.5)
Therefore,
Tixaa
p(
KL(OI(0') Ey
log
p' p' x1 ...., 12-1)
Lt=Tna+1
Tioaa
log T(x+) x'{))
Tha (2t)
log T x'(22)
sup
+ log
t (are) 9ram (2:))
T=in++
Plugging this bound into B(((() - 1(0011 - V (2K yields
[1()] - [(00)] S Tiee (EStab + EMH),
E 0,0
where
1
mbag
(n + d) log(QT QTQoooe (agg
EStab
min
and
-1
1 exp
TMH (2
71
EMH
exp
exp
7
2A
Applying
Theorem
3 yields the desired result.
Algorithm 2 An algorithm to compute the empirical Rademacher complexity.
Input: The random forest predictor Tree TreeQ.
Output: The empirical Rademacher complexity GRF and G
1: Let ÔRF, 5% +-
2: for == 1,....,.. MM do
3: Randomly sample the Rademacher variables o1...., 000
~ (-1,1
4: Let MAX,, MAXy O.
5: for (0, Φ) in each piece of (Tee;;(, 1)s (by calling Algorithm 3 do
6: Let MAX;, +- max (MAXR, D 1= T0,e, (0,()) Φ)).
7:
Let MAXy +- max (MXXy, 1= o, (Tree Φ) (0,)))))
Q/2
8: end for
9: Let GRF + ŚRF + MAXE, and GHV + GRF + MAXy.
end for
11: Let GRF &- ÔRF/M and GVV + /M.
12:
return ŚRF and G%
29

---

C Numerical Experiments
C.1 Data-dependent empirical Rademacher complexity
In our generalization bound, the Ö(v(n d)/Q) term usually dominates the generalization error, since it converges slower as the number of decision trees Q grows, compared with the number of samples m. As shown in Appendix [B.3] this term comes from the Rademacher complexities RGgg and RGy). fact, we can derive tighter data-dependent bounds by computing the empirical Rademacher complexity.
Notice that
R(GE)
E a 11111
sup
o Gape (1) (0,
0,0
1=1
sup
(0,
Tree (0, 6))
1,11-
0,0
1=1
1
sup 0,0
ai Tree, (0,, x)
+
E (~1-1111
sup
ag Tree (0, ())
1~1-11119
Q
Note that the training samples for Tree and Tree' are identical (though not independent). Thus, suffices to compute the Rademacher complexity of the decision tree class
RRF
E,
sup 0.0
ag Tree; (0,
given the problem instances for the algorithm configurator. Similarly, for R(GV), it suffices to compute the empirical Rademacher complexity
Q/2
1
RM = E, sup 0.0 Q
oi (Treex-1(0,00) Treee; (0, o))²
t=1
Since the decision tree predictor is piecewise-constant function, it is easy to compute the values of ŚRF and &% We can randomly sample the values of Rademacher variables and compute the supremum by enumerating all pieces (Algorithm 2 By Hoeffdiig inequality, Algorithm returns ŚRF and Ff with an additive error of at most O (lo/oo//////// with probability at least - 8. The key problem is to compute the piecewise-constant structure of (:, for the random forest model in Line 5 of Algorithm 2
To enumerate the piecewise structure of the random forest model, propose divide-and-come algorithm (Algorithm 3) Suppose the total number pieces of (", ")s is P. It is easy to note that Algorithm 3 finds all pieces in O(P (n + d)) time.
C.2 Experimental results
In this section, we present numerical results for our generalization bound using the empirical Rademacher complexity by Algorithm 2 Experiments are conducted on 2.0GHz Intel CPU with cores.
AC settings. We perform experiments on the algorithm configuration of the SCIP integer program ming (IP) solver. SCIP is classic open-source IP solver with many tunable parameters For simplicity, we select four continuous parameters that most significantly influence the performance of the solver. These parameters directly control the key components of the solver, including branching. conflict analysis, cut generation, and presolving. All these four parameters lie in |0. 1]. See Table for concrete descriptions. We tune these parameters with other ones being the default values to minimize the total running time. In the surrogate model, besides the algorithm parameter, we use two
'See https::/www..cippppe
php for complete list of parameters.
30

---

Algorithm 3 A divide-and-conquer algorithm to enumerate the pieces of (Tree:(:; -))-
Input: The random forest predictor Tree Treeq.
Output: Each piece (0, o) of (Trees(:.))4 Node (Node;).)
I: function
2: if Node; a leaf for all 1,.... Q then
3: return (Space).
4: end
5:
Find i such that Node; that is a leaf node.
6:
Let Left and Right be the left and right children of Node,, respectively.
7:
Let Space, and Space, be the parameter and feature space of Left and Right, respectively.
8:
Let Pieces t- 0.
9:
if Space n Space; * then Let LeftNodes = (Node1..... Node: Left, Node Nodel.) Let Pieces Pieces U DDVIDDD---NN---ONUUUXCCEETTTT Space,, LeftNodes). end if
10:
12:
if Space n Space, + then
14:
Let RightNodes (Node)...., Node; Right, Node; I...... Nodea). Let Pieces +- Pieces UNVIDD--ND--OOOUUUXSSPe Space RightNodes).
15:
16: end if
17: return Pieces.
18: end function
19: Let Space + [0, 1]m=td denote the complete parameter and feature space.
20: Let Node (Root Rooto) where Root, is the root node of the i-th decision tree.
21: return DIVID--AID-COONQUURRSPEC Node).
Table 2: Selected parameters of SCIP in our experiments.
Name
Implication
branching/scorefac
The branching score factor to weigh downward and upward gain prediction in the score function.
confaacc//awwarcfac
maximal fraction of variahles involved conflict constraint. The maximal relative distance compared to the best node's dual bound for applying separation. Abort presolving. most this fraction of the problem was changod in last round.
separatiigg/axzounddiaa
preeolving/abor seoriigggbborrttre
values, the number of integer variables and the number of continuous variables in the IP formulation, as the instance features.
We implement the model- based algorithm configurator in Algorithm T We set the of the configurator as follows: Tini = 20, Titer = 10, maag = 10, Q = 1000, Jmin = 0.1, 7 = 0.1, TMи 105, and A = 0.03. We set the maximum time limit of the IP solver to be 60 seconds. and normalize the running time by the time limit so that the performance metric lies in [0, 1]. If the solver exceeds the limit, the performance is 1.0. With Q = 1000, the data-dependent Rademacher complexity computed by Algorithm 2 is about 10-3 which is rather small and in the same order as mbag/ m.
We tune these parameters two applications of integer programming: VLSI routing and facility location.
VLSI routing (29 is the problem of interconnecting multiple sets of points P. (called nets) grid graph. For each net P., select a rectilinear Steiner tree topology to connect all points and minimize the total length of all trees. Each Steiner tree should not intersect with topologies of other nets. We randomly synthesize instances of VLSI routing on a 20 x 20 grid graph with 5 to 10 nets. Each net randomly consists of 2 to 5 points. The length of each grid edge is set to be 1.
Facility location is classic operations research problem that selects the best locations for set of facilities. There are customers and m facilities that have not been built. Customer i can obtain some fraction Yiy the good from facility j with a cost diy Building facility j has cost fj- We aim to select subset of facilities to minimize the total cost. We randomly synthesize instances of facility location with n E [400, 500) eustomers and m E [200, 300] facilities. The cost uniformly sampled from [0, 10
31

---

Table Verification of the assumptions in Section intervals, which characterize the performances on different instances in the test set.
The performance results give 1-sigma error
Configurator
VLSI routing
Facility location
Ours
0.3657 + 0.1041
0.1295 + 0.0970 0.1244 + 0.0954
SMAC
0.3629 + 0.1125
Facility location
VLSI routing
Performance metric u
Test loss Generalization bound
Performance metric
Test loss Generalization bound
15
15
12
10
102
10
10a
10
10
102
10
10a
10a
Sample number m
Sample number m
Figure 2: Our generalization bounds for facility location (left) and VLSI routing (right).
Generalization bounds. We plot the generalization bounds in Figure 2 as well as the empirical test loss on the dataset. The data-dependent Rademacher complexity bound is computed using Algorithm?? 2 We can notice that the generalization error converges to zero and our bound is non- vacuous as the sample number is larger than about 10
Verification of our assumptions. We make some assumptions on the model-based algorithm configurator we considered in Section Now, we empirically show that these assumptions are reasonable. They do not noticeably affect the performance of the configurator. We compare our configurator with the classic SMAC (2) configurator. The results are illustrated in Table It can be seen that effect our modifications to the configurator is very small. This verifies the rationality of our assumptions.
32


Reviews:
[{"review_id": "5a1qiPQvW4", "reviewer": "Reviewer_2hU7", "summary": "Sequential model-based optimization (SMBO) techniques employ a surrogate model (e.g., a random forest) to fit observed performance data and then iteratively propose promising parameter vectors; these methods have demonstrably excelled in practice. However, no theoretical generalization guarantees exist to explain why configurations optimized on finite training instances maintain effectiveness on unseen instances from the same distribution. This paper establishes the first generalization guarantees for model-based algorithm configuration (AC) with continuous parameters. Addressing a critical gap in theory-practice alignment, it analyzes widely used configurators that employ random forest surrogates and Bayesian optimization.\n\nThe core contributions of this paper are as follows:\n1) This paper proposes the first problem-independent generalization bound for AC with multiple continuous parameters, overcoming limitations of prior discrete or algorithm-specific analyses. It leverages algorithmic stability to link random forest surrogate properties to generalization error.\n2) By directly analyzing industry-standard configurators with minimal performance-preserving adaptations, this work derives a non-vacuous bound where dominant terms become negligible under practical settings.\n3) This paper demonstrates the tightness of key theoretical terms through data-dependent bounds.", "questions": "See above.", "limitations": "Yes.", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1) The paper is the first to deliver a model-based, algorithm-dependent generalization bound that explicitly matches how SMBO systems such as SMAC operate—i.e., random-forest surrogates plus local search for EI maximisation. Previous bounds were either problem-specific or relied on uniform convergence. Here the authors close that gap and provide a guarantee that aligns with the configurators practitioners actually deploy. \n2) The bound aligns with real-world algorithm configurators and provides a robust theoretical foundation for algorithm tuning in practice.\n3) This paper demonstrates the negligibility of dominant theoretical terms (e.g., Rademacher complexity) via data-dependent bounds and verifies minimal performance impact from analytical adaptations.\n\nWeaknesses:\nThe model-based approach may struggle with large parameter spaces or high-dimensional problems, leading to increased computational complexity.", "was_revised": true, "final_justification": "After considering the response of the authors (W2 and Q1 are well explained) and the discussions from other reviewers again, I decide to raise my score. \nThe paper presents a novel and well-motivated theoretical contribution by establishing the first algorithm-dependent generalization bounds for model-based algorithm configuration with continuous parameters. The response clarifies that the analysis focuses on generalization rather than optimization complexity. It also explains that the assumptions are mild and reflect common practice. \nOverall, the paper makes a clear theoretical contribution and addresses key concerns effectively. Based on these strengths, I recommend accepting the paper.", "rebuttal": "Thanks for your review! We are delighted that you acknowledge the strengths of our work, including the **alignment with real-world configurators** and the **rigorous theoretical guarantee**.\n\nWe address your concerns as follows:\n\n> The model-based approach may struggle with large parameter spaces or high-dimensional problems, leading to increased computational complexity.\n\nOn the one hand, the drawback of high complexities on high-dimensional problems is due to the weakness of model-based algorithm configurators, instead of the our generalization bound analysis. In fact, high-dimensional AC is inherently difficult due to the black-box nature of the problem. As far as we know, there is no efficient approach to solving high-dimensional black-box optimization problems with, say, more than 1000 variables.\n\nOn the other hand, the focus of our work is the generalization bound, instead of the optimization complexity. Our generalization bound is $O(n^{1/4})$ with respect to the problem dimension $n$, which is a rather mild growth. The optimization intractability of high-dimensional AC seems to go beyond the scope of this paper.\n\n> To make the stability analysis tractable, the paper fixes several implementation details: every random-forest surrogate must use sub-bagging with a constant bag size, the local search is reformulated as a fixed-temperature Metropolis-Hastings sampler, and so forth.\n\nWe thank for your kind comment. This is indeed a drawback of our work. However, we want to emphasize the following points.\n\nOn the one hand, we kindly clarify that **our assumptions on implementation details are not strong**.\n\n(a) Constant bag size: In practice, algorithm configurators generally use $<100$ instances for the bagging size, e.g., in SMAC [2]. Since decision trees may overfit with too many datapoints and users often apply pruning to limit the tree size, enlarging the bagging size may not necessarily increase the performance of the configurator. We believe the constant assumption is indeed reasonable.\n\n(b) Fixed-temperature Metropolis-Hastings sampler: The vanilla local search in practice is equivalent to MH with temperature being zero. As long as the temperature is small enough, the behavior of MH is almost identical to local search. We believe the temperature is small enough by assuming that it is a small constant in our work, since we may not need to distinguish two parameters with very, very close EI. Moreover, since local search may be trapped in a local optimum, while MH may accept a new configuration with a worse acquisition function value, MH may have the potential to outperform vanilla local search.\n\n(c) No consideration of intensification: In fact, intensification can be incorporated into our framework via a temperature-scaled acceptance rule, analogous to MH, e.g., accepting a challenger $\\theta^\\prime$ over incumbent $\\theta$ with probability $\\exp((l(\\theta)−l(\\theta^\\prime))/T)$. This can be added into the proof (Appendix B.4), but it would mirror our MH analysis with cumbersome computations. While feasible, it would add much technical complexity without altering the core stability concepts or bringing new technical insights. Given our 10+ pages of proofs, we prioritize clarity in conveying the key techinical novelties.\n\nOn the other hand, since the primary area of this paper is theory, our work focuses on the theoretical insights of generalization in AC. Although there is still some gap between our theory and practice, we believe our work has made a solid step towards understanding the generalization ability of AC by studying the concrete configurators in practice, while previous work generally focuses on toy settings of AC with a fixed parameter space.\n\nThe main insight of this paper is to open a new perspective on generalization of AC via the stability of configurators. The technical novelty of this work lies in the framework of bounding stability via KL divergence of sampling paths, together with technical tools for RF stability and MCMC convergence. We believe a theory paper should prioritize **presenting new theoretical insights and proposing new technical tools or frameworks**, instead of covering every detail of algorithms in practice (which always contain complicated heuristics). In future work, we will extend our framework to explore more practical and tighter generalization bounds of AC.\n\n> In typical data regimes, at what sample sizes does your bound stop being vacuous and start giving useful guidance?\n\nAs discussed in Appendix C.2, our bound is non-vacuous if the sample number is beyond about $10^4$. This is indeed large, but still acceptable in practice.\n\nFor example, Brandt et al. [BSB+23] propose AC-Band, a practical AC approach together with theoretical guarantees. (Their guarantee is on the complexity of finding nearly optimal configurations on the training set, while we focus on the gap between training and testing.) In their experiments, they use more than 20000 instances for a (discrete) parameter space with only less than 2000 configurations. As a rough comparison, our bound is still of practical value.\n\n[BSB+23] Brandt et al. AC-Band: A Combinatorial Bandit-Based Approach to Algorithm Configuration. AAAI'23."}, {"review_id": "5LwfOXLVgX", "reviewer": "Reviewer_EMXB", "summary": "Many general purpose algorithms such as algorithms for SAT solving, linear programming, etc, have several configurable parameters. Algorithm Configuration is the process of tuning such parameters to fit a given application. This process, when performed manually may be very time consuming, and therefore several approaches for automated algorithm configuration have been proposed along the years. One popular approach is model-based algorithm configuration, where random forests are used as surrogate models. In this work, the authors provide a generalization bound for this particular algorithm configuration method. More specifically, they show essentially that the error of this method converges with a rate of m^{-1/2}, where m is the number of samples, plus an additive factor of ((n+d)/Q)^{1/4} where n is the number of parameters of the model, d is the number of instance features and Q the number of random forests. In summary, the higher the number of samples and the higher the number of random forests, the smallest the error.", "questions": "No questions.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThe paper is (in most parts) well written and the results are interesting. In particular, this seems to be the first generalization bound for the model based AC with random forests that works both with continuous and with discrete parameters. According to the authors, previous generalization bounds only work with discrete parameters. \t\n\nWeaknesses:\n\nThere are some minor issues with the presentation that if fixed would make the paper easier to read. \n\nThe expression \"generalization bound\" is being used since the abstract, but no intuitive discussion of what this means is given until about the statement of theorem 1. It would be easier for the reader if you can state right away by what you mean with \"generalization bound\", preferentially in the abstract. \n\nIt seems that in line 96, the expression should be  ((n+d)/Q)^{1/4}  and not {-1/4}. \n\nFigure 1 needs improvement. The color choice is not ideal. Using black text with lightly colored background would make the figure much more readable. The text is also overlapping with boxes and arrows (eg. Black-box optimization). Finally the figure is not informative, in the sense that it does not really help understanding the content of the paper. So, my suggestion is simply to remove it and use the space to improve on the clarity of the text.", "was_revised": true, "final_justification": "After reading the reports from the other reviewers and the replies from the authors, my impression of the paper is still positive. For this reason I will keep my score unchanged.", "rebuttal": "Thanks for your review! We are delighted that you consider our work **well-written and interesting**.\n\nWe will modify our paper based on your comments (if accepted).\n\n> The expression \"generalization bound\" is being used since the abstract, but no intuitive discussion of what this means is given until about the statement of theorem 1. It would be easier for the reader if you can state right away by what you mean with \"generalization bound\", preferentially in the abstract.\n\nWe will add an intuitive explanation of generalization bounds in the abstract.\n\n> It seems that in line 96, the expression should be ((n+d)/Q)^{1/4} and not {-1/4}.\n\nThis is indeed a typo. We will fix it.\n\n> Figure 1 needs improvement. The color choice is not ideal. Using black text with lightly colored background would make the figure much more readable. The text is also overlapping with boxes and arrows (eg. Black-box optimization). Finally the figure is not informative, in the sense that it does not really help understanding the content of the paper. So, my suggestion is simply to remove it and use the space to improve on the clarity of the text.\n\nThanks for the valuable comment. We will keep the figure since readers may not be familiar with the setting of algorithm configuration, but we will modify the figure to make it more readable based on your suggestion."}, {"review_id": "FD0OhpbVMk", "reviewer": "Reviewer_eRPv", "summary": "This paper studies stability-based generalization guarantees for model-based algorithm configuration. The basic setup is that we have a parameterized family of algorithms (parameterized by $\\theta \\in [0,1]^n$), a distribution $D$ over input instances to those algorithms, and a utility function $u$ that evaluates the performance (e.g., running time) of a parameter vector on a single input instance. The goal is to leverage a collection of sampled problem instances $I_1, \\ldots, I_m$ drawn from $D$ in order to find an algorithm configuration that has high expected utility for new samples drawn from $D$. Prior work has studied this problem through the lens of uniform convergence, showing that when the algorithm family is not too complicated, a relatively small sample of instances is sufficient to guarantee uniform convergence of every parameter's empirical and expected utility, ensuring that the empirically optimal configuration is also approximately optimal for the underlying distribution. This work instead applies the machinery of stability based convergence guarantees to algorithm configuration to argue that due to the stability of the configuration procedure itself, its output configuration has empirical and expected utilities that are close in expectation.\n\nThe authors study a model-based configuration procedure that at each iteration approximates the mapping from parameters to expected utility with a random forest and uses a Metropolis-Hastings local search sampling method to update the current parameters. The stability argument has a few key components. Fix a pair of datasets that differ on a single instance. First, the authors study the Rademacher complexity of the dual of decision trees, arguing that uniformly for all parameters the surrogate models trained on each dataset make similar utility predictions. They use this result to argue that a single round of the local search has similar output distributions on the two datasets leveraging the fact that the limiting distribution of the Metropolis-Hastings distribution are similar (due to the utility estimates being similar) and a convergence analysis of the sampling. Finally, they argue that the final iterate distribution is also close by decomposing the difference into a product of the differences of each step, which were just shown to be small.", "questions": "1. Please see questions listed in the strengths and weaknesses.\n1. Given that Theorem 5 scales with the number of algorithm parameters, I wonder how the result compares to the following simpler argument: suppose that each of the $n$ parameters is represented as a $b$-bit number so that there are $2^{bn}$ possible configurations. We can establish uniform convergence over those configurations by applying Hoeffding's inequality and the union bound to argue that with probability at least $1-\\delta$, every configuration's empirical utility is within $O\\left(\\sqrt{\\frac{bn + \\ln(1/\\delta)}{m}}\\right)$ of its expected utility. Now applying an arbitrary algorithm configurator to selecting values for the parameters automatically enjoys convergence guarantees, and, moreover, if the configuration is nearly optimal empirically then they are nearly optimal on the underlying distribution (among the $b$-bit values for each parameter). This bound has a worse dependence than the proposed method on the number of parameters ($\\sqrt{n}$ instead of $n^{1/4}$), but it makes no assumption at all on the configurator, does not degrade with the number of iterations of the configurator, provides uniform convergence, and yet still applies to a wide class of multi-parameter algorithm families. Restricting to $b$-bit numerical parameters might miss out on extremely precise algorithm configurations, but it seems like model-based configurators are likely to miss these configurations as well because the surrogate model will be unlikely to capture high utility parameters that are like needles in a haystack. Aside from the better dependence on the number of parameters, are there other advantages of the proposed method?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "# Strengths\n1. This paper fills a gap by applying stability-based convergence guarantees to the problem of algorithm configuration.\n1. The generalization guarantee holds for arbitrary algorithm families by relying only on properties of the configuration procedure, which I think covers realistic cases that are not addressed by prior work.\n1. The main ideas of the analysis are relatively easy to follow.\n\n# Weaknesses\n1. The authors correctly point out an important limitation of prior work on data-driven algorithm design: the analysis tends to hold for a single algorithm family which usually only has a small number of parameters (often one). However, it is worth mentioning that these works typically come with a much stronger guarantee than provided in this submission. As the authors write, the prior work on problem-specific results provide uniform convergence guarantees (and often also efficient empirical risk minimizers), which ensure that those configuration procedures output essentially optimal configurations for the underlying distribution. The guarantee from this submission is much weaker: it provides a bound on the difference between the expected and empirical utilities of the single configuration the method outputs. Essentially, this only rules out surprises where the output configuration performs much worse on new instances than it did on the training instances. But, it cannot rule out the existence of significantly better configurations. In particular, even if the configurator happens to output an empirically optimal configuration, there is no guarantee that it is close to optimal on the underlying distribution (whether this is true or not depends primarily on the algorithm class being optimized over, not the configurator). It is useful to know that the parameters output from realistic configurators will generalize their utility from the sample to the distribution, but this is a significant reduction in scope from the prior work that should be clearly acknowledged.\n1. The authors make a number of simplifications compared to modern configurators (greedy local search is replaced by Metropolis-Hastings sampling, there is no intensification, the configurator outputs final iterate instead of the best observed). The changes do seem relatively minor, but the appendix only compares them empirically for one algorithm family and two problem domains. Given that the analysis depends heavily on these simplifications, it would be good to verify that they do not come at too great a cost to utility.\n1. I would have appreciated more detail about the specific configurator studied in the main body. A few examples:\n    - a. Lines 186-189: Is the surrogate model trained to predict the expected utility of a parameter vector $\\theta$ over the draw of a random instance from the data distribution in addition to $\\xi$? This seems like the intent but it's not explicitly written.\n    - b. Lines 198: Even if it is standard, it might be helpful to state how the decision trees are trained on each bag. (From the proof of Lemma 21, it seems that all that is required is that each tree has at most one leaf per data point and those leaves correspond to hyperrectangles, but it would still be good to clarify).\n    - c. In line 224, my understanding of this statement is that modern algorithm configurators retry the same parameters multiple times to improve the accuracy of the estimates, but the proposed method does not. Is the proposed configurator likely to try each configuration exactly once? Does that impact the configurator's ability to rule out high-variance configurations?\n1. I think the paper would be strengthened by trying to move more of the core analysis into the main body (for example, the VC bounds on the dual class of decision trees with few leaves seem like they could be explained in the main body).", "was_revised": true, "final_justification": "I appreciated the authors responses to my question and maintain my positive score.", "rebuttal": "Thanks for your review! We are delighted that you acknowledge the strengths of our work, e.g., **filling a gap of AC**, **the analysis covers realistic cases**, and the **ideas are easy to follow**.\n\nWe address your concerns as follows:\n\n> It is worth mentioning that previous works typically come with a much stronger guarantee than provided in this submission. As the authors write, the prior work on problem-specific results provide uniform convergence guarantees (and often also efficient empirical risk minimizers), which ensure that those configuration procedures output essentially optimal configurations for the underlying distribution. The guarantee from this submission is much weaker: it provides a bound on the difference between the expected and empirical utilities of the single configuration the method outputs. Essentially, this only rules out surprises where the output configuration performs much worse on new instances than it did on the training instances. But, it cannot rule out the existence of significantly better configurations.\n\nFirst, we kindly clarify that prior work indeed provides uniform convergence guarantees, but they **do not provide efficient ERM algorithms**, or guarantees that the configurator outputs the optimal parameter for the distribution.\n\nPrevious work on problem-specific guarantees generally uses the following argument: They show that the performance metric is a piecewise-structured function w.r.t. the parameters with a bounded number of pieces (usually **exponential**). Then, using a classic VC-/pseudo-dimension argument, the generalization bound is logarithmic to the number of pieces (usually polynomial). However, it is often hard to optimize a piecewise function with an **exponential** number of pieces.\n\nFor instance, Balcan et al. (Ref. [8] in our paper) present generalization bounds for the branching parameter of MILP solvers. Their key argument is to show the size of the search tree is a piecewise-constant function with $O(2^{n(n-1)/2}n^n)$ pieces, and this yields $O(n^2)$ bound for pseudo-dimension. However, their ERM algorithm is not practical: (a) It requires an oracle to enumerate the pieces of the performance metric. Their performance metric is the size of the search tree, while in practice, the performance metric is usually the running time. It may not be easy to implement the oracle; (b) Even if the oracle exists, we need to enumerate $O(2^{n(n-1)/2}n^n)$ pieces to compute the optimum, which is **exponential** time and thus non-efficient.\n\nTo the best of our knowledge, the only work that discusses efficient ERM for previous uniform convergence methods is [BSS24]. Their algorithm is also not practical, and the time complexity still grows linearly w.r.t. to the number of pieces.\n\n[BSS24] Balcan et al. Accelerating ERM for data-driven algorithm design using output-sensitive techniques. NeurIPS'24.\n\nIn fact, it is extremely difficult to show that a configurator provably finds a (near-)optimal configuration on the training set. There is indeed some previous work (e.g., [WGS18] and [BSB+23]), but their results are based on **strong assumptions**, e.g., [BSB+23] assumes that there is an $\\alpha\\in (0,1)$ proportion of configurations in the parameter space being nearly optimal. Due to these challenges, since our work focuses on the generalization bound, guarantees for finding optimal configurations seem to be an **orthogonal** question to this work.\n\n[WGS18] Weisz et al. LeapsAndBounds: A Method for Approximately Optimal Algorithm Configuration. ICML'18.  \n[BSB+23] Brandt et al. AC-Band: A Combinatorial Bandit-Based Approach to Algorithm Configuration. AAAI'23.\n\nSecond, we argue that moving from uniform convergence to algorithm-dependent bounds is not a weakness of our work, but rather a **tradeoff**. Since AC is a black-box, we cannot prove nontrivial guarantees without any structural information. This can be seen as an impossibility triangle: For problem-, algorithm-, and data-independence, take **only two**. Previous work selects algorithm- and data-independence, and yields uniform convergence bounds. We select problem- and data-independence, and obtain an algorithmic stability bound. We believe problem-independence is more important than algorithm-independence, since uniform convergence is often too pessimistic, considering the worst parameter in the space. In practice, we cannot enumerate every configuration in the space. Our work can be seen as a beyond-worst-case analysis of the parameter space, compared with previous work.\n\nLastly, generalization bound itself is a strong guarantee for the configurator's performance, which bounds the number of samples to prevent overfitting. As far as we know, there is no technique (and it may be intractable) to prove optimality guarantees for Bayesian optimization in the model-based AC framework. Since model-based AC performs well in practice, we may not really need such a guarantee. This is similar to the generalization theory of neural networks. There is hardly any provable algorithm that efficiently finds the optimum of a large neural network due to the high non-convexity, but academics still put much effort into generalization bounds of NN. Moreover, our bound indeed cannot rule out the existence of significantly better configurations on the distribution. However, from the viewpoint of practice, even a perfect black-box optimizer cannot achieve this, since the distribution is not accessible to the configurator.\n\n> The authors make a number of simplifications compared to modern configurators. The changes do seem relatively minor, but the appendix only compares them empirically for one algorithm family and two problem domains.\n\nThanks for your comment. We will add more experiments in the appendix to make it more convincing if accepted. We also conceptually discuss why our assumptions are rather mild. Please see the response to reviewer 2hU7 due to the word limit.\n\n### Regarding algorithmic details:\n\n> Is the surrogate model trained to predict the expected utility of a parameter vector $\\theta$\nover the draw of a random instance from the data distribution in addition to $\\xi$?\n\nYes. The surrogate model is trained over the randomness of $\\xi$. We kindly point out that the existence of $\\xi$ does not really affect our analysis. In fact, we can eliminate $\\xi$ by assuming the instance distribution is a joint distribution of both instances and random seeds.\n\n> Even if it is standard, it might be helpful to state how the decision trees are trained on each bag.\n\nYes. We apply the standard method of decision tree construction method. We recursively select a split condition (e.g., $\\theta_2\\le 0.4$) that minimizes the total empirical variances of two subtrees, until a node has a small number of datapoints. Each leaf is a hyper-rectangle with one or multiple datapoints (the number of datapoints in the leaf does not affect the upper bound).\n\n> Is the proposed configurator likely to try each configuration exactly once? Does that impact the configurator's ability to rule out high-variance configurations?\n\nIn fact, our analysis applies to the case of trying each configuration an arbitrary number of times, as long as the number is **fixed**. As abovementioned, we can move the randomness of $\\xi$ into the instance distribution without affecting the proof. Evaluating each configuration multiple times indeed decreases the random seed variance, which may empirically improve the configurator. Yet this does not improve our bound, since there still exists the variance of instances.\n\n### Regarding the discretization argument:\n\n> Given that Theorem 5 scales with the number of algorithm parameters, I wonder how the result compares to the following simpler argument: (...)\n\nThis is an excellent question!\n\nThe discretization technique gives a reasonable generalization bound. Even more surprisingly, it could **supersede many previous studies on generalization of both AC and machine learning**. For instance, Ref. [8] in our paper gives $O(n^2)$ pseudo-dimension bound for MILP solver, while discretization directly gives $O(b)$ bound (the variable number $n$ is often more than $10^4$, while $b\\le 64$ in modern 64-bit computers). [BHLM19] proves $O(WL\\log W)$ VC-dimension for neural networks with $W$ weights and $L$ layers, while discretization yields $O(Wb)$ upper bound.\n\n[BHLM19] Bartlett et al. Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks. JMLR'19.\n\nHowever, we argue that the aim of studying generalization is not only proving the tightest bound, but also **finding insights of the learning problem**. If one needs a numerically tight bound, it is sufficient to simply evaluate on a validation set. Instead, we aim to understand generalization by **relating generalization errors with the structural properties of the problem and the learning algorithm**. Ref. [8] and [BHLM19] are important since they shed light on the interval structures of the parameter spaces of NNs and MILP solvers. On the contrary, the discretization argument hardly presents any insight.\n\nThus, the main target of our work is to open a new perspective on generalization of AC. From our view, it is somewhat surprising that model-based AC is stable even with a black-box optimization landscape (note that **we make no assumptions on the instances and landscapes of the performance metric**). This may illustrate some theoretical insights on model-based configurators. Recall that the algorithmic stability framework explains why regularization terms may prevent overfitting in machine learning models. We hope our work could motivate future work to further improve the generalization ability of configurators in practice."}, {"review_id": "xrQENNKYLs", "reviewer": "Reviewer_wUqi", "summary": "This paper focuses on the theoretical guarantee on the generalization performance in algorithm configuration. Specifically, this paper utilizes the theoretical connection between the stability and the generalization performance of algorithms. It considers an algorithm configurator based on random forests surrogate model. Then it derives a generalization guarantee of such model-based algorithm configurator by proving its stability. The key technical tool in establish the theoretical results is algorithmic stability (which should be credited to Bousquet & Elisseeff 2002, not Ben-David’s textbook).", "questions": "1. The improvement equation after line 207: the LHS depends on $\\hat{u}$, but in the RHS, $\\hat{u}$ is expected over. \n2. What is $\\sigma_{\\rm min}$ in Theorem 5? I did not see it defined in the paper.", "limitations": "NA", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strength:\n\n* The application of algorithm stability in this context seems interesting.\n\nWeakness: \n\nWeakness: \n\n* The paper is not clearly written. There are missing details and errors, which make the paper confusing. Ignoring the minor things, the main confusion is the blurred boundary between two notions: the **true performance** of some $(\\theta, I)$ (which is measured by function $u(\\cdot)$ and the **surrogate performance** of $(\\theta, I)$ (namely, the performance measured under the surrogate model).  Another confusion is the distinction between two different sources of randomness: the first is the randomness in the true performance (or in the evaluated algorithm): the function $u(\\theta, I, \\xi) $ depends on a random seed $\\xi$, and the second is the randness in the surrogate random forest model. These two sources are different but the paper might have used the second to replace the first without justification.  -- I am not too sure about this though.\n\n* Possibly due its lack of clarity,  I think that the main result, Theorem 5, is irrelevant to the proposed algorithm.  Specifically, Theorem 5 upper bounds the gap between the expected **true performance** of  configuration $\\tilde{\\theta}$ and empirical **true performance** of $\\tilde{\\theta}$.  However, there can be a gap between the empirical **true performance** of $\\tilde{\\theta}$ and the empirical **surrogate performance** of $\\tilde{\\theta}$. The proposed algorithm, under the guidance of the surrogate model, finds some $\\tilde{\\theta}$ whose **surrogate performance**  is good, but the theorem has nothing to do with the surrogate performance. In other words, the theorem does not justify that $\\tilde{\\theta}$ found by the proposed algorithm has good **true performance**.\n\nTo be more concrete, let me explain my understanding of the proposed algorithm.The algorithm runs in two phases. \n\nIn Phase 1, it first sample a number of $\\theta$'s, and for each $\\theta$, sample some tasks $I$, and for each pair $(\\theta, I)$, evaluate its performance $u(\\theta, I)$, which is inherently random (due toi the first source of randomness). It then first a best $\\theta$, which I denote by $\\theta_0$  in this list of $\\theta$'s that has the best average performance over the sampled tasks. \n\nIn Phase 2, a surrogate random forest model is trained, which tries to predict the expected performance of $u(\\theta, I)$. I will denote the learned predictor by $\\hat{u} (\\theta, I)$.  Note that $\\hat{u}(\\theta, I)$ is also random due to random forest predictor, i.e., this is the second source of randomness. Guided by $\\hat{u}$, $\\theta_0$ is iteratively updated to $\\tilde{\\theta}$, where $\\tilde{\\theta}$ improves upon $\\theta_0$ in some sense,  under **the learned surrogate performance metric** $\\hat{u}$.   \n\nTheorem 5 is about true performance $u$, bounding the gap between the expected $u$ and the emprical average of $u$ for $\\tilde{\\theta}$. But there is still a gap between the emprical average of $u$ and the emprical average of $\\hat{u}$ for $\\tilde{\\theta}$. In other words, although $\\tilde{\\theta}$ may be good measured under $\\hat{u}$, it may not be good under $u$, namely, the surrogate model may not generalize over changing $\\theta$.\n\nMy above complaints may result from some misunderstanding of the paper, due to its lack of clarify. If this is the case, I hope the authors in your rebuttal please clearly summarize the algorithm flow and make clear distinctions of these notions with clear notations.", "was_revised": true, "final_justification": "The authors' rebuttal clarifies the major confusions I had during the review. I have changed my score to 4 (borderline accept).  I encourage the authors to make their best effort in polishing presentation of the paper. This may involve: 1) making the workflow of algorithm configurators more accessible for audiences outside the field but adequately knowledgeable in general machine learning (as myself). 2) using clearer notations to emphasize the distinction of the related notions of performances: empirical performance, true performance, and the predicted performance by the surrogate model. (Ideally, when the workflow is described, these notions of performance should be used).", "rebuttal": "Thanks for your review. To address your concerns, we kindly make the following clarifications.\n\n### Regarding the understanding of our result:\n\n> Theorem 5 upper bounds the gap between the expected true performance of configuration $\\tilde{\\theta}$ and empirical true performance of $\\tilde{\\theta}$. However, there can be a gap between the empirical true performance of $\\tilde{\\theta}$ and the empirical surrogate performance of $\\tilde{\\theta}$. The proposed algorithm, under the guidance of the surrogate model, finds some $\\tilde{\\theta}$ whose surrogate performance is good, but the theorem has nothing to do with the surrogate performance. In other words, the theorem does not justify that $\\tilde{\\theta}$ found by the proposed algorithm has good true performance.\n\nThere is a misunderstanding about the target of our work. We aim to **provide theoretical guarantees on the generalization ability of the popular model-based algorithm configurators, instead of proposing new model-based methods with good surrogate models** (see Lines 34--36). We discuss in the introduction (Lines 33--42) why generalization guarantees are important. We highlight the discussion and make some clarifications as follows. \n\nA typical modern AC flow is as follows: There is a computational problem together with a parameterized solver. The problem instances follow a distribution, and we aim to find a parameter configuration with a good expected performance on this distribution. However, we cannot access the distribution but only samples from it. Thus, we sample instances $I_1,\\dots,I_m$, and apply an algorithm configurator (e.g., Algorithm 1) to find the a configuration that performs well on $I_1,\\dots,I_m$.\n\nHowever, how many sampled instances do we need to ensure that **the found configuration which performs well on $I_1,\\dots,I_m$ also performs well on other unseen samples in the distribution**? We answer this question by presenting a generalization bound to upper bound the gap between the performances of the widely used model-based AC on the training set, i.e., $\\frac{1}{m}\\sum_i u(\\tilde{\\theta},I_i,\\xi_i)$ and the expected performance on the testing set $\\mathbb{E} _{I,\\xi} [u(\\tilde{\\theta},I,\\xi)]$. In practice, we only access $\\frac{1}{m}\\sum_i u(\\tilde{\\theta},I_i,\\xi_i)$ on the training set. If we obtain an upper bound $\\varepsilon$ of the generalization error, then we can bound the true performance by $\\frac{1}{m}\\sum_i u(\\tilde{\\theta},I_i,\\xi_i)+\\varepsilon$. This is important since it tells us how many samples do we need to prevent overfitting on the training set. Note that we only compare the **true performances** on problem instances.\n\nIndeed, we do not bound the approximation error of the surrogate model. (In fact, it is easy to prove that the surrogate model cannot be perfectly accurate even with an infinite number of samples.) The surrogate model is only a **heuristic** method that is widely used in black-box optimization, and it is empirically good. The approximation error of surrogate models, and more deeply, whether Algorithm 1 provably finds a nearly optimal solution on the training set, are also interesting questions, but are **orthogonal to this work**. The target of this work is to explain the generalization ability of the parameter found by the widely used model-based algorithm configurator (Algorithm 1) in practice.\n\nWe can make an analogy to the standard machine learning setting to help to understand. For example, previous work [HRS16] shows that stochastic gradient descent has a good generalization ability since it is stable in particular cases. However, whether SGD could minimizes the loss function on the training set (relating to the convergence rate of SGD) is an **orthogonal** question to the generalization ability of the model found by SGD. In fact, SGD may not provably find an optimal solution for modern neural network models due to the highly non-convexity. In our work, the model-based algorithm configurator (Algorithm 1) is similar to the SGD algorithm, and the main result of this paper is to prove the generalization ability of the algorithm configurator.\n\n[HRS16] Hardt et al. Train faster, generalize better: stability of stochastic gradient descent. ICML'16.\n\n> To be more concrete, let me explain my understanding of the proposed algorithm. The algorithm runs in two phases.  \nIn Phase 1, it first sample a number of $\\theta$'s, and for each $\\theta$, sample some tasks $I$, and for each pair $(\\theta,I)$, evaluate its performance $u(\\theta,I)$, which is inherently random (due to the first source of randomness). It then first a best $\\theta$, which I denote by $\\theta_0$ in this list of $\\theta$'s that has the best average performance over the sampled tasks.  \nIn Phase 2, a surrogate random forest model is trained, which tries to predict the expected performance of $u(\\theta,I)$. I will denote the learned predictor by $\\hat{u}(\\theta,I)$. Note that $\\hat{u}(\\theta,I)$ is also random due to random forest predictor, i.e., this is the second source of randomness. Guided by $\\hat{u}$, $\\theta_0$ is iteratively updated to $\\tilde{\\theta}$, where $\\tilde{\\theta}$ improves upon $\\theta_0$ in some sense, under the learned surrogate performance metric $\\hat{u}$.\n\nWe kindly clarify that your notations are not precise, which may lead to a misunderstanding of our result. Concretely, **the notation $\\hat{u}$ in our paper is not the learned predictor**. It is the real empirical performance of a configuration on an instance in the training set, and it is independent of the surrogate model. We clarify Algorithm 1 as follows:\n\nInput: Instances $I_1,\\dots,I_m$. (Note that instances are not sampled in Phase 1, it is sampled before the training algorithm, i.e., training data in general machine learning settings.)  \nPhase 1: We randomly sample $\\theta$s, evaluate them on $I_1,\\dots,I_m$, and select the best one.  \nPhase 2: In each iteration, we train a surrogate model $\\mathsf{RF}$, and select a $\\theta$ based on the model.  \nNote that the surrogate model is represented by $\\mathsf{RF}$ in Line 202, while $\\hat{u}$ is the fitting data for $\\mathsf{RF}$ by previous evaluations. In Line 184, we define $\\hat{u} _{ij}=u(\\theta_i,I_j,\\xi _{ij})$. Thus, $\\hat{u}$ is only a shorthand for samples of $u(\\theta,\\cdot,\\cdot)$.\n\n> Ignoring the minor things, the main confusion is the blurred boundary between two notions: the true performance of some $(\\theta,I)$ (which is measured by function $u(\\cdot)$ and the surrogate performance of $(\\theta,I)$ (namely, the performance measured under the surrogate model).\n\nWe kindly clarify that this is **not true**. Based on the above clarifications, the notations of $u$ and the surrogate model $\\mathsf{RF}$ are clearly distinct. Our main theorem is about the gap between the expected $u$ and the empirical average of $\\hat{u}_{ij}$ (which are samples of $u$), and it does not relate to the surrogate prediction. We prove the stability of the surrogate model (Appendix B.3) only as a technical building block to obtain our generalization bound, while the true performance $u$ is what we really care about.\n\n> Another confusion is the distinction between two different sources of randomness: the first is the randomness in the true performance (or in the evaluated algorithm): the function $u(\\theta,I,\\xi)$ depends on a random seed $\\xi$, and the second is the randomness in the surrogate random forest model. These two sources are different but the paper might have used the second to replace the first without justification.\n\nWe kindly clarify that this is **not true**. In the initial notation preparation of our proof (Appendix B.1), we fix the instances $I_1,\\dots,I_m,I^\\prime_m$ together with the random seeds $\\xi_{ij}$. Throughout the proof, we are dealing with deterministic instances and random seeds. Please point out the concrete arguments if we violate this principle.\n\n### Minor questions:\n\n> The improvement equation after line 207: the LHS depends on $\\hat{u}$, but in the RHS, $\\hat{u}$ is expected over.\n\nThanks for pointing out this typo. The LHS should depend on $\\hat{\\mu},\\hat{\\sigma}$.\n\n> What is $\\sigma_{\\rm min}$ in Theorem 5? I did not see it defined in the paper.\n\nThanks for pointing out this mistake. We will add it to the main text. The notation $\\sigma_{\\rm min}$ is simply a lower bound on the variance prediction of the surrogate model and is only used in Line 550 of the proof. We naturally assume $\\sigma_{\\rm min}$ is a constant, since in practice, the predicted variance cannot be arbitrarily small due to the variance of random forests. The variance ensures that the configurator will explore new parameters instead of purely exploiting.\n\nWe hope that our response clarifies the contributions of our work. We kindly request you to reevaluate our paper based on the response."}, {"review_id": "0qdKABl8Dg", "reviewer": "Reviewer_KtNU", "summary": "The paper presents the first generalization bound for model-based algorithm configurators (AC), a widely used class of methods for automatic parameter tuning of complex algorithms (e.g., SAT or MIP solvers). The authors focus on the practical setting where the AC process is guided by surrogate models (here: random forests) and search heuristics based on acquisition functions like expected improvement. Using the framework of algorithmic stability, the paper derives a generalization bound that accounts for continuous and multi-dimensional parameter spaces, and that is dependent on properties of the configurator itself (rather than the parameterized algorithm). The bound incorporates terms reflecting the surrogate model complexity and the sampling procedure’s convergence, offering insights into how algorithm configurations found on a finite set of instances can generalize well to unseen problem instances.", "questions": "* How confident are you that the MCMC abstraction sufficiently captures the true search dynamics for EI maximization, as EI maximization can be relatively tough in practice?\n* Since RFs can only poorly predict values beyond observed samples (i.e. extrapolation), the configurator may miss regions with better configurations. Could this limitation be reflected in the theoretical bound (e.g., via a bias term)?\n* The stability analysis focuses on predicted values, but practical configuration decisions depend on the relative ranking of configurations. Could not changes in configuration orderings, even under small perturbations, cause significant differences in behavior? \n* What happens when problem instances are non-i.i.d.? The generalization bound assumes i.i.d. sampling from a distribution D, but in real applications (e.g., solver competitions), instances may be clustered or adversarial. Also, algorithm configuration might be performed on a system different from where the found configuration is ultimately deployed. How sensitive is the theory to this assumption?\n* Can we deduct requirements for an intensification scheme from your theory to reduce the number of trials conducted during algorithm configuration?", "limitations": "The authors discuss their assumptions and mention some practical caveats (e.g., surrogate model choice, algorithmic assumptions), but they do not fully address limitations such as the inability of RFs to extrapolate or the fragility of configuration rankings under slight perturbations. Including a deeper discussion of these issues would strengthen the paper and increase its transparency.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 4, "strengths_and_weaknesses": "The major strength of the paper is that it addresses a longstanding gap between empirical success and theoretical understanding of algorithm configuration, offering the first generalization guarantees aligned with methods that are used in practice, such as SMAC. The use of algorithm-dependent stability for generalization in algorithm configuration, combined with an analysis of random-forest-based surrogate models, which are typically used for their speed, robustness in generalization performance, and native applicability to mixed input spaces (i.e., parameter spaces comprising categorical, Boolean, integer, and float parameters). The theoretical framework is sound and uses established learning theory tools, e.g., Rademacher complexity, Pinsker’s inequality, and MCMC convergence. The problem setup and assumptions are precisely formulated, with clear definitions of the algorithm configuration process, surrogate model, and generalization objective.\n\nHowever, the paper also comes with a couple of weaknesses. First of all, the use of random forests as surrogate models introduces significant limitations not accounted for in the theory. Most notably, RFs cannot extrapolate, which constrains the EI acquisition function and may limit the configurator’s ability to explore promising but unseen regions of the parameter space. While mean predictions might be relatively stable and are bound in the paper to not deviate too much, the ordering of configurations can, in fact, also be affected by smaller changes in the predictions, e.g., when values are relatively close to each other. In practice, even small prediction changes can flip orderings and substantially alter the sampled configurations, which is not reflected in the analysis. \nFurthermore, the mean might be too prone to be distorted by “outliers”, as in algorithm configuration, we often deal with performance landscapes that exhibit heavy-tailed distributions. I am wondering to what extent this impedes the stability of the learning algorithms.\nAnother issue is with the acquisition function maximization and whether it is sufficiently stable via MCMC. In practice, EI is known to be sensitive, especially with non-smooth or multimodal landscapes, which are indeed induced by random forests. This raises concerns about the robustness of the practical applicability of the bound. Lastly, while the theoretical contributions are substantial, empirical analysis (as described in the appendix) is limited in demonstrating whether the bound meaningfully correlates with observed generalization for diverse algorithm configuration scenarios. This includes considerations about the homogeneity of the problem instances, i.e., whether assumptions on the best configuration being consistent for all problem instances (or even entire rankings of configurations in the case of strong homogeneity) need to be fulfilled to allow for generalization bounds. Note that there exists the classical algorithm configuration and the per-instance algorithm configuration setup, which differ in their assumptions about the homogeneity of the problem instances. While in classical algorithm configuration, one would assume homogeneity for all problem instances, in the case of per-instance algorithm configuration, the assumption is only about homogeneous subsets of problem instances. In other words, for different such subsets, different algorithm configurations work best. It is quite surprising to me that the only assumption on the problem instances in the paper is that the problem instances are i.i.d.", "was_revised": true, "final_justification": "Important step towards better theory in AC; close to real-world AC systems and providing ways for future research.", "rebuttal": "Thanks for your review! We are delighted that you consider our work **sound and precise**. We address your concerns as follows.\n\n### Regarding limitations of RFs:\n\n> First of all, the use of random forests as surrogate models introduces significant limitations not accounted for in the theory. Most notably, RFs cannot extrapolate, which constrains the EI acquisition function and may limit the configurator’s ability to explore promising but unseen regions of the parameter space.\n\nWe acknowledge that random forests (RFs) lack extrapolation capabilities. However, RFs remain the de facto standard in practical algorithm configurators (e.g., SMAC) due to their scalability, robustness to mixed parameter types, and compatibility with structured performance landscapes. Crucially, the performance of SAT/ILP solvers often exhibits piecewise-constant behavior, which aligns naturally with the inductive bias of decision trees (see the discussion in Refs. [8, 9] in our paper). While RFs cannot extrapolate beyond observed samples, the variance term in EI actively promotes exploration of undersampled regions by favoring high-uncertainty configurations. This mitigates the risk of missing promising regions.\n\nMoreover, our work focuses on explaining why existing configurators generalize well --- not designing new ones. Thus, RF limitations are **orthogonal** to our theoretical goal of bounding generalization errors, though we will further study other models in future work.\n\n> Since RFs can only poorly predict values beyond observed samples (i.e. extrapolation), the configurator may miss regions with better configurations. Could this limitation be reflected in the theoretical bound (e.g., via a bias term)?\n\nGeneralization (stability) and optimization bias are distinct challenges. Our bound characterizes how configurator output stability depends on data perturbations, not the optimization quality using the surrogate model. Incorporating bias would require analyzing the optimality gap of the black-box optimizer --- a problem significantly harder than generalization analysis, beyond the scope of this work. There is indeed some prior work on configurators with provable optimization guarantees (e.g., [WGS18] [BSB+23]). Their work requires much stronger assumptions, e.g., [BSB+23] assumes that there is an $\\alpha\\in (0,1)$ proportion of configurations in the parameter space being nearly optimal.\n\n[WGS18] Weisz et al. LeapsAndBounds: A Method for Approximately Optimal Algorithm Configuration. ICML'18.  \n[BSB+23] Brandt et al. AC-Band: A Combinatorial Bandit-Based Approach to Algorithm Configuration. AAAI'23.\n\n### Regarding MCMC sampling, intensification, and relative rankings:\n\n> How confident are you that the MCMC abstraction sufficiently captures the true search dynamics for EI maximization, as EI maximization can be relatively tough in practice?\n\n> In practice, EI is known to be sensitive, especially with non-smooth or multimodal landscapes, which are indeed induced by random forests. This raises concerns about the robustness of the practical applicability of the bound.\n\nWe adopted MCMC as a theoretically tractable proxy for stability analysis. The key insight is that MCMC’s probabilistic acceptance rule (based on $\\exp⁡(\\Delta\\text{EI}/\\tau))$ smooths the search process compared to greedy hill-climbing. This smoothing ensures that small perturbations to EI values (from data changes) induce bounded changes in the sampling distribution --- enabling the stability proof. If $\\tau=0$, this is exactly local search. We set $\\tau$ as a small constant to approximate its behavior. We believe this is reasonable since we do not need to distinguish two parameters with very, very close EI.\n\nAnother advantage of MCMC is that it is similar to simulated annealing, which may, compared with vanilla local search, **escape from local minima**. This is sometimes even better since the landscape may be multimodal.\n\n> In practice, even small prediction changes can flip orderings and substantially alter the sampled configurations, which is not reflected in the analysis.\n\n> The stability analysis focuses on predicted values, but practical configuration decisions depend on the relative ranking of configurations. Could not changes in configuration orderings, even under small perturbations, cause significant differences in behavior?\n\n> Can we deduct requirements for an intensification scheme from your theory to reduce the number of trials conducted during algorithm configuration?\n\nAs in the previous discussion, we apply MCMC instead of local search in our analysis, to avoid the issue of ordering flips. For the same reason, we do not consider intensification.\n\nIn fact, intensification can be incorporated into our framework via a temperature-scaled acceptance rule, analogous to MCMC, e.g., accepting a challenger $\\theta^\\prime$ over incumbent $\\theta$ with probability $\\exp((l(\\theta)−l(\\theta^\\prime))/T)$. This can be added into the proof (Appendix B.4), but it would mirror our MCMC analysis with cumbersome computations. While feasible, it would add much technical complexity without altering the core stability concepts. Given our 10+ pages of proofs, we prioritize clarity in conveying the key technical novelties --- bounding stability via KL divergence of sampling paths, together with technical tools for RF stability and MCMC convergence. We believe a theory paper should prioritize **presenting new theoretical insights, and proposing new technical tools or frameworks**, instead of covering every detail of algorithms in practice (which always contain complicated heuristics).\n\n### Regarding outliers, i.i.d., and other settings:\n\n> Furthermore, the mean might be too prone to be distorted by “outliers”, as in algorithm configuration, we often deal with performance landscapes that exhibit heavy-tailed distributions. I am wondering to what extent this impedes the stability of the learning algorithms.\n\nThis is a very good question. In our setting, we assume the performance function is bounded in $[0,1]$, which is a normal assumption in previous work (Refs. [7-16] in our paper). This is key to ensuring the stability of the configurator. Although the running time of a particular instance may be extremely long, an important observation is that the real running time may not be a good loss function. We may instead define a bounded utility function as the loss function, such that it conforms to our framework. Such utility functions exist due to some simple axioms. This is discussed in detail in [GLR23].\n\n[GLR23] Graham et al. Formalizing Preferences Over Runtime Distributions. ICML'23.\n\n> While in classical algorithm configuration, one would assume homogeneity for all problem instances, in the case of per-instance algorithm configuration, the assumption is only about homogeneous subsets of problem instances. In other words, for different such subsets, different algorithm configurations work best.\n\nIndeed, a single configuration may not work well for every instance. Yet this paper focuses on the generalization of the standard AC, while the question of whether there exists a universally optimal configuration goes beyond our scope.\n\nFor per-instance configuration, or more advanced settings, [BSV21] studies generalization bounds for selecting configurations from an algorithm portfolio using a feature-based predictor. However, their approach is also based on uniform convergence, and they consider rather toy settings, similar to Refs. [7-16] in our paper. It would be interesting to extend our stability-based framework to algorithm selection, but we defer it to future work, since it requires more assumptions on the instance features and algorithm selectors, possibly also new techniques.\n\n[BSV21] Balcan et al. Generalization in portfolio-based algorithm selection. AAAI'21.\n\n> What happens when problem instances are non-i.i.d.? The generalization bound assumes i.i.d. sampling from a distribution D, but in real applications, instances may be clustered or adversarial.\n\nIn this paper, we make no assumptions on the performance metric besides the boundedness. Non-i.i.d. settings require other assumptions on the performance landscape of instances. For example, we may borrow technical tools from the theory of domain adaptation to obtain guarantees for AC.\n\nClustered settings can be seen as a special kind of i.i.d. setting. We can regard the instances as samples from a mixture of multiple distributions. However, adversarial settings are extremely hard, compared with i.i.d. settings. For example, [BSV18] studies the adversarial online learning of algorithm configuration. Even with some additional randomness assumptions on the instances, the regret bound is $O(n^4)$ (n being problem size) even for tuning **a simple single-parameter greedy heuristic**. We feel that it may be intractable for adversarial learning of general AC.\n\n[BSV18] Balcan et al. Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization. FOCS'18.\n\n> Also, algorithm configuration might be performed on a system different from where the found configuration is ultimately deployed. How sensitive is the theory to this assumption?\n\nLet $u_1(\\theta,I,\\xi)$ and $u_2(\\theta,I,\\xi)$ be the performance on the training and deployment systems, respectively. If $\\sup |u_1(\\theta,I,\\xi)-u_2(\\theta,I,\\xi)|\\le \\phi$ (the deployment loss), and the generalization error of our bound is $\\varepsilon$, then a simple triangular inequality shows that the generalization gap on the deployment system is upper bounded by $\\varepsilon+\\phi$. In general, we believe the impact of systems is small and thus $\\phi$ is also small.\n\nWe hope our response clarifies the key contributions of our work. We kindly request you to reevaluate our paper based on the response."}]

Author rebuttal:

Meta-review: This paper provides generalization bounds for the problem of selecting algorithm parameters based on sampled problem instances. The reviewing team was overwhelmingly positive about the submission. Clear accept. Good job!

Please incorporate all the feedback received from the reviewers in the revised version.
Decision: Accept (poster)