Abstract
In Valiant's model of evolution, a class of representations is evolvable iff a polynomial-time process of random mutations guided by selection converges with high probability to a representation as $\epsilon$-close as desired from the optimal one, for any required $\epsilon > 0$. Several previous positive results exist that can be related to evolving a vector space, but each former result imposes disproportionate representations or restrictions on (re)initialisations, distributions, performance functions and/or the mutator. In this paper, we show that all it takes to evolve a normed vector space is merely a set that generates the space. Furthermore, it takes only $\tilde{O}(1/\epsilon^2)$ steps and it is essentially stable, agnostic and handles target drifts that rival some proven in fairly restricted settings. Our algorithm can be viewed as a close relative to a popular fifty-years old gradient-free optimization method for which little is still known from the convergence standpoint: Nelder-Mead simplex method.
Introduction
Leslie Valiant’s 2009 framework for evolvability treats evolution as a polynomial-time machine learning process. A representation class is considered evolvable if random mutations and selection can drive an organism toward an optimal state with high probability. However, previous proofs of evolvability for vector spaces often relied on restrictive assumptions, such as specific data distributions (Gaussian or uniform), quadratic loss functions, or "reflexive" mutators that allow an organism to remain unchanged. This paper introduces a more general approach that removes these constraints, demonstrating that any generating set is sufficient to evolve a normed vector space in an agnostic, distribution-free environment.
The Simple-Evol-Gen Framework
The core of this work is the Simple-Evol-Gen algorithm. Unlike previous models requiring orthonormal bases, this algorithm utilizes any generating set $\mathcal{B}$ of the vector space. Mutations are generated by scaling vectors from $\mathcal{B}$ and adding or subtracting them from the current state.
The framework employs Bregman divergences to measure performance, encompassing a wide array of distance metrics like squared loss and KL divergence. Selection is based on categorizing mutations into beneficial (BENE) or neutral (NEUT) sets. Notably, the model uses non-reflexive neighborhoods, meaning the current organism is not its own neighbor, forcing active evolution to maintain or improve fitness.
Comparative Analysis and Results
The proposed algorithm achieves convergence to an $\epsilon$-close representation in $\tilde{O}(1/\epsilon^2)$ steps. It demonstrates strict monotonicity—performance increases at each step when far from the target—and maintains stability once the optimum is reached.
As shown in the comparative analysis above, the "Simple-Evol-Gen" approach (labeled 'us') satisfies a broader range of criteria than previous literature, including handling agnostic evolution and unknown distributions without restrictive loss assumptions. The algorithm's behavior mirrors the Nelder-Mead simplex method, providing a theoretical bridge between evolutionary biology and classical gradient-free optimization. Experimental validation in toy 2D simulations further confirms that the evolutionary path successfully navigates toward targets even in the presence of noise and non-separable data.
Discussion and Future Directions
While the results are robust for finite-dimensional normed vector spaces, scaling to higher dimensions remains a consideration as the "Evolvability Horizon" grows. Future research may explore extending these principles to non-linear representation classes and fully discrete genetic codes, moving closer to the complexities of biological "Evo-Devo" (Evolutionary Developmental biology) systems.
Summary updated