Efficient Data-Dependent Learnability

Yaniv Fogel, Tal Shapira, Meir Feder

The predictive normalized maximum likelihood (pNML) approach has recently been proposed as the min-max optimal solution to the batch learning problem where both the training set an…