The "Amazing Hidden Power" of Random Search? I have the following question that compares random search optimization with gradient descent optimization:
Based on the (amazing) answer provided over here Optimization when Cost Function Slow to Evaluate , I realized something really interesting about Random Search:

Random Search
Even when the cost function is expensive to evaluate, random search
can still be useful. Random search is dirt-simple to implement. The
only choice for a researcher to make is setting the the probability
$p$ that you want your results to lie in some quantile $q$; the rest
proceeds automatically using results from basic probability.
Suppose your quantile is $q = 0.95$ and you want a $p=0.95$
probability that the model results are in top $100\times (1-q)=5$
percent of all hyperparameter tuples. The probability that all $n$
attempted tuples are not in that window is $q^n = 0.95^n$ (because
they are chosen independently at random from the same distribution),
so the probability that at least one tuple is in that region is $1 - 0.95^n$. Putting it all together, we have
$$ 1 - q^n \ge p \implies n \ge \frac{\log(1 - p)}{\log(q)} $$
which in our specific case yields $n \ge 59$.
This result is why most people recommend $n=60$ attempted tuples for
random search. It's worth noting that $n=60$ is comparable to the
number of experiments required to get good results with Gaussian
process-based methods when there are a moderate number of parameters.
Unlike Gaussian processes, the number of queries tuples does not
change with the number of hyperparameters to search over; indeed, for
a large number of hyperparameters, a Gaussian process-based method can
take many iterations to make headway.
Since you have a probabilistic characterization of how good the
results are, this  result can be a persuasive tool to convince your
boss that running additional experiments will yield diminishing
marginal returns.

Using random search, you can mathematically show that:  regardless of how many dimensions your function has, there is a 95% probability that only 60 iterations are needed to obtain an answer in the top 5% of all possible solutions!

*

*Suppose there are 100 possible solutions to your optimization function (this does not depend on the number of dimensions). An example of a solution is $(X_1 = x_1, X_2 = x_2.... X_n = x_n)$.


*The top 5% of solutions will include the top 5 solutions (i.e. the 5 solutions that provide the 5 lowest values of the function you want to optimize)


*The probability of at least encountering one of the top 5 solutions in "$n$ iterations" :  $\boldsymbol{1 - [(1 - 5/100)^n]}$


*If you want this probability $= 0.95$, you can solve for $n$: $\boldsymbol{1 - [(1 - 5/100)^n] = 0.95}


*Thus, $\boldsymbol{n = 60}$ iterations!
But the fascinating thing is, $\boldsymbol{n = 60}$ iterations  is still valid regardless of how many solutions exist. For instance, even if 1,000,000,000 solutions exist – you still only need 60 iterations to ensure a 0.95 probability of encountering a solution in the top 5% of all solutions!

*

*$\boldsymbol{1 - [(1 - ( (0.05 \times 1000000000) /1000000000 )^{n} )] = 0.95}$


*"$\boldsymbol{n}$" will still be 60 iterations!
My Question: Based on this amazing "hidden power" of random search, and further taking into consideration that random search is much faster than gradient descent since random search does not require you to calculate the derivatives of multidimensional complex loss functions (e.g., neural networks) : Why do we use gradient descent instead of random search for optimizing the loss functions in neural networks?
The only reason that I can think of, is that if the ranked distribution of the optimization values are "heavily negative skewed", then the top 1% might be significantly better than the top 2%–5%, and the amount of iterations required to encounter a solution in the top 1% will also be significantly larger:

But even with such a distribution of optimization scores, would gradient descent still have its advantages? Does gradient descent (or stochastic gradient descent) really have the ability to compete with this "hidden power" of random search? If certain conditions are met, due to its attractive theoretical properties (e.g., convergence) – does gradient descent have the ability to reach the best solution (not best 5%, but the best solution) much faster than random search? Or in real life applications with non-convex and noisy objective functions, do these "attractive theoretical properties" of gradient descent generally not apply, and once again – the "amazing hidden power" of random search wins again?
In short :  Based on this amazing "hidden power" (and speed) of random search, why do we use gradient descent instead of random search for optimizing the loss functions in neural networks?
Can someone please comment on this?
Note: Based on the sheer volume of literature which insists and praises the ability of stochastic gradient descent, I am assuming that stochastic gradient descent does have many advantages compared to random search.
Note: Related Question that resulted from an answer provided to this question: No Free Lunch Theorem and Random Search


Why do we use Gradient Descent instead of Random Search for optimizing the loss functions in Neural Networks?

We do use both at the same time currently. Meaning that, there is already a degree of random search even if we use stochastic gradient decent in training neural networks, i.e., random initialisation and in reinforcement learning via random search in game trees.
For supervised deep learning, this is prominently studied by The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks arXiv. A random initialisation is acting as a random search.
In reinforcement learning, deep Q-learning is achieved actually with the synergy of Monte Carlo Tree Search.
In short, random search algorithms are already a practical part of training deep learning models. Completely gradient-free optimisation for deep learning, there was a different discussion here.
