# Hyperparameter Optimization Using Successive Halving with Greedy Cross Validation
## 2 Materials and Methods
### The Greedy Successive Halving Algorithm  
By design, standard cross validation fully evaluates each candidate ML model from start to finish and returns the model's overall level of performance [16]. Standard cross validation is a memoryless process insofar as it neither cares about nor pays attention to how the performance of any candidate ML model compares to that of any other model. In contrast, greedy cross validation maintains an estimate of every candidate model's level of performance and uses that information to prioritize the evaluation of the most promising models. This means that when using greedy cross validation, the most promising models will be the earliest to be completely evaluated during the overall model evaluation process [8]. The proposed greedy successive halving algorithm capitalizes on this difference between standard and greedy cross validation to achieve its superior performance. As illustrated in Figure 2, both the number of candidate ML models and the number of training cases that will be used during each iteration of the successive halving algorithm are determined by exponential functions and can be easily calculated before the algorithm begins evaluating any ML models. Since the number of models needed for each successive halving iteration can be easily calculated in advance, the current successive halving iteration can be terminated immediately as soon as the number of ML models needed for the next iteration have been fully evaluated via greedy cross validation. Put differently, there is no need to wait until _every_ candidate model for the current iteration has been fully evaluated before identifying the set of best-performing models that will be used in the next iteration. Instead, by virtue of greedy cross validation's innate prioritization of the most promising ML models, any iteration of successive halving (except the final iteration) can be concluded immediately as soon as greedy cross validation has fully evaluated a sufficient number of models to satisfy the input requirements of the next iteration. This is the key insight that endows greedy successive halving with its superior performance. Successive halving--including greedy successive halving--is an iterative algorithm. During the first iteration, successive halving considers the complete set of candidate ML models but does so using a minimally sized random sample of the available training data. By the time successive halving reaches the final iteration, it considers only the two most promising candidate models but does so using all of the available training data. For the current study, the maximum number of training cases to use per iteration (\(N_{max}\)) was thus set equal to the total number of available training cases, while the minimum number of training cases to use per iteration (\(N_{min}\)) was set equal to \(6*k\), with \(k\) being the number of folds to use during the cross-validation process. Since 5 and 10 are the two most common values of \(k\) used by AI/ML practitioners [17], setting \(N_{min}=6*k\) guaranteed that a minimum of \(6*5=30\) cases would be used to train and evaluate each candidate model during the first iteration of the successive halving algorithm. In successive halving, the amount by which the number of candidate models is reduced from one iteration to the next and the amount by which the number of training cases is increased from one iteration to the next both depend on exponential functions, which in turn depend on the number of successive halving iterations. Prior to calculating the parameters of the exponential functions, it is therefore necessary to calculate the number of iterations that will be needed during the successive halving process. The total number of iterations to perform (\(N_{iter}\)) is a function of the minimum and maximum number of cases per iteration and a halving factor (\(h\)), as shown in Equation (1). Each successive halving iteration considers approximately \(1/h\) of the models from the previous iteration.