DNF Are Teachable in the Average Case.

Homin K. Lee Rocco A. Servedio Andrew Wan

Published in: COLT (2006)

Keyphrases

average case
uniform distribution
boolean functions
pac learning
worst case analysis
membership queries
learning curves
target concept
worst case
agnostic learning
dnf formulas
learning theory
average case complexity
data sets
concept learning
sample complexity bounds
learning algorithm