Proper vs Improper Quantum PAC learning

arXiv:2403.03295v1 Announce Type: cross
Abstract: A basic question in the PAC model of learning is whether proper learning is harder than improper learning. In the classical case, there are examples of concept classes with VC dimension $d$ that have sample complexity $\Omega\left(\frac d\epsilon\log\frac1\epsilon\right)$ for proper learning with error $\epsilon$, while the complexity for improper learning is O$\!\left(\frac d\epsilon\right)$. One such example arises from the Coupon Collector problem.
Motivated by the efficiency of proper versus improper learning with quantum samples, Arunachalam, …

abstract arxiv basic case complexity concept cs.cc cs.lg epsilon error examples quant-ph quantum question sample type