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 @math -close as desired from the optimal one, for any required @math . Several previous positive results exist that can be related to evolving a vector space, but each former result imposes restrictions either on (re)initialisations, distributions, performance functions and or the mutator. In this paper, we show that all it takes to evolve a complete normed vector space is merely a set that generates the space. Furthermore, it takes only @math steps and it is essentially strictly monotonic, agnostic and handles target drifts that rival some proven in fairly restricted settings. In the context of the model, we bring to the fore new results not documented previously. Evolution appears to occur in a mean-divergence model reminiscent of Markowitz mean-variance model for portfolio selection, and the risk-return efficient frontier of evolution shows an interesting pattern: when far from the optimum, the mutator always has access to mutations close to the efficient frontier. Toy experiments in supervised and unsupervised learning display promising directions for this scheme to be used as a (new) provable gradient-free stochastic optimisation algorithm.
Our main result suffers none of these downsides: our mutator meets time and space optimality properties (Section ), we do not change the set of mutations (Section ), we do not do restart. Also, our evolvability scheme is agnostic (Section ), stable (Section ) and handles significant drift (Section ). Finally, instead of fixed-degree polynomials, we consider any finite-valued function @math . Thus, we can evolve functions with infinite Taylor expansion, something @cite_1 does not cover It is also not clear whether a simple trick to extend @cite_1 --- replacing variables by bounded functions --- is possible without endangering the distribution support assumption or the complexity parameters. . Finally, our mutator yields an extremely simple and provable evolutionary scheme, implementable using few lines of code as sketched in Algorithm ( ).
@cite_1
2130700086
We consider the problem of predicting a random variable X from observations, denoted by a random variable Z. It is well known that the conditional expectation E[X|Z] is the optimal L sup 2 predictor (also known as "the least-mean-square error" predictor) of X, among all (Borel measurable) functions of Z. In this orrespondence, we provide necessary and sufficient conditions for the general loss functions under which the conditional expectation is the unique optimal predictor. We show that E[X|Z] is the optimal predictor for all Bregman loss functions (BLFs), of which the L sup 2 loss function is a special case. Moreover, under mild conditions, we show that the BLFs are exhaustive, i.e., if for every random variable X, the infimum of E[F(X,y)] over all constants y is attained by the expectation E[X], then F is a BLF.