Learning DNF Expressions from Fourier Spectrum

Details Learning DNF Expressions from Fourier Spectrum Learning DNF Expressions from Fourier Spectrum

2012-03-03

arxiv.org/abs/1203.0594v1

Computer Science

Learning

Scientific paper

Since its introduction by Valiant in 1984, PAC learning of DNF expressions remains one of the central problems in learning theory. We consider this problem in the setting where the underlying distribution is uniform, or more generally, a product distribution. Kalai, Samorodnitsky and Teng (2009) showed that in this setting a DNF expression can be efficiently approximated from its "heavy" low-degree Fourier coefficients alone. This is in contrast to previous approaches where boosting was used and thus Fourier coefficients of the target function modified by various distributions were needed. This property is crucial for learning of DNF expressions over smoothed product distributions, a learning model introduced by Kalai et al. (2009) and inspired by the seminal smoothed analysis model of Spielman and Teng (2001). We give a new, simple algorithm for approximating any polynomial-size DNF expression from its "heavy" low-degree Fourier coefficients alone. Our algorithm greatly simplifies the proof of learnability of DNF expressions over smoothed product distributions. We also describe an application of our algorithm to learning monotone DNF expressions over product distributions. Building on the work of Servedio (2001), we give an algorithm that runs in time $\poly((s \cdot \log{(s/\eps)})^{\log{(s/\eps)}}, n)$, where $s$ is the size of the DNF expression and $\eps$ is the accuracy. This improves on $\poly((s \cdot \log{(ns/\eps)})^{\log{(s/\eps)} \cdot \log{(1/\eps)}}, n)$ bound of Servedio (2001). Another advantage of our algorithm is that it can be applied to a large class of polynomial threshold functions whereas previous algorithms for both applications relied on the function being a polynomial-size DNF expression.

Affiliated with

Also associated with

No associations

Rating

Learning DNF Expressions from Fourier Spectrum does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Learning DNF Expressions from Fourier Spectrum, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Learning DNF Expressions from Fourier Spectrum will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-344713