title: A Probabilistic Reformulation of No Free Lunch: Continuous Lunches Are Not Free.
abstract: No Free Lunch (NFL) theorems have been developed in many settings over the last two decades. Whereas NFL is known to be possible in any domain based on set-theoretic concepts, probabilistic versions of NFL are presently believed to be impossible in continuous domains. This article develops a new formalization of probabilistic NFL that is sufficiently expressive to prove the existence of NFL in large search domains, such as continuous spaces or function spaces. This formulation is arguably more complicated than its set-theoretic variants, mostly as a result of the numerous technical complications within probability theory itself. However, a probabilistic conceptualization of NFL is important because stochastic optimization methods inherently need to be evaluated probabilistically. Thus the present study fills an important gap in the study of performance of stochastic optimizers.
authors.affiliation: CS Disco, Inc., 4400 Post Oak Pkwy, Suite 2700, Houston, TX, 77027, USA alan.lockett@gmail.com.
authors.forename: Alan J
authors.initials: AJ
authors.lastname: Lockett
authors.affiliation: Department of Computer Science, University of Texas, Austin, TX, 78712, USA risto@cs.utexas.edu.
authors.forename: Risto
authors.initials: R
authors.lastname: Miikkulainen
mesh_terms: D000465:Algorithms; D003198:Computer Simulation; D057386:Search Engine / Q000379:methods*; D012984:Software / Q000592:standards*
keywords: Analysis of optimization; NFL Identification Theorem; No Free Lunch