Shai-Ben-David

Impossibility of Characterizing Distribution Learning -- a simple solution to a long-standing problem

2023 · arXiv (Cornell University)

We consider the long-standing question of finding a parameter of a class of probability distributions that characterizes its PAC learnability. We provide a rather surprising answer - no such parameter exists. Our techniques allow us …