Efficient Quantum Agnostic Improper Learning of Decision Trees

Sagnik Chatterjee, Tharrmashastha SAPV, 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}})…