Paul Valiant
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. Towards this end, we introduce a simple and natural algorithm that we call wide-scale random noise and prove a corresponding result for the L2 metric. We conjecture that the algorithm works for a more general class of metrics.
- K. Ball. 1997. An elementary introduction to modern convex geometry. MSRI Pub. 31.Google Scholar
- V. Feldman. 2008. Evolvability from learning algorithms. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC’08). 619--628. Google ScholarDigital Library
- V. Feldman. 2009a. A complete characterization of statistical query learning with applications to evolvability. In Proceedings of the 50th Annual Symposium on Foundations of Computer Science (FOCS’09). Google ScholarDigital Library
- V. Feldman. 2009b. Robustness of evolvability. In Proceedings of the 22nd Conference on Learning Theory (COLT’09).Google Scholar
- V. Feldman. 2011. Distribution-independent evolvability of linear threshold functions. In Proceedings of the 24th Annual Conference on Learning Theory (COLT’11).Google Scholar
- D. Haussler. 1992. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Inform. Computat. 100, 1, 78--150. Google ScholarDigital Library
- A. Kalai and S. Vempala. 2006. Simulated annealing for convex optimization. Math. Oper. Res. 31, 2, 253--266. Google ScholarDigital Library
- V. Kanade. 2011. Evolution with recombination. In Proceedings of the 52nd Annual Symposium on Foundations of Computer Science (FOCS’11). Google ScholarDigital Library
- V. Kanade, L. Valiant, and J. Vaughan. 2010. Evolution with drifting targets. In Proceedings of the 23rd Conference on Learning Theory (COLT’10).Google Scholar
- M. Kearns. 1998. Efficient noise-tolerant learning from statistical queries. J. ACM 25, 6, 983--1006. Google ScholarDigital Library
- A. Livnat, C. Papadimitriou, J. Dushoff, and M. Feldman. 2008. A mixability theory for the role of sex in evolution. Proc. Nat. Acad. Sci. 105, 50.Google ScholarCross Ref
- A. Livnat, C. Papadimitriou, N. Pippenger, and M. Feldman. 2009. Sex, mixability, and modularity. Proc. Nat. Acad. Sci. 107, 4.Google Scholar
- L. Lovász. 1986. An Algorithmic Theory of Numbers, Graphs, and Convexity. SIAM, Chapter 2. Google ScholarDigital Library
- L. Michael. 2012. Evolvability via the Fourier tranform. Theor. Comput. Sci. 462, 88--98. Google ScholarDigital Library
- Y. Nesterov and B. Polyak. 2009. Cubic regularization of Newton method and its global performance. Math. Program. 108, 1, 177--205. Google ScholarDigital Library
- L. Valiant. 2009. Evolvability. J. ACM 56, 1. Google ScholarDigital Library
Index Terms
- Evolvability of Real Functions
Recommendations
Evolvability from learning algorithms
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computingValiant has recently introduced a framework for analyzing the capabilities and the limitations of the evolutionary process of random change guided by selection. In his framework the process of acquiring a complex functionality is viewed as a ...
Evolvability tradeoffs in emergent digital replicators
The role of historical contingency in the origin of life is one of the great unknowns in modern science. Only one example of life exists-one that proceeded from a single self-replicating organism or a set of replicating hypercycles to the vast ...
Evolvability Search: Directly Selecting for Evolvability in order to Study and Produce It
GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016One hallmark of natural organisms is their significant evolvability, i.e.,their increased potential for further evolution. However, reproducing such evolvability in artificial evolution remains a challenge, which both reduces the performance of ...
Comments