Abstract:

Statistical query (SQ) learning (Kearns, 1993) model is a restriction of Valiant's learning model (1984) that models learning from statistical properties of examples rather than from individual examples. Almost all known learning algorithms can be expressed using statistical queries making the SQ complexity of learning useful in understanding the complexity of learning in general. In addition, SQ learning is closely related to Valiant's (2006) model of evolvability where evolution is modeled as a learning process.

In this talk I will give an overview of the techniques for characterizing and evaluating the SQ complexity of learning and describe two recent applications of these techniques to evolvability. The first application resolves the question of whether Boolean conjunctions are evolvable distribution-independently. The second application gives a simple algorithm for evolving linear threshold functions.