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).
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 k-parities in the on-line mistake-bound model: given a hidden vector x∈{0,1}n with ∣x∣=k and a sequence of "questions" a1,a2,...∈{0,1}n, where the algorithm must reply to each question with <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) factor in the time complexity. Second, we consider the problem of learning k-parities in the presence of classification noise of rate η∈(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 (k/2n)1+4η2+o(1). Note that this algorithm inherently requires time (k/2n) even when the noise rate η is polynomially small. We observe that for sufficiently small noise rate, it is possible to break the (k/2n) barrier. In particular, if for some function f(n)=ω(1) and α∈[1/2,1), k=n/f(n) and η=o(f(n)−α/logn), then there is an algorithm for the problem with running time 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}}: given copies of an unknown n-qubit state ∣ψ⟩ which has fidelity opt with a phase state ∣ϕc⟩=2n1∑x∈{0,1}n(−1)c(x)∣x⟩ for some c∈C, output ∣ϕ⟩ which has fidelity ∣⟨ϕ∣ψ⟩∣2≥opt−ε. To this end, we give agnostic learning protocols for the following classes: (i) Size-t decision trees which runs in time poly(n,t,1/ε). This also implies k-juntas can be agnostically learned in time poly(n,2k,1/ε). (ii) s-term DNF formulas in time 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 ∣ϕ⟩ such that ∣⟨ϕ∣ψ⟩∣2≥opt/poly(n), into a strong learner which outputs a superposition of parity states ∣ϕ′⟩ such that ∣⟨ϕ′∣ψ⟩∣2≥opt−ε. Using quantum agnostic boosting, we obtain a nO(log(n/ε)⋅loglogn)-time algorithm for ε-learning poly(n)-sized depth-3 circuits (consisting of AND, OR, NOT gates) in the uniform PAC model given quantum examples. Classically, obtaining an algorithm with a similar complexity has been an open question in the 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) 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.
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/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)/nk with success probability greater than 1/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.