Weakly learning DNF and characterizing statistical query learning using Fourier analysis

By Avrim Blum, Merrick L. Furst, Jeffrey C. Jackson, Michael Kearns, Yishay Mansour, S. Rudich. 1994

We present new results, both positive and negative, on the well-studied problem of learning disjunctive normal form (DNF) expressions. We first prove that an algorithm due to Kushilevitz and Mansour [16] can be used to weakly learn DNF using membership queries in polynomial time, with respect to the uniform distribution on the inputs. This is the first positive result for learning unrestricted DNF expressions in polynomial time in any nontrivial formal model of learning. It provides a sharp contrast with the results of Kharitonov [15], who proved that ACO is not efficiently learnable in the same model (given certain plausible cryptographic assumptions). We also present efficient learning algorithms in various models for the read-k and SAT-k subclasses of DNF. For our negative results, we turn our attention to the recently introduced statistical query model of learning [11]. This model is a restricted version of the popular Probably Approximately Correct (PAC) model [23], and practically every class known to be efficiently learnable in the PAC model is in fact learnable in the statistical query model [11]. Here we give a general characterization of the complexity of statistical query learning in terms of the number of uncorrelated functions in the concept class. This is a distributiondependent quantity yielding upper and lower bounds on the number of st atistical queries required for learning on any input distribution. As a corollary, we obtain that DNF expressions and decision trees are not even weakly learnable with ●This research M sponsored in part by the Wr]ght Laboratory, Aeronautical Systems Center, Air Force Materiel Command, USAF, and the Advanced Research Projects Agency (ARPA) under grant number F33615-93-1-1330 Support also M sponsored by the National Sc]ence Foundation under Grant No CC-91 19319. Blum also supported m part by NSF National Young Investigator grant CCR9357793 Views and conclusions contained in this document are those of the authors and should not be interpreted as necessarily representing official po!lcles or endorsements, either expressed or implied, of Wright Laboratory or the United States Government, or NSF tcontact ~“thor Address: AT&T Bell Laboratcmes, Room 2A423, 600 Mountain Avenue, P.O. Box 636, Murray Hill, NJ 07974 Electronic mail. mkearns@research .at t corn ~Thi~ research ~a~ ~“pported in p~~t by The Israel science Foun. datlon administered by The Israel Academy of Sc]ence and Humanities and by a grant of the Israeli Ministry of Science and Technology Permission to co y without fee all or part of this material is granted provided%atthe copies are not madeordistrftrutectfor direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association of Computing Machinery. To copy otherwise, or to republish, requires a fee ancf/or specific permission. STOC 945/94 Montreal, Quebec, Canada Q 1994 ACM 0-89791 -663-8/94/0005..$3.50 respect to the uniform input distribution in polynomial time in the statistical query model. This result is informationtheoretic and therefore does not rely on any unproven assumptions. It demonstrates that no simple modification of the existing algorithms in the computaticmal learning theory literature for learning various restricted forms of DNF and decision trees from passive random examples (and also several algorithms proposed in the experimental machine learning communities, such as the ID3 algorithm for decision trees [22] and its variants) will solve the general problem. The unifying tool for all of our results is the Fourier analysis of a finite class of boolean functions 011 the hypercube.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Adversarial examples from computational constraints (2018, methodology): “To show an SQ lower bound, we use – as in [4] – the framework of [2, 8] to reduce the question to computing a certain non-standard notion of correlation between the distributions.”
SGD Learns the Conjugate Kernel Class of the Network (2017, background): “Unfortunately, this approach it is probably doomed to fail, as implied by various computational hardness results [Blum and Rivest, 1989, Kearns and Valiant, 1994, Blum et al., 1994, Kharitonov, 1993, Klivans and Sherstov, 2006, 2007, Daniely et al., 2014, Daniely and Shalev-Shwartz, 2016]. So, what ”
VC bounds on the cardinality of nearly orthogonal function classes (2010, background): “Our interest in this regime stems from applications in machine learning, where some characterizations and algorithms consider nearly orthogonal or decorrelated function classes [3,7,2].”
Learning DNF Expressions from Fourier Spectrum (2012, methodology): “As is wellknown (e.g. Blum et al., 1994), this implies that ‖t̂i‖1 = 1.”
Optimally-Smooth Adaptive Boosting and Application to Agnostic Learning (2002, result): “An algorithm M adaBoost constructed by Domingo and Watanabe [7] is smooth, but it is adaptive only for a non-increasing sequence of weak hypotheses accuracies (i.e., when γhi+1 ≤ γhi for 1 ≤ i ≤ T − 1). Besides, their result applies only to the case of binary-valued weak hypotheses, which seems to p”
Boosting and Hard-Core Set Construction (2003, methodology): “At the heart of Jackson’s Harmonic Sieve algorithm is a procedure WDNF which was first studied in Blum et al. (1994) .”
On the Complexity of Learning Neural Networks (2017, background): “Statistical dimension is a key concept in the study of SQ algorithms, and is known to characterize the query complexity of supervised learning via SQ algorithms [3, 19, 9].”
Sub-Task Decomposition Enables Learning in Sequence to Sequence Tasks (2022, background): “could not be efficiently learned by either Statistical Query algorithms (Kearns, 1998; Blum et al., 1994) or by noisy gradient descent1 on neural nets with polynomially many parameters (Kearns, 1998; Shalev-Shwartz et al.”
Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures (2016, background): “This complexity measure was introduced in [10] for PAC learning of Boolean functions and was recently generalized to the unsupervised setting [41], [38].”
Efficient noise-tolerant learning from statistical queries (1993, unknown): “Recent papers have provided more general solutions, again in the statistical query setting [Blum et al. 1994; Cohen 1997].”
Efficient Algorithms and Lower Bounds for Robust Linear Regression (2018, unknown): “This complexity measure was introduced in [BFJ + 94] for PAC learning of Boolean functions and was recently generalized to the unsupervised setting [FGR + 13, Fel16a].”
Quantum machine learning: a classical perspective (2017, background): “[156] showed that DNFs are not learnable under noise with respect to the uniform distribution.”
An efficient membership-query algorithm for learning DNF with respect to the uniform distribution (1994, methodology): “, who showed that for every DNF expression f there is a parity function that weakly approximates f with respect to the uniform distribution [10].”