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

*

*As soon as one moves from discrete to continuous search spaces, it becomes necessary to specify a distribution on the parameter space in order to perform the random search. Then it is evident that thie performance of the random search will very strongly depend on the features of this distribution. In fact, one of the key developments in the history of training neural network was the development of various random weight initialization procedures (Glorot, He, etc.). So in a sense the random search is already being used as a (very important) first step for training the networks.


*In fact, there is recent work showing that pure random-search like approaches can be used to train neural networks to high accuracy. This is related to the Lottery Ticket hypothesis, which has already been mentioned by msuzen. But what is even more dramatic, is that it turns out that large randomly-initialized neural networks contain subnetworks that can nearly match the performance of the trained model with no training (Zhou et. al. Ramanujan et. al.).
You may note, though, that I have done a bit of a sleight of hand. In the linked papers, they look for the subnetworks by basically searching over the space of all subnetworks of the original network. It is not as if they are only sampling 60 subnetworks at a time. But this underscores a crucial observation which makes the random search approach somewhat feasible or neural networks: Sampling a single, large network is equivalent to sampling a massive number of small networks. This is because a large network has a very large number of subnetworks. The catch is that they search space is much more than 60: in fact, the combinatorics make an exhaustive enumeration out of the question. So in the linked papers, they  have to use specialized search algorithms to identify the best (or near best) subnetwork. I am not claiming that this is the best way to train a neural network, but in principle random search is a feasible training procedure.


*You ask "Why do we use gradient descent instead of random search?". So really this is not just a question about random search, but also about gradient descent. It has been hypothesized that the stochastic gradient descent algorithm itself is actually key to the remarkable generalization abilities of neural networks. (Here are a few examples of papers that take this approach) This is sometimes called "algorithmic regularization" or "implicit regularization". A simple example: suppose you fit an underdetermined linear regression using gradient descent. There are multiple global minima, but it turns out that the the GD will always converge to the minimum that has smallest norm. So the point is that gradient descent has a bias towards certain kinds of solutions, which can be important when the models are over parametrized, with many gloabl minima. You can easily find a ton of literature on this by googling these key words. But here is the upshot: suppose that we could actually train neural networks using 60 iterations of random search. Then stochastic gradient descent would still probalby be the preferred way to train them, because the solutions found by random search have no useful regularization.

