Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

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)}.