Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR11-089 | 16th January 2012 21:39

Distribution Free Evolvability of Polynomial Functions over all Convex Loss Functions

RSS-Feed




Revision #1
Authors: Paul Valiant
Accepted on: 16th January 2012 21:39
Downloads: 2985
Keywords: 


Abstract:

We formulate a notion of evolvability for functions with domain and range that are real-valued vectors, a compelling way of expressing many natural biological processes. We show that linear and fixed-degree polynomial functions are evolvable in the following dually robust sense: There is a single evolution algorithm that for all convex loss functions converges for all distributions.

It is possible that such dually robust results can be achieved by simpler and more natural evolution algorithms. In the second part of the paper we introduce a simple and natural algorithm that we call "wide-scale random noise" and prove a corresponding result for the $L_2$ metric. We conjecture that the algorithm works for more general classes of metrics.


Paper:

TR11-089 | 7th June 2011 00:40

Distribution Free Evolvability of Polynomial Functions over all Convex Loss Functions





TR11-089
Authors: Paul Valiant
Publication: 10th June 2011 09:41
Downloads: 3038
Keywords: 


Abstract:

We formulate a notion of evolvability for functions with domain and range that are real-valued vectors, a compelling way of expressing many natural biological processes. We show that linear and fixed degree polynomial functions are evolvable in the following dually robust sense: There is a single evolution algorithm that for all convex loss functions converges for all distributions. Existing results suggest that for Boolean function evolution no correspondingly general result is possible.

It is possible that such dually robust results can be achieved by simpler and more natural evolution algorithms. In the second part of the paper we introduce a simple and natural algorithm that we call "wide-scale random noise" and prove a corresponding result for the L_2 metric. We conjecture that the algorithm works for more general classes of metrics.



ISSN 1433-8092 | Imprint