I am using 3-fold cross validation for hyperparameter selection of my XGBOOST model. To be specific, I use xgboost.cv for cross validation instead of sklearn. I use random search for hyperparameter search and choose the one or a few set of hyperparameters with the best average score in the hold-out fold of data. The standard deviation of score is approximately the same across all hyperparameter set.
What I observe is that the model is overfitting to the cross validation data. The score of model on testing data is always much worse than the average score on hold-out fold of data. So instead of selecting the set of hyperparameter with the best average score, is there any other criterion I should consider in order to reduce the overfitting?