8 citations · 18 across the 23 of their papers we have counts for
4 papers · 1 filter
Samplability makes learning easier
Guy Blanc, Caleb Koch, Jane Lange +2
The standard definition of PAC learning (Valiant 1984) requires learners to succeed under all distributions -- even ones that are intractable to sample from. This stands in contras…
The power of quantum circuits in sampling
Guy Blanc, Caleb Koch, Jane Lange +2
We give new evidence that quantum circuits are substantially more powerful than classical circuits. We show, relative to a random oracle, that polynomial-size quantum circuits can…
A Distributional-Lifting Theorem for PAC Learning
Guy Blanc, Jane Lange, Carmen Strassle +1
The apparent difficulty of efficient distribution-free PAC learning has led to a large body of work on distribution-specific learning. Distributional assumptions facilitate the des…
Robust learning of halfspaces under log-concave marginals
Jane Lange, Arsen Vasilyan
We say that a classifier is \emph{adversarially robust} to perturbations of norm if, with high probability over a point drawn from the input distribution, there is no point…