Which Grid Search technique should you use?
Grid Search is an integral part of parameter optimization. Essentially, it helps us find the best hyperparameters over a set of combinations. There multiple types of grid search. We will discuss 3 main types:
- Exhaustive Grid Search
- Randomized Grid Search
- Halving Grid Search
Exhaustive Grid Search
As the name suggests, it exhausts all combinations of parameters available, given a parameter grid. The combination that produces the highest cross validation score is considered the best parameter.
Randomized Grid Search
Again, as the name suggests, it randomly selects a number of parameter combinations (n_iter) from the parameter grid. The combination that produces the highest cross validation score is considered the best parameter.
Halving Grid Search
We can think of this method ‘series of matches’ among the parameter combinations. As the competition progresses, more and more parameter combinations/candidates are filtered out until we arrive at the best parameter. Diving a little deeper..
First, all candidates are evaluated on a small subset of the data. Next, the proportion of candidates are ‘halved’ based on their performance (do note that this proportion can be adjusted based on the factor parameter, so it doesn’t necessarily need to be a halving). Thereafter, the remaining candidates are evaluated on more data/resource and then ‘halved’ again. We repeat until the best candidate is chosen.
Experimentation
We conduct a simple experiment to compare the types of Grid Search to help us gauge which one to use. Default parameters were used and parameter grids were held equal to keep the comparisons fair.
Methodology
We create two parameter grids, one small and one large:
Evaluate the grid searches on the small parameter grid yields the following:
Observation: Both randomized grid search and exhaustive grid search yield a logloss of 1.106986, though the latter required much less time. Introducing halving technique greatly reduces wall time but at the cost of some performance.
Evaluating randomized grid search on large parameter grid yields the following:
Observation: Randomized grid search over a large parameter grid of 13122 candidates yield a slightly better logloss of 1.106043. Introducing halving greatly reduces runtime at the cost of some performance.
Conclusion
RandomGridSearch: In my opinion, is the clear winner. It is able to cover a large parameter grid in a respectable amount of time while producing a decent score comparable to ExhaustiveGridSearch.
HalvingGridSearch: Though is the fastest, by a huge margin, it does lose some performance. If a very large parameter grid needs to be covered, this could be a better choice because the alternatives may take too long.
ExhaustiveGridSearch: This method will take too long if the parameter grid becomes large. However, if the parameter grid is small because a developer has a rough idea based on past experience, this might be the better choice.
How the experiment was done: https://github.com/chingfhen/Experiments/blob/main/GridSearch%20Compared.ipynb
