Noise-tolerant learning, the parity problem, and the statistical query model

By Avrim Blum, Adam Tauman Kalai, H. Wasserman. Symposium on the Theory of Computing, 2000

817 citations recorded by the source corpus.

We describe a slightly subexponential time algorithm for learning parity functions in the presence of random classification noise, a problem closely related to several cryptographic and coding problems. Our algorithm runs in polynomial time for the case of parity functions that depend on only the first O(log n log log n) bits of input, which provides the first known instance of an efficient noise-tolerant algorithm for a concept class that is not learnable in the Statistical Query model of Kearns [1998]. Thus, we demonstrate that the set of problems learnable in the statistical query model is a strict subset of those problems learnable in the presence of noise in the PAC model.In coding-theory terms, what we give is a poly(n)-time algorithm for decoding linear k × n codes in the presence of random noise for the case of k = c log n log log n for some c > 0. (The case of k = O(log n) is trivial since one can just individually check each of the 2k possible messages and choose the one that yields the closest codeword.)A natural extension of the statistical query model is to allow queries about statistical properties that involve t-tuples of examples, as opposed to just single examples. The second result of this article is to show that any class of functions learnable (strongly or weakly) with t-wise queries for t = O(log n) is also weakly learnable with standard unary queries. Hence, this natural extension to the statistical query model does not increase the set of weakly learnable functions.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/f87f327f64573fd79a5c3feabb608cf04837881c

How researchers see this paper

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

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

SWIFFT: A Modest Proposal for FFT Hashing (2008, methodology): “Finding one vector from each list such that the sum is 0 is essentially the k-list problem that was studied by Wagner [28], and is also related to the technique used by Blum, Kalai, and Wassserman [5] for solving the parity problem in the presence of noise.”
A Generalized Birthday Problem (2002, background): “Blum, Kalai, and Wasserman previously have independently discovered something closely related to the k-tree algorithm for xor in the context of their work on learning theory [5].”
A brief introduction to weakly supervised learning (2018, background): “There are many theoretical studies [4,10,35], among which most assumes random classification noise, i.”
Combating Noisy Labels by Agreement: A Joint Training Method with Co-Regularization (2020, methodology): “To alleviate this problem, data annotation companies choose some alternating methods such as crowdsourcing [39, 43] and online queries [3] to improve labelling efficiency.”
Lossy trapdoor functions and their applications (2008, background): “(Formal deﬁnitions, constructions, and proofs are given in Sections 3 and 4.)”
Complexity Theoretic Limitations on Learning DNF's (2014, background): “Also, 5 follows from the hardness of learning parities with noise2 [9], which is often taken as a hardness assumption.”
Lattice-Based Cryptography (2006, methodology): “The best combinatorial methods to find short vectors in q-ary lattices are variants of the algorithms presented [9, 79], e.”
Early-Learning Regularization Prevents Memorization of Noisy Labels (2020, background): “However, datasets with lower quality annotations, obtained for instance from online queries [5] or crowdsourcing [49, 53], may be available.”
A General Characterization of the Statistical Query Complexity (2016, methodology): “Their characterization has been strengthened and simplified in several subsequent works (Yang, 2001; Bshouty and Feldman, 2002; Blum et al., 2003; Yang, 2005) and applied to a variety of problems in learning theory (e.”
On agnostic boosting and parity learning (2008, methodology): “Learning parity with noise is a longstanding open problem in computational learning theory, which has attracted attention in recent years [4, 5, 20, 9, 10, 19, 17, 7], for several reasons.”
Simple Encrypted Arithmetic Library - SEAL v2.1 (2016, background): “To label the other attacks we follow the notation of [7]: ‘bkw’ denotes a variant [23] of the BKW attack [10, 5], ‘sis’ denotes a distinguishing attack as described in [32]; ‘dec’ denotes a decoding attack as described in e.”
Trapdoors for hard lattices and new cryptographic constructions (2008, background): “LWE can seen as a “unique decoding” problem on a certain family of random lattices, and is a generalization (to larger moduli) of the well-studied learning parity with noise problem, which is believed to be hard and has seen many applications in cryptography (e.g., [ BKW03 , HB01, JW05, KS06]).”
Programming Puzzles (2021, background): “The most difficult puzzles involve longstanding open problems 44 such as learning parity with noise [9]; factoring [22, 28]; or finding a cycle in the 3n+1 process which 45 would disprove the Collatz conjecture [33].”
Secure Human Identification Protocols (2001, background): “The proof follows by induction on s [11].”