Reshuffling Resampling Splits Can Improve Generalization of Hyperparameter Optimization
Authors: Thomas Nagler
Lennart Schneider
Bernd Bischl
Matthias Feurer
Venue: NeurIPS 2024 poster (2024)
Keywords: Hyperparameter Optimization
Generalization Performance
Cross-Validation
Resampling
Validation Splits
Model Selection
Automated Machine Learning
Primary area: other
TL;DR: We propose to reshuffle resampling splits during hyperparameter optimization to improve generalization performance, demonstrating its effectiveness through theoretical analysis, simulations and benchmark experiments.

Abstract: Hyperparameter optimization is crucial for obtaining peak performance of machine learning models. The standard protocol evaluates various hyperparameter configurations using a resampling estimate of the generalization error to guide optimization and select a final hyperparameter configuration. Without much evidence, paired resampling splits, i.e., either a fixed train-validation split or a fixed cross-validation scheme, are often recommended. We show that, surprisingly, reshuffling the splits for every configuration often improves the final model's generalization performance on unseen data. Our theoretical analysis explains how reshuffling affects the asymptotic behavior of the validation loss surface and provides a bound on the expected regret in the limiting regime. This bound connects the potential benefits of reshuffling to the signal and noise characteristics of the underlying optimization problem. We confirm our theoretical results in a  controlled simulation study and demonstrate the practical usefulness of reshuffling in a large-scale, realistic hyperparameter optimization experiment. While reshuffling leads to test performances that are competitive with using fixed splits, it drastically improves results for a single train-validation holdout protocol and can often make holdout become competitive with standard CV while being computationally cheaper.

Reshuffling Resampling Splits Can Improve Generalization of Hyperparameter Optimization
Thomas Nagler" t wwn.neerlll.. de
Lennart Schneider*
Bernd Bischl
Matthias Feurer
Department of Statistics, LMU Munich Munich Center for Machine Learning (MCML)
Abstract
Hyperparameter optimization is crucial for obtaining peak performance of ma- chine learning models. The standard protocol evaluates various hyperparameter configurations using resampling estimate of the generalization error guide opti- mization and select a final hyperparameter configuration. Without much evidence, paired resampling splits, i.e., either fixed train- vrinnvalidation split fixed cross- validation scheme, are often recommended. We show that, surprisingly. reshuffling the splits for every configuration often improves the final model's generalization performance on unseen data. Our theoretical analysis explains how reshuffling affects the asymptotic behavior of the validation loss surface and provides bound on the expected regret in the limiting regime. This bound connects the potential benefits of reshuffling the signal and noise characteristics of the underlying optimization problem. We confirm our theoretical results in controlled simula- tion study and demonstrate the practical usefulness of reshuffling in a large-scale, realistic hyperparameter optimization experiment. While reshuffling leads to test performances that are competitive with using fixed splits, drastically improves results for single train-validation holdout protocol and can often make holdout become competitive with standard CV while being computationally cheaper.
1 Introduction
Hyperparameters have been shown to strongly influence the performance of machine learning models (van Rijn & Hutter, 2018; Probst et al., 2019). The primary goal of hyperparameter optimization (HPO; also called tuning) the identification and selection of a hyperparameter configuration (HPC) that minimizes the estimated generalization error (Feurer & Hutter, 2019; Bischl et al., 2023). Typically, this task is challenged by the absence of closed-form mathematical description of the objective function, the unavailability of an analytic gradient, and the large cost evaluate HPCs, categorizing HPO noisy, black-box optimization problem. An HPC is evaluated via resampling, such as holdout split or Mffold cross-vale valos-valiotionn (CV), during tuning.
These resampling splits are usually constructed in a fixed and instantiated manner, i.c., the same training and validation splits are used for the internal evaluation of all configurations. On the one hand, this is an intuitive approach, as it should facilitate a fair comparison between HPCs and reduce the variance in the comparison.' On the other hand, such fixing of train and validation splits might steer the optimization, especially after a substantial budget of evaluations, towards favoring HPCs
"qqual contribution.
'This approach likely originates from the concept of paired statistical tests and the resulting variance reduction, but in our literature search did not find any references discussing this in the context of HPO. example, when comparing the performance of two classifiers on one dataset, paired tests are commonly
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

which are specifically tailored to the chosen splits. Such and related effects, where we "overoptimize" the validation performance without effective reward in improved generalization performance have been sometimes dubbed "overtuning" or "oversearccing", For more detailed discussion of this topic, including related work, see Section and Appendix B. The practice of reshuffling resampling splits during HPO is generally neither discussed in the scientific literature nor HPO software tools. To the best of our knowledge, only Lévesque (2018) investigated reshuffling vain-validation splits for every new HPC. For both holdout and M-fold CV using reshuffled resampling splits resulted in, on average, slightly lower generalization error when used combination with Bayesian optimization (BO, Garnett, 2023) CMA-ES (Hansen & Ostermeier, 2001) as HPO algorithms. Additionally, reshuffling was used by a solution to the NeurIPS 2006 performance prediction challenge to estimate the final generalization performance (Guyon et al., 2006). Recently, in the context of evolutionary optimization, reshuffling was applied after every generation (Larcher & Barbosa, 2022).
In this paper, systematically examine the effect of reshuffling on HPO performance. Our contribu- tions can be summarized follows:
1. We show theoretically that reshuffling resampling splits during HPO can result in finding a configuration with better overall generalization performance, especially when the loss surface is rather flat and its estimate is noisy (Section 2).
2. We confirm these theoretical insights through controlled simulation studies (Section 3).
3. We demonstrate in realistic HPO benchmark experiments that reshuffling splits can lead to a real-world improvement of HPO (Section 4). Especially in the case of reshuffled holdout, we find that the final generalization performance is often on par with 5-fold CV under a wide range of settings.
We discuss results, limitations, and avenues for future research in Section 5.
Theoretical Analysis
2.1 Problem Statement and Setup
Machine learning (ML) aims to fit a model to data, so that it generalizes well to new observations of the same distribution. Let variables from a distribution P. i.e., in the supervised setting Z; = (X,, Y.). 3.4 Formally, an inducer g configured by an HPC A E A maps a dataset D to model from our hypothesis space
{Z be the observed dataset consisting of i.i.d. random
(D) E H. During HPO, we want to find HPC that minimizes the expected generalization error, i.e., find
A arg min ((A), where p(A) EEi(Z. (D)),
AEA
where e(Z, h)) is the loss of model h fresh observation Z. In practice there is usually limited computational budget for each HPO run, so we assume that there only a finite number of distinct to be evaluated, which also simplifies the subsequent analysis. Naturally, we cannot optimize the generalization error directly, but only an estimate of it. To do so, a resampling constructed. For every HPC Xy. draw M random sets Iij..... IM C {l..... n) of validation
HPCs A == {AI..... }
indices with Reyalid [an] instances each. The random index draws are assumed to be independent
of the observed data. The data is then split accordingly into pairs Vin.j (Z hiem.. Tm..j
{Z (Zihezm.. of disjoint validation and training sets. Define the validation loss on the mn-th fold
L(Vm.j' 9x, (Tm.))
Σ (Zi,gA,,TTa
Doaaldd iEZm!
employed that implicitly assume that differences between the performance of classifiers given CV fold comparable (Dietterich, 1998; Nadeau & Bengio, 1999, 2003; Demsar, 2006).
"I Appendix B, present an overview of how resampling is addressed in tutorials and examples of standard HPO libraries and software. We conclude that usually fixed splits used recommended.
'Throughout, we use bold letters to indicate (fixed random) vectors.
We provide notation table for symbols used in the main paper in Table in the appendix.

---

and the M-fold validation loss as
1 T(),)) M Σ
L(vm.i9., 9x, (0.niii);(TTm)))) (Tmai)).
Since is unknown, we minimize X arg minXEA (()), hoping that μ(²) will also be small. Typically, the same splits are used for every HPC, so Im.j - Im for all j = I,...,J and m 1...., M. In the following, we investigate how reshuffling train-validation splits (i.e., Im F Immj'' for j + j') affects the HPO problem.
2.2 How Reshuffling Affects the Loss Surface
We first investigate how different validation and reshuffling strategies affect the empirical loss surface
μ. In particular, we derive the limiting distribution of the sequence /n(p(()) ((),)) This limiting regime will not only reveal the effect of reshuffling on the loss surface, but also give us tractable setting to study HPO performance.
Theorem 2.1. Under regularity conditions stated in Appendix C.I, holds
(ī(ss) ( -
+N ~N(O in distribution,
where
T...M lim Eig (A,,M((A
Pr(s Im,i O (m)
nM2
8=1 m=
and
K(A;, lim Cov(En A.), A,),, (((( ElC(Z, (0(((29x(7)) (x))) 12000
where the expectation taken over a training set T of size n and two fresh samples Z, Z' from the same distribution.
The regularity conditions are rather mild and discussed further Appendix C.I. The kernel K reflects the (co-) variabilityy of the losses caused by validation samples. The contribution of training samples only has a higher-order effect. The validation scheme enters the distribution through the quantities T. In what follows, we compute explicit expressions for some popular examples. The following list provides formal definitions for the index sets Im.j-
(holdout) Let M 1 and Zi.; I₁ for all j 1, J, and some size- [am] index set I₁. iIi) (reshuffled holdout) Let M 1 and Z......, In,J be independently drawn from the uniform distribution over all size-[am] subsets from f1...., nn..
(iii) (M-fold CV) Let a = 1/M and I,...., Ias be disjoint partition of {1...., Im for all j = 1, J.
(......n) n), and Im. =
(iv) (reshuffled M-fold CV) Let a = 1/M and (I,j,.... I.a).jj = 1,....JJ J. be independently drawn from the uniform distribution over disjoint partitions of {l,..., nn..
(v) (M Mfld holdout) Let m ...... M, be independently drawn from the uniform distribution over size- an] subsets of [l..... n and set Im.i = Im for all m = I,..., M.j = I,....J. (vi) (reshuffled M-fold holdout) Let Zm m 1,.... M,j L,..., be independently drawn from the uniform distribution over size- [am] subsets of (1.....n).
The value of T...M for each example is computed explicitly in Appendix In all these examples, we in fact have
1 i i=j
TeJ.M = 7022 i i j.
for some method-ddeenddet parameters a, shown in Table 1. The parameter o² captures any increase variance caused by omitting an observation from the validation sets. The parameter quantifies potential decrease in correlation in the loss surface due reshuffling. More preciscly,
3

---

Table 1: Exemplary parametrizations in Equation (1) for resamplings; see Appendix for details.
Method
d²
2
holdout (HO)
1 1/a
reshuffled HO
1 1/a
M-fold CV
reshuffled M-fold CV
1
M-fold HO (subsampling Monte Carlo CV)
I 1+ (1 o)) /M
reshuffled M-fold HO
1 1+ (1 /a/Ma (1-
the observed losses ) ((}z) at distinct HPCs A * } become less correlated when 7 is small. Generally, increase in variance leads to worse generalization performance. The effect of correlation decrease is less obvious and is studied in detail in the following section.
We make the following observations about the differences between methods in Table 1:
M-fold CV incurs no increase in variance (o² = 1) and 1o because every HPC uses the same folds decrease in correlation. Interestingly, the correlation does not even decrease when reshuffling the folds. any case, all samples are used exactly once as validation and training instance. At least asymptotically, this leads the same behavior, and reshuffling should have almost no effect on M-fold CV.
The two (1-fold) holdout methods bear the same 1/a increase in variance. This is caused by only using fraction of the data validation samples. Reshuffled holdout also decreases the correlation parameter 72. In fact, if HPCs A; # X3 are evaluated on largely distinct samples, the validation losses 70( (x) and Ti(2,) become almost independent.
M-fold holdout also increases the variance, because some samples may still be omitted from validation sets. This increase much smaller for large M. Accordingly, the correlation is also decreased by less in the reshuffled variant.
2.3 How Reshuffling Affects HPO Performance
In practice, mainly interested in the performance of a model trained with the optimal HPC X. To simplify the analysis, we explore this in the large-sample regime derived in the previous section. Assume
m(A)) m(x;) + <(2))
where e(A) is zero-mean Gaussian process with covariance kernel
(((,)) x x>= X,
Cov(e(A), (² else.
Let A C RA: |А 1 with |A| = < oo be the set of hyperparameters, Theorem 2.2 ahead depends on several quantities characterizing
gives bound on the expected regret ()juAA)-(() the difficulty of the HPO problem. The constant
K(A,, - -(A,A)) IALIIII
K
sup
K(A, 2
can interpreted as a measure of correlation of the process e. In particular, eXX))) > 1 - xi| A A1112. The constant is small when is strongly correlated, and large otherwise. Further, define 77 as the minimal number such that any ball contained in ||] < 1} contains at least one element of A. It measures how densely the set of candidate HPCs A covers of all possible HPCs. If A is deterministic uniform grid, we have about J-1/d, Similarly, Lemma D.1 in the Appendix shows that S J-1/2d when randomly sampling HPCs. Finally, the constant
| A) (a(*))
= sup AeA
X 1

---

Loos Surface
Loss
-2
9.00
9.23
0.30
0.75
1.00
0.00
9.25
9.50
0.75
1.00
X
A
Type
tt-)
Emprical (r-b33)
Type
Empiical (r-0.3)
(a) High signal-to-noise ratio
(b) Low signal-to-noise ratio
Figure 1: Example of reshuffled empirical loss yielding a worse (left) and better (right) minimizer.
measures the local curvature at the minimum of the loss surface μ. Finding an HPC À close to the theoretical optimum A is easier when the minimum is more pronounced (large m). On the other hand, the regret ((() μ((*) ) also punishing mistakes more quickly. Defining log(x))
max(0, log(z)), we can now state our main result.
Theorem 2.2. Let P follow the Gaussian process model (2). Suppose & < co, 0 << o² Var[e(A)] s
o² < for all X E A, and m 0. Then
El m(x)) < ovdi8 B(7)--(7)]-
where
B(r) = 48 [1 V1 Vlog log +or T + 1og(3))) A(T) 10)=v1--1 (1))-v1- log 2mm?
The numeric constants result from several simplifications in worst-case analysis, which lowers their practical relevance. qualitative analysis of the bound is still insightful. The bound is increasing in and d, indicating that the HPO problem is harder when there is a lot of noise or there are many parameters to tune. The terms (T) and A(T) have conceptual interpretations:
The term B(r) quantifies how likely is to pick bad À because bad luck: a far away from A had such small c()) that it outweighs the increase in μ.. Such events more likely when the process is weakly correlated. Accordingly, B(T) is decreasing in r and increasing in K.
The term A(T) quantifies how likely it is to pick good Ā by luck: a close to X had such small e (A) that it overshoots all the other fluctuations. Also such events more likely when the process is weakly correlated. Accordingly. the term A(T) is decreasing in r.
The B, stated, is unbounded, but closer inspection of the proof shows that it is upper bounded by / Vlog J. This bound is attained only in the unrealistic scenario when the validation losses are essentially uncorrelated across all HPCs. The term A is bounded from below by zero, which is also the worst case because the term enters our regret bound with a negative sign.
Both A and B are decreasing in the reshuffling parameter There are two regimes. If a 7/2mm)² S then A(T) = and reshuffling cannot lead to an improvement of the bound. The term a mmn2 can be interpreted as noise-to-signa ratio (relative to the grid density). If the signal is much stronger than the noise, the HPO problem is so easy that reshuffling will not help. This situation is illustrated in Figure la.
on the other hand a a/mo?² > e, the terms A(T) and B(T) enter bound with opposing signs. This creates tension: reshuffling between HPCs increases B(r), which is countered by decrease in A(r). So which scenarios favor reshuffling? When the process is strongly correlated, small and reshuffling (decreasing 7) incurs high cost in (T)). This is intuitive: When there is strong
5

---

correlation, the validation loss surface ğ is essentially just a vertical shift of Finding the optimal then almost as easy as if we would know μr, and decorrelating the surface through reshuffling would make it unnecessarily hard. When is less correlated (x large) however, reshuffling does not hurt the term (7) as much, but we can reap all the benefits of increasing A(T). Here, the effect of reshuffling can be interpreted as hedging against the catastrophic case where all (i(A) close to the optimal X are simultancously dominated by a region of bad hyperparameters. This is illustrated in Figure lb.
3 Simulation Study
To test our theoretical understanding of the potential benefits of reshuffling resampling splits during HPO, we conduct a simulation study. This study helps us explore the effects of reshuffling in a controlled setting.
3.1 Design
We construct univariate quadratic loss surface function μ C RR m(- 0.5) which we want to minimize. The global minimum is given at (v(0.5 kernel for the noise process as in Equation (3), this allows us to simulate an objective as ob- served during HPO by sampling (A(A) =aA) + c()). We use a squared exponential kernel X') = o exp (-x(A /2) that is plugged into the covariance kernel of the noise process e in Equation (3). The parameters m and 6 in our simulation setup correspond exactly to the curva- ture and correlation constants from the previous sections. Recall that Theorem 2.2 states that the effect of reshuffling strongly depends on the curvature m of the loss surface μ (a larger m implies a stronger curvature) and the constant K as measure of correlation of the noise (a larger implies weaker correlation). Combined with the possibility to vary T in the covariance kernel of e, we can systematically investigate how curvature of the loss surface, correlation of the noise and the extent of reshuffling affect optimization performance. In each simulation run, we simulate the observed objective (()), identify the minimizer = arg minxe (A(),, and calculate its true risk, p(A). We repeat this process 10000 times for various combinations of T, m, and K.
Combined with
3.2 Results
Figure 2 visualizes the true risk of the configuration that minimizes the observed objective. We observe that for loss surface with low curvature (i.e., m S 2), reshuffling beneficial (lower values of 7 resulting in a better true risk of the configuration that optimizes the observed objective) as long as the noise process not too correlated (i.e., x 2 1). As soon as the noise process more strongly correlated, even flat valleys of the true risk μ remain clearly visible in the observed risk ğr, and reshuffling starts to hurt the optimization performance. Moving to scenarios of high curvature, the general relationship of m and к remains the same, but reshufiling starts to hurt optimization performance already with weaker correlation in the noise. In summary, the simulations show that in cases of low curvature of the loss surface, reshuffling (reducing 7) tends to improve the true risk of the optimized configuration, especially when the loss surface is flat (small m) and the noise is not strongly correlated (i.e., is large). This exactly confirms our theoretical predictions from the previous section.
4 Benchmark Experiments
In this section, we present benchmark experiments of real-world HPO problems where we investigate the effect of reshuffling resampling splits during HPO. First, we discuss the experimental setup. Second, we present results for HPO using random search (Bergstra & Bengio, 2012). Third, we also show the effect of reshuffling when applied in BO using HEBO (Cowen-Rivers et al., 2022) and SMAC3 (Lindauer et al., 2022). Recall that our theoretical insight suggests that 1) reshuffling might be beneficial during HPO and 2) holdout should be affected the most by reshuffling and other resamplings should only be affected to lesser extent.

---

m
m2
m=2
m:2
k:0.00
K:1
K24
1C 100
0.080
0.08
0.11
0.12
0.085
0.04
0.09
0.10
0.080
0.02
0.08
0.08
0.775
0.07
10
m:10 10
m: 10
m:10
k:0.04
Ic1
K:44
100
0.20
0275
0.15
0.16
0.500
0.10
0.25
0.05
0.18
0.000
0.00
0.175
0.0
0.20
0.200
0.15
0.15
0.175
0.27
0.10
0.10
0.150
0.24
0.125
0.05
0.00
0.100
Figure 2: Mean true risk (lower is better) of the configuration minimizing the observed objective systematically varied with respect to curvature m, correlation strength к of the noise (a larger implying weaker correlation), and extent reshuffling (lower 7 increasing reshuffling). A of indicates no reshuffling. Error bars represent standard errors.
4.1 Experimental Setup
As benchmark tasks, tabular datasets for binary classification. We suspect the effect of the resampling variant used and whether the resampling reshuffled to be larger for smaller datasets, where the variance of the validation loss estimator is naturally higher. Furthermore, from a practical perspective, this also ensures computational feasibility given the large number of HPO runs in our experiments. We systematically vary the learning algorithm, optimized performance metric, resampling method, whether the resampling is reshuffled, and the size of the dataset used for training and validation during HPO. Below, we outline the general experimental design and refer to Appendix F for details.
of standard HPO problems defined small- medium-sized
We used subset of the datasets defined by the AutoML benchmark (Gijsbers et al., 2024), treating these as data generating processes (DGPs; Hothorn et al., 2005). We only considered datasets with less than 100 features reduce the required computation time and required the number of observations to between 10000 and 1000000; for further details see Appendix F.1. Our aim was to robustly measure the generalization performance when varying the size n, which, as defined in Section denotes the size of the combined data for model selection, so one training and validation set combined. First, we sampled 5000 data points per dataset for robust assessment of the generalization error; these points are not used during HPO any way. Then, from the remaining points we sampled tasks with n E (500, 1000, 5000).
We selected CatBoost (Prokhorenkova et al., 2018) and XGBoost (Chen & Guestrin, 2016) for their state-of-the-ar performance tabular data (Grinsztajn et al., 2022; Borisov et al., 2022; McElfresh et al., 2023; Kohli et al., 2024). Additionally, we included an Elastic Net (Zou & Hastie, 2005) to represent linear baseline with smaller search space and funnel-shaped MLP (Zimmer al., 2021) as a cost-effective neural network baseline. We provide details regarding training pipelines and search spaces in Appendix F.2.
We conduct random search with 500 HPC evaluations for every resampling strategy we described in Table for both fixed and reshuffled splits. We always 80/20 wain-validation splits for holdout
7

---

Moan Performance
-0.84
-0.715
-0.67
-0.65
-0.720
-0.68
-0.06
-0.67
-0.69
-0.725
-0.68
-0.70
-0.730
1
100
200
300
400
500
100
200
300
400
500
100
200
300
400
500
No. HPC Evaluations
Reshufliig
Resampling
Holdout
5-
Figure 3: Average test performance (negative ROC AUC) of the incumbent for XGBoost on dataset albert for increasing n (train- validation sizes, columns). Shaded areas represent standard errors.
and 5-fold CVs, so that training set size (and negative estimation bias) are the same. Anytime test performance of an HPO run is assessed by re- re-training the current incumbent (i.e. the best HPC until the current HPO iteration based on validation performance) on all available train and validation data the outer test set. Note we do this for scientific evaluation in this
and evaluating its performance experiment; obviously, this not possible in practice. Using random search allows us to record various metrics and afterwards simulate optimizing for different ones, specifically, we recorded accuracy, area under the ROC curve (ROC AUC) and logloss.
We also investigated the effect of reshuffling on two state-of-the-art BO variants (Eggensperger et al., 2021: Turner et al., 2021), namely HEBO (Cowen-Rive) Rivers al., 2022) and SMAC3 (Lindauer et al., 2022). The experimental design was the same as for random search, except for the budget, which we reduced from 500 HPCs 250 HPCs, and only optimized ROC AUC.
4.2 Experimental Results
In the following, we focus on the results obtained using ROC AUC. We present aggregated results over different tasks, learning algorithms and replications to get general understanding of the effects. Unaggregated results and results involving accuracy and logloss can be found in Appendix G.
Results of Reshuffling Different Resamplings For each resampling (holdout, 5-fold holdout, 5-fold CV, and 5x 5-fold CV), we empirically analyze the effect of reshuffling train and validation splits during HPO.
In Figure 3 we exemplarily show how test performance develops over the course of HPO run on single task for different resamplings (with and without reshuffling). Naturally, test performance does necessarily increase in a monotonic fashion, and especially holdout without reshuffling tends to be unstable. Its reshuffled version results in substantially better test performance.
Next, look the relative improvement (compared to standard 5-fold CV, which we consider our baseline) with respect to lest ROC AUC performance of the incumbent over time in Figure 4, i.e., the difference in test performance of the incumbent between standard 5-fold CV and different resampling protocol; hence a positive difference tells us how much better test error we are, we would have chosen the other protocol instead 5-fold CV. We observe that reshuffling generally results in equal or better performance compared to the same resampling protocol without reshuffling, For 5-fold holdout and especially 5-fold CV and 5x 5-fold CV, reshuffling has a smaller effect on relative test performance improvement, as expected. Holdout is affected the most by reshuffling and results substantially better relative test performance compared standard holdout. We also observe that an HPO protocol based on reshuffled holdout results in similar final test performance as standard 5-fold CV while overall being substantially cheaper due to requiring less model fits per HPC evaluation. In Appendix G.2, we further provide an ablation study on the number of folds when using M-lold holdout, where we observed that in line with our theory - the more folds are used, the less reshuffling affects M-lold holdout.
8

---

0.5
0.25
0.0
0.00
Mcan Test
-0.5
-0.25
-1.0
-0.8
-0.50
-12
100
200
300
400
500
100
200
300
400
500
100
200
300
400
500
HPC Evaluations
Reshuffling
FALSE
Resampling
Holdout
Figure 4: Average improvement (compared to standard 5-fold CV) with respect to test performance (ROC AUC) of the incumbent over different tasks, learning algorithms and replications separately for increasing (train-validation sizes, columns), Shaded areas represent standard errors.
However, this general trend can vary for certain combinations of classifier and performance metric, see Appendix G. Especially for logloss, we observed that reshuffling rarely beneficial; see the discussion in Section 5. Finally, the different resamplings generally behave expected. The more we are willing to invest compute resources into a more intensive resampling like 5-fold CV or 5x 5-fold CV, the better the generalization performance of the final incumbent.
Results for BO and Reshuffling Figure 5 shows that, generally HEBO and SMAC3 outperform random search with respect generalization performance (i.e., comparing HEBO and SMAC3 to random search under standard holdout, or comparing under reshuffled holdout). More interestingly. HEBO, SMAC3 and random search all strongly benefit from reshuffling. Moreover, the performance gap between HEBO and random search but also SMAC3 and random search narrows when the resampling is reshuffled, which is an interesting finding of its own: As soon as we are concerned with generalization performance of HPO and not only investigate validation performance during optimization, the choice optimizer might have less impact on final generalization performance compared to other choices such as whether the resampling is reshuffled during HPO not. We present results for BO and reshuffling for different resamplings Appendix G.
500
1000
5000
Mean Test Imprreeeee
1.5
1.0
0.5
0.5
0.0
0.0
-0.5
150
250
100
250
100
200
No. HPC Evaluations
Optimizer
Random Search
HEBO
SMAC3
Reshuffling
FALSE
TRUE
Figure 5: Average improvement (compared to random search on standard holdout) with respect to test performance (ROC AUC) of the incumbent over tasks, learning algorithms and replications for different iaain-validttion sizes, columns). Shaded areas represent standard errors.
Discussion
In the previous sections, we have shown theoretically and empirically that reshuffling can enhance generalization performance of HPO. The main purpose of this article is to draw attention to this

---

surprising fact about a technique that is simple but rarely discussed. Our work goes beyond a preliminary experimental study on reshuffling (Lévesque, 2018), in that we also study the effect of reshuffling on random search, multiple metries and learning algorithms, and most importantly, for the first time, we provide theoretical analysis that explains why reshuffling can be beneficial.
Limitations To unveil the mechanisms underlying the reshuffling procedures, our theoretical analysis relies on an asymptotic approximation of the empirical loss surface. This allows us to operate on Gaussian loss surfaces, which exhibit convenient concentration and anti-concentratioo properties required in our proof. The latter are lacking for general distributions, which explains our asymptotic approach. The analysis was further facilitated by loss stability assumption regarding the learning algorithms that is generally rather mild; see the discussion in Bayle et al. (2020). However, it typically fails for highly sensitive losses, which has practical consequences. In fact, Figure in Appendix G shows that reshuffling usually hurts generalization for the logloss and small sample sizes. It is still an open question whether this problem be fixed by less naive implementations of the technique. Another limitation is our focus on generalization after search through a fixed, finite set of candidates. This largely ignores the dynamic nature of many HPO algorithms, which would greatly complicate our analysis. Finally, our experiments are limited in that we restricted ourselves to tabular data and binary classification and avoided extremely small or large datasets.
Relation to Overfitting The fact that generalization performance can decrease during HPO (or computational model selection general) sometimes known as oversearching, overtuning, or overfitting to the validation set (Quinlan & Cameron-Jones, 1995; Escalante et al., 2009; Koch et al., 2010; Igel, 2012; Bischl et al., 2023), but has arguably not been studied very thoroughly. Given recent theoretical (Feldman et al., 2019) and empirical (Purucker & Beel, 2023) findings, we expect less overtuning on multi-class datasets, making interesting to see how reshuffling would affect the generalization performance.
Several works suggest strategies to counteract this effect. First, LOOCVCV proposes a conservative choice of incumbents (Ng, 1997) at the cost of leave-one-out analysis or an additional hyperparameter. Second, it is possible to use an extra selection set (Igel, 2012: Lévesque, 2018; Mohr et al., 2018) at the cost of reduced training data, which was found to lead to reduced overall performance (Lévesque, 2018). Third, by using early stopping one can stop hyperparameter optimization before the generaliza- tion performance degrades again. This was so far demonstrated to be able to save compute budget at only marginally reduced performance, but also requires either a sensitivity hyperparameter or correct estimation of the variance of the generalization estimate and was only developed for cross-valle valsddaalooiion so far (Makarova et al., 2022). Reshuffling itself orthogonal to these proposals and a combination with the above-mentioned methods might result in further improvements.
Outlook Generally, the related literature detects overfitting to the validation set either visually (Ng, 1997) or by measuring it (Koch et al., 2010; Igel, 2012; Fabris & Freitas, 2019). Developing a unified formal definition of the generalization performance after many HPO iterations and how it relates to our measurements of the validation performance is an important direction for future work.
terms and thoroughly analyzing the effect of decreased
We further found, both theoretically and experimentally, that investing more resources when evaluating each HPC can result in better final HPO performance. To reduce the computational burden on HPO again, we suggest further investigating the use of adaptive CV techniques, proposed by Auto- WEKA (Thornton et al., 2013) or under the name Lazy Paired Hyperparameter Tuning (Zheng & Bilenko, 2013). Designing more advanced HPO algorithms exploiting the reshufiling effect should be a promising avenue for further research.
Acknowledgments and Disclosure of Funding
We thank Martin Binder and Florian Karl for helpful discussions. Lennart Schneider is supported by the Bavarian Ministry of Economic Affairs, Regional Development and Energy through the Center for Analytics Data Applications (ADACenter) within the framework of BAYERN DIGITAL II (20-3410-2-9-8). Lennart Schneider acknowledges funding from the LMU Mentoring Program of the Faculty of Mathematies, Informatics and Statistics.
10

---

References
Arlot, S. and Celisse, A. A survey of cross-validation procedures for model selection. Statistics Surveys, 4:40 - 79, 2010. B
Austern, M. and Zhou, W. Asymptoties of cross-validation. arXiv:2001.1111 [math.ST), 2020. C.1
Awad, N., Mallik, N., and Hutter, F. DEHB: Evolutionary hyberband for scalable, robust and efficient Hyperparameter Optimization. In Zhou, Z. (ed.), Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI'21) pp. 2147-2153, 2021.
Bayle, P., Bayle, A., Janson, L., and Mackey, L.
confidence intervals for test error. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M.-F., and Lin, H. (eds.), Proceedings of the 33rd International Conference on Advances in Neural Information Processing Systems (NeurlPS 200). pp. 16339-16350. Curran Associates, 2020. 5, C.I, C.I, C.1
Bergman, E., Purucker, L., and Hutter, F. Don't 't waste your time: Early stopping cross-validation. In Eggensperger, K., Garnett, R., Vanschoren, J., Lindauer, M., and Gardner, J. (eds.), Proceedings of the Third International Conference on Automated Machine Learning, volume 256 of Proceedings of Machine Learning Research, pp. 9/1-31. PMLR, 2024. B
Bergstra, J. and Bengio, Y. Random search for pypee--ar optimization. Journal of Machine Learning Research, 13:281-300 2012. 4, B
Bischl, B., Binder, M., Lang, M., Piclok. Richter, J., Coors, S., Thomas, Ullmann, T., Becker, M., Boulesteix, A., Deng, D., and Lindauer, M. Hyperparameter optimization: Foundations, algorithms, best practices, and open challenges. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, pp. e e1484, 2023. 1, B
Blum, A., Kalai, A., and Langford, J. Beating the hold-out: Bounds for k-fold and progressive wross-validttion. In Proceedings of the Twelfth Annual Conference on Computational Learning Theory, COLT '99, pp. 203-208, 1999. B
Borisov, V., Leemann, T., Seßler, K., Haug J., Pawelezyk, M., and Kasneci, G. Deep neural networks and tabular data: A survey, IEEE Transactions on Neural Networks and Learning Systems, pp. 1-21, 2022. 4.1
Bouckaert, Remcoand Frank, E. Evaluating the Replicability of Significance Tests for Comparing Learning Algorithms. In Dai, H., Srikant, R., and Zhang, C. (eds.), Advances in Knowledge Discovery and Data Mining, pp. 3-12. Springer, 2004. B
Bousquet, O. and Zhivotovskiy, N. Fast classification rates without standard margin assumptions. Information and Inference: A Journal of the IMA, 10(4):1389 1121111899441,,,,, 2021. C.1
Bouthillier, X., Delaunay, P., Bronzi, M., Trofimov, A., Nichyporuk, B., Szeto. J., Sepahvand, N. M., Raff, E., Madan, K., Voleti, V., Kahou, S. E.,, Michalski, V., Arbel, T., Pal, C., Varoquaux, G., and Vincent, P. Accounting for variance in machine learning benchmarks. In Smola, A., Dimakis, A., and Stoica, I. (eds.), Proceedings of Machine Learning and Systems 3, volume 3, pp. 747-769, 2021. B
Buczak, P., Groll, A., Pauly, M., Rehof, J., and Horn, D. Using sequential statistical tests for efficient hyperparameter tuning. ASIA Advances Statistical Analysis, 108(2):441-40) 2024.
Cawley, G. and Talbot, N. On Overfitting in Model Selection and Subsequent Selection Bias in Performance Evaluation. Journal of Machine Learning Research, 1 11:009-21077, 2010.
Chen, Т. and Guestrin, C. XGBoost: scalable tree boosting system. In Krishnapuram. B., Shah, M.. Smola. A., Aggarwal, C., Shen, D., and Rastogi, R. (eds.), Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 16), pp. 785-794. ACM Press, 2016. 4.1
Cowen-Rivers, A., Lyu, W., Tutunov, R., Wang, Z., Grosnit, A., Griffiths, R., Maraval, A., Jianye, H., Wang, J., Peters, J., and Ammar, H. HEBO: Pushing the limits of sample-efficient hyper-parameter optimisation. Journal of Artificial Intelligence Research, 74:1269-1349, 2022. 4, 4.1, B
11

---

Demšar, J. Statistical comparisons of classifiers over multiple data sets. Journal of Machine Learning Research, 7:1-30, 2006.
Dietterich, T. G. Approximate statistical tests for comparing supervised classification learning algorithms. Neural Compulation, 10(7):1955-1923 1998.
Dunias, Z., Van Calster, B., Timmerman, D., Boulesteix, A.-L., and van Smeden, M. comparison of hyperparameter tuning procedures for clinical prediction models: A simulation study. Statistics in Medicine, 43(6):1119 111--11111111,,, 2024. B
Eggensperger, K., Lindauer, M., Hoos, H., Hutter, F., and Leyton-Brown, K. Efficient benchmarking of algorithm configurators via model-based surrogates. Machine Learning, 107(():15-41, 2018.
Eggensperger, K., Lindauer, M., and Hutter, F. Pitfalls and best practices in algorithm configuration.
Journal of Artificial Intelligence Research, pp. 861-893, 2019. B
Eggensperger, K., Müller, P., Mallik, N., Feurer, M.. Sass, R., Klein, A., Awad, N., Lindauer, M., and Hutter, HPOBench: A collection of reproducible multi-fidelity benchmark problems for HPO. In Vanschoren, and Yeung, S. (eds.), Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks. Curran Associates, 2021, 4.1,
Escalante, H., Montes, M., and Sucar, Particle Swarm Model Selection. Journal of Machine Learning Research, 10:405-440, 2009.
Fabris, and Freitas, A. Analysing the overfit of the auto-sklearn automated machine learning tool. In Nicosia, G., Pardalos, P., Umeton, R., Giuffrida, G., and Sciacca, V. (eds.), Machine Learning, Optimization, and Data Science, volume 11943 of Lecture Notes Computer Science, pp. 508-520, 2019. 5
Falkner, S., Klein, A., and Hutter, BOHB: Robust and efficient Hyperparameter Optimization at scale. In Dy, J. and Krause, A. (eds.), Proceedings of the 35th International Conference on Machine Learning (ICML'I8) volume 80, pp. 1437-1446. Proceedings of Machine Learning Research, 2018. B
Feldman, V., Frostig, R., and Hardt, M. The advantages of multiple classes for reducing overfitting from test set reuse. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th Interna- fional Conference Machine Learning (ICML'19) 19), volume 97, pp. 1892-1900. Proceedings of Machine Learning Research, 2019. 5
Feurer, M. and Hutter, F. Hyperparameter Optimization. In Hutter, F., Kotthoff, L., and Vanschoren, (eds.), Automated Machine Learning: Methods, Systems, Challenges, chapter 1, pp. 38. Springer, 2019. Available for free at http://autonl: org/book. 1, B
Feurer, M., Eggensperger, K.,, Falkner, S., Lindauer, M., and Hutter, Auto-Skleam 2.0: Hands free automl via meta-learning- Journal of Machine Learning Research, 23(261):1-61, 2022. B
Garnett, R. Bayesian Optimization. Cambridge University Press, 2023.
Gijsbers, P., Bueno, M., Coors, S., LeDell, E., Poirier, S., Thomas, J., Bischl, B., and Vanschoren, J. AMLB: an automl benchmark. Journal of Machine Learning Research, 25(101):1-65, 2024. 4.1
Giné, E. and Nickl, R. Mathematical Foundations of InfiitteDimensioonal Statistical Models, vol- ume 40. Cambridge University Press, 2016. C.2
Grinsztajn, L., Oyallon, E., and Varoquaux, G. Why do tree-based models still outperform deep learning on typical tabular data? In Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks, pp. 507-520, 2022. 4.1
Guyon, I., Alamdari, A., Dror, G., and Buhmann, J. Performance prediction challenge. In The 2006 IEEE International Joint Conference Neural Network Proceedings, 2006. 1
Guyon, I., Saffari, A., Dror, G., and Cawley, G. Model selection: Beyond the Bayesian/Frequentist divide. Journal of Machine Learning Research, 11:61-87, 2010. B
12

---

Guyon, I., Bennett, K., Cawley, G., Escalante, H. J., Escalera, S., Ho, T. K., Macia, N., Ray, B.. Saced, M., Statnikov, A., and Viegas, Design of the 2015 ChaLearn AutoML challenge. In 2015 International Joint Conference on Neural Networks (IJCNN' 15), pp. 1-8. International Neural Network Society and IEEE Computational Intelligence Society, IEEE, 2015.
Guyon, I., Sun-Hosoya, L.. Boullé, M., Escalante, H., Escalera, S., Liu, Z., Jajetic, D., Ray, B., Saeed, M., Sebag, M., Statnikov, A., Tu, W., and Viegas, E. Analysis of the AutoMI. Challenge Series 2015-2018. In Hutter, F., Kotthoff, I.,, and Vanschoren, J. (eds.), Automated Machine Learning: Methods, Systems, Challenges, chapter 10, pp. 177-219. Springer, 2019. Available for free at http:// http:://attml...om org.omo..rg//oooooooo B
Hansen, N. and Ostermeier, A. Completely derandomized self-adaptation in evolution strategies. Evolutionary C., 9(2):199-195, 2001.
Hothorn, T., Leisch, F., Zeileis, A., and Hornik, K. The design and analysis of benchmark experiments.
Journal of Compulational and Graphical Statisticx, 14(3):675-699, 2005. 4.1, F.1
Igel, C. A note on generalization loss when evolving adaptive pattern recognition systems. IEEE Transactions Evolutionary Computation, (733):34-332,, 2012. 5,5
Jamieson, K. and Talwalkar, A. Non-stochastic best arm identification and Hyperparameter Op- timization. In Gretton, A. and Robert, C. (eds.), Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics (AISTATS' 166, volume 51, Proceedings of Machine Learning Research, 2016. B
Kadra, A., Janowski, M., Wistuba, M. and Grabocka, J. Scaling laws for hyperparameter optimization. In Oh, A., Naumann, T.,, Globerson, A., Saenko, K., Hardt, M., and Levine, S, Advances in Neural Information Processing Systems, volume 36, pp. 47527-47553, 2023. B
Kallenberg, O. Foundations of modern probability, volume Springer, 1997. D
Klein, A., Falkner, S., Bartels, S., Hennig, P., and Hutter, F. Fast Bayesian optimization of machine learning hyperparameters large datasets. In Singh, A. and Zhu, J. (eds.), Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics (AISTATS' 17), volume 54, Proceedings of Machine Learning Research, 2017. B
Koch, P., Konen, W., Flasch, O., and Bartz-Beielstein, Optimizing support vector machines for stormwater prediction. Technical Report TR10-2-007, Technische Universität Dortmund, 2010. Proceedings of Workshop on Experimental Methods for the Assessment of Computational Systems joint to PPSN2010. 5,
Kohli, R., Feurer, M., Bischl, B., Eggensperger, K., and Hutter, F. Towards quantifying the effect of datasets for benchmarking: A look at tabular machine learning. In Data-centric Machine Learning (DMLR) workshop at the International Conference Learning Representations (ICLR), 2024. 4.1
Lang, M., Kotthaus, H., Marwedel, P., Weihs, C., Rahnenführer, J., and Bischl, B. Automatic model selection for hign-dime survival analysis. Journal of Statistical Computation and Simulation, 85:62-76, 2015.
Larcher, C. and Barbosa, H. Evaluating models with dynamic sampling holdout auto-ml. SN Computer Science, 3(506), 2022.
Li, I.., Jamieson, K., DeSalvo, G., Rostamizadeh, A., and Talwalkar, Hyperband: A novel bandit-based approach to Hyperparameter Optimization. Journal of Machine Learning Research, 18(185):1-52, 2018. B
Lindauer, M., Eggensperger, K., Feurer, M., Biedenkapp, A., Deng, D., Benjamins, C., Ruhkopf, T. Sass, R., and Hutter, F. SMAC3: A versatile bayesian optimization package for Hyperparameter Optimization. Journal of Machine Learning Research, 23(54):1-9, 2022. 4, 4,1,1,11 B
Loshchilov, I. and Hutter, F. CMA-ES for Hyperparameter Optimization of deep neural networks. In International Conference on Learning Representations Workshop truck, 2016. Published online: iclr.co cc. B
13

---

Lévesque, J. Bayesian Hyperparameter Optimization: Overfitting. Ensembles and Conditional Spaces. PhD thesis, Université Laval, 2018. 1, 5,5
Makarova, A., Shen, H., Perrone, V., Klein, A., Faddoul, J., Krause, A., Seeger, M., and Archambeau, C. Automatic termination for hyperparameter optimization. In Guyon, I., Lindauer, M., van der Schaar, M., Hutter, F., and Garnett, R. (eds.), Proceedings of the First International Conference on Automated Machine Learning. Proceedings of Machine Learning Research, 2022. 5
Mallik, N., Bergman, E., Hvarfner, C., Stoll, D., Janowski, M., Lindauer, M., Nardi, L., and Hutter, F. PriorBand: Practical hyperparameter optimization in the age of deep learning. In Oh, A., Neumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Proceedings of the 36th International Conference on Advances in Neural Information Processing Systems (NeurIPS'23) Curran Associates, 2023. B
McElfresh, D., Khandagale, S., Valverde. J., Prasad C., V., Ramakrishnan, G., Goldblum, M., and White, C. When do neural nets outperform boosted trees on tabular data? In Oh, A., Neumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Proceedings of the 36th International Conference on Advances Neural Information Processing Systems (NeurIPS 23),, pp. 76336- 76369. Curran Associates, 2023. 4.1, F.2
Mohr, F., Wever, M., and Hüllermeier, E. ML-Plan: Automated machine learning via hierarchical planning. Machine Learning, 107 1e:::00):44911111 2018. 5, B
Molinaro, A., Simon, R., and Pfeiffer, R. Prediction error estimation: comparison of resampling methods. Bioinformatics, 21(15):3301-3300 2005. B
Nadeau, C. and Bengio, Y. Inference for the generalization error. In Solla, S., Leen, T., and Müller, K. (eds.), Proceedings of the 13th International Conference on Advances in Neural Information Processing Systems (NeurIPS'99), The MIT Press, 1999. 1
Nadeau, C. and Bengio, Y. Inference for the generalization error. Machine Learning, 52:239-22 2003. 1
Ng. A. Preventing ""vveffitiigg" of cross-validation data. In Fisher, D. H. (ed.), Proceedings of the Fourteenth International Conference on Machine Learning (ICML (97), pp. 245-253. Morgan Kaufmann Publishers, 1997. 5.5
Pfisterer, F., Schneider, L., Moosbauer, J., Binder, M., and Bischl, B. YAHPO Gym efficient multi-objective multi- multi-fidelity benchmark for hyperparameter optimization. In Guyon, I., Lindauer, M., van der Schaar, M., Hutter, F., and Garnett, R. (eds.), Proceedings of the First International Conference on Automated Machine Learning. Proceedings of Machine Learning Research, 2022. 5,5
Pineda Arango, S., Jomaa, H., Wistuba, M., and Grabocka, J. HPO-B: B: A large-scale reproducible benchmark for black-box box HPO based on OpenML. In Vanschoren, J. and Yeung, S. (eds.), Proceedings of the Neural Information Processing Systems Track Datasets and Benchmarks. Curran Associates, 2021. 5,5
Probst, P., Boulesteix, A., and Bischl, B. Tunability: Importance of hyperparameters of machine learning algorithms. Journal of Machine Learning Research, 20(53):1-32 2019.
Prokhorenkova, I.., Gusev, G., Vorobev, A., Dorogush, A., and Gulin, A. Catboost: Unbiased boosting with categorical features. In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. (eds.), Proceedings of the 31st International Conference Advances in Neural Information Processing Systems (NeurIPS' 18), pp. 6639-6649, Curran Associates, 2018. 4.1
Purucker, I.. and Beel, J. CMA-ES for post hoc ensembling in automl: great success and salvageable failure. In Faust, A., Garnett, R., White, C., Hutter, F., and Gardner, J. R. (eds.), Proceedings of the Second International Conference on Automated Machine Learning, volume 224 of Proceedings of Machine Learning Research, pp. 1/1-23. PMLR, 2023. 5
Quinlan, J. and Cameron-Jones, R. Oversearching and layered search in empirical learning. In Proceedings of the 14th International Joint Conference on Artificial Intelligence, volume 2 of IJCAI'95, 995, pp. 1019-1024 1995. 5
14

---

Rao, R.. Fung, G., and Rosales, R. On the dangers of cross-valliee validation. an experimental evaluation. In Proceedings of the 2008 SIAM International Conference on Data Mining (SDM), pp. 588-596, 2008. B
Salinas, D., Seeger, M., Klein, A., Perrone, V., Wistuba, M., and Archambeau, C. Syne Tune: A library for large scale hyperparameter tuning and reproducible research. In Guyon, I., Lindauer, M., van der Schaar, M., Hutter, F., and Garnett, R. (eds.), Proceedings of the First International Conference on Automated Machine Learning, pp. 16-1. Proceedings of Machine Learning Research, 2022. B
Schaffer, C. Selecting a classification method by cross-validation. Machine Learning Journal, 13: 135-143, 1993. B
Swersky, K., Snoek, J., and Adams, R. Freeze-thaw Bayesian optimization. arXiv:1406.388 [slats.ML.), 2014.
Talagrand, M. The generic chaining: upper and lower bounds of stochastic processes. Springer Science & Business Media, 2005. C.2
Thortoon, C., Hutter, F., Hoos, H., and Leyton-Brown K. Auto WEKA:: Combined selection and Hyperparameter Optimization classification algorithms. In Dhillon, I., Koren, Y., Ghani, R., Senator, T., Bradley, P., Parekh, R., He, J.. Grossman, R., and Uthurusamy, R. (eds.). The 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 13), pp. 847-855. ACM Press, 2013. 5,
Turner, R., Eriksson, D., McCourt, M., Kiili, J., Laaksonen, E., Xu, Z., and Guyon, I. Bayesian optimization superior random search for machine learning hyperparameter tuning: Analysis of the Black-Box Optimization Challenge 2020. In Escalante, H. and Hofmann, K. (eds.), Proceedings of the Neural Information Processing Systems Track Competition and Demonstration, pp. 3-26. Curran Associates, 2021. 4.1
van der Vaart, A. Asymptotic statistics, volume 3. Cambridge university press, 2000. C.I
van Erven, T., Grünwald, P., Mehta, N., Reid, M., and Williamson, R. Fast rates in statistical and online learning. Journal of Machine Learning Research, 16(54): 793-18611111111 2015. C.1
van Rijn, J. and Hutter, F. Hyperparameter importance across datasets. In Guo, Y. and Farooq, F. (eds.). Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 18), pp. 2367-2376, ACM Press, 2018. 1
Vanschoren, J., van Rijn, J., Bischl, B., and Torgo. L. OpenML: Networked science in machine learning. SIGKDD Explorations, 15(2):49-60) 60, 2014. 4
Wainer, J. and Cawley, G. Empirical Evaluation Resampling Procedures for Optimising SVM Hyperparameters. Journal of Machine Learning Research, 18:1-35, 2017. B
Wainwright, M. High- biigh-dimessonal statistics: A non-asymptotic viewpoint, volume 48. Cambridge university press, 2019. C.2
Wistuba, M., Schilling, N., and Schmidt-Thieme, L. Scalable Gaussian -based transfer surrogates for Hyperparameter Optimization. Machine Learning, 107(1):43-78, 2018. G.I
Wu, J., Toscano- Palmerin, S., Frazier, P., and Wilson, A. Practical multi-fidelity Bayesian optimization for byperparameter tuning. In Peters, J. and Sontag, D. (eds.), Proceedings of The 36th Uncertainty in Artificial Intelligence Conference (UAT'20), pp. 788-798. PMLR, 2020.
Zheng, A. and Bilenko, M. Lazy paired
tuning. In Rossi, F. (ed.), Proceedings of the rdd International Joint Conference on Artificial Intelligence (IJCAI'13) pp. 1924-1931, 2013. 5, B
Zimmer, L., Lindauer, M., and Hutter, F. Auto-Pytorch: Multi-fidelity metalcarning for efficient and robust AutoDL. IEEE Transactions on Pattern Analysis and Machine Intelligence, 43:3079-3090, 2021. 4.1, F.2
Zou, H. and Hastie, Regularization and variable selection via the elastic net. Journal of the Royal Statistical Society Series B: Statistical Methodology, 67(2):301-3)) 2005. 4.1
15

---

A
Notation
Table Notation table. We discuss all symbols used in the main paper.
X;
Random vector, describing the features
Random variable, deseribing target
2,
(X,, XO
Data point
(2/15=1
Dataset consisting
variables
Number of observations
Inducer/ML Inducer/MLalgorrihmm algorithm
Model, created by the inducer via A (D
Hyperparameter configuration
Finite sct of hyperparameter configurations
[A], i... the number of ht hyperparameter configurations
9A
Iyperpurametetiieel inducer
((A)
Expected
hyperpaaamteriiedl inducer on distribution dataset
((Z,))
Loss of model h on fresh observation Z Number of folds in M-fold cross-validation
Percentage of samples be used for validation
T1.j IMus C f1..... n)
M sets of validation indices, to be used evalanting A3
Ven
Validation data for fold and confi confi guration A Truining data for foold mn and configuration A Validation for fold
Tmm
L(Vm 3: Bx, (Tm.a))
configuration A
P(A))
M-lold validation loss
Increase variance validation loss caused by resampling
Decrense in correlation among validation losses caused by reshuffling Resampling-relan related component validation
covariance
KG.))
Kemnel capturing the covariance of the pointwise losses between two HPCss
((A))
Zero-mean mean Goussian process, see Equation (2)
Number of hyperparamcters
Curvature constant of covariance kernel
Density typerpurameter
Local curvature at the minimum of the loss surface noise level
Lower bound
B(T)
Part of the regret bound penalizing reshuflling
A(r)
Part of the regret bound rewarding reshuffling
B Extended Related Work
Due to the black box nature of the HPO problem (Feurer & Hutter, 2019; Bischl et al., 2023), gradient free, zeroth-order optimization algorithms such as BO (Garnett, 2023), Evolutionary Strate- gies (Loshchilov & Hutter, 2016) or simple random search (Bergstra & Bengio, 2012) have become standard optimization algorithms to tackle vanilla HPO problems.
In the last decade, most research on HPO has been concerned with constructing new algorithms that excel finding configurations with low estimated generalization error. Examples include BO variants such as as HEBO (Cowen- Rivers et al.. 2022) or SMAC3 (Lindauer et al., 2022). Another direction HPO research has been concerned with speeding up the HPO process allow more efficient spending of compute resources. Multifidelity HPO, for example, turns the black box optimization problem into a gray box one by making use of lower fidelity approximations to the target function, i.e., using fewer numbers of epochs or subsets of the data for cheap low-fidelity evaluations that approximate the costly high-fidelity evaluation. Examples include bandit- budget allocation algorithms such as Successive Halving (Jamieson & Talwalkar, 2016), Hyperband (Li et al., 2018) and their extensions that use non-random search mechanisms (Falkner et al., 2018: Awad et al., 2021; Mallik et al., 2023) or algorithms making use of multi-fidelity information in the context of BO (Swersky et al., 2014; Klein et al., 2017: Wu et al., 2020; Kadra et al., 2023). Several works address the problem of speeding up cross-validation techniques and use techniques that could be described as grey box optimization techniques. Besides the ones mentioned in the main paper (Thornton et al., 2013; Zheng & Bilenko, 2013), it is possible to employ racing techniques for model selection in machine learning as demonstrated by Lang et al. (2015), and there has been a recent interest in methods that adapt the cost of running full voos-vaaliation procedures (Bergman al., 2024; Buczak et al., 2024).
When addressing the problem of HPO, we must acknowledge an inherent mismatch between the explicit objective we optimize namely, the estimated generalization performance of model and the actual implicit optimization goal, which is to identify configuration that yields the best
16

---

generalization performance on new, unseen data. Typically, evaluations and comparisons of different HPO algorithms focus exclusively on the final best validation performance (i.e., the objective that is directly optimized), even though an unbiased estimate of performance on external unseen test set might be available. While this approach is logical for assessing the efficacy of an optimization algorithm based on the metric it seeks to improve, relying solely on finding an optimal validation configuration is beneficial only if there is reason to assume a strong correlation between the optimized validation performance and true generalization ability on new, unseen test data. This discrepancy can be found deeply within the HPO community, where the evaluation of HPO algorithms on standard benchmark libraries is usually done solely with respect to the validation performance (Eggensperger et al., 2021; Pineda Arango et al., 2021; Salinas et al., 2022; Pfisterer et al., 2022). 5 This relationship between validation performance (i.e., the estimated generalization enror derived from resampling) and true generalization performance (e.g., assessed through an outer holdout test set or additional resampling) of optimal validation configuration found during HPO remains largely unexplored area of research.
In general, little research has focused on the selection of resampling types, let alone the automated selection of resampling types (Guyon et al., 2010; Feurer et al., 2022). While we usually expect that a more intensive resampling will reduce the variance of the estimated generalization error and thereby improve the (rank) correlation between optimized validation and unbiased outer test performance within HPCs, this benefit is naturally offset by higher computational expense. Overall, there is little research on which resampling method to use in practice for model selection, and we only know of a study for support vector machines (Wainer & Cawley, 2017), simulation study for clinical prediction models (Dunias et al., 2024), a study on feature selection (Molinaro et al., 2005) and a study on fast CV (Bergman et al., 2024). In addition, ML-Plan (Mohr et al., 2018) proposed a two-stage procedure. In a first stage (search), the tool uses planning on hierarchical task networks to find promising machine learning pipelines on 70% of the training data. In a second step (selection), it uses 100% of the training data and retrains the most promising candidates from the search step. Finally, it uses combination of the internal generalization error estimation that was used during search and the 0.75 percentile of the generalization error estimation from the selection step to make a more unbiased selection of the final model. The paper found that this improves performance over using only regular cross-valide cooss-valiattion for search and selection. The general consensus, that is in agreement with our findings, is that CV or repeated CV generally leads to better generalization performance. In addition, while there are theoretical works that compare the accuracy of estimating the generalization error of holdout and CV (Blum et al., 1999), our goals is to correctly identify a single solution, which generalizes well, see the excellent survey by Arlot & Celisse (2010) for a discussion on this topic.
Bouthillier et al. (2021) studied the sources of variance in machine learning experiments, and find that the split into training and test data has the largest impact. Consequently, they suggest to reshuffle the data prior to splitting into the training, which is then used for HPO, and the test set. We followed their suggestion when designing our experiments and draw new test sample for every replication, see Section 4.1 and Appendix This dependence on the exact split was further already discussed in the context of how much the outcome of a statistical test on results of machine learning experiments depended on the exact train-test split (Bouckaert, 2004).
Finally, the first warning against comparing too many hypothesis using cross-validation was raised by Schaffer (1993), and in addition to the works discussed in Section 5 in the main paper, also picked up by Rao et al. (2008); Cawley& & Talbot (2010). Moreover, the problem of finding a correct "upper objective" in bilevel optimization problem has been noted (Guyon et al., 2010, 2015, 2019). Also, in the related field of algorithm configuration the problem has been identified (Eggensperger et al., 2019).
B.1 Current Treatment of Resamplings in HPO Libraries and Software
In Table 3. we provide a brief summary of how resampling is handled in popular HPO libraries and software." For each library, we checked whether the core functionality, examples, or tutorials mention
'We admit that these benchmark libraries implement efficient benchmarking methods such as surro- gate (Eggensperger al., 2018, Pfisterer et al., 2022) tabular benchmarks (Pineda Arango et al., 2021). would be possible to adapt them to return the test performance, however, changes in the HPO evaluation protocol, such as the one we propose, would not he feasible.
'This summary is not exhaustive but reflects the general consensus observed in widely- software.
17

---

the possibility of reshuffling the resampling during HPO or if the resampling is considered fixed. If reshufiling is used in an example, mentioned, or if core functionality uses it, we mark it with /. If it is unclear or inconsistent across examples and core functionality, we mark it with a ? Otherwise, we use a X. Our conclusion is that the concept of reshuffling resampling generally receives little attention.
Table 3: Exemplary Treatment of Resamplings in HPO Libraries and Software
Software
Reshufiled?
Reference(s)
sklearn
GridSearchCV/ RandomizedSSerchhy
HEBO
X
sklearn, "elearn_tuner"
optuna
?
Inconsistency between examples
bayesian-opimmization
X
sklearn Example 7.8
ax
CNN Example
spearmint
X
No official HPO Examples
scikit-optimize
X
BO for GBT Example 7.10
SMAC3
SVM Example 7.11
dragonfly
Tree Based Ensemble Example
aws sagemaker
X
Blog P3st
raytune
?
Inconsistency between examples 1415
hy eoperopt(-sllaamp
Cost Function Logic
X: reshulling, both reshulling and no reshuflling or unclesr. /: redhulliing
attps://gitae con/sciks Learn/scikis wtwp:///.oo///1110111120221 wtt.aee22222ettteeeee adee e633 carn/a odul ael.alaliioo Lswarch. 4L1222
3 httpa://githuh consseikkt.-----... wasnn-///////eee t-- Tawr http://aaee////222555551aaaaaaa 5f addedd8eedee warn/n
odel_pelectie www.eceooo//ccco _ewarehee_cccco pyPl1661
httge://gt thub. huwwww mowh/ /FBB// 10
B9Cddda441 1a /HRRO/ hwbo/ wil warn.
uner- py4775
httpa://githan coa/oppuna/ /optuna- integrati wosestoo///baaa http///l///eeeeeeeeeaaaa 2w722 8478:36257
/optuna. tegratii on/ on/.ooie/eetene /etttarra//////a///aaa sklearn, pyst2223 here skleam's s croce_ ralidate used which by de defuult does not resbutile the resampling
//gg//ttaat con/ aww.ttiittiii t- leare//rr//e catarr//cckkie acikit- Tears /blb// 2llob//7222ee 11w222225551111222222 I Dea aud 663c // earuu
odel. wwt.s/elloocccccoooo wwwlidationn, py8L188
httpe: //gtthub. con/ con//ptuse tomaa////////////// optuna- -stamplee Lee/ btlbb//dd//ae/////e
a0 dudl c 16d0 ooytorchh/ chrchhpp torch..st strple ppyll.77 here, data londers for train and valid are instantisted within the objective of the trial but the data within the loaders fixed
httpp://gittub. cww./ooo///aaae /wtp//ptu/////a ooptuna- examples les// ottb///bbeseee02ee in 6 aeseesieee cedd of ct tidis /tg.oott////ooooooooooooooo /xggho nxt immmpl ee -pyl1.22 here, the miin valisttion split is performed wi within the ohjeerive of the trial and no seed set w hich results in con/ ocaket learn/ /cciitt learn/ /b/ 27 2450 11 de 220r Paaddd 6C3e klearn/ ceorr///oeel.... seeee___..eetton.. ssp 1y5125977
reshuilling https://gitbun
fanctionality relies on skleam's crose, val, scoze which by default does not reshuiile the resampling ba hpe huub. cocl/ scclee t- --aaaa/ acili bettt-leann/te /ole//boo/// /878//45211111 sdw2/225 5I DaaSt add ded444433333 all aadde aul ion/ ida
on. py41631
https://es //gtthub. con/ bn an- opsint zat wttp/eeesssnngggeeeeeeeee t www.pppppttmmmmmtoooomoomommm on/ blob/ http://ccccccceeeeee/ www. 9000 29e edde meneppe
enmppe le py91.32
hitga thub con/ Tacebook/ /t/////l//ll 5881 waw.aaa000000000a0000000 4w2
4 tu tut ialaa Lunn coun,
ce. tpybba hetge //g thsb con/t ncebools/
a/ /tsstoria inl ott 1a py 154
he ppa / thub. aadi opt /accliliee biciiit optini /boo// (223664403332240 333.0333333331111331133333331131 445004 44423432/4 axples/ httpp//pppprarreereeeeee
optinization py gy9222221 L82036
hetpes/ / t/ubb con/autonn /SM/C// Lob/ Setaeeeeeeaaaeeeeeeeeeeee 731 457 w00.e000 eeaepp Lee /1, baw 2e.
cue py
he spa / /gi thub. con/ con/dragon Ca (drggno /bllb/ Beat B 230 2221 w240
eg/ saltaeetree pyslis1
horpe: //are, anazon, con/ bi blogg/ /wt.//atetttrreeeeeaaaaoaeaaaaee htwuure//teelee eld- notes- brs cross- wall rallddate dat machine- Learning mod el- pipeline- at- scale
sagesakez/
his spa /g shub. con/ pay-pro /ect/eay/ hal///o//// /31 155555556442aaa 12447 www.w/ddwwwwwessddddedd 181555511111111 22 /sou//uuuur Lune/ waza xpl en/ /uuee pytarch- citar pypoooi 120 here, data londers for train and valid are instamiaatd within the objective but the data
laaders fined
15 pespp: //ghthbb. con/ray- project/ http///a////////beeeeeteeeeeett /ttob///aaabccee22eee dPddd
291 /tc///ureee///eeo/o///oo///e cource/ tumne/ exxe rpl ht//ttmn-aae agboost. 1pynbel here, the train validation split is performed within the objective and no seed is set which results in reshuffling he buttge/// //gi thib con /ac ikit- bwwn/sccki warn / oh/ 94555 1 idw 1S 3edd /ekleerr//ne htt.///eeeeeeeeeeeeeeeeeeeeeeeee as acrpo: / /gggt/g..bbboo...............b con/ http//pppppp/toooooooooooo stsperopt/aypproppp /hyperppt sklearz /ttbb//////// http///bt///////eeeeeee /Bt.///b22666777608 7abbr www.222dddddda (B 2996639 httpt//ppllaaaa
Leplit Ly182
Featisation /or/ i_ pys.144
raadom seed which by defanlt
there discussion reshuttling
behavsoc somewhat unclear
18

---

C Proofs of the Main Results
C.1 Proof of Theorem 2.1
We impose stability assumptions on the learning algorithm similar to Bayle et al. (2020); Austern & Zhou (2020). Let Z, Z1,...; Zn Zí be iid random variables. Define T [Z ) and 'T' 'T
but with 2n replaced by the independent copy z Define
(z A) = ((z, (T) (le((Z.x(T)) [7),
assume that each 9x(T) is invariant to the ordering in T, É bounded, and
max AEλ
[[(
i (Z = =(1/n).
(4)
This loss stability assumption is rather mild, see Bayle et al. (2020) for an extensive discussion. Further, define the risk R(g) = E(e(Z,9) and assume that for every X E A, there is prediction rule 9 such that
max E [ (()x R( o(1/vl))
This assumption requires (T) converge to some fixed prediction rule sufficiently fast and serves as reasonable working condition for our purposes. satisfied, for example, when é the square loss and d사 is an empirical risk minimizer over hypothesis class 9x with finite VC-dimension. For further examples, see, e.g., Bousquet Zhivotovskiy (2021), van Erven et al. (2015), and references therein. The assumption could be relaxed, but this would lead to a more complicated limiting distribution but with the same essential interpretation.
Theorem C.1. Under assumptions (4) and (5), it holds
vn (f())) 1 ((2))) -a
where
Eg. = T.J.M
lim CoviCn (2, (2)), R-000
Tis',M = lim 22
Pr(i E Immij O Imme ):).
(=1 m==mm m'=1
Proof. Define
m(A,)) M Σ ELL(Ym.. 9x, (Tm.)) [m..l.
By the triangle inequality (first and second step), Jensen's inequality (third step), and (5) (last step).
[(()((,)) - ((x))1
< max EE
LELL(V m...: 9A, (Tm.))) Tmul - (E[L(V 9A, (Tml))]]]
15 1.mmah M
EEL [[ (Vmm.i 92, (Tm.s)) Tm. ELL m. 92, [1]
max SmS M
E
+ max
E
E[L(V m. 92, (Tm.))) E[L(Vm..j m. 92
92, )1]
M
< 2 max
E
E E[L(V m. 22, (Tm.)) Tm..j] E[I(Ym.. (x,,1
M
Riga, (Tma)) - R(g2,) }
2 max
M
= =(1/Vm)
Next, assumption (4) together with Theorem and Proposition 3 of Bayle et al. (2020) yield
(T( -0(1))())))))))))))))))))))
1
Σ i, 21) -,p 0.
M
avn
VEIm..
19

---

Now rewrite
M Σ Σ (z)
M 1(i E I (n
Mayn m=liETm.
May n
1=1 m=1
The sequence (Ei,n) = (Sim)..... 20 triangular array of independent, centered, and bounded random vectors. Because (Z; E V) and Z, are independent, holds
M
M
Cov(E c(()) Sin
Ei E Im n nIm' (1,
m=1
m'=1
e(''
lim Cov
Mayn 1=1
Stnt Mayn
lim n-o
nM2a2
Cov
S Si.n
Ejs
Now the result follows from Lindeberg's central limit theorem for triangular arrays (e.g., van der Vaart, 2000, Proposition 2.27).
C.2 Proof of Theorem 2.2
We want to bound the probability that u(²) (xX*) is large. For some d >> 0, define the set of 'good' hyperparameters
As {Ay: m())) - (u(*) 53.
Now
Pr (2(2) -M(A))) > 0) Pr (A $ As)
Pr
min (a(A) < min (((A)
AgAs
XEa,
$ Pr
min ((A) < min
1(2))
AgAs
xEAs/2
Pr
min ((A) E(A)
min u(A) c(A) XEAay2
AgAs
Pr
8 min e(>) < 8/2
min <(A))
AgA
xEAs/2
Pr
min <(A)
min <(2) < -8/2
AgAo
XEAs/2
Pr
max c(A) AgAa
max <()) > 8/2 ΛEA1/2
(c _ -c)
There is tension between the two maxima. The more A's there are in A8/2 and the less they correlated, the more likely it is to find one e(X) that is large. This makes the probability small. However, the less c is correlated, the larger is max c(A), making the probability large. To formalize this, use the Gaussian concentration inequality (Talagrand, 2005, Lemma 2.1.3):
Pr
max E(A) AgAs
max <(A) 5/2 XEAg/2
< Pr 2 max maxx(A) - E
max maxe(A) c(A) AEA
> >5/2 - E
max E(A)
+ +E
max c(A))
AEA
XEAs12
AgA
(8/2 - E.. maxxExA92
((2)
[maxAÇas ((A))) 2)
eexp
802
provided 6/2- E maxxEAs52 E(A)) +E mmaxagas e(A)] 2 0. We bound the two maxima separately.
20

---

Lower Bound for Maximum over the Good Set
Recall the definition of m right before Theorem 2.2 and observe
A8/2 = (A: (()) - (=)*) ) = 8/2) > {A: m ml|
X 1 - 6/2) = (A: || X - (6/2m)2/23 [Xx (6 16/2m)
Pack the ball B(X", (6/2m))1/2 with smaller balls with radius We can always construct such packing with at least (6) /22mm)2)d/2 elements. By assumption, each small ball contains at least one element of A. Pick one element from each small ball and collect them into the set A//2- By construction, //2 2 (6/2mn2) and
min AEXE
A
X
2 17.
Sudakov's minoration principle (e.g., Wainwright, 2019, Theorem 5.30) gives
IF
max XEAs/2
{(2)
2 2V
V
log 6/22
(A#X)
min
Var (c(A) c(x)]
1
2
log |1//21
min -
V
||A~X1122
In general,
Var (c()) -(())
=) + K(X,, X - -2-
-1- ( + ((X. + P(K(A,))
K(A,\))
21 79).
Hence, we have
min X-
Var (EA) <(\)) 2 (1
which implies
E max AEA3/2
E( (2))
Favav1- 1- 2mm))) =: oVd((T,6))2
Upper Bound for Maximum over the Bad Set
Dudley's ' entropy bound (e.g., Giné & Nickl, 2016, Theorem 2.3.6) gives
Lo0 Vlog N(s)ds,
E
max (2)
11
where (s) is the minimum number of points Bi....,ANG,, such that
sup min ISkEN)))
Var (c(A) c (Ax) s..
Note that
sup A.EA
(Vrr(((A)
(E(A) - c(X') < 20,
so (ss) = for all > 2o. For 82 < 40 - 72), we can use the trivial bound N(s) < J. For 8² > 40 - 72), cover with fz-balls of size (s/20Tx). We can do this with less than
N(s) S (60x/s) s)a v such balls. Let AI,...,AN be the centers of these balls. In general, it holds Var - -e(X']
K(>, A) + K(X',,,AA X) - 272 X)
(1 (1--7)] (1_ K(X) -U--K--XX-X---KKKKKAKA---------- -(AXX))) -
s 2(1 7²)0² +
X112.
21

---

For s2 > (?),, we thus have
sup min Var ( [s)]
-
sup
Var (c()) =(\))
A (g
||A-X ====\/
$ 2(1 70)0² 2 ( (s/2ToN)
as desired. Now decompose the integral
2011-72
2a
log -
log N(s)ds +
log (s)ds
20V1- 20
12V1og -
VloddSs)dss.
20v1-72
For the second term, compute
20
S Vd f 20
Vlog(Bon:/s+dd ds
JVVIT
20V1-72
= =vd 1
(og((6r/s)) ds
2VT-T2
sovd (f, log(6x/s)+ ds
1/2
(2(1 V1 v1--2)) -2)) 1/2
2(( v1 [[]-))) 1/2
=ovd 2 + 2 10gg
-20V0 log log(3x)
+ v1 - 73)1/2
220VdT/1+ Log(3)))
We have shown that
E max e( (2))
< 24od /1 - 72 Voloo + +TVL + log(3x)+ =: oVdd((r)/4.
AgAs
Integrating Probabilities
Summarizing the two previous steps, we have
(b-ovd[B(r) A(T,
Pr ( - 2) S 2exp
3602
provided t 2 ovd(B(T) - A(T, Now for any 2 0 and
> 2 mnj it holds
A(T,8) (o10)
In partieular, if
t 2 2 mnj - A(T)s) =: C,
we have
-(-
Pr (x(2) m(X') > >6) < 4exp
3602
22

---

Integrating the probability gives
Ela(A) u(>*) / Pr (M(2) - -m(x' >6) 6)d8 d8
Pr (u(2) - -1(2)> (0)))6)))) d8 + [0
10
Pr (1(2) (((a)) > 6) d8
(o-ova[(() A(T)s)
$ C exp
dd
3602
< C' + v36o
2e mnj + +oVd(B(T) A(r)s] + 60.
Simplifying
The bound can be optimized with respect to but the solution involves the Lambert W -funcction, which has no analytical expression. Instead choose for simplicity as
log
2mn?
which gives
Elp(A) ((A') 8 B()) A(ryy log
2rminj
D Additional Results on the Density of Random HPC Grids
Lemma D.1. Suppose that the J elements in A are drawn independently from a continuous density with mingalis p(A) > 0. Then with probability at least 8,
x (Vlog(1/0)/3) 1/d
and with probability
7 (Vlog())/J)" 1/4
1/4
for all J sufficiently large.
Proof. We want to bound the probability that there is a À such that B(, 17) n| = follows À is silently understood to have norm bounded by 1. Let A A....., AN the centers of 1/2--blls covering { {|A] s 1}, for which we may assume N < (6/n) For A the closest center A, it holds
In what
X
\ll < XX X + A Al
s |X'
54ll n/2,
so | Xull S 1/22 implies
| A|| < 7.
We thus have
Pr(3A: B(A, A| = 0) = Pr
inf
1(Ia: - -1
i=1
< Pr
min
Σ
Rol / 50
ISKSN
2m
23

---

Further
Pr
min ISKSN
1[1A: > S n/22 = =0)
[[|A, - Rxll >x / /n/22 20 0)
Pr
max ISKEN
Pr
max ISKSN 1=1
E [IAA s/ /3/23] -111 Aoll S m/22 E All S /n/22)
holds
n/2 Pr (1IA; ^l 5n/2) f1x- /1X--MIS0/2 p(X))X 2 (v0.((((0n)22))
E [ ^||
ccu(ln/2)
where Uy = vol(B(0, 1)).
Now the union bound and Hoeffding's inequality give
Jc
Pr
min ISK N
x n/2) s =0)
s N exxp
2
S (6/n)) exp ( (
Choosing
1/d
(V2log(33 (olog(3//Jeva/0///oo
17
gives
Pr(3A: [B(A 11 0 = 0) S 5/v 2 2lgg(3d 2log((3VJJer)))
which is bounded by 8 when VJ 2 e// ///2///cu.. Further, setting 17 2( (Vooo gives
Pr
min ISRN
Σ
1[1A dell s 1n/23 00 5-5
so that
8
Σ
Pr
min
min
1[1 S $0
15J5J
ISKSN
J=1
1=1
E - -xal < 50
<
JPr
min
ISKSN 1=1
J=1
00
2
00.
J3/2
J=1
Now the Borel-Cantell. lemma (e.g., Kallenberg, 1997. Theorem 4.18) implies that, with probability
1,
B(A, m) n A 1,
for all J sufficiently large.
24

---

E Selected Validation Schemes
E.1
Definition of Index Sets
Recall:
(holdout) Let M and Σı, I, for all j = 1, 1.....,J, J, and some size-fan) index set IT. iii) (reshuffled holdout) Let M 1 and Ii......, In, be independently drawn from the uniform distribution over all size-[an] subsets from (I....,7)) n)..
(iii) (M-foll CV) Let = 1/M and II..... Ias be disjoint partition of {I...., n). and Im. Im for all j I.....JJ
(iv) (reshuffled M-fold CV) Let a = 1/M and (Iz.j...... IM.)).j = l.....JJ J. independently drawn from the uniform distribution over disjoint partitions of [1)...,n.. nn.
(v) (M-fold holdout) Im. m7 1, M, be independently drawn from the uniform distribution over size- an] subsets of (1...., n and Im..j Im for m 1..... M. l.....J.
(vi) (reshuffled M-fold holdout) Let Im..j 1, ...... M, I..... J, be independently drawn from the uniform distribution over size- [am] subsets of nn........ n).
E,2 Derivation of Reshuffling Parameters Limiting Distribution
Recall
M ΣΣΣ Pr(s E Immii O (mmm g)).
M
T.J.M
nm
s=1 --1m=lm's
For all schemes in the proposition, the probabilities are independent of the index s, so the average over 1, ,,..., can be omitted. We now verify the constants r from Table 1.
ii holds
Pr(s E I,, (Zz.j) = Pr(s E IT) a.
Hence,
TE.. = 1 x 1=
x 7
(ii) (reshuffled holdout) This is a special case of part (vi) with M 1.
iiii) (M-fold CV) holds
11/M,
m m
Pr(s Im IIm's) J) Pr(s Im Imm)
0,
m + m'
Only M probabilities in the double non-zero, whence
= T.J.M M2 x M/M = x2
where we used = 1/M. (iv) (reshuffled M-fold CV) It holds
1/M,
ml j m # ml i j m = ml m ii m + m'
0,
Pr(s Immit O I)
1/M2,
1/M2,
For j. only M probabilities in the double sum are non-zero. Also using a = 1/M, we get
T.J.M = M2a² x M 1/M=1=0-
For }
1
M 1/M² = 1
J.
22
25

---

(v) (M-foll holdout) It holds
a.
m m',
Pr(s E Imn (Im' Pr(s E Im (Imm)
a²
else.
This gives
T.J.M M Mxxx (M x a² |1/aM (M x (M-
for all i,j.
(vi) (reshuffled M-fold holdout) It holds
a, m=m'ii=
Pr(s E Impa O Im'm
a² else.
For = j. this gives
1
IMx++ (M 1M x 1/aM (M 1)/M.
TRJ.M
M2
Fori *
1
T.J.M M20² x (M² x a²)=
This implies that (1) holds with o² - 11MM + C0M-1//,11 1//1/Ma> + (M -M 1)/M),
Remark E.1. Although not technically covered by Theorem 2.1, performing independent bootstraps for each Xj correspond reshuffled n-fold holdout with 1/n. Accordingly, v2 and 1/2.
F
Details Regarding Benchmark Experiments
F1 Datasets
We list all datasets used in the benchmark experiments in Table 4.
Table 4:
List of datasets used in benchmark experiments. OpenML. (Vanschoren et al., 2014).
All information can be found on
OpenMI. Dataset ID
Dataset Name
Size (n p)
23517
numerai28.6
96320 x
1169
airlines albert
539383 x
41147
425240 x 78
4135
Amazon wwtps_emplllppppeeeee _cccess_csssssss
32769 x
1461
bank-marketing
45211 x 16
1590
adult
48842 x 14
41150
MiniBooNE
130064 x 50
41162
kick
72983 x 32
42733
Click prediction_
39948 X 11
42742
porto-seguro
595212 x 57
Note that datasets serve data generating processes (DGPs; Hothorn al., 2005). As are mostly concerned with the actual generalization performance of the final best HPC found during HPO based on validation performance we rely on comparably large held out test set that is not used during HPO. We therefore use 5000 data points sampled from a DGP as an outer test set. To further be able measure the generalization performance robustly for varying data sizes available during HPO, we construct concrete tasks based on the DGPs by sampling subsets of (train_ iiiinnvaidd; n) size 500, 1000 and 5000 from the DGPs. This results in 30 tasks total (10 DGPS x traannraalllll valid sizes). For more details and the concrete implementation of this procedure, see Appendix F.3. We also collected another 5000 data points as an external validation set, but did not use it. Therefore, we had tighten the restriction to 10000 data points mentioned in the main paper to 15000 data points as the lower bound on data points. To allow stronger variation over different replications, we decided to use 20000 the final lower bound.
26

---

F.2
Learning Algorithms
Here we briefly present training pipeline details and search spaces of the learning algorithms used in our benchmark experiments.
The sannel-shaped MLP based on sklearn's MLP Classifier and is constructed in the following way: The hidden layer size for each layer is determined by num_ sum_layers and max_ _ax_nniss. We start with max_ units and half the number of units for every subsequent layer to create a funnel. max_ saxx_batch_siee
is the largest power of 2 that is smaller than the number of training samples available. We use ReLU as activation function and train the network optimizing logloss as loss function via SGD using a constant learning rate and Nesterov momentum for 100 epochs. Table 5 lists the search space (inspired from Zimmer et al. (2021)) used during HPO.
The Elastic Net is based on sklearn's 's Logistic Regression Classifier. We train it for a maximum of 1000 iterations using the "saga" solver. Table 6 lists the search space used during HPO.
The XGBoost and CatBoost search spaces are listed in Table 7 and Table 8, both inspired from their search spaces used in McElfresh et al. (2023).
For both the Elastic Net and Funnel MLP, missing values are imputed in the preprocessing pipeline (mean imputation for numerical features and adding a new level for categorical features). Categorical features are target encoded in a cross-var valsdaaadd manner using a 5-fold CV. Features are then scaled to zero mean and unit variance via standard scaler. For XGBoost, we impute missing values for categorical features (adding new level) and target encode them a cross-validated manner using a 5-fold CV. For CatBoost, no preprocessing is performed.
XGBoost and CatBoost models are trained for 2000 iterations and stop early if the validation loss (using the default internal loss function used during training, i.c., logloss) does not improve over a horizon of 20 iterations. For retraining the best configuration on the whole train and validation data, the number of boosting iterations is set to the number of iterations used to find the best validation performance prior to the stopping mechanism taking action.? ?
F.3 Exact Implementation
In the following, we outline the exact implementation of performing one HPO run for a given learning algorithm concrete task (dataset x train_vall valid size) and given resampling. We release all code to replicate benchmark results and reproduce our analyses via ht https::///// ttm.tttooooo.o..... mu/ htpppapprr____ 2paper_2024_ 2eeeee2222eellll1_1e reshuffling, For given replication (in total 10):
1. We sample (without replacement) train_ train_valid size (500, 1000 or 5000 points) and test size (always 5000) points from the DGP (i.e. a concrete dataset in Table 4). These shared for every learning algorithm (i.e. all learning algorithms are evaluated on the same data).
2. A given HPC is evaluated in the following way:
The resampling operates on the train validation set of size train valid.
The learning algorithm is configured by the HPC.
The learning algorithm is trained on training splits and evaluated on validation splits according to the resampling strategy. In case reshuffling is turned on, the training and validation splits are recreated for every HPO. We compute the Accuracy, ROC AUC and logloss when using random search and compute ROC AUC when using HEBO or SMAC3 and average performance over all folds for resamplings involving multiple folds.
For each HPC we then always re-train the model on all train_vall valid data being available and evaluate the model on the held-out test set to compute outer estimate of generalization performance for each HPC (regardless of whether it is the incumbent for given iteration or not).
Forr CV and repeated holdout take the average number of boosting iterations the models trained on the different folds.
'With train validation we refer to all data being available during HPO which is then further split by resampling into train and validation sets.
27

---

Table 5: Search Space for Funnel-Shaped MLP Classifier.
Parameter
Type
Range
Log
num num_layers
Int.
to
No
max units
Int.
64, 128, 256, 512
No
learning_ran rate
Num.
1 10 to 10-1
Yes
batch size
Int.
16, 32, ... max batch size
No
momentum
Num.
0.1 to 0.99
No
alpha
Num.
1 10 10- to 1 x 10
Yes
Table 6: Search Space for Elastic Net Classifier.
Parameter
Type
Range
Log
C
Num. 1 x 10 to 104
Yes
ratio
Num.
0.0 to 1.0
No
Table 7: Search Space for XGBoost Classifier.
Parameter
Type
Range
Log
max depth
Int.
2 to 12
Yes
alpha
Num.
1 x 10 to 1.0
Yes
lambda
Num.
1 10-8 1.0
Yes
eta Num.
0.01 to 0.3
Yes
Table 8: Search Space for CatBoost Classifier.
Parameter
Type
Range
Log
learning_ rate
Num.
0.01 0.3
Yes
depth
Int. 2 to 12
Yes
12 leaf reg
Num.
0.5 to 30
Yes
3. We evaluate 500 HPCs when using random search and 250 HPC when using HEBO or SMAC3 (SMAC4HPO facade).
As resamplings, we use holdout with a 80/20 validaaaioation split and 5 folds for CV, so that the holdout strategy is just one fold of the CV and the fraction of data points being used for training and respectively validation are the same across different resampling strategies. 5-fold holdout simply repeats the holdout procedure five times and 5x 5-fold CV repeats the 5-fold CV five times. Each of the four resamplings can be reshuffled or not (standard).
As mentioned above, the test set is only varied for each of the 10 replica (repetitions with different seeds), but consistent for different tasks (i.e. the different learning algorithms are evaluated on same test set, similarly, also the different dataset subsets all share the same test set). This allows for fair comparisons of different resamplings on a concrete problem (i.c. a given dataset, train_ valid size and learning algorithm). Additionally, for the random search, the 500 HPCs evaluated for a given learning algorithm are also fixed over different dataset and train_ vaniddald size combinations. This is done to allow for an isolation of the effecct the concrete resampling (and whether it is reshuffled or not) has on generalization performance, reducing noise arising due to different HPCs. Learning not explicitly seeded allow for variation during model training over
algorithms themselves different replications. Resamplings and partitioning of data are always performed in a stratified manner with respect the target variable.
For the random search, we only ran (standard and reshuffled) holdout and (standard and reshuffled) 5x 5-fold CV experiments (because we can simulate 5-fold CV and 5-fold holdout experiments based
28

---

on the results obtained from the 5x 5-fold CV (by only considering the first repeat or the first fold for each of the five repeats).
For running HEBO or SMAC3, each resampling (standard and reshuffled for holdout, 5-fold holdout, 5-fold CV, 5x 5-fold CV) has to be actually run due to the adaptive nature of BO.
For the random search experiments, this results in 10 (DGPs) x (train_ valid sizes) x (learning algorithms) x 2 (holdout or 5x 5-fold CV) X 2 (standard or reshuffled) x 10 (replications) = 4800 HPO runs, each involving the evaluation of 500 HPCs and each evaluation of an HPC involving either 2 (for holdout; due to retraining retraining on train validation data) model fits. In summary, the random search experiments involve the evaluation of 2.4 Million HPCs with in total 33.6 Million model fits.
train validation data) 26 (for 5x 5-fold CV; due to
Similarly, for the HEBO and SMAC3 experiments, this each results in 10 (DGPs) 3 (train_valll valid sizes) x 4 (learning algorithms) x 4 (holdout, 5-fold CV, 5x 5-fold CV or 5-fold holdout) x 2 (replications) 9600 HPO runs'! each involving the evaluation of 250 HPCs and each evaluation of an HPC involving either 2 (for holdout; due to retraining on train validation data), 6 (for 5-fold CV or 5-fold holdout; due to retraining on train validation data) or 26 (for 5x 5-fold CV; due to retraining on train validation data) model fits. In summary, the HEBO and SMAC3 experiments each involve the evaluation of 2.4 Million HPCs with in total 24 Million model fits.
(standard or reshuffled)
F44 Compute Resources
We estimate our total compute time for the random search, HEBO and SMAC3 experiments to be roughly 11 11.86 CPU years. Benchmark experiments were run on an internal HPC cluster equipped with a mix of Intel Xeon E5-2670, Intel Xeon E5-2683 and Intel Xeon Gold 6330 instances. Jobs were scheduled to use single CPU core and were allowed to use up to 16GB RAM. Total emissions are estimated be an equivalent of roughly 6508.67 kg CO2.
G Additional Benchmark Results Visualizations
G.1 Main Experiments
In this section, we provide additional visualizations of the results of our benchmark experiments.
Figure illustrates the trade-off between the final number of model fits required by different resam- plings and the final average normalized test performance (AUC ROC) after running random search for budget of 500 hyperparameter configurations. We can see that the reshuffled holdout on average comes close to the final test performance of the overall more expensive 5-fold CV.
Below, we give an overview of the different types of additional analyses and visualizations we provide. Normalized metrics, i.c., normalized validation or test performance refer to the measure being scaled to [0, 1] based on the empirical observed minimum and maximum values obtained on the raw results level (ADTM; see Wistuba et al., 2018). More concretely, for each scenario consisting of learning algorithm that is run on given task (dataset x train_valid size) given a certain performance metric, the performance values (validation or test) for all resamplings and optimizers are normalized on the replication level to [0, 1] by subtracting the empirical best value and dividing by the range of performance values. Therefore normalized performance value of 0 is best and 1 is worst. Note that we additionally provide further aggregated results on the learning algorithm level and raw results of titb........ com/ com/slds ssss- 1mu 1mmu/aperrrrppppepe _024_ fl
validation and test performance via https: //github..
ing.
* Random search
Normalized validation performance in Figure 7.
"We even could have simulated the vanilla holdout from the 5x 5-fold CV experiments by choosing an arbitrary fold and repeat but choose not to do so, to have some sanity checks regarding our implementation by being able to compare the "true" holdout with the simulated holdout.
"ooe that we do not have to take the different metrics into account because random search allows us to simulate runs for different metric post hoc.
Note that HEBO and SMAC3 were only run for ROC AUC the performance metric.
29

---

900
JE6C
SE62
8-45
045
2.40
Maan Nannaoonaeed
8.40
1.30
0.35
0:30
10000
1008
30399
No. Final Model Fits
Reshufting
FALSE
TRUE
Resampting
Hobeat
CV
Hokoou
St 5V5--
Figure 6: Trade-off between the final number of model fits required by different resamplings and the final average normalized test performance (AUC ROC) after rumning random search for budget of 500 hyperparameter configurations. Averaged over different tasks, learning algorithms and replications separately for increasing n (train-validation sizes, columns). Shaded areas represent standard errors.
Normalized test performance in Figure 8.
Improvement in test performance over 5-fold CV in Figure 9.
Rank w.rt. test performance in Figure 10.
HEBO and SMAC3 random search holdout
Normalized validation performance in Figure 11. Normalized test performance in Figure 12.
Improvement in test performance over standard holdout in Figure 13.
Rank w.t.. test performance in Figure 14.
НEBO and SMAC3 vs. random search 5-fold holdout Normalized validation performance in Figure 15. Normalized test performance in Figure 16.
Improvement in test performance over standard 5-fold holdout in Figure 17.
Rank w.r.t. test performance in Figure 18.
HEBO and SMAC3 vs. random search 5-fold CV
Normalized validation performance in Figure 19. Normalized test performance in Figure 20,
Improvement in test performance over 5-fold CV in Figure 21.
Rank w.r.t. test performance in Figure 22.
НEBO and SMAC3 vs. random search 5x 5-fold CV
Normalized validation performance in Figure 23. Normalized test performance in Figure 24.
Improvement in test performance over 5x 5-fold CV in Figure 25,
Rank w.r.t. test performance in Figure 26.
30

---

Accuracy,
Accuracy,
Accuracy,
0.75
0.75
0.50
0.50
0.50
Mcan Norralized Validation Performance
0.25
0.25
0.25
0.00
0.00
ROC AUC, 500
ROC AUC, 1000
ROC AUC, 5000
0.75
0.50
0.25
0.25
0.00
Logloss, 500
Logloss, 1000
Logloss, 5000
0.75
0.75
0.50
0.50
0.25
0.00
0.00
0.00
No. HPC Evaluations
Reshuffling
FALSE
TRUE
Resampling
Holoout
S-fold CV
5-fold Holdout
5x 5-fbld CV
Figure 7: Random search. Average normalized performance over tasks, learners and replications for different (train-validation sizes, columns). Shaded areas represent standard errors.
Accuracy,
1000
Accuracy, 5000
0.5
0.4
0.4
0.4
0.3
0.3
Mcan Normelzzed Test Porformnne
0.2
ROC AUC, 500
ROC AUC, 1000
ROC AUC. 5000
0.45
0.5
0.5
0.40
0.4
0.35
0.3
0.30
0.3
0.2
Locloss, 500
Logioss, 1000
Logloss, 5000
0.3
0.5
0.3
0.2
0.2
0.1
0.1
No. HPC Evaluations
Reshuffinng
FALSE
TRUE
Resampling
Holdout
S-Hold CV
5-fold Holdout
5x 5-feld CV
Figure 8: Random search. Average normalized test performance over tasks, learners and replications for different (rain-validation sizes, columns). Shaded areas represent standard errors.
31

---

Accuracy. 500
Accuracy, 1000
Accuracy 5000
0.25
0.00
0.0
0.0
-0.1
-0.25
-0.2
-0.2
-0.4
-0.75
Mean Test Improveeee
ROC
ROC 5000
0.4
0.5
0.0
0.0
0.00
-0.5
-0.4
-0.25
-1.0
-0.8
-0.50
200
300
400
500
100
200
300
500
100
200
300
400
500
Logless, 500
Logloss, 1000
Logless, 5000
0.0
0.1
-0.5
0.0
-1.0
-1.5
-0.2
-2.0
100
200
300
400
500
100
200
300
500
1.00
200
300
400
500
No. HPC Evaluations
Reshuffiing
Resampling
Holdout
5-fold Holdout
5-fid CV
Figure 9: Random search. Average improvement (compared to standard 5-fold CV) with respect to test performance the incumbent over tasks, learners and replications for different n (train-validation sizes, columns). Shaded areas represent standard errors.
Accuracy: 500
Accuracy, 1000
Accuracy, 5000
5.0
5.0
4.5
4.5
4.0
Mcan Rank (Test Performeree)))
ROC
ROC. AUC, 1000
RDC AUC.
5.5
5.0
5.0
5.0
0.5
4.5
4.0
4.0
3.5
3.5
100
200
300
400
500
100
200
300
400
500
100
200
300
400
500
Logloss, 500
Logloss, 1000
Logloss, 5000
100
200
300
400
500
100
200
300
500
100
200
300
400
500
No. HPC Evaluations
Reshuflinng
FALSE
TRUE
Resampling
Holdout
S-fold Holdout
5-fold CV
Figure 10: Random search. Average ranks (lower is better) with respect to test performance over tasks, learners and replications for different (train-vall valii-vvllittion sizes, columns). Shaded areas represent standard errors.
32

---

500
1000
5000
Validation Performaine
0.8
0.8
0.8
Mcan Normallzzg salllllee
0.6
0.4
0.4
0.4
0.2
50
150
200
250
100
150
200
250
50
100
150
200
250
No. Evaluations
O Optimizer
Random Searth
HEBO
SMAC3
Reshuffling
FALSE
TRUE
Figure 11: HEBO and SMAC3 vs. random search for holdout. Average normalized validation performance (ROC AUC) over tasks, learners and replications for different (train-validation sizes, columns). Shaded areas represent standard errors.
1000
0.50
0.5
0.5
Mcan Normelized
Perfomane
0.45
0.40
0.4
0.35
0.3
0.3
0.2
50
100
150
200
250
50
100
150
200
250
100
150
200
250
No. HPC Evaluations
Optimizer
Random Search
HEBO
SMAC3
Reshuffling
FALSE
TRUE
Figure 12: HEBO and SMAC3 vs. random search for holdout. Average normalized test performance (ROC AUC) over tasks, learners and replications for different validataliottion sizes, columns). Shaded areas represent standard errors.
500
1000
5000
Mcan Test Improvementt
1.5
1.0
1.0
0.5
0.5
0.0
0.0
-0.5
100
150
200
250
100
150
200
250
50
100
150
200
250
Evaluations
Optimizer
Random Search
HEBO
SMAC3
Reshuffling
FALSE
TRUE
Figure 13: HEBO and SMAC3 vs. random search for holdout. Average improvement (compared standard holdout) with respect to test performance (ROC AUC) of the incumbent over tasks, learners and replications for different n (train-validation sizes, columns). Shaded areas represent standard errors.
33

---

Moan Rank (Test Perforrranc)
4,00
3.75
2.75
3.50
3.50
3.50
3.25
3.00
3.00
100
150
200
250
50
100
150
200
250
100
150
200
250
No. HPC Evaluations
Optimizer
Reshuffing
FALSE
Figure 14: HEBO and SMAC3 vs. random search for holdout. Average ranks (lower is better) with respect to test performance (ROC AUC) incumbent over tasks, learners and replications for different (train-validation sizes, columns). Shaded areas represent standard errors.
500
1000
5000
Validation Performance
0.8
Mcan Normalizdd
0.6
0.6
0.4
0.4
0.4
0.2
0.2
No. HPC Evaluations
O ptimizer
Random Search
HEBO
SMAC3
Reshuffling
FALSE
TRUE
Figure 15: HEBO and SMAC3 vs. random search for 5-fold holdout. Average normalized validation performance (ROC AUC) over tasks, learners and replications for different validttaii sizes, columns). Shaded areas represent standard errors.
Moan Normllized
Perbmancc
0.50
0.45
0.40
0.35
0.30
50
100
150
200
250
50
100
150
200
250
50
100
150
200
250
HPC Evaluations
O ptimizer
Random Search
HEBO
SMAC3
Reshuffling
FALSE .... TRUE
Figure 16: HEBO and SMAC3 random search for 5-fold holdout. Average normalized test. performance (ROC AUC) over tasks, learners and replications for different n (train-validation sizes, columns). Shaded areas represent standard errors.
34

---

500
1000
5000
1.5
1.5
0.5
1.0
0.5
Mcan Test
0.0
0.0
-0.5
100
150
200
250
100
150
200
250
50
100
150
200
250
HPC Evaluations
Optimizer
Random Search
HEBO
SMAC3
Reshuffling
FALSE
TRUE
Figure 17: HEBO and SMAC3 vs. random search for 5-fold holdout. Average improvement (compared to standard 5-fold holdout) with respect to test performance (ROC AUC) of the incumbent over tasks, learners and replications for different represent standard errors.
sizes, columns). Shaded areas
500
1000
5000
Mcan Rank (Test Performance
4.00
3.75
3.50
3.50
3.50
3.25
3.25
100
200
250
50
150
250
100
200
HP Evaluations
Optimizer
Random Search
HEBO
SMAC3
Reshuffling
FALSE
TRUE
Figure 18: HEBO and SMAC3 vs. random search for 5-fold holdout. Average ranks (lower better) with respect to test performance (ROC AUC) of the incumbent tasks, learners and replications for different n validaaiitttion sizes, columns). Shaded areas represent standard errors.
500
1000
5000
Validaation Perforennc
Mean Normalized
0.6
0.4
0.2
0.2
0.2
50
150
200
250
100
150
250
50
100
200
No. HPC Evaluations
Optimizer
Random Search
HEBO
SNAC3
Reshuflling
FALSE
TRUE
Figure 19: HEBO and SMAC3 vs. random search for 5-fold CV. Average normalized validation performance (ROC AUC) over tasks, learners and replications for different (train-validation sizes, columns). Shaded areas represent standard errors.
35

---

500
1000
5000
Mcan Normallzzd
Parfomance
0.50
0.5
0.45
0.35
0.3
0.30
0.2
50
100
150
200
250
50
100
150
200
250
100
200
250
HPC Evaluations
Optimizer
Random Search
HEBO
SMAC3
Reshuffling
FALSE
TRUE
Figure 20: HEBO and SMAC3 vs. random search for 5-fold CV. Average normalized performance (ROC AUC) over tasks, learners and replications for different (trai-validaation sizes, columns). Shaded areas represent standard errors.
1000
5000
1.0
1.5
0.5
1.0
0.5
Mcan Test
0.0
0.0
50
100
150
200
250
50
100
150
200
50
100
150
200
No. HPC Evaluations
Optimizer
Random Search
HEBO
SMAC3
Reshuffling
FALSE
TRUE
Figure 21: HEBO and SMAC3 vs. random search for 5-fold CV. Average improvement (compared standard 5-fold CV) with respect test performance (ROC AUC) of the incumbent over tasks, learners and replications for different (triinvaliddation sizes, columns). Shaded areas represent standard errors.
Mcan Rank (Test Performance)
500
1000
5000
3.7
3.75
3.5
3.50
3:25
100
150
200
250
150
200
50
150
200
No. HPC Evaluations
Optimizer
Random Search
HEBO
SMAC3
Reshuffling
FALSE
TRUE
Figure 22: HEBO and SMAC3 vs. random search for 5-fold CV. Average ranks (lower is better) with respect to performance (ROC AUC) of the incumbent over tasks, learners and replications for different n (train- validation sizes, columns). Shaded areas represent standard errors.
36

---

500
1000
5000
Validation Performnnne
Mcan Normallzzs sellllzzed
0.6
0.6
0.4
0.4
0.2
0.2
0.2
50
150
200
250
100
150
200
250
50
100
150
200
250
No. Evaiuations
Optimizer
Random Searth
HEBO
SMAC3
Reshuffling
FALSE
TRUE
Figure 23: HEBO and SMAC3 vs. random search for 5x 5-fold CV. Average normalized validation performance (ROC AUC) over tasks, learners and replications for different (train-validation sizes, columns). Shaded areas represent standard errors.
500
1000
5000
Mcan Normalized Perfomannc
0.4
0.4
0.3
0.3
0.2
50
100
150
200
250
100
150
200
250
50
100
150
200
250
No. HPC Evaluations
Optimizer
Random Searth
HEBO
SNAC3
Reshuffling
FALSE
TRUE
Figure 24: HEBO and SMAC3 vs. random search for 5x 5-fold CV. Average normalized test performance (ROC AUC) over tasks, learners and replications for different (trainvvaidattion sizes, columns). Shaded areas represent standard errors.
500
1000
5000
Mcan Test Improvementt
0.8
1.0
0.4
0.5
0.0
0.0
-0.4
50
100
150
200
250
50
100
150
200
50
100
150
200
250
Evaluations
Optimizer
Random Search
HEBO
SMAC3
Reshuffling
FALSE
TRUE
Figure 25; HEBO and SMAC3 vs. random search for 5x 5-fold CV. Average improvement (compared to standard 5x 5-fold CV) with respect to test performance (ROC AUC) of the incumbent over tasks, learners and replications for different (train-validation sizes, columns). Shaded areas represent standard errors.
37

---

Mcan Rank (Test Performncce
500
1000
5000
4.00
3.75
3.6
3.75
3.50
3.4
3.50
3.25
3.25
3.00
No. HPC Evaluations
Optimizer
Random Search
HEBO
SMAC3
Reshuffling
FALSE
TRUE
Figure 26: HEBO and SMAC3 vs. random search for 5x f-fold CV. Average ranks (lower is better) with respect to test performance (ROC AUC) of the incumbent over tasks, learners and replications for different n vrain-validation sizes, columns). Shaded areas represent standard errors.
38

---

G.2
Ablation on M-fold holdout
Based on the 5x 5-fold CV results we further simulated different M-fold holdout resamplings (standard and reshuffled) by taking M repeats from the first fold of the 5x 5-fold CV. This allows us get an understanding the effect more folds have on M- holdout, especially in the context of reshuffling.
Regarding normalized validation performance we observe that more folds generally result in less optimistically biased validation performance (see Figure 27). Looking at normalized test performance (Figure 28) observe the general trend that more folds result in better test performance which is expected. Reshuflling generally results in better test performance compared to the standard resampling (with the exception logloss where especially in the case of single holdout, reshuffling can hurt generalization performance). This effect is smaller, the more folds are used, which is in line with our theoretical results presented Table Looking at improvement compared to standard 5-fold holdout with respect to test performance and ranks with respect to test performance, we observe that often reshuffled 2-fold holdout results that are highly competitive with standard 3, 4 or 5-fold holdout.
Accuracy,
1000
Accuracy,
0.75
0.75
0.50
0.50
0.50
Mean Norralized Validation Performnee
0.25
0.25
0.00
ROC AUG, 500
ROC AUC, 1000
ROC AUC, 5000
0.8
0.75
0.6
0.50
0.4
0.2
0.25
Logloss. 500
Logioss, 1000
Logloss, 5000
0.75
0.75
0.50
0.50
0.50
0.25
0.25
0.25
0.00
No. HPC Evaluations
Holdout
1-folc
2-bod
3-old
4-fold
S-old
Reshuffing
FALSE
TRUE
Figure 27: Random search. Average normalized validation performance over tasks, learners and replications for different (trainvvalidatin sizes, columns). Shaded areas represent standard errors.
39

---

Accuracy,
Accuracy, 1000
Accuracy, 5000
0.5
0.50
0.45
0.40
0.4
0.40
0.35
0.35
0.30
0.3
0.30
Mcan Nomalized Test Performenee
0.25
0.25
AUC,
ROC 1000
AUC,
0.6
0.50
0.5
0.40
0.4
0.3
0.3
0.30
0.2
Logioss, 500
Logloss, 1000
Logloss, 5000
0.3
0.6
0.5
0.5
0.3
0.3
0.4
0.3
0.2
0.2
0.1
0.1
100
200
300
500
200
300
400
500
100
200
400
No. HP Evaluations
Holdout
1-fbld
2-fold
2-fold
4-fold
S-kid
Reshuflling
FALSE
TRUE
Figure 28: Random search. Average normalized test performance over tasks, learners and replications for different (train-validation sizes, columns). Shaded areas represent standard errors.
Accuracy, 500
Accurary 1000
Accuracy, 5000
0.50
0.1
0.25
0.0
0.0
0.00
-0.1
-0.1
-0.2
-0.2
-0.50
-0.3
-0.3
-0.4
-0.4
100
200
400
500
100
200
400
100
200
300
400
500
Moan Test Improvement
ROC 1000
ROC 5000
0.0
-0.2
-0.5
-0.4
-1.0
-0.6
200
400
200
400
100
200
300
400
500
Logloss, 500
Logloss, 1000
Logloss, 5000
0.0
0.1
-0.5
-1.0
-0.1
-1.5
-1.0
-0.2
-2.0
-1.5
-0.3
100
200
300
400
500
100
200
300
400
500
100
200
300
400
500
No. HPC Evaluations
Holdout
Reshuflling
Figure 29: Random search. Average improvement (compared to standard 5-fold holdout) with respect to test performance of the incumbent over tasks, learners and replications for different n irrainvvaldation sizes, columns). Shaded areas represent standard errors.
40

---

Accuracy, 500
Accuracy, 1000
Accuracy, 5000
6.5
6.0
5.6
5.5
5.2
5.0
5.0
Mcan Rank (Test Pafforancc
ROC 500,
ROC AUC, 1000
RDC AUC,
7.0
7.0
6.5
6.5
6.0
5.5
5.5
5.0
5.0
4.5
100
200
300
400
500
100
200
300
400
500
100
200
300
400
500
Logloss, 500
Logloss, 1000
Logloss, 5000
6.5
6.0
5.5
5.0
100
200
300
400
500
100
200
300
400
500
100
200
300
400
No.
HPC Evaluations
Holdout
1-told
2-4oid
4-told
Reshuffling
FALSE
TRUE
Figure 30: Random search. Average ranks (lower is better) with respect to test performance of the incumbent over tasks, learners and replications for different validaaaiotiion sizes, columns). Shaded areas represent standard enrors.
41

---

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 outline our three main contributions the introduction (Section 1), do not discuss generalization in the introduction, but rather in the discussion in Section 5.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in 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
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 of the work performed by the authors?
Answer: [Yes]
The paper provides an analysis of reshuffling data in the context of estimating the generalization error for hyperparameter optimization. Our theoretical analysis explains why reshuffling works, and we experimentally verify the theoretical analysis. We discuss the limitations of our work in Section 5.
Justification:
Guidelines:
The answer NA means that the paper has 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 separate "Limitations" section in 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 on 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should 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 or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails 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 fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best 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.
3. Theory Assumptions and Proofs
42

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Full assumptions and proofs for our main results (Theorem 2.1 and Theo- rem 2.2) are given in Appendix C.1 and Appendix C.2, respectively. Derivations for the parameters in Table are provided in Appendix E. The additional results for the grid density are stated and proven directly in Appendix D.
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 proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide 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 supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide thorough details on the experimental setup Section 4.1 and Appendix F. Moreover, we provide code to reproduce our results under an open source license at https:: //te:////ttttt com/ sassslddmmmm /aaperppprr__ 2024_reehuffeeee
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a 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 a 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 to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the case of a 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) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution 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).
43

---

(d)
reproducible, they We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe 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., to 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 faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Regarding datasets, we rely on OpenML.org. We provide thorough details the experimental setup in Section 4.1 and Appendix F. Morcover, we provide code to reproduce our results under an open source license at https: htops:://ithhbl com/slde 1mu /paper_2022 _024 reshuffling.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurIPS code and data submission guidelines (https://nip) cc/pu
blic/ /ece//gids////eeee httgggddd//ooduuunnneeee weiissssiiccccycc for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for 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:
/t///uudessseee httpbiii//g.eeeeoddeeuuiiiieeeee /Cooe//umissiiioooocc www.aiiiisioooiiiiioooooooacmicl 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,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments 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 as possible supplemental material (appended the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide thorough details on the experimental setup in Section 4. and Appendix F. Moreover, provide code to reproduce results under open source license at httpss:/githai
coom/slss-2ae wwslddssmmmppae 1ewlllmumppppeee 1acppe__2000 2024_ reshuffling.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
44

---

Justification:
We report the standard error in every analysis.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to 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.
It is OK to report 1-sigma error bars, but 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 errors 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 error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures 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 execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide details in Appendix F.4.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as 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 or failed experiments that NeurlPS Code of Ethics https: : /nwuriss..../// cc wwtpppcccc/caaccccccccccccccctct cew.ae/teeiiiiieeeeeneeeeeeeee
didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the
Answer: [Yes]
Justification: Our work provides a study on reshuffling data when estimating the generaliza- tion in hyperparameter tuning. Therefore, work is applicable wherever standard machine learning is applicable, and we do not see any ethical concerns in our method.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS 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 (c.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
45

---

Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper conducts fundamental research that is not tied to particular applica- tions, let alone deployment.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
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 unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a 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 intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
The paper conducts fundamental research that is not tied to particular applica- tions, let alone deployment. The paper does not develop models that have high risk for misuse.
Justification:
Guidelines:
The answer NA means that the paper poses no 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 require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses 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]
46

---

We used datasets from OpenML.org and reference the dataset pages. Further information the datasets, including their licenses, are available OpenML.org.
Justification:
Guidelines:
The answer NA means that the paper does use 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 used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
license, copyright information, and terms of use package should be provided. For popular datasets, saperswithcode com/ dataatasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
assett are released,
For existing datasets that are re- e-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We provide code as new asset and describe how we make our code available in Point of the NeurlPS Paper Checklist.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing 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: The paper does neither involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing 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 to the NeurIPS Code of Ethies, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
47

---

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 equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does neither involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on 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 we 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 as the institution conducting the review.
48


Reviews:
[{"review_id": "61sIzHa6eo", "reviewer": "Reviewer_DL64", "summary": "The paper suggests the idea that reshuffling the splits for every configuration during the hyperparameter optimization can improve the generalization property. The paper derives the theoretical analysis to shows how reshuffling affects the asymptotic behaviour of the validation loss surface, and the paper also provides a bound on the expected regret in the limiting regime. Finally, the paper also conducts some experiments to demonstrate the effectiveness of the proposed approach.", "questions": "Please see my questions in the Weakness section.", "limitations": "The paper describes the limitations of their method in Section 5.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "+ The general idea of the paper is to reshuffle the sampling split when evaluating the hyperparameters, which is very interesting to me. It also makes sense and is reasonable.\n+ The writing of the paper (except the theoretical analysis part) is good in general. I can understand the key ideas and also other details of the proposed approach.\n+ The experiments include different aspects like understanding the shape of the loss function, and also it shows the improvement of the proposed approach when finding the optimal objective function values when applying to a state-of-the-art BO method.", "weaknesses": "Firstly, I have various concerns with the theoretical analysis conducted in the paper, in particular, I think they’re not rigorous. I list in the below some of my concerns regarding the theoretical analysis.\n+ In Theorem 2.1, the “regularity conditions” need to be explicitly mentioned in the theorem (cannot be put in the appendix) because the theorem itself needs to be self-contained in the main paper.\n+ In Theorem 2.1, it’s unclear whether the covariance matrix \\Sigma exist (because it’s a limitation of an expression and what if that expression goes to infinity?). Furthermore, even when it exists, how is it related to n? If it is larger than O(n) then the theorem doesn’t have any meaning because it doesn’t show the convergence of \\hat{\\mu}(\\lambda_j)? \n+ In the discussion of Theorem 2.1, I don’t understand why we have Eq. (1). More explanations need to be provided.\n+ In Theorem 2.2, why can we assume that \\hat{\\mu} follows a Gaussian process model? Is this assumption used in existing literature? And does it make sense in practice? Furthermore, what are the limits of the terms B(\\tau) and A(\\tau) in the RHS of the equation in Theorem 2.2? Without any quantification of these terms, we cannot conclude anything about how far \\mu(\\hat{\\lambda}) from \\mu(\\lambda^*)\n\nSecondly, for the experiments, my main concern is that the paper only evaluates the performance of the reshuffling approach using one state-of-the-art BO method (HEBO). I think it should be evaluated on at least 2 state-of-the-art BO methods to clearly demonstrate the effectiveness of the proposed approach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your helpful feedback on the presentation of our theoretic results, which will help us to improve their presentation. Below, we give detailed answers to your suggestions:\n\n**Concerns regarding the theoretical analysis**\n\n> In Theorem 2.1, the “regularity conditions” need to be explicitly mentioned in the theorem (cannot be put in the appendix) because the theorem itself needs to be self-contained in the main paper.\n\nGood point. We will surely do that.\n> In Theorem 2.1, it’s unclear whether the covariance matrix \\Sigma exist (because it’s a limitation of an expression and what if that expression goes to infinity?). Furthermore, even when it exists, how is it related to n? If it is larger than O(n) then the theorem doesn’t have any meaning because it doesn’t show the convergence of \\hat{\\mu}(\\lambda_j)?\n\nThe covariance $\\Sigma$ cannot diverge: First, the kernel $K$ is bounded because the loss function $\\ell$ is assumed to be bounded (this could be relaxed by explicit conditions involving the generic learner $g_{\\lambda}$, but we prefer not to overcomplicate matters here). Second, the term $\\tau_{i, j, M}$ is bounded above by $1/\\alpha^2$ because all probabilities are bounded by 1. The limit itself is, of course, no longer related to $n$ (as we have taken $n \\to \\infty$). We will add a corresponding remark to the paper.\n\n> In the discussion of Theorem 2.1, I don’t understand why we have Eq. (1). More explanations need to be provided.\n\nPlease refer to our general comment, point 2.\n\n> In Theorem 2.2, why can we assume that \\hat{\\mu} follows a Gaussian process model? Is this assumption used in existing literature? And does it make sense in practice? \n\nWe think this is an appropriate and realistic assumption: \n1. Theorem 2.1 shows that this assumption at least holds in the large-sample limit, under standard assumptions (see, e.g., [1], [2]). Further, as stated in the sentence preceding Theorem 2.1:  *\"This limiting regime will not only reveal the effect of reshuffling on the loss surface but also give us a tractable setting to study HPO performance.\"* This remark was intended to explain that a) the upcoming GP assumption is appropriate because it is approximately true due to Theorem 2.1, b) it makes a theoretical analysis of the generalization behavior possible. This sentence can certainly be made clearer.\n2. From a state-of-the-art standpoint: Using a GP to model hyperparameter landscapes is one of the most successful HPO principles and very popular in BO. For example, the BO method HEBO we use in the experiments follows this approach. GPs are also directly used to model and analyze HP landscapes, for example in [3]. \n\n[1] Bayle, P., Bayle, A., Janson, L., & Mackey, L. (2020). Cross-validation confidence intervals for test error. Advances in Neural Information Processing Systems, 33, 16339-16350.  \n[2] Austern, M., & Zhou, W. (2020). Asymptotics of cross-validation. arXiv preprint arXiv:2001.11111.  \n[3] Mohan et al., AutoRL Hyperparameter Landscapes. AutoML 2023.\n\n> Furthermore, what are the limits of the terms B(\\tau) and A(\\tau) in the RHS of the equation in Theorem 2.2? Without any quantification of these terms, we cannot conclude anything about how far \\mu(\\hat{\\lambda}) from \\mu(\\lambda^*)\n\nThe terms $B$ and $A$ have an explicit form that can be evaluated for a given data-generating process and hyper-parameter grid. The term $B(\\tau)$, as stated, is unbounded, but a closer inspection of the proof shows that it is upper bounded by $\\sqrt{\\log J}$ (l661: *“we can use the trivial bound $N (s) \\le J$”*). This bound is attained only in the unrealistic scenario when the validation losses are essentially uncorrelated across all HPCs. The term $A(\\tau)$ is lower bounded by $0$, which is also the worst case because $A$ enters with a negative sign. We shall include this discussion in the revised version since it may also interest other readers.\n\nFinally, let us emphasize that, like most bounds in learning theory, this bound is not meant to provide a sharp quantitative result but to gain general insights about the influence of the various parameters on the generalization performance. The simulation study in the following section corroborates these insights.\n\n**Concerns regarding the experimental evaluation**\n\nPlease refer to our general comment, point 1.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4QYK1vm5Sh", "reviewer": "Reviewer_sYf9", "summary": "In hyperparameter optimization (HPO), individuals often use the same resampling for different configurations to ensure fair comparison. However, this fixed split may introduce bias into the optimization process, particularly after numerous evaluations, as it tends to favor configurations that align well with that specific split. This study systematically explores the effects of reshuffling on HPO performance through theoretical analysis, controlled simulation studies, and real dataset experiments. The authors highlight that reshuffling resampling splits during HPO can help find configurations with superior overall generalization, particularly in scenarios where the loss surface is flat and estimates are noisy. Experimental findings indicate that when holdout reshuffling is employed, the ultimate generalization performance often rivals that of 5-fold cross-validation in a broad array of settings.", "questions": "1. In practical applications, reshuffling implies an increase in time consumption. How do the different methods in the experiments of this paper perform in terms of time consumption? When the total time is constant, does using reshuffling have advantages over using only resampling, or what advantages does it have?\n2. In the experiments of this paper, how do the methods perform on each dataset? Does reshuffling exhibit different performances on different datasets?\n3. Successive halving, as a method that uses different sampling ratios in the optimization process, how does reshuffling perform in it?", "limitations": "Already discussed.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. This paper is well organized, with rich mathematical expressions and clear experimental figures.\n2. The authors delve deeply into the effect of reshuffling in HPO from theoretical analysis, simulation studies, and experiments on realistic datasets, highlighting its significance especially when the loss surface is float and estimates are noisy.\n3. In the experiments, the authors study the effect of reshuffling with different resampling methods and HPO methods. The design and visual presentation of the experiments is clear.", "weaknesses": "1. The authors use a large number of symbols in the paper, adding a notation table may be considered to enhance readability.\n2. The authors primarily investigate the impact of reshuffling in resampling and HPO but do not propose novel methods. The actual implementation is simple, with $n\\in\\{500,1000,5000\\}$. The authors could consider making improvements to reshuffling itself based on the analysis of dataset noise and surface to determine reshuffling strategies.\n3. The paper could consider conducting experiments on a wider range of models (e.g., SVM), datasets (e.g., mnist and cifar10), and HPO methods (e.g., successive halving) to demonstrate the effects of reshuffling comprehensively.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your suggestions on the presentation and the experimental setup, which will help us make our paper more convincing. In the following, we provide detailed answers to your questions:\n\n>The authors use a large number of symbols in the paper, adding a notation table may be considered to enhance readability.\n\nThis is a very good idea. We will include this in the appendix of our paper, and we already show a preview in the attached PDF.\n\n> The authors primarily investigate the impact of reshuffling in resampling and HPO but do not propose novel methods. The actual implementation is simple, with n∈500,1000,5000. The authors could consider making improvements to \nreshuffling itself based on the analysis of dataset noise and surface to determine reshuffling strategies.\n\nIt is true that we primarily investigate the impact of reshuffling in HPO. We firmly believe that providing theoretical and empirical insights into an arguably important method/field like HPO is extremely valuable in itself (and traditionally valued at venues like NeurIPS). Further, the technique is immediately available, and we think that our quite large-scale experiments convincingly demonstrate its effectiveness (see also the reviews of rcFG and QU3x, which seem to strongly agree with our argument here). Building more sophisticated shuffling methods exploiting data set characteristics is, however, beyond the foundational scope of our paper.\n\n> The paper could consider conducting experiments on a wider range of models (e.g., SVM), datasets (e.g., mnist and cifar10), and HPO methods (e.g., successive halving) to demonstrate the effects of reshuffling comprehensively.\n\nPlease see our general response, point 1.\n\n> In practical applications, reshuffling implies an increase in time consumption. How do the different methods in the experiments of this paper perform in terms of time consumption? When the total time is constant, does using reshuffling have advantages over using only resampling, or what advantages does it have?\n\nWe think this is a slight misunderstanding. Shuffling the data amounts to drawing a random permutation of the observation indices and comes at pretty much no additional computational cost. Shuffling takes less than a millisecond, which is negligible compared to the costs of model fits / the overhead of BO. The advantage of the approach is better generalization performance in many cases, and you basically get this \"free of charge\", which we think is indeed a nice result. Of course, there is no “free lunch”, which is explained by our theoretical analysis. But as our experiments clearly show: On average you often run better in HPO with reshuffling than without. We will state this more clearly in the paper.\n\n> In the experiments of this paper, how do the methods perform on each dataset? Does reshuffling exhibit different performances on different datasets?\n\nExperimental results per data set are already available in our anonymous repository (link in Appendix F; navigate to e.g., plots/catboost_accuracy/test.pdf). Reshuffling can exhibit different performances on different datasets but results in a strong performance on average, as exemplified in the aggregated plots in the main paper and Appendix.\n\n> Successive halving, as a method that uses different sampling ratios in the optimization process, how does reshuffling perform in it?\n\nWhile we think that this could later be an interesting direction to explore, we think this is out-of-scope for the current paper. SH uses subsampling of the data to address the multi-fidelity problem in HPO (and SH is not restricted to subsampling, other ways exist to reduce compute cost, such as lower numbers of epochs). We already evaluate the method in complex contexts (data sets, learners, complex HPO methods), and adding a further (complex) aspect doesn't seem helpful in getting to the \"core effect\" of reshuffling. \n\nBut please note that we instead opted to add further experiments on a different SOTA HPO method; see general comment 1.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7TUKnRFiJ5", "reviewer": "Reviewer_8FSs", "summary": "This paper studies the effect of reshuffling the splits over which hyper-parameter optimiazation is performed. Specifically, the authors provide theoretical guarantees on the generalization performance achieved via reshuffling and empirically demonstrate its impact both via simulation and benchmark experiments. Overall, the results demonstrate that reshuffling improves HPO performance according to the theoretical analysis.", "questions": "**a)** \nHow do you derive Equation (1)? Are the observations that follow based only off of theorem 2.1 and Equation (1)? Or based on other equations and theorems?\n\n&NewLine;  \n**Comments:**\n\nYou should repeat (on the figures) the meaning of 500, 1000, and 5000. It would make it much easier to read/interpret the results.\n\nIt seems that if you were to plot something like mean test improvement as a function of the cost  of each HPO approach, the benefits of shuffling would be more visible. From the current plots, it is not clear that the advantage of trying to improve the performance of holdout (especially when there are better approaches, as you show) is that holdout is cheaper than these other (better performing) approaches.\n\n&NewLine;  \n**[minor comment / observation]**\n\n[line 26] You should explicitly introduce the CV acronym\n\n[line 204] repeated 'sized'", "limitations": "The authors adequately discussed the limitations of the work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Originality:** \nRelated work seems to be adequately cited and, to the best of my knowledge, this work explores a dimension of the hyper-parameter tuning problem that I had not seen explored yet.\n\n&NewLine;\n**Quality:** \n\nOverall, the paper is well written and easy to follow. It is also generally well organised and self-contained. I did not carefully check the mathematical results and deductions. I particularly appreciated the discussion on the limitations of the study.\n\n&NewLine;\n**Clarity:** \n\n[Line 94] You introduce some initial observations for different selection methods, but you haven't yet introduced the methods. There seems to be too big of a jump from the equations to the observations for the several methods. Similarly, it would have helped me better understand the reshuffling idea if Table 1 had more explanation. First, the meaning of \"reshuffling effect\" is not clear at this stage of the paper. Second, I think it would help the reader if you clarified whether increases/decreases in tau and sigma are desirable and why.\n\nThere are a lot of variables introduced throughout (which is absolutely normal) but this also means the reader may forget what some of them mean as they are reading and new variables are introduced. It could be helpful to periodically remind the reader of what some variables mean (especially if they have been introduced some paragraphs ago). (For example, as you do in lines 215-216). \n\nSome things seem to come out of the blue: e.g. line 140 -- \"there are two regimes\". Did you figure this out while deriving the equations or did you suspect this a priori? Where do these two regimes come from?\n\nJust like you illustrate one of the scenarios via Figure 1, you could have a similar figure illustrating the case when the process is correlated.\n\nIt would be quite useful for a reader if you had some form of pseudo-code highlighting the reshuffling procedure.\n\n\n&NewLine;  \n**Significance:**\n\nAlthough not explicitly highlighted in the paper, it seems to me that the idea of reshuffling is interesting as it can contribute significantly to finding better configurations at a cheaper cost.", "weaknesses": "See above for weaknesses", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your positive review and the suggestions, which will help us to improve our paper. We are very happy that you find our paper well-written and that you appreciate our up-front discussion of the limitations of the study. Below you can find detailed answers to your questions.\n\n> [Line 94] You introduce some initial observations for different selection methods, but you haven't yet introduced the methods. There seems to be too big of a jump from the equations to the observations for the several methods. Similarly, it would have helped me better understand the reshuffling idea if Table 1 had more explanation. First, the meaning of \"reshuffling effect\" is not clear at this stage of the paper. Second, I think it would help the reader if you clarified whether increases/decreases in tau and sigma are desirable and why. [...] a) How do you derive Equation (1)? Are the observations that follow based only off of theorem 2.1 and Equation (1)? Or based on other equations and theorems?\n\nThank you for raising this issue and for the great suggestions. Please refer to our general comment, point 2, for some clarification. By “reshuffling effect” we simply mean “the difference in behavior between the unshuffled and shuffled variant of a resampling method”. We will add more explanation for Table 1 and discuss whether and why increase/decrease in $\\tau$ and $\\sigma$ are desirable as suggested.\n\n> There are a lot of variables introduced throughout (which is absolutely normal) but this also means the reader may forget what some of them mean as they are reading and new variables are introduced. It could be helpful to periodically remind the reader of what some variables mean (especially if they have been introduced some paragraphs ago). (For example, as you do in lines 215-216).\n\nWe have revised the papers and added some reminders as suggested. Further, as suggested by another reviewer, we now include a Table of symbols and their meaning in the appendix (a preview is also shown in the attached PDF).\n\n> Some things seem to come out of the blue: e.g. line 140 -- \"there are two regimes\". Did you figure this out while deriving the equations or did you suspect this a priori? Where do these two regimes come from?\n\nThe two regimes became apparent after our derivations. When looking at the final bound, reshuffling can only help when the term $A(\\tau)$ is strictly positive. This is exactly the case when $\\sigma / 2m \\eta^2 \\le e$. Intuitively speaking, the two regimes come from the fact that reshuffling always adds some noise to the HPO process. Our analysis shows that this can be helpful, but only if the HPO problem is “sufficiently hard” in the first place. If $\\sigma / 2m \\eta^2 \\le e$ the curvature is very high compared to the noise, so it is extremely easy to find the best configuration. We will revise our discussion of the regimes accordingly.\n\n> Just like you illustrate one of the scenarios via Figure 1, you could have a similar figure illustrating the case when the process is correlated.\n\nThanks for the suggestion. We added a version of Figure 1 where the correlation in the (unshuffled) empirical loss is so high that reshuffling doesn’t help, and refer to it in the main text. For your convenience, the figure is also provided in the PDF accompanying the rebuttal. \n\n> It would be quite useful for a reader if you had some form of pseudo-code highlighting the reshuffling procedure.\n\nThank you very much for your suggestion, but we find it difficult to comply. The method is so simple (1. Randomly permute the observation indices, 2. Do resampling as usual) that it would feel odd to write this in pseudo-code. If you think this would benefit the paper or we misunderstood the request, we are of course happy to reconsider.\n\n> You should repeat (on the figures) the meaning of 500, 1000, and 5000. It would make it much easier to read/interpret the results.\n\nGood idea; we will update the figures accordingly.\n\n> It seems that if you were to plot something like mean test improvement as a function of the cost of each HPO approach, the benefits of shuffling would be more visible. From the current plots, it is not clear that the advantage of trying to improve the performance of holdout (especially when there are better approaches, as you show) is that holdout is cheaper than these other (better performing) approaches.\n\nWe have added a plot in the newly provided PDF which shows the trade-off between the final number of model fits required by different resamplings and the final test performance. We can see that the reshuffled holdout on average comes close to the final test performance of the more expensive 5-fold CV. A similar plot be added to the final version of the paper.\n\n> [minor comment / observation]\n\nThank you very much for finding these two mistakes, we will of course correct them.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1DCxRYU0aR", "reviewer": "Reviewer_QU3x", "summary": "The standard protocol evaluates various hyperparameter configurations using a resampling estimate of the generalization error to guide optimization and select a final hyperparameter configuration. The authors argue that reshuffling the splits for every configuration often improves the final model’s generalization performance on unseen data. They provide a theoretical analysis explaining how reshuffling affects the asymptotic behavior of the validation loss surface and provides a bound on the expected regret in the limiting regime.\n\nThe paper also presents a simulation study confirming the theoretical results and demonstrates the practical usefulness of reshuffling in a large-scale, realistic hyperparameter optimization experiment. The authors found that reshuffling leads to test performances that are competitive with using fixed splits, and it drastically improves results for a single train-validation holdout protocol.", "questions": "I am interested in seeing how reshuffling performs on more complex benchmarks and with more sophisticated models, such as training Resnet on CIFAR-10/100 or Imagenet. Experiments in such realistic settings could further strengthen the results.", "limitations": "The authors acknowledge that the benefits of reshuffling may vary based on noise correlation and loss surface curvature. I believe that the authors have conducted enough discussion regarding the limitations of the paper", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper provides a rigorous theoretical analysis explaining how reshuffling the splits affects the asymptotic behavior of the validation loss surface. This analysis helps establish the foundation for understanding the benefits of reshuffling.\n\nThe authors conduct a simulation study to validate their theoretical results. By demonstrating that reshuffling leads to competitive test performances and improved results in a realistic hyperparameter optimization experiment, they provide empirical evidence supporting their claims.\n\nThe technique of reshuffling resampling splits is directly applicable to hyperparameter optimization in machine learning. It addresses a common challenge faced by practitioners and provides a practical solution to improve model generalization.", "weaknesses": "The effectiveness of reshuffling depends on dataset characteristics, such as its size, noise level, and correlation structure, which limits the usefulness of reshuffling.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your positive review of our submission and for assessing our study as “large-scale, realistic hyperparameter optimization experiment”. Below you can find detailed answers to your questions and criticism:\n\n> The effectiveness of reshuffling depends on dataset characteristics, such as its size, noise level, and correlation structure, which limits the usefulness of reshuffling.\n\nWhile we fully agree with the statement that the effectiveness of reshuffling depends on the characteristics of the optimization problem (we assume that this is what you mean by “dataset characteristics”), we do not think this is a weakness. On the contrary, a significant contribution of our paper is to establish, for the first time, an explicit connection between generalization and dataset characteristics. We are confident this will prove useful in many applications and future methodological developments.\n\n> I am interested in seeing how reshuffling performs on more complex benchmarks and with more sophisticated models, such as training Resnet on CIFAR-10/100 or Imagenet. Experiments in such realistic settings could further strengthen the results.\n\nPlease see our general response, point 1.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Bfih0r5gSp", "reviewer": "Reviewer_rcFG", "summary": "The paper presents a compelling investigation into the effects of reshuffling resampling splits on the generalization performance of hyperparameter optimization (HPO) strategies. Through a mix of theoretical analysis and empirical studies, the authors argue that reshuffling can lead to statistically significant improvements in model performance, especially when the loss surface is flat and its estimate is noisy.", "questions": "There is little discussion on the computational costs associated with reshuffling, which could be significant, especially in large-scale applications. Understanding this trade-off is crucial for practical adoption.", "limitations": "As mentioned in the paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Novel Approach: The paper introduces a new approach to HPO by proposing the reshuffling of train-validation splits. This contrasts with the fixed splits to ensure consistency across evaluations.\n\nTheoretical and Empirical Validation: The combination of theoretical insights and empirical validation is a strong aspect of this paper. The theoretical model explaining how reshuffling affects the asymptotic behavior of the validation loss surface is particularly insightful.\n\nPractical Implications: The findings suggests that reshuffling could be a simple yet effective technique to improve the robustness of hyperparameter tuning.", "weaknesses": "Generalizability of Results: The experiments are somewhat limited in scope, focusing on specific types of data sets and HPO strategies. It would be beneficial to see broader testing across more varied data types and with different models to fully understand the generalizability of the results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your positive review of our submission and your suggestions on how to improve our submission. Below you can find the answers to your criticism and questions:\n\n> Generalizability of Results: The experiments are somewhat limited in scope, focusing on specific types of data sets and HPO strategies. It would be beneficial to see broader testing across more varied data types and with different models to fully understand the generalizability of the results.\n\nPlease see our general response, point 1.\n\n> There is little discussion on the computational costs associated with reshuffling, which could be significant, especially in large-scale applications. Understanding this trade-off is crucial for practical adoption.\n\nShuffling the data amounts to drawing a random permutation of the observation indices, which comes at almost no computational cost. Shuffling takes less than a millisecond, which is negligible compared to the costs of model fits and/or the overhead of BO. We will add a comment to the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for their time, constructive feedback, useful suggestions, and positive evaluation. We want to use the space here to address two points that were raised by multiple reviewers.

**1. (DL64, sYf9, QU3x, rcFG) Additional experiments**

Some reviewers suggested various additional experiments. We value strong empirical analyses as much as theoretical insights, but we also argue that our paper already contains a very thorough experimental setup. 
Summarizing what was said in Appendix E.4: We ran RS, BO (a modern and advanced version with a proven track record), 3 different version of resampling, and many learners which are arguable in the set of "SOTA methods for tabular data", on 10 different data sets with diverse characteristics. The RS experiments covered 33.6 Mio. model fits, for HEBO it was 24 Mio. We deem that "quite large scale". In view of the already extensive experiments involving many different data sets and dozens of millions of model fits, we have deliberately limited our scope to tabular data. We strongly believe that these experiments reflect realistic settings encountered by practitioners many times, see for example [vBvdS, BLSH+, MKVC+].

Because two reviewers were specifically interested in results for a second state-of-the-art HPO method to more clearly show the effectiveness of reshuffling, we have nevertheless conducted extra experiments in the interest of scientific discussion here. We ran SMAC (SMAC4HPO facade, [LEFB+]) in addition to HEBO on all 4 models (CatBoost, XGBoost, funnel-shaped MLP, Elastic Net) on all 30 tasks (3 train_valid sizes * 10 DGPs) with 10 repetitions for the standard and reshuffled holdout and provide an updated Figure 5 from the main submission in the uploaded rebuttal pdf. We can observe that reshuffling the holdout has a similar effect on SMAC as on HEBO and results in better generalization performance. We will continue running SMAC for all other resamplings, similarly as already reported for HEBO in Appendix F.1.


**2. (DL64, 8FSs) Confusion about Eq (1)**

There was some confusion about Eq (1) in the paper and where it comes from. We apologize for jumping too fast. The term $\tau_{i, j, M}$ appears in Theorem 2.1 and captures the influence of reshuffling on the loss surface.
Eq (1) follows from our method-specific computations for the term $\tau_{i, j, M}$ provided Appendix D. In all cases, the result happens to have the form displayed in Eq (1). The method-specific values for $\sigma$ and $\tau$ are then summarized in Table 1. 

In the revised version, we will
* first introduce the different resampling methods,
* then refer to Appendix D for mathematical computations,
* only then state and explain Eq (1) and the values in Table 1;
* revise the presentation in Appendix D.2 to make the form appearing in Eq (1) more clearly visible.

We hope that this clarifies our paper and makes our results more accessible.

--- 
[vBvdS] Position: Why Tabular Foundation Models Should Be a Research Priority. Boris Van Breugel, Mihaela van der Schaar; ICML 2024.  
[BLSH+] Deep neural networks and tabular data: A survey. Vadim Borisov, Tobias Leemann, Kathrin Seßler, Johannes Haug, Martin Pawelczyk, Gjergji Kasneci; IEEE 2022  
[MKVC+] When Do Neural Nets Outperform Boosted Trees on Tabular Data? Duncan McElfresh, Sujay Khandagale, Jonathan Valverde, Vishak Prasad C, Ganesh Ramakrishnan, Micah Goldblum, Colin White, NeurIPS 2023  
[LEFB+] SMAC3: A versatile Bayesian optimization package for hyperparameter optimization. Lindauer, M., Eggensperger, K., Feurer, M., Biedenkapp, A., Deng, D., Benjamins, C., ... & Hutter, F. Journal of Machine Learning Research, 23(54), 1-9, 2022

Meta-review: After the initial review, rebuttal, and discussion, the reviewers remain split on their decisions, but I am inclined to recommend accepting the submission.  Given its novel theoretical insights and thorough empirical analysis of a simple yet not well studied modification to ubiquitous hyperparameter optimization methodologies, the results in this work can provide value to both theoreticians and practitioners.

As reviewers pointed out (and authors acknowledged in the rebuttal) the clarity of presentation should be improved in several places.  I additionally suggest giving a few concrete examples of learning algorithms / model families that meet the regularity conditions required for your analysis. The additional empirical results using SMAC should also be included in the final version.

Finally, as mentioned in the thoughtfully written Limitations section, the theoretical analysis applies only to the setting in the limit of infinite data. Any insights on the possibility of (or obvious roadblocks) to a finite sample analysis would be a valuable addition and helpful for future extensions of this work.
Decision: Accept (poster)