meaning of "algorithms that do not resample points" in the algorithms that do not resample points theorem

Question

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?

Answer 1

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