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
$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.
Users
Please
log in to take part in the discussion (add own reviews or comments).