0
$\begingroup$

Recently, I posted a question about a very interesting property of the Random Search Algorithm (The "Amazing Hidden Power" of Random Search?), in particular - in the context of function optimization, regardless of the number of dimensions your data set has, Random Search can return a result that has a 0.95 probability of being in the top 5% of all solutions, in only 60 iterations!

However, many people provided very useful analysis and comments on this property of Random Search, indicating that in most real world problems, solutions within the top 5% are often insufficient - and we often want solutions in the top 1%. Unfortunately, the number of iterations required to reach a solution in the top 1% of all solution far exceeds (exponentially) 60 iterations.

One of the users (@ Thomas Lumley) posted an (amazing) answer to this question that related Random Search to the (famous) "No Free Lunch Theorem":

enter image description here

Regarding this (amazing) answer, I am trying to understand the "nature of the discrete function F", and as well why the proposition outlined is true (i.e. Over all Functions, Random Search will perform the best).

First Part: Regarding the first part, here is how I understand the set-up:

enter image description here

Suppose you have a class of functions (N number of such functions exist) where the input can be all strings of length 3 involving the first 3 letters of the (English) Alphabet "A, B, C" - and the output of this class of functions is a discrete number between 0-1000. From this set of functions, if you you take one of these functions (e.g."F1"), and using the Random Search algorithm, randomly evaluate F1 for "n" iterations - and finally select the iteration which gave you the largest value within these "n" iterations. Is the gist of the example?

Part 2: How is it possible to prove that in the above example, for all functions "F1 to Fn" Random Search will definitely perform better than any other optimization algorithm?
Informally, I can accept this fact - perhaps some of these functions might have completely random structures in which some optimization algorithm other than Random Search (e.g. Gradient Descent) might be at a disadvantage - but using math, how can we prove that in the above example, Random Search will provide the best possible results when averaged over all such functions?

Can someone please comment on this?

Thanks!

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ The NFL theorem doesn't say that "random search will definitely perform better than any other optimization algorithm". Rather, it says that all optimization algorithms have equal performance (when averaged over all objective functions) i.e. no algorithm can beat any other in this context. $\endgroup$
    – user20160
    Commented Jan 23, 2022 at 22:03
  • 2
    $\begingroup$ That's not quite true: an algorithm that tries $n$ function evaluations and reports the worst one does worse than random search. $\endgroup$
    – Thomas Lumley
    Commented Jan 24, 2022 at 1:16
  • $\begingroup$ @ Thomas Lumley: thank you for your reply! I wasn't sure how about the details! $\endgroup$
    – stats_noob
    Commented Jan 24, 2022 at 1:29
  • 2
    $\begingroup$ @ThomasLumley I think the situation you described falls outside the scope of the NFL results from Wolpert & Macready (1996). They consider performance to be evaluated based on the set of function values seen during optimization. As they define it, an optimization algorithm can't choose which value to report (or lie about the optimal value). Its job is simply to choose the next point at which the function is evaluated. At least under the specific conditions they define, any algorithm that loses to random search on some problems must beat it on others (and vice versa). $\endgroup$
    – user20160
    Commented Jan 24, 2022 at 3:07
  • $\begingroup$ thank you everyone for your comments! it's a really interesting example (i.e. no free lunch and random search), and I am really interested in learning more about it! I appreciate all your comments! $\endgroup$
    – stats_noob
    Commented Jan 24, 2022 at 3:09

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.