Efficient noise-tolerant learning from statistical queries

By Michael Kearns. 1993

In this paper, we study the problem of learning in the presence of classification noise in the probabilistic learning model of Valiant and its variants. In order to identify the class of “robust” learning algorithms in the most general way, we formalize a new but related model of learning from statistical queries. Intuitively, in this model, a learning algorithm is forbidden to examine individual examples of the unknown target function, but is given access to an oracle providing estimates of probabilities over the sample space of random examples. One of our main results shows that any class of functions learnable from statistical queries is in fact learnable with classification noise in Valiant’s model, with a noise rate approaching the informationtheoretic barrier of 1/2. We then demonstrate the generality of the statistical query model, showing that practically every class learnable in Valiant’s model and its variants can also be learned in the new model (and thus can be learned in the presence of noise). A notable exception to this statement is the class of parity functions, which we prove is not learnable from statistical queries, and for which no noise-tolerant algorithm is known.

Citations in the corpus

• Fairness Through Computationally-Bounded Awareness (2018, neutral): “In general, agnostic learning is considered a notoriously hard computational problem [15, 17, 8]; that said, in the context of fairness in machine learning, [16] show that using heuristic methods to agnostically learn linear hypotheses seems to work well in practice.”
• Machine Unlearning (2019, neutral): “Statistical Query Learning: Cao et al. [15] model unlearning in the statistical query learning framework [36].”
• A reliable effective terascale linear learning system (2011, unknown): “In general, any statistical query algorithm (Kearns, 1993) can be parallelized with AllReduce with only a handful of additional lines of code.”
• Learning with Symmetric Label Noise: The Importance of Being Unhinged (2015, unknown): “The problem of learning with symmetric label noise ( SLN learning ) is the following [Angluin and Laird, 1988, Kearns, 1998, Blum and Mitchell, 1998, Natarajan et al., 2013].”
• Practical privacy: the SuLQ framework (2005, unknown): “5 Capturing the Statistical Queries Learning Model The Statistical Query model, proposed by Kearns in [10], is a framework for examining statistical algorithms executed on samples drawn independently from an underlying distribution.”
• Learning with Annotation Noise (2009, unknown): “It is assumed, often tacitly, that the kind of noise existing in human-annotated datasets used in computational linguistics is random classification noise (Kearns, 1993; Angluin and Laird, 1988), resulting from annotator attention slips randomly distributed across instances.”
• Simple and Scalable Response Prediction for Display Advertising (2014, unknown): “In general, any statistical query algorithm [Kearns 1993] code.”
• Machine Unlearning for Random Forests (2020, unknown): “More recently, Cao & Yang (2015) developed deletion mechanisms for several models that fall under the umbrella of non-adaptive SQ-learning (Kearns, 1998) in which data deletion is efficient and exact (e.g. naive Bayes, item-item recommendation, etc.); Schelter (2020) has also developed decremental up”
• DART: Data Addition and Removal Trees (2020, unknown): “…introduced the concept of model unlearning, recognizing that a certain class of models (e.g. naive Bayes) fall under the umbrella of SQ-learning (Kearns 1998), where data deletion is efficient and exact; Schelter (2020) has also developed decremental update procedures for similar classes of…”
• Noise Tolerance Under Risk Minimization (2011, unknown): “Noise tolerant learning using statistical queries [8] is on e such approach.”
• Vox Populi: Collecting High-Quality Labels from a Crowd (2009, unknown): “A somewhat related problem is designing machine learning algorithms that withstand spe-cific types of label-noise, either on the training set [KL93, Kea98], or on the test set [TGRS07, DS08].”
• A Survey of Methods for Scaling Up Inductive Algorithms (1999, unknown): “learning from statistical queries (Kearns, 1993)).”
• Part-dependent Label Noise: Towards Instance-dependent Label Noise (2020, unknown): “Specifically, RCN assumes that clean labels flip randomly with a constant rate [1, 4, 24]; CCN assumes that the flip rate depends on the latent clean class [40, 18, 75]; IDN considers the most general case of label noise, where the flip rate depends on its instance.”
• Quantum variational algorithms are swamped with traps (2022, unknown): “This is analogous to the classical setting where parity functions are hard to learn in the noisy SQ setting, but ef fi cient to learn using simple linear regression 29 .”