Efficient Data-Dependent Learnability
  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 and the test data feature are individuals, known
sequences. This approach has yields a learnability measure that can also be
interpreted as a stability measure. This measure has shown some potential in
detecting out-of-distribution examples, yet it has considerable computational
costs. In this project, we propose and analyze an approximation of the pNML,
which is based on influence functions. Combining both theoretical analysis and
experiments, we show that when applied to neural networks, this approximation
can detect out-of-distribution examples effectively. We also compare its
performance to that achieved by conducting a single gradient step for each
possible label.
