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

ACM Symposium on Theory of Computing (STOC)

On agnostic boosting and parity learning

Adam Tauman Kalai, Yishay Mansour, Elad Verbin

Published May 17, 2008• 27 citations
Publisher

Abstract

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).

DOI
10.1145/1374376.1374466

Related papers

Learning depth-3 circuits via quantum agnostic boosting

Srinivasan Arunachalam, Arkopal Dutt, Alexandru Gheorghiu +1 more

We initiate the study of quantum agnostic learning of phase states with respect to a function class $\mathsf{C}\subseteq \{c:\{0,1\}^n\rightarrow \{0,1\}\}$: given copies of an unknown $n$-qubit state $|ψ\rangle$ which has fidelity $\textsf{opt}$ with a phase state $|ϕ_c\rangle=\frac{1}{\sqrt{2^n}}\sum_{x\in \{0,1\}^n}(-1)^{c(x)}|x\rangle$ for some $c\in \mathsf{C}$, output $|ϕ\rangle$ which has fidelity $|\langle ϕ| ψ\rangle|^2 \geq \textsf{opt}-\varepsilon$. To this end, we give agnostic learning protocols for the following classes: (i) Size-$t$ decision trees which runs in time $\textsf{poly}(n,t,1/\varepsilon)$. This also implies $k$-juntas can be agnostically learned in time $\textsf{poly}(n,2^k,1/\varepsilon)$. (ii) $s$-term DNF formulas in time $\textsf{poly}(n,(s/\varepsilon)^{\log \log (s/\varepsilon) \cdot \log(1/\varepsilon)})$. Our main technical contribution is a quantum agnostic boosting protocol which converts a weak agnostic learner, which outputs a parity state $|ϕ\rangle$ such that $|\langle ϕ|ψ\rangle|^2\geq \textsf{opt}/\textsf{poly}(n)$, into a strong learner which outputs a superposition of parity states $|ϕ'\rangle$ such that $|\langle ϕ'|ψ\rangle|^2\geq \textsf{opt} - \varepsilon$. Using quantum agnostic boosting, we obtain a $n^{O(\log(n/\varepsilon) \cdot \log \log n)}$-time algorithm for $\varepsilon$-learning $\textsf{poly}(n)$-sized depth-$3$ circuits (consisting of $\textsf{AND}$, $\textsf{OR}$, $\textsf{NOT}$ gates) in the uniform $\textsf{PAC}$ model given quantum examples. Classically, obtaining an algorithm with a similar complexity has been an open question in the $\textsf{PAC}$ model and our work answers this given quantum examples.

arXiv:2509.14461•Sep 17, 2025•0 citations

Quantum-classical reinforcement algorithm for learning parity with noisy classical data and a noisy quantum machine

Kyungdeok Park, June‐Koo Kevin Rhee, Jonghun Park

•Oct 23, 2019•0 citations

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•126 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•20 citations

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. 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 by n codes in the presence of random noise for the case of k = c log n loglog 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.

arXiv:cs/0010022•Oct 15, 2000•0 citations

Unconditional Quantum PAC Learning Advantage in the Large Error Regime

Igor C. Oliveira

We establish an unconditional super-polynomial separation between quantum and classical PAC learning of Boolean functions under the uniform distribution in the large error regime. For every advantage $λ(n) = n^{-ω(1)}$, we construct a concept class that a polynomial-time quantum learner learns to agreement $1/2+λ(n)$ with success probability at least $1-1/n^k$. The learner uses only quantum random examples and outputs a polynomial-size deterministic classical circuit. In contrast, no polynomial-time classical learner achieves agreement $1/2 + λ(n)/n^k$ with success probability greater than $1/n^k$, even with membership queries. To achieve this, we develop a nearly-optimal quantum learner that uses quantum random examples to produce a hypothesis achieving a prescribed correlation with an arbitrary Boolean function. The learner generalizes Fourier sampling from parity hypotheses to quadratic hypotheses. While standard Fourier sampling is insensitive to the sign of the correlation, we use interference to bias sampling toward positively correlated hypotheses. This is combined with a careful analysis of the resulting distribution to boost both the learner's success probability and its agreement with the target function. We believe that the resulting quantum learning algorithm might be of independent interest. Finally, although a robust quantum PAC learning advantage holds unconditionally in the large error regime, we note that an analogous separation between quantum and classical learning in the small error regime would imply that $\mathsf{NP} \nsubseteq \mathsf{BPP}$.

cs.CCCross-listedarXiv:2610.23268•Oct 19, 2026•0 citations
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).
We initiate the study of quantum agnostic learning of phase states with respect to a function class C⊆{c:{0,1}n→{0,1}}\mathsf{C}\subseteq \{c:\{0,1\}^n\rightarrow \{0,1\}\}C⊆{c:{0,1}n→{0,1}}: given copies of an unknown nnn-qubit state ∣ψ⟩|ψ\rangle∣ψ⟩ which has fidelity opt\textsf{opt}opt with a phase state ∣ϕc⟩=12n∑x∈{0,1}n(−1)c(x)∣x⟩|ϕ_c\rangle=\frac{1}{\sqrt{2^n}}\sum_{x\in \{0,1\}^n}(-1)^{c(x)}|x\rangle∣ϕc​⟩=2n​1​∑x∈{0,1}n​(−1)c(x)∣x⟩ for some c∈Cc\in \mathsf{C}c∈C, output ∣ϕ⟩|ϕ\rangle∣ϕ⟩ which has fidelity ∣⟨ϕ∣ψ⟩∣2≥opt−ε|\langle ϕ| ψ\rangle|^2 \geq \textsf{opt}-\varepsilon∣⟨ϕ∣ψ⟩∣2≥opt−ε. To this end, we give agnostic learning protocols for the following classes: (i) Size-ttt decision trees which runs in time poly(n,t,1/ε)\textsf{poly}(n,t,1/\varepsilon)poly(n,t,1/ε). This also implies kkk-juntas can be agnostically learned in time poly(n,2k,1/ε)\textsf{poly}(n,2^k,1/\varepsilon)poly(n,2k,1/ε). (ii) sss-term DNF formulas in time poly(n,(s/ε)log⁡log⁡(s/ε)⋅log⁡(1/ε))\textsf{poly}(n,(s/\varepsilon)^{\log \log (s/\varepsilon) \cdot \log(1/\varepsilon)})poly(n,(s/ε)loglog(s/ε)⋅log(1/ε)). Our main technical contribution is a quantum agnostic boosting protocol which converts a weak agnostic learner, which outputs a parity state ∣ϕ⟩|ϕ\rangle∣ϕ⟩ such that ∣⟨ϕ∣ψ⟩∣2≥opt/poly(n)|\langle ϕ|ψ\rangle|^2\geq \textsf{opt}/\textsf{poly}(n)∣⟨ϕ∣ψ⟩∣2≥opt/poly(n), into a strong learner which outputs a superposition of parity states ∣ϕ′⟩|ϕ'\rangle∣ϕ′⟩ such that ∣⟨ϕ′∣ψ⟩∣2≥opt−ε|\langle ϕ'|ψ\rangle|^2\geq \textsf{opt} - \varepsilon∣⟨ϕ′∣ψ⟩∣2≥opt−ε. Using quantum agnostic boosting, we obtain a nO(log⁡(n/ε)⋅log⁡log⁡n)n^{O(\log(n/\varepsilon) \cdot \log \log n)}nO(log(n/ε)⋅loglogn)-time algorithm for ε\varepsilonε-learning poly(n)\textsf{poly}(n)poly(n)-sized depth-333 circuits (consisting of AND\textsf{AND}AND, OR\textsf{OR}OR, NOT\textsf{NOT}NOT gates) in the uniform PAC\textsf{PAC}PAC model given quantum examples. Classically, obtaining an algorithm with a similar complexity has been an open question in the PAC\textsf{PAC}PAC model and our work answers this given quantum examples.
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.
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. 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 by n codes in the presence of random noise for the case of k = c log n loglog 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.
We establish an unconditional super-polynomial separation between quantum and classical PAC learning of Boolean functions under the uniform distribution in the large error regime. For every advantage λ(n)=n−ω(1)λ(n) = n^{-ω(1)}λ(n)=n−ω(1), we construct a concept class that a polynomial-time quantum learner learns to agreement 1/2+λ(n)1/2+λ(n)1/2+λ(n) with success probability at least 1−1/nk1-1/n^k1−1/nk. The learner uses only quantum random examples and outputs a polynomial-size deterministic classical circuit. In contrast, no polynomial-time classical learner achieves agreement 1/2+λ(n)/nk1/2 + λ(n)/n^k1/2+λ(n)/nk with success probability greater than 1/nk1/n^k1/nk, even with membership queries. To achieve this, we develop a nearly-optimal quantum learner that uses quantum random examples to produce a hypothesis achieving a prescribed correlation with an arbitrary Boolean function. The learner generalizes Fourier sampling from parity hypotheses to quadratic hypotheses. While standard Fourier sampling is insensitive to the sign of the correlation, we use interference to bias sampling toward positively correlated hypotheses. This is combined with a careful analysis of the resulting distribution to boost both the learner's success probability and its agreement with the target function. We believe that the resulting quantum learning algorithm might be of independent interest. Finally, although a robust quantum PAC learning advantage holds unconditionally in the large error regime, we note that an analogous separation between quantum and classical learning in the small error regime would imply that NP⊈BPP\mathsf{NP} \nsubseteq \mathsf{BPP}NP⊈BPP.