Hi all,
I hope you had a good start in the new year!
We are starting again this week with a talk from our guest Vojtěch Havlíček on “On Quantum Statistical Query Learning”. See below for the abstract. The talk will take place at 14:00 in HIT E41.1.
Best, Ladina
%%%%% Title: On Quantum Statistical Query Learning
Joint work with Louis Schatzki (UIUC) and Srinivasan Arunachalam (IBM Almaden).
Abstract:
Statistical Query Learning (SQ) is a restriction of PAC learning in which learners form hypotheses by querying expectation values over the data distribution and labels. It is well known that SQ cannot learn the concept class of parities, even under uniform distribution. This shows that it is a restriction of PAC. We study an obvious quantum generalization of SQ, proposed by Arunachalam, Grilo and Yuen, which is not separable from a quantum generalization of PAC by parity learning and our main result is a task that separates the two learning classes. To prove it, we built on Feldman‘s work on statistical query dimension, which yields lower bounds on SQ learning. I will discuss our result, the lower bounding technique and some of its applications.