Fantastic Generalization Measures are Nowhere to be Found

Michael Gastpar, Ido Nachum, Jonathan Shafer +1

We study the notion of a generalization bound being uniformly tight, meaning that the difference between the bound and the population loss is small for all learning algorithms and…