The "Amazing Hidden Power" of Random Search?

Question

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

Answer 1

1. One limitation of random search is that searching over a large space is extremely challenging; even a small difference can spoil the result.

   Émile Borel's 1913 article "Mécanique Statistique et Irréversibilité" stated if a million monkeys spent ten hours a day at a typewriter, it's extremely unlikely that the quality of their writing would equal a library's contents. And of course we understand the intuition: language is highly structured (not random), so randomly pressing keys is not going to yield a coherent text. Even a text that is extremely similar to language can be rendered incoherent by a minor error.

   

   In terms of estimating a model, you need to estimate everything correctly simultaneously. Getting the correct slope $\hat{\beta}_1$ in the model $y = \beta_0 + \beta_1 x +\epsilon$ is not very meaningful if $\hat{\beta}_0$ is very very far from the truth. In a larger number of dimensions, such as in a neural network, a good solution will need to be found in thousands or millions of parameters simultaneously. This is unlikely to happen at random!

   This is directly related to the curse of dimensionality. Suppose your goal is to find a solution with a distance less than 0.05 from the true solution, which is at the middle of the unit interval. Using random sampling, the probability of this is 0.1. But as we increase the dimension of the search space to a unit square, a unit cube, and higher dimensions, the volume occupied by our "good solution" (a solution with distance from the optimal solution less than 0.05) shrinks, and the probability of finding that solution using random sampling likewise shrinks. (And naturally, increasing the size of the search space but keeping the dimensionality constant also rapidly diminishes the probability.)

   The "trick" to random search is that it purports to defeat this process by keeping the probability constant while dimension grows; this must imply that the volume assigned to the "good solution" increases, correspondingly, to keep the probability assigned to the event constant. This is hardly perfect, because the quality of the solutions within our radius is worse (because these solutions have a larger average distance from the true value).

2. You have no way to know if your search space contains a good result. The core assumption of random search is that your search space contains a configuration that is “good enough” to solve your problem. If a “good enough “ solution isn’t in your search space at all ( perhaps because you chose too small a region), then the probability of finding that good solution is 0. Random search can only find the top 5% of solutions with positive probability from among the solutions in the search space.

   You might think that enlarging the search space is a good way to increase your odds. While it might make the search region contain an extremely high quality region, but the probability of selecting something in that region shrinks rapidly with increasing size of the search space.

   

3. High-quality model parameters often reside in narrow valleys. When considering hyperparameters, it's often true that the hyperparameter response surface changes only gradually; there are large regions of the space where lots of hyperparameter values are basically the same in terms of quality. Moreover, a small number of hyperparameters make large contributions to improving the model; see Examples of the performance of a machine learning model to be more sensitive to a small subset of hyperparameters than others?

But in terms of estimating the model parameters, we see the opposite phenomenon. For instance, regression problems have likelihoods that are prominently peaked around their optimal values (provided you have more observations than features); moreover, these peaks become more and more "pointy" as the number of observations increases. Peaked optimal values are bad news for random search, because it means that the "optimal region" is actually quite small, and all of the "near miss" values are actually much poorer in comparison to the optimal value.

To make a fair comparison between random search and gradient descent, set a budget of iterations (e.g. the $n=60$ value derived from random search). Then compare model quality of a neural network fit with $n$ iterations of ordinary gradient descent & backprop to a model that uses $n$ iterations of random search. As long as gradient descent doesn't diverge, I'm confident that it will beat random search with high probability.

4. Obtaining even stronger guarantees rapidly becomes expensive. You can of course adjust $p$ or $q$ to increase the assurances that you'll find a very high quality solution, but if you work out the arithmetic, you'll find that $n$ rapidly becomes very large (that is, random search becomes expensive quickly). Moreover, in a fair comparison, gradient descent will likewise take $n$ optimization steps, and tend to find even better solutions than random search.

Some more discussion, with an intuitive illustration: Does random search depend on the number of dimensions searched?

Answer 2

Consider a neural network model with 100 weights. If we think only about getting the sign of the weights right and don't worry for the moment about their magnitude. There are 2^100 combinations of the signs of these weights, which is a very large number. If we sample 60 random weight vectors, we will have seen only an minuscule proportion of that space, not even enough to be confident that we have at least one solution for which a given seven weights have the right sign. So even for a small neural network, random sampling has a vanishingly small chance of getting all of the signs of the weights right.

Now of course, the structure of the neural net means that there are symmetries that mean there are multiple equivalent solutions (e.g. flipping the signs of all of the input weights of a neuron and its output weights), but this doesn't cut down the number of equivalent combinations of signs very much.

I suspect part of the problem is indeed that the distribution of performance is very sharply peaked around the best solutions. So even if 60 samples gets you into the top 5% of solutions, if the search space is very large, and the optimum of the cost function is very localised, then a top 5% random solution may still be nonsense and you need, perhaps, a top 0.0005% solution or better to have acceptable performance.

If random search was an effective way of training neural networks, then I would expect someone to have found that out, rather than ~50 years of gradient descent.

Random search is useful for hyper-parameter search though, but mostly because the dimension is lower, and the models are trained on the data using gradient descent, so you are choosing from a set of plausibly good solutions, rather than random ones. In that case, most of the search space has goodish solutions, and the optimum of the cost function is not highly localised (at least not for kernel learning methods).

Answer 3

Suppose we want to answer your question with a 1000 character answer. One approach could be to sample 60 1000-tuples of characters, punctuation marks, and whitespace. With 95% probability, one of these will be within the most useful 5% of all possible Stack Exchange answers within this character limit.

Basically the problem as you point out is that being within some ranked quantile of all possible solutions is not usually very interesting. Generally you have some evaluation function, and what you are really interested in is the difference between either the best possible model or some current model and the model defined by your new set of parameters. Random search is useful when you are optimizing hyperparameters because (really if, it's not always useful) the non-random optimization of the parameters following hyperparameter selection already restricts you to a class of generally useful models.

Answer 4

There's a mathematical result in optimisation, less interesting than it first sounds, called the "No Free Lunch Theorem". It says that for a discrete problem (like @JonnyLomond's answer), no algorithm can beat random search when its performance is averaged over all possible functions to be optimised. That is, you have a function $f:\Omega\to L$ where $\Omega$ is a finite discrete space (like the space of 1000-character strings) and $L$ is a discrete space of numerical values (like 1:10 or 1:1000000000). There are only finitely many such $f$.

You can define any algorithm that evaluates $f(\omega_1)$, $f(\omega_2)$, and so on for $n$ attempts, choosing $\omega_{i+1}$ in terms of earlier results, and then take $\max_i f(\omega_i)$ as your best result. No algorithm will outperform random search averaged over all $f$. One proof idea is to consider $f$ as randomly chosen from the possible functions with equal probability. Because $f$ could be anything, with equal probability, evaluations at $\omega_1,\ldots,\omega_i$ are independent of $f(\omega_{i+1})$; you can't learn anything.

This result isn't that interesting because we usually aren't interested in the average performance over all possible objective functions. But it does imply that the reason random search isn't actually a good competitor is because the objective functions we care about have structure. Some have smooth (or smooth-ish) structure -- parameter values near the optimum give better outputs than those far from the optimum. Sometimes the structure is more complicated. But there is (typically) structure.

[The no-free-lunch theorem is also perhaps less interesting than it seems because it doesn't seem to have an analogue for continuous parameter spaces]

Answer 5

1. 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.

2. 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.

3. 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.

Answer 6

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.

Answer 7

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!

Finding a 95th-percentile solution is no guarantee of finding a good solution. The nature of the curse of dimensionality is that your "optimization distribution" becomes very skewed. When you have a lot of dimensions, 99.99999999% of your parameter space is going to be far from optimum. If you ask random search to find you a 99.99999999th percentile result, it will take billions of times as many trials as finding a 95th-percentile result (and honestly, I probably haven't added nearly enough nines for most real-world scenarios).

And from an information-theoretic perspective, random search is purely "stupid" — it doesn't use any information from the objective function to inform its next guess, and the millionth guess is no more likely to be near the optimum than the first guess is.

In many cases, a gradient is no more expensive per-evaluation than the objective function itself, and its value is obvious: it's a signpost that says "go this way to get a local improvement".

In other cases, no gradient is available (unless we want to estimate it by doing a bunch of function evaluations, which is of course expensive), but then, the answers to the 2016 question you linked cover other techniques we can use to incorporate information about "where we've been and what we found there", which will hopefully enable our later guesses to be more productive than our earlier guesses.

Every optimization technique (whether gradient descent, the simplex method, Bayesian optimization, or whatever else) encodes some sort of assumption about the structure of the objective function. They perform well (and justify their overheads) when the objective function agrees well with that structure, and poorly when it doesn't. Random search incorporates no implicit structure, which means that it's the optimal optimizer when the objective function itself is unstructured and completely random (you're looking for a needle in a haystack, and finding a slightly more silvery stalk of hay doesn't indicate the presence of a needle nearby). Otherwise, you can probably win by doing something else.

Answer 8

The only reason that I can think of, is that if the ranked distribution of the optimization values are "heavily negative skewed"

Sort of. There is a compounding that occurs when you add dimensions that is similar to what you get when you add more randomly sampled models, except that it works against you rather than for you. As you add more dimensions, the models become more and more likely to be "average", and the probability of them being exceptionally good decreases. It's not so much they're skewed towards "bad", so much as they're skewed towards "average", and the "average" model is really bad (remember, if you look at the space of all models, not just the ones created through a rational generation process, most of them are actually worse than just "Use $\bar y$ as your estimator regardless of the $x$ values"). There are many ways of thinking of this:

According to the CLT, adding more features decreases the spread of the distribution of models in terms of loss function per feature. So the standard deviations needed to get to a model quality increases. If you look at how much increasing your percentile increases your standard deviations, this is the reciprocal of the probability density. As your percentile increases, the impact of increasing it further increases. Increasing your percentile from $0.999$ to $0.9999$ increases your z-score much, much more that increasing your percentile from $0.99$ to $0.991$.

The length of a vector increases as you add dimensions, if you keep the individual component lengths fixed. For instance, if you have an $n$ dimensional vector with components equal to $0.7$, the length is $0.7\sqrt n$. So if you want vectors that are within some fixed distance of a "good" solution, the percentage of actual solutions that are within that distance decreases as you add dimensions.

Suppose we give each feature a percentile rank (i.e. "This model is in the 70th percentile as far as how well it incorporates this feature", however that is defined). If there are $k$ features, the probability that all them will be in the top $p$ percentile is $(1-p)^k$. Even if $p$ is a relatively low number like $0.7$, this probability quickly becomes tiny; with ten features, it's about $3$%.

Answer 9

This thought has appeared in some of the answers, but I would like to say, that being in the 5% of the best solutions may still produce a solution of very poor quality.

Consider classification problem on ImageNet and some large networks with millions of parameters. Doing a random search in the space of parameters, you can find a network, that is in the top 5% of all possible weight configurations. However, being in the top 5% may only guarantee, that the accuracy is 0.11%, say, only slightly better, than the random guess classifier (since there are 1000 classes).

Answer 10

The key to the answer to OP's question is in the ... loss function. Here's why.

OP's question has a clue to its answer: yes, by random search you can get the top $\alpha$ quantile of best solution with very few attempts. Why then this isn't good enough, if you believe everyone who answered the question before me?

Several answers refer to "skewness" as does OP in the question. In fact, the skewness is related to the true answer but doesn't address it directly. The skewness itself is the result of two factors: high dimensionality (and its curse) and the choice of the loss function.

It is well known that some distance measures, such as Cartesian distances (quadratic loss being a close cousin), are prone to suffer from [high] dimensionality curse: the distance between any two points in the space explodes when the points are further apart. In other words, any two points are infinitely far away unless they're almost on top of each other. This is what makes those top 5% best solution look like a garbage to us. So, we insist that we want to do much, and I mean $\large MUCH$, better. This is the real reason why random search doesn't work with high dimensional problems.

Note, you can come up with a loss function with which the random search could work. The loss function must not suffer from dimensionality curse in this case. It should re-define what is "good enough" of a solution.

Finally, I didn't address a key point yet" why then the gradient search has a better chance to navigate the dimensionality curse compared to a random search. I'll answer this part later.

Answer 11

A different perspective. The chemistry that led to the first life forms and from there to life forms with a simple nervous system and onward to organisms with a brain, involved only processes analogous to random search. Any more sophisticated algorithms will have had to evolve from random search.

This means that it should be possible to use only random search in machine learning and to get to excellent results. We couldn't exist if this were not true. The question is then how to use random search. Biology would strongly suggest that we should use a genetic algorithm. For example, with your 60 trials to get to the top 5% method, you can iterate this where you take the best few and create 60 mutants of these best few and search for the best of these.

The problem is then that you can get stuck in a local maximum in the fitness landscape. There are many different solutions to this problem. One can use the analogue of sexual reproduction in biology, by mixing the weights from different networks. It is also good idea to also include a few results that are not in the top, as mutations of these may yield good results.

And instead of starting with a very complex loss function, one can start with a simpler one. In many visual tasks such as handwriting recognition, coarse graining can work well. One then trains the neural networks using blurred images where instead of 26 letters there are only a few. You then reduce the amount of blurring so that more letters can be distinguished and then continue with the results of the previous learning session.

Answer 12

If you choose at random from some hypercube $ I_1 \times \dots \times I_n $ tuples $(c_1, \dots, c_n)$ of (real valued) hyperparameters ($I_i$ being intervals), which somehow affect the performance of some algorithm, the performance cannot be independent of the algorithm you want the hyperparameters to be optimized for. I assume a uniform random sample (per dimension). I can easily construct an algorithm, for which finding optimal hyperparameters is arbitrarily unlikely using random search. Just say my algorithm $A(c_1, \dots, c_n)$ does the following: $$A(c_1,\dots, c_n) = 1, (c_1,\dots, c_n) \not\in M_1\times \dots \times M_n $$ and $$A(c_1,\dots, c_n) = 0, (c_1,\dots, c_n) \in M_1\times \dots \times M_n$$ with $M_i \subset I_i$. Let's say we want to minimize A. I can just make $M_1$ to $M_n$ arbitrarily small (but contained in your search space) so that your chance of finding a tuple $(c_1^*, \dots, c_n^*)$, which minimizes A, becomes arbitrarily small. As such, you would need an increasingly larger number of trials to yield a probability of >= 95 % to find hyperparameters "that are useful". In fact, if I chose an $M_i$ as a null set the chance would be zero (or, more precisely, finding an optimal Hyperparameter would have probability zero). You can find counterexamples for any random sampler you choose. Therefore, you can construct examples, such that all but finitely many hyperparameter tuples are terrible. As others have stated, the meaning of "top 5%" is of key importance. In my example, this would still mean they are equally as terrible as the other 95 %, because they yield the same algorithm performance.