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• 42 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

On learning k-parities with and without noise

Arnab Bhattacharyya, Gadekar, Ameet, Ninad Rajgopal

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}$.

arXiv:1502.05375•Feb 18, 2015•4 citations

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•2 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•139 citations

Efficient Quantum Agnostic Improper Learning of Decision Trees

Sagnik Chatterjee, SAPV, Tharrmashastha, Debajyoti Bera

The agnostic setting is the hardest generalization of the PAC model since it is akin to learning with adversarial noise. In this paper, we give a poly$(n,t,{\frac{1}{\varepsilon}})$ quantum algorithm for learning size $t$ decision trees with uniform marginal over instances, in the agnostic setting, without membership queries. Our algorithm is the first algorithm (classical or quantum) for learning decision trees in polynomial time without membership queries. We show how to construct a quantum agnostic weak learner by designing a quantum version of the classical Goldreich-Levin algorithm that works with strongly biased function oracles. We show how to quantize the agnostic boosting algorithm by Kalai and Kanade (NIPS 2009) to obtain the first efficient quantum agnostic boosting algorithm. Our quantum boosting algorithm has a polynomial improvement in the dependence of the bias of the weak learner over all adaptive quantum boosting algorithms while retaining the standard speedup in the VC dimension over classical boosting algorithms. We then use our quantum boosting algorithm to boost the weak quantum learner we obtained in the previous step to obtain a quantum agnostic learner for decision trees. Using the above framework, we also give quantum decision tree learning algorithms for both the realizable setting and random classification noise model, again without membership queries.

arXiv:2210.00212•Oct 1, 2022•1 citation

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 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 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.
The agnostic setting is the hardest generalization of the PAC model since it is akin to learning with adversarial noise. In this paper, we give a poly(n,t,1ε)(n,t,{\frac{1}{\varepsilon}})(n,t,ε1​) quantum algorithm for learning size ttt decision trees with uniform marginal over instances, in the agnostic setting, without membership queries. Our algorithm is the first algorithm (classical or quantum) for learning decision trees in polynomial time without membership queries. We show how to construct a quantum agnostic weak learner by designing a quantum version of the classical Goldreich-Levin algorithm that works with strongly biased function oracles. We show how to quantize the agnostic boosting algorithm by Kalai and Kanade (NIPS 2009) to obtain the first efficient quantum agnostic boosting algorithm. Our quantum boosting algorithm has a polynomial improvement in the dependence of the bias of the weak learner over all adaptive quantum boosting algorithms while retaining the standard speedup in the VC dimension over classical boosting algorithms. We then use our quantum boosting algorithm to boost the weak quantum learner we obtained in the previous step to obtain a quantum agnostic learner for decision trees. Using the above framework, we also give quantum decision tree learning algorithms for both the realizable setting and random classification noise model, again without membership queries.
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.