The Fundamental Learning Problem that Genetic Algorithms with Uniform
  Crossover Solve Efficiently and Repeatedly As Evolution Proceeds
  This paper establishes theoretical bonafides for implicit concurrent
multivariate effect evaluation--implicit concurrency for short---a broad and
versatile computational learning efficiency thought to underlie
general-purpose, non-local, noise-tolerant optimization in genetic algorithms
with uniform crossover (UGAs). We demonstrate that implicit concurrency is
indeed a form of efficient learning by showing that it can be used to obtain
close-to-optimal bounds on the time and queries required to approximately
correctly solve a constrained version (k=7, \eta=1/5) of a recognizable
computational learning problem: learning parities with noisy membership
queries. We argue that a UGA that treats the noisy membership query oracle as a
fitness function can be straightforwardly used to approximately correctly learn
the essential attributes in O(log^1.585 n) queries and O(n log^1.585 n) time,
where n is the total number of attributes. Our proof relies on an accessible
symmetry argument and the use of statistical hypothesis testing to reject a
global null hypothesis at the 10^-100 level of significance. It is, to the best
of our knowledge, the first relatively rigorous identification of efficient
computational learning in an evolutionary algorithm on a non-trivial learning
problem.
