Ah, that makes sense. By random search, I thought you were referring to random search as defined in http://www.jmlr.org/papers/volume13/bergstra12a/bergstra12a..... I believe that's the more common method for hyperparameter optimization cases like this (https://static.googleusercontent.com/media/research.google.c..., https://scikit-learn.org/stable/modules/generated/sklearn.mo...).

It has much better guarantees than the method you used and tends to work quite well in practice. It's also probably what the reviewers meant by a random search baseline.