Abstract
Johannes Köbler and Wolfgang Lindner
Abstract:
We extend the notion of general dimension, a combinatorial
characterization of learning complexity for arbitrary query
protocols, to encompass approximate learning. This immediately
yields a characterization of the learning complexity in the
statistical query model. As a further application, we consider
approximate learning of DNF formulas and we derive close upper and
lower bounds on the number of statistical queries needed. In
particular, we show that with respect to the uniform distribution,
and for any constant error parameter \varepsilon < 1/2, the number of
statistical queries needed to approximately learn DNF formulas (over
n variables and s terms) with tolerance \tau= \Theta(1/s) is
n^{\Theta(\log s)}.