Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1502.05375

On learning k-parities with and without noise

Arnab Bhattacharyya, Gadekar, Ameet, Ninad Rajgopal

Published Feb 18, 2015• 4 citations
arXivHTMLPDF

Abstract

We first consider the problem of learning $k$-parities in the on-line mistake-bound model: given a hidden vector $x \in \{0,1\}^n$ with $|x|=k$ and a sequence of "questions" $a_1, a_2, ...\in \{0,1\}^n$, where the algorithm must reply to each question with $< a_i, x> \pmod 2$, what is the best tradeoff between the number of mistakes made by the algorithm and its time complexity? We improve the previous best result of Buhrman et al. by an $\exp(k)$ factor in the time complexity. Second, we consider the problem of learning $k$-parities in the presence of classification noise of rate $η\in (0,1/2)$. A polynomial time algorithm for this problem (when $η> 0$ and $k = ω(1)$) is a longstanding challenge in learning theory. Grigorescu et al. showed an algorithm running in time ${n \choose k/2}^{1 + 4η^2 +o(1)}$. Note that this algorithm inherently requires time ${n \choose k/2}$ even when the noise rate $η$ is polynomially small. We observe that for sufficiently small noise rate, it is possible to break the $n \choose k/2$ barrier. In particular, if for some function $f(n) = ω(1)$ and $α\in [1/2, 1)$, $k = n/f(n)$ and $η= o(f(n)^{- α}/\log n)$, then there is an algorithm for the problem with running time $poly(n)\cdot {n \choose k}^{1-α} \cdot e^{-k/4.01}$.

DOI
10.48550/arxiv.1502.05375

Related papers

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

Avrim L. Blum, Adam Tauman Kalai, Hal Wasserman

We describe a slightly sub-exponential time algorithm for learning parity functions in the presence of random classification noise. This results in a polynomial-time algorithm for the case of parity functions that depend on only the first O(log n log log n) bits of input. This is the first known instance of an efficient noise-tolerant algorithm for a concept class that is provably not learnable in the Statistical Query model of Kearns [7]. 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 = clog 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 2 k 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 single examples). The second result of this paper 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.

ACM Symposium on Theory of Computing (STOC)•May 1, 2000•139 citations

On agnostic boosting and parity learning

Adam Tauman Kalai, Yishay Mansour, Elad Verbin

The motivating problem is agnostically learning parity functions, i.e., parity with arbitrary or adversarial noise. Specifically, given random labeled examples from an *arbitrary* distribution, we would like to produce an hypothesis whose accuracy nearly matches the accuracy of the best parity function. Our algorithm runs in time 2O(n/log n), which matches the best known for the easier cases of learning parities with random classification noise (Blum et al, 2003) and for agnostically learning parities over the uniform distribution on inputs (Feldman et al, 2006).

ACM Symposium on Theory of Computing (STOC)•May 17, 2008•42 citations

Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas

Gregory J. Valiant

Given a set of n d-dimensional Boolean vectors with the promise that the vectors are chosen uniformly at random with the exception of two vectors that have Pearson-correlation ρ (Hamming distance d · 1-ρ/2), how quickly can one find the two correlated vectors? We present an algorithm which, for any constants ε, ρ >; 0 and d >;>; logn/ρ2, finds the correlated pair with high probability, and runs in time O(n 3ω/4 + ϵ)1.8), where w2-O(ρ)), given by Paturi et al. [15], Locality Sensitive Hashing (LSH) [11] and the Bucketing Codes approach [6]. Applications and extensions of this basic algorithm yield improved algorithms for several other problems: ApproximateClosest Pair: For any sufficiently small constant ϵ >; 0, given n vectors in Rd, our algorithm returns a pair of vectors whose Euclidean distance differs from that of the closest pair by a factor of at most 1+ϵ, and runs in time O(n2-Θ(√ϵ)). The best previous algorithms (including LSH) have runtime O(n2-O(ϵ)). Learning Sparse Parity with Noise: Given samples from an instance of the learning parity with noise problem where each example has length n, the true parity set has size at most kkpoly(1/1-2η)0.8kpoly(1/1-2η). This is the first algorithm with no depenJence on η in the exponent of n, aside from the trivial brute-force algorithm. Learning k-Juntas with Noise: Given uniformly random length n Boolean vectors, together with a label, which is some function of just kkpoly(1/1-2η)0.8kpoly(1/1-2η), 2 which improves on the previous best of >; nk(1-2/2k)poly( 1/1-2η ), from [8]. Learning k-Juntas without Noise:1 Our results for learning sparse parities with noise imply an algorithm for learning juntas without noise with runtime n ω+ϵ/4kpoly(n)0.6kpoly(n), which improves on the runtime n ω+1/ω poly(n) ≈ n0.7kpoly(n) of Mossel n et al. [13].

Annual Symposium on Foundations of Computer Science•Oct 1, 2012•69 citations

On learning linear functions from subset and its applications in quantum computing

Gábor Ivanyos, Anupam Prakash, Miklós Sántha

Let $\mathbb{F}_q$ be the finite field of size $q$ and let $\ell: \mathbb{F}_q^n \to \mathbb{F}_q$ be a linear function. We introduce the {\em Learning From Subset} problem LFS$(q,n,d)$ of learning $\ell$, given samples $u \in \mathbb{F}_q^n$ from a special distribution depending on $\ell$: the probability of sampling $u$ is a function of $\ell(u)$ and is non zero for at most $d$ values of $\ell(u)$. We provide a randomized algorithm for LFS$(q,n,d)$ with sample complexity $(n+d)^{O(d)}$ and running time polynomial in $\log q$ and $(n+d)^{O(d)}$. Our algorithm generalizes and improves upon previous results \cite{Friedl, Ivanyos} that had provided algorithms for LFS$(q,n,q-1)$ with running time $(n+q)^{O(q)}$. We further present applications of our result to the {\em Hidden Multiple Shift} problem HMS$(q,n,r)$ in quantum computation where the goal is to determine the hidden shift $s$ given oracle access to $r$ shifted copies of an injective function $f: \mathbb{Z}_q^n \to \{0, 1\}^l$, that is we can make queries of the form $f_s(x,h) = f(x-hs)$ where $h$ can assume $r$ possible values. We reduce HMS$(q,n,r)$ to LFS$(q,n, q-r+1)$ to obtain a polynomial time algorithm for HMS$(q,n,r)$ when $q=n^{O(1)}$ is prime and $q-r=O(1)$. The best known algorithms \cite{CD07, Friedl} for HMS$(q,n,r)$ with these parameters require exponential time.

arXiv:1806.09660•Jun 25, 2018•4 citations

On Noise-Tolerant Learning of Sparse Parities and Related Problems

Elena Grigorescu, Lev Reyzin, Santosh Vempala

Lecture notes in computer science•Jan 1, 2011•23 citations

On learning linear functions from subset and its applications in quantum computing

Gábor Ivanyos, Anupam Prakash, Miklós Sántha

Let F_{q} be the finite field of size q and let l: F_{q}^{n} -> F_{q} be a linear function. We introduce the Learning From Subset problem LFS(q,n,d) of learning l, given samples u in F_{q}^{n} from a special distribution depending on l: the probability of sampling u is a function of l(u) and is non zero for at most d values of l(u). We provide a randomized algorithm for LFS(q,n,d) with sample complexity (n+d)^{O(d)} and running time polynomial in log q and (n+d)^{O(d)}. Our algorithm generalizes and improves upon previous results [Friedl et al., 2014; Gabor Ivanyos, 2008] that had provided algorithms for LFS(q,n,q-1) with running time (n+q)^{O(q)}. We further present applications of our result to the Hidden Multiple Shift problem HMS(q,n,r) in quantum computation where the goal is to determine the hidden shift s given oracle access to r shifted copies of an injective function f: Z_{q}^{n} -> {0, 1}^{l}, that is we can make queries of the form f_{s}(x,h) = f(x-hs) where h can assume r possible values. We reduce HMS(q,n,r) to LFS(q,n, q-r+1) to obtain a polynomial time algorithm for HMS(q,n,r) when q=n^{O(1)} is prime and q-r=O(1). The best known algorithms [Andrew M. Childs and Wim van Dam, 2007; Friedl et al., 2014] for HMS(q,n,r) with these parameters require exponential time.

•Jan 1, 2018•0 citations
We first consider the problem of learning kkk-parities in the on-line mistake-bound model: given a hidden vector x∈{0,1}nx \in \{0,1\}^nx∈{0,1}n with ∣x∣=k|x|=k∣x∣=k and a sequence of "questions" a1,a2,...∈{0,1}na_1, a_2, ...\in \{0,1\}^na1​,a2​,...∈{0,1}n, where the algorithm must reply to each question with <ai,x>(mod2)< a_i, x> \pmod 2<ai​,x>(mod2), what is the best tradeoff between the number of mistakes made by the algorithm and its time complexity? We improve the previous best result of Buhrman et al. by an exp⁡(k)\exp(k)exp(k) factor in the time complexity. Second, we consider the problem of learning kkk-parities in the presence of classification noise of rate η∈(0,1/2)η\in (0,1/2)η∈(0,1/2). A polynomial time algorithm for this problem (when η>0η> 0η>0 and k=ω(1)k = ω(1)k=ω(1)) is a longstanding challenge in learning theory. Grigorescu et al. showed an algorithm running in time (nk/2)1+4η2+o(1){n \choose k/2}^{1 + 4η^2 +o(1)}(k/2n​)1+4η2+o(1). Note that this algorithm inherently requires time (nk/2){n \choose k/2}(k/2n​) even when the noise rate ηηη is polynomially small. We observe that for sufficiently small noise rate, it is possible to break the (nk/2)n \choose k/2(k/2n​) barrier. In particular, if for some function f(n)=ω(1)f(n) = ω(1)f(n)=ω(1) and α∈[1/2,1)α\in [1/2, 1)α∈[1/2,1), k=n/f(n)k = n/f(n)k=n/f(n) and η=o(f(n)−α/log⁡n)η= o(f(n)^{- α}/\log n)η=o(f(n)−α/logn), then there is an algorithm for the problem with running time poly(n)⋅(nk)1−α⋅e−k/4.01poly(n)\cdot {n \choose k}^{1-α} \cdot e^{-k/4.01}poly(n)⋅(kn​)1−α⋅e−k/4.01.
We describe a slightly sub-exponential time algorithm for learning parity functions in the presence of random classification noise. This results in a polynomial-time algorithm for the case of parity functions that depend on only the first O(log n log log n) bits of input. This is the first known instance of an efficient noise-tolerant algorithm for a concept class that is provably not learnable in the Statistical Query model of Kearns [7]. 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 = clog 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 2 k 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 single examples). The second result of this paper 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.
The motivating problem is agnostically learning parity functions, i.e., parity with arbitrary or adversarial noise. Specifically, given random labeled examples from an *arbitrary* distribution, we would like to produce an hypothesis whose accuracy nearly matches the accuracy of the best parity function. Our algorithm runs in time 2O(n/log n), which matches the best known for the easier cases of learning parities with random classification noise (Blum et al, 2003) and for agnostically learning parities over the uniform distribution on inputs (Feldman et al, 2006).
Given a set of n d-dimensional Boolean vectors with the promise that the vectors are chosen uniformly at random with the exception of two vectors that have Pearson-correlation ρ (Hamming distance d · 1-ρ/2), how quickly can one find the two correlated vectors? We present an algorithm which, for any constants ε, ρ >; 0 and d >;>; logn/ρ2, finds the correlated pair with high probability, and runs in time O(n 3ω/4 + ϵ)1.8), where w2-O(ρ)), given by Paturi et al. [15], Locality Sensitive Hashing (LSH) [11] and the Bucketing Codes approach [6]. Applications and extensions of this basic algorithm yield improved algorithms for several other problems: ApproximateClosest Pair: For any sufficiently small constant ϵ >; 0, given n vectors in Rd, our algorithm returns a pair of vectors whose Euclidean distance differs from that of the closest pair by a factor of at most 1+ϵ, and runs in time O(n2-Θ(√ϵ)). The best previous algorithms (including LSH) have runtime O(n2-O(ϵ)). Learning Sparse Parity with Noise: Given samples from an instance of the learning parity with noise problem where each example has length n, the true parity set has size at most kkpoly(1/1-2η)0.8kpoly(1/1-2η). This is the first algorithm with no depenJence on η in the exponent of n, aside from the trivial brute-force algorithm. Learning k-Juntas with Noise: Given uniformly random length n Boolean vectors, together with a label, which is some function of just kkpoly(1/1-2η)0.8kpoly(1/1-2η), 2 which improves on the previous best of >; nk(1-2/2k)poly( 1/1-2η ), from [8]. Learning k-Juntas without Noise:1 Our results for learning sparse parities with noise imply an algorithm for learning juntas without noise with runtime n ω+ϵ/4kpoly(n)0.6kpoly(n), which improves on the runtime n ω+1/ω poly(n) ≈ n0.7kpoly(n) of Mossel n et al. [13].
Let Fq\mathbb{F}_qFq​ be the finite field of size qqq and let ℓ:Fqn→Fq\ell: \mathbb{F}_q^n \to \mathbb{F}_qℓ:Fqn​→Fq​ be a linear function. We introduce the {\em Learning From Subset} problem LFS(q,n,d)(q,n,d)(q,n,d) of learning ℓ\ellℓ, given samples u∈Fqnu \in \mathbb{F}_q^nu∈Fqn​ from a special distribution depending on ℓ\ellℓ: the probability of sampling uuu is a function of ℓ(u)\ell(u)ℓ(u) and is non zero for at most ddd values of ℓ(u)\ell(u)ℓ(u). We provide a randomized algorithm for LFS(q,n,d)(q,n,d)(q,n,d) with sample complexity (n+d)O(d)(n+d)^{O(d)}(n+d)O(d) and running time polynomial in log⁡q\log qlogq and (n+d)O(d)(n+d)^{O(d)}(n+d)O(d). Our algorithm generalizes and improves upon previous results \cite{Friedl, Ivanyos} that had provided algorithms for LFS(q,n,q−1)(q,n,q-1)(q,n,q−1) with running time (n+q)O(q)(n+q)^{O(q)}(n+q)O(q). We further present applications of our result to the {\em Hidden Multiple Shift} problem HMS(q,n,r)(q,n,r)(q,n,r) in quantum computation where the goal is to determine the hidden shift sss given oracle access to rrr shifted copies of an injective function f:Zqn→{0,1}lf: \mathbb{Z}_q^n \to \{0, 1\}^lf:Zqn​→{0,1}l, that is we can make queries of the form fs(x,h)=f(x−hs)f_s(x,h) = f(x-hs)fs​(x,h)=f(x−hs) where hhh can assume rrr possible values. We reduce HMS(q,n,r)(q,n,r)(q,n,r) to LFS(q,n,q−r+1)(q,n, q-r+1)(q,n,q−r+1) to obtain a polynomial time algorithm for HMS(q,n,r)(q,n,r)(q,n,r) when q=nO(1)q=n^{O(1)}q=nO(1) is prime and q−r=O(1)q-r=O(1)q−r=O(1). The best known algorithms \cite{CD07, Friedl} for HMS(q,n,r)(q,n,r)(q,n,r) with these parameters require exponential time.
Let F_{q} be the finite field of size q and let l: F_{q}^{n} -> F_{q} be a linear function. We introduce the Learning From Subset problem LFS(q,n,d) of learning l, given samples u in F_{q}^{n} from a special distribution depending on l: the probability of sampling u is a function of l(u) and is non zero for at most d values of l(u). We provide a randomized algorithm for LFS(q,n,d) with sample complexity (n+d)^{O(d)} and running time polynomial in log q and (n+d)^{O(d)}. Our algorithm generalizes and improves upon previous results [Friedl et al., 2014; Gabor Ivanyos, 2008] that had provided algorithms for LFS(q,n,q-1) with running time (n+q)^{O(q)}. We further present applications of our result to the Hidden Multiple Shift problem HMS(q,n,r) in quantum computation where the goal is to determine the hidden shift s given oracle access to r shifted copies of an injective function f: Z_{q}^{n} -> {0, 1}^{l}, that is we can make queries of the form f_{s}(x,h) = f(x-hs) where h can assume r possible values. We reduce HMS(q,n,r) to LFS(q,n, q-r+1) to obtain a polynomial time algorithm for HMS(q,n,r) when q=n^{O(1)} is prime and q-r=O(1). The best known algorithms [Andrew M. Childs and Wim van Dam, 2007; Friedl et al., 2014] for HMS(q,n,r) with these parameters require exponential time.