Evolving a Vector Space with any Generating Set
This provides a more general and efficient solution for evolutionary computation in vector spaces, addressing limitations in previous methods, though it is incremental in refining existing theoretical frameworks.
The paper tackles the problem of evolving a normed vector space in Valiant's model of evolution, showing that it can be achieved with any generating set, requiring only Õ(1/ε²) steps and offering stability, agnosticism, and target drift handling.
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 $ε$-close as desired from the optimal one, for any required $ε>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/ε^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.