Background 3

Question 1

Explain No free lunch theorem in optimization

Answer 1

The average performance across all problems is the same for all algorithms, there is no such thing as a best optimization algorithm

if you have an algorithm that is better than random search on some problems, then there are other problems may not work.

Question 2

Explain Curse of Dimensionality ?

What could help with this?

Answer 2

the volume of the search space increases (exponentially) fast with the dimension

separable problem may help

Question 3

comparison-based vs. value-based optimization

Answer 3

• comparison-based algorithms converge linearly at best
• discontinuity doesn’t make difference in comparison based.
• value based will Fail that if discontinuity.