[Brown CS Talks] Brown CS Seminar: Rocco Servedio in Lubrano on 4/1/02 at noon

[talks-admin@list.cs.brown.edu]

			      CS Seminar
		  
		  The Department of Computer Science
			   BROWN UNIVERSITY

			      
			       presents

			    Rocco Servedio

			  
			  Harvard University

				 
		    Monday, April 1, 2002 at noon
	       Lubrano Conference Room (CIT 4th floor)
	       Refreshments will be served at 11:45 am


		 Frontiers of Efficient Learnability

 
			       Abstract

Machine learning techniques now play an important role in many real
world systems.  As these applications proliferate, the need for
provably effective and efficient learning algorithms has become more
acute.  A central goal in machine learning theory is to construct such
computationally efficient learning algorithms for expressive classes
of Boolean functions.  In this talk we describe three recent results
along these lines which significantly extend the frontiers of
efficient learnability.

We first present the fastest known algorithm for one of the major open
problems in machine learning: learning an unknown disjunctive normal
form formula, or DNF, from labeled examples.  At the heart of our
approach is a new upper bound for expressing DNF formulas as
thresholded polynomials.  This bound matches a longstanding lower
bound for DNF due to Minsky and Papert from 1968 and is of independent
complexity-theoretic interest.

Next we present a uniform distribution learning algorithm for constant
depth Boolean circuits composed of AND, OR, NOT and MAJORITY
gates. This is the first algorithm for learning a more expressive
circuit class than the class $AC^0$ of constant-depth AND/OR/NOT
circuits, a class which was shown to be learnable in quasipolynomial
time by Linial, Mansour and Nisan in 1989.  We also give cryptographic
evidence that our new learning algorithm is essentially optimal with
respect to both its running time and the expressive power of the
circuits it can learn.

Finally we describe some recent results on learning neural networks.
While neural network learning has been intensively studied for many
years, to date very few provably efficient algorithms have been given
for learning neural networks from random examples only.  We present
the first provably efficient algorithm for learning a broad class of
neural networks from uniform random examples.

A recurring theme in the talk, illustrated by each of the results
described above, is that machine learning theory has much to gain from
ideas and interactions with other areas such as computational
complexity, cryptography, and discrete probability.


		     Host:  Professor Steve Reiss