Maybe we're talking about different algorithms. Do you agree that we are talking about random search as outlined in this Wikipedia page (https://en.wikipedia.org/wiki/Random_search)?
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.
Reviewers asked for a comparison with this specific random search. You can go look at the reviews on OpenReview.