Computer Science Seminar
Dimitris Diochnos
University of Virginia, Department of Computer Science
On the evolution of monotone conjunctions: drilling for best approximations
Abstract: About a decade ago, Valiant introduced a formal model for evolution. The
purpose is to allow and explain the evolution of complex mechanisms in
realistic population sizes within realistic time periods. Due to a simulation
result by Feldman, evolvability is equivalent to learning with correlational
statistical queries and as a consequence monotone conjunctions are evolvable
over any fixed distribution.
However, in this talk, we will discuss the evolution of monotone conjunctions
using an intuitive neighborhood that was first used by Valiant in the paper
that introduced evolvability. Building on the ideas of Diochnos and Turan from
a 2009 paper, we will extend the evolutionary mechanism and allow convergence
over binomial distributions. We will also provide uniform convergence results
for appropriate classes of binomial distributions and thus provide results that
lie somewhere between distribution-specific and distribution-independent
learning. Finally, we will also discuss connections between Valiant's model
and evolutionary/genetic algorithms as the model is presented.
Tuesday March 7, 2017 at 2:00 PM in SEO 427