Evaluating Algorithms and Model Classes: Fundamental Limits in the Distribution-free Setting

RINA FOYGEL BARBER – UNIVERSITY OF CHICAGO

ABSTRACT

When we run a complex algorithm on real data, it is standard to use a holdout set, or a cross-validation strategy, to evaluate its behavior and performance. When we do so, are we learning information about the algorithm itself — or only about the particular fitted model that this particular data set produced? Relatedly, if our algorithm is choosing a fitted model within some model class, by examining its performance can we determine how well this model class fits the data — or are we again only learning about the particular fitted model? These questions are particularly challenging for black-box algorithms, and for high-dimensional model classes. In this talk, we will establish fundamental hardness results on these inference problems in the distribution-free regime. This work is joint with Yuetian Luo and Manuel Müller.