Efficient Quantum Agnostic Improper Learning of Decision Trees

arXiv:2210.00212v3 Announce Type: replace-cross
Abstract: 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 …

abstract adversarial algorithm arxiv cs.lg decision decision trees instances noise paper quant-ph quantum queries trees type uniform