A Query Algorithm for Agnostically Learning DNF
Parikshit Gopalan, Adam Tauman Kalai, Adam R. Klivans · 2008
function and let C be a concept class where each concept has size at most t. Define opt = min c∈C Pr x∈{−1,1}n [c(x) 6 = f(x)] where x is chosen uniformly at random from {−1, 1}n. We say that C is agnostically learnable with queries with respect to the uniform distribution if there exists an algorithm that– given black box access to any f – runs in time poly(n, t, −1) and outputs a hypothesis h such that Pr x∈{−1,1}n [h(x) 6 = f(x)] ≤ opt+ . The algorithm may be randomized, in which case it must output such an h with high probability. The main question is as follows: are polynomial-size DNF formulas agnostically learnable with queries with re-spect to the uniform distribution? A related question is, are halfspaces agnostically learnable with queries with respect to the uniform distribution? Motivation: One of the most celebrated results in com-putational learning theory is Jackson’s query algorithm for PAC learning DNF formulas with respect to the uniform dis-tribution [3]. A natural question is whether DNF formulas can be learned (even with queries and with respect to the uniform distribution) in a highly noisy setting, i.e., the well-known agnostic framework of learning [5]. Additionally, it is straightforward to see that an agnostic learning algorithm for DNF formulas would give algorithms for weakly learning polynomial-size depth-3 circuits with re-spect to the uniform distribution in the standard PAC learning model. Halfspaces are another simple and important concept class of functions still not known to be agnostically learnable with respect to the uniform distribution, even if the learner can make queries (although some relevant work exists for the uniform distribution that we mention below). Current status: Very recently, Gopalan et al. [2] have shown that the weaker concept class of decision trees are