Reshuffling Resampling Splits Can Improve Generalization of Hyperparameter Optimization

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.

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. Theoretical 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. Practical 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.

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.

Rating

7

Confidence

3

Soundness

3

Presentation

4

Contribution

3

Limitations

As mentioned in the paper.

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

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

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.

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

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

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.

Strengths

**Originality:** Related 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. 
 **Quality:** Overall, 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. 
 **Clarity:** [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. 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). 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? 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. It would be quite useful for a reader if you had some form of pseudo-code highlighting the reshuffling procedure. 
 **Significance:** Although 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

Questions

**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? 
 **Comments:** You should repeat (on the figures) the meaning of 500, 1000, and 5000. It would make it much easier to read/interpret the results. 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. 
 **[minor comment / observation]** [line 26] You should explicitly introduce the CV acronym [line 204] repeated 'sized'

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors adequately discussed the limitations of the work.

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.

Strengths

1. This paper is well organized, with rich mathematical expressions and clear experimental figures. 2. 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. 3. 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. 2. 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. 3. 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.

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? 2. In the experiments of this paper, how do the methods perform on each dataset? Does reshuffling exhibit different performances on different datasets? 3. Successive halving, as a method that uses different sampling ratios in the optimization process, how does reshuffling perform in it?

Rating

4

Confidence

3

Soundness

2

Presentation

2

Contribution

2

Limitations

Already discussed.

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.

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. + 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. + 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. + 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. + 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)? + In the discussion of Theorem 2.1, I don’t understand why we have Eq. (1). More explanations need to be provided. + 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^*) Secondly, 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.

Questions

Please see my questions in the Weakness section.

Rating

4

Confidence

4

Soundness

2

Presentation

3

Contribution

2

Limitations

The paper describes the limitations of their method in Section 5.

Author Rebuttal Availible

Dear Reviewers, Thank you for your reviews and your time. The authors have provided a rebuttal, answering specific questions that were raised and have also provided additional empirical observations. Please take a careful look and follow up with additional questions and/or update your review as necessary. At the minimum indicate you have read and understood the feedback. Also, please feel free to start a private discussion in a separate thread. Thank you, Area Chair for Submission 1124