  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 all population distributions. Numerous generalization
bounds have been proposed in the literature as potential explanations for the
ability of neural networks to generalize in the overparameterized setting.
However, in their paper ``Fantastic Generalization Measures and Where to Find
Them,'' Jiang et al. (2020) examine more than a dozen generalization bounds,
and show empirically that none of them are uniformly tight. This raises the
question of whether uniformly-tight generalization bounds are at all possible
in the overparameterized setting. We consider two types of generalization
bounds: (1) bounds that may depend on the training set and the learned
hypothesis (e.g., margin bounds). We prove mathematically that no such bound
can be uniformly tight in the overparameterized setting; (2) bounds that may in
addition also depend on the learning algorithm (e.g., stability bounds). For
these bounds, we show a trade-off between the algorithm's performance and the
bound's tightness. Namely, if the algorithm achieves good accuracy on certain
distributions, then no generalization bound can be uniformly tight for it in
the overparameterized setting. We explain how these formal results can, in our
view, inform research on generalization bounds for neural networks, while
stressing that other interpretations of these results are also possible.
