Thanks for the response and paper. My main question here is that it doesn't seem to make sense that random search did significantly worse than random parameters? It seems that random search should only consistently lose in cases when the dev set performance is anti-correlated with the test set performance. Why do you think you saw random parameters beating random search? (Is there a typo in the table or something)?
I believe in this specific case, there was a local optimum that random search (with the parameters we selected, which we actually tuned as well) was not able to escape.
In most cases I think you would find random search doing better than random parameters (unless we have the paradoxical situation you described), so your intuition is correct in the general case. But in this case there is no typo on the table!
Does this answer your question?
Anyways, if you had a bad random search prior, then that should have equally negatively impacted your random parameters as both should have been drawn from the same distribution. If you used a different random distribution for random search vs your "random parameters", why did you use a different distribution and why were they so different?
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.