Abstract
Valiant has recently introduced a framework for analyzing the capabilities and the limitations of the evolutionary process of random change guided by selection [24]. in his framework the process of acquiring a complex functionality is viewed as a substantially restricted form of PAC learning of an unknown function from a certain set of functions [23]. Valiant showed that classes of functions evolvable in his model are also learnable in the statistical query (SQ) model of Kearns [16] and asked whether the converse is true. We show that evolvability is equivalent to learnability by a restricted form of statistical queries. Based on this equivalence we prove that for any fixed distribution D over the instance space, every class of functions learnable by SQs over D is evolvable over D. Previously, only the evolvability of monotone conjunctions of Boolean variables over the uniform distribution was known [25]. On the other-hand, we prove that the answer to Valiant's question is negative when distribution-independent evolvability is considered. To demonstrate this, we develop a technique for proving lower bounds on evolvability and use it to show that decision lists and linear threshold functions are not evolvable in a distribution-independent way. This is in contrast to distribution-independent learnability of decision lists and linear threshold functions in the statistical query model. © Copyright 2008 ACM.