I'm currently going through Bengio's and Bergstra's Random Search for Hyper-Parameter Optimization [1] where the authors claim random search is more efficient than grid search in achieving approximately equal performance.
My question is: Do people here agree with that claim? In my work I've been using grid search mostly because of the lack of tools available to perform random search easily.
What is the experience of people using grid vs. random search?

Random search has a probability of 95% of finding a combination of parameters within the 5% optima with only 60 iterations. Also compared to other methods it doesn't bog down in local optima.
Check this great blog post at Dato by Alice Zheng, specifically the section Hyperparameter tuning algorithms.

I love movies where the underdog wins, and I love machine learning
papers where simple solutions are shown to be surprisingly effective.
This is the storyline of “Random search for hyperparameter
optimization” by Bergstra and Bengio. [...] Random search wasn’t taken
very seriously before. This is because it doesn’t search over all the
grid points, so it cannot possibly beat the optimum found by grid
search. But then came along Bergstra and Bengio. They showed that, in
surprisingly many instances, random search performs about as well as
grid search. All in all, trying 60 random points sampled from the grid
seems to be good enough.
In hindsight, there is a simple probabilistic explanation for the
result: for any distribution over a sample space with a finite
maximum, the maximum of 60 random observations lies within the top 5%
of the true maximum, with 95% probability. That may sound complicated,
but it’s not. Imagine the 5% interval around the true maximum. Now
imagine that we sample points from his space and see if any of it
lands within that maximum. Each random draw has a 5% chance of landing
in that interval, if we draw n points independently, then the
probability that all of them miss the desired interval is
$\left(1−0.05\right)^{n}$. So the probability that at least one of
them succeeds in hitting the interval is 1 minus that quantity. We
want at least a .95 probability of success. To figure out the number
of draws we need, just solve for n in the equation:
$$1−\left(1−0.05\right)^{n}>0.95$$
We get $n\geqslant60$. Ta-da!
The moral of the story is: if the close-to-optimal region of
hyperparameters occupies at least 5% of the grid surface, then random
search with 60 trials will find that region with high probability.

You can improve that chance with a higher number of trials.
All in all, if you have too many parameters to tune, grid search may become unfeasible. That's when I try random search.
