Learning DNF by Statistical and Proper Distance Queries Under the Uniform Distribution

摘要

We show that s-term DNF formulas can be learned under the uniform distribution in quasi-polynomial time with statistical queries of tolerance Ω(ε/s). The tolerance improves on the known tolerance Ω(ε~2/s) and is optimal with respect to its dependence on the error parameter ε. We further consider the related model of learning with proper distance queries and show that DNF formulas can be learned under the uniform distribution with quasi-polynomial queries, where the hypotheses are DNF formulas of polynomial size. Finally we consider the class of majorities over DNF formulas and provide polynomially related upper and lower bounds for the number of distance queries required to learn this class.