<p>The theorem is about optimization algorithms that take in a loss function <span class="math-container">$f$</span> over some space <span class="math-container">$\mathcal{X}$</span>, visit a sequence of <span class="math-container">$n$</span> points <span class="math-container">$x_1, x_2, \cdots x_n$</span>, and return the points they have seen minimizing the loss. When the sequence of visited points does not repeat, i.e. exactly <span class="math-container">$n$</span> distinct points are evaluated, the theorem says that the expected value of the output is identical between all algorithms, where the expectation is over all loss functions from some admissible class. If the algorithm is allowed to visit the same point multiple times (called resampling in the above), it could in principle set <span class="math-container">$x_1 = x_2 = \cdots = x_n$</span> and thus output the minimum element from a set of size <span class="math-container">$1$</span>, which for most loss functions (from an appropriate class) is worse than returning the minimum element from a set of size <span class="math-container">$n$</span> as would an algorithm that attempted to do anything (e.g. random sampling <span class="math-container">$x_i$</span> without replacement).</p>

CC BY-SA 4.0
2022-03-20T23:13:50.267Z
2022-03-20T23:13:50.267Z
Yonatan N
<p>The No Free Lunch theorems for search and optimization demonstrate that for search/optimization problems in a limited search space, where the points being searched through are not resampled, the performance of any two given search algorithms over all possible problems is the same.</p>
<p><strong>No Free Lunch for Search/Optimization</strong></p>
<p><em>The no free lunch theorem for search and optimization (Wolpert and Macready 1997) applies to finite spaces and algorithms that do not resample points. All algorithms that search for an extremum of a cost function perform exactly the same when averaged over all possible cost functions. So, for any search/optimization algorithm, any elevated performance over one class of problems is exactly paid for in performance over another class.</em></p>
<p>I have not clear the meaning of <strong>algorithms that do not resample points</strong></p>
<ol>
<li><p>What can be an example of an algorithm that do not resample points and one that resample points?</p>
</li>
<li><p>Finally, why does the theorem not apply for algorithms that implement resampling of points?</p>
</li>
</ol>

<it.information-theory>
meaning of "algorithms that do not resample points" in the algorithms that do not resample points theorem
Gianni Spear
# meaning of "algorithms that do not resample points" in the algorithms that do not resample points theorem

(Asked by: username_0 on 2022-03-20)

The No Free Lunch theorems for search and optimization demonstrate that for search/optimization problems in a limited search space, where the points being searched through are not resampled, the performance of any two given search algorithms over all possible problems is the same.

**No Free Lunch for Search/Optimization**

*The no free lunch theorem for search and optimization (Wolpert and Macready 1997) applies to finite spaces and algorithms that do not resample points. All algorithms that search for an extremum of a cost function perform exactly the same when averaged over all possible cost functions. So, for any search/optimization algorithm, any elevated performance over one class of problems is exactly paid for in performance over another class.*

I have not clear the meaning of **algorithms that do not resample points**

1. What can be an example of an algorithm that do not resample points and one that resample points?
2. Finally, why does the theorem not apply for algorithms that implement resampling of points?

**Tags:** it.information-theory


---

## 1 answers

### Answer by username_1 on 2022-03-20. Score: 2

The theorem is about optimization algorithms that take in a loss function $f$ over some space $\mathcal{X}$, visit a sequence of $n$ points $x\_1, x\_2, \cdots x\_n$, and return the points they have seen minimizing the loss. When the sequence of visited points does not repeat, i.e. exactly $n$ distinct points are evaluated, the theorem says that the expected value of the output is identical between all algorithms, where the expectation is over all loss functions from some admissible class. If the algorithm is allowed to visit the same point multiple times (called resampling in the above), it could in principle set $x\_1 = x\_2 = \cdots = x\_n$ and thus output the minimum element from a set of size $1$, which for most loss functions (from an appropriate class) is worse than returning the minimum element from a set of size $n$ as would an algorithm that attempted to do anything (e.g. random sampling $x\_i$ without replacement).


---

