Reshuffling Resampling Splits Can Improve Generalization of Hyperparameter Optimization

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:

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.

Please see our general response, point 1.

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.

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

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:

The effectiveness of reshuffling depends on dataset characteristics, such as its size, noise level, and correlation structure, which limits the usefulness of reshuffling.

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

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.

Please see our general response, point 1.

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.

[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?

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

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

We 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).

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?

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

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.

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

It would be quite useful for a reader if you had some form of pseudo-code highlighting the reshuffling procedure.

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

You should repeat (on the figures) the meaning of 500, 1000, and 5000. It would make it much easier to read/interpret the results.

Good idea; we will update the figures accordingly.

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.

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

[minor comment / observation]

Thank you very much for finding these two mistakes, we will of course correct them.

PseudoCode: We can surely add it, if you think it improves readability, no problem.

Practical consideration/usage: We disagree here, please reconsider this: Especially for holdout, there is a clear on average advantage using reshuffling. This is clearly demonstrated by our experiments. Staying with the current "state" / "recommendation" (no reshuffling) means you will perform worse, in many experiments. Just because we provide a deeper theoretical analysis, which shows in which situations this is most beneficial, and because we currently cannot exactly pinpoint them in a practical manner, shouldn't have us ignore this piece of knowledge now. We think your criticism would be merited if the situations where resampling / HPO are improved are somewhat "specific and rare", and then we would not help the reader to identify these situations. But as explained above (and the paper) this is not the case.

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:

The authors use a large number of symbols in the paper, adding a notation table may be considered to enhance readability.

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

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 reshuffling itself based on the analysis of dataset noise and surface to determine reshuffling strategies.

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

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.

Please see our general response, point 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?

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

In the experiments of this paper, how do the methods perform on each dataset? Does reshuffling exhibit different performances on different datasets?

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

Successive halving, as a method that uses different sampling ratios in the optimization process, how does reshuffling perform in it?

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

But please note that we instead opted to add further experiments on a different SOTA HPO method; see general comment 1.

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:

Concerns regarding the theoretical analysis

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.

Good point. We will surely do that.

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)?

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

In the discussion of Theorem 2.1, I don’t understand why we have Eq. (1). More explanations need to be provided.

Please refer to our general comment, point 2.

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?

We think this is an appropriate and realistic assumption:

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

[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.
[2] Austern, M., & Zhou, W. (2020). Asymptotics of cross-validation. arXiv preprint arXiv:2001.11111.
[3] Mohan et al., AutoRL Hyperparameter Landscapes. AutoML 2023.

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^*)

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

Finally, 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.

Concerns regarding the experimental evaluation

Please refer to our general comment, point 1.