*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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.
