Notes on NH Bshouty, E Mossel, R O’Donnel, and RA Servedio: Learning DNF from Random Walks

This is a set of notes for a paper from the learning theory reading group, which I’m posting here with some keywords so I can easily search for them. I doubt they’ll be useful for anyone else, but who knows?

These notes include notes on the following material which is a pre-requisite for understanding this paper:

Kushilevitz and Mansour First gave a polynomial time membership query algorithm for learning decision trees under the uniform distribution. Their algorithm uses a subroutine (often called KM), based on the list-decoding algorithm of Goldreich and Levin, which fnds and estimates all “large” Fourier coefficients of the target function using membership queries. Subsequently Jackson extended the KM algorithm and combined it with the hypothesis boosting algorithm of Freund to give the Harmonic Sieve algorithm, which uses membership queries to learn DNF under the uniform distribution in polynomial time. Bshouty and Feldman later observed that a certain algorithmic variant of KM, which they called the Bounded Sieve, is all that is necessary for Jackson’s algorithm to work.

Dr. O’Donnel has some slides from a DNF survey talk here

Advertisements
Notes on NH Bshouty, E Mossel, R O’Donnel, and RA Servedio: Learning DNF from Random Walks

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s