|
Abstract:
|
Schumacher, Vose & Whitley have shown that Wolpert & MacReady's celebrated No Free Lunch theorem applies only to classes of target functions which are closed under permutation (c.u.p.). In the same paper, Schumacher et al. demonstrated that there exist both highly compressible and highly incompressible classes of objective functions for which NFL applies. However, I will show that there is a free lunch for the class of all n-compressible target functions f : X -> Y given reasonable conditions on n, |X| and |Y|. While previous authors have considered NFL in the context of some form of complexity restriction on function classes, this paper appears to be the first to contain a proof using the general measure of Kolmogorov complexity.
|
