Attribute-Efficient Evolvability of Linear Functions
  In a seminal paper, Valiant (2006) introduced a computational model for
evolution to address the question of complexity that can arise through
Darwinian mechanisms. Valiant views evolution as a restricted form of
computational learning, where the goal is to evolve a hypothesis that is close
to the ideal function. Feldman (2008) showed that (correlational) statistical
query learning algorithms could be framed as evolutionary mechanisms in
Valiant's model. P. Valiant (2012) considered evolvability of real-valued
functions and also showed that weak-optimization algorithms that use
weak-evaluation oracles could be converted to evolutionary mechanisms.
  In this work, we focus on the complexity of representations of evolutionary
mechanisms. In general, the reductions of Feldman and P. Valiant may result in
intermediate representations that are arbitrarily complex (polynomial-sized
circuits). We argue that biological constraints often dictate that the
representations have low complexity, such as constant depth and fan-in
circuits. We give mechanisms for evolving sparse linear functions under a large
class of smooth distributions. These evolutionary algorithms are
attribute-efficient in the sense that the size of the representations and the
number of generations required depend only on the sparsity of the target
function and the accuracy parameter, but have no dependence on the total number
of attributes.
