  Machine learning models that are developed with invariance to certain types
of data transformations have demonstrated superior generalization performance
in practice. However, the underlying mechanism that explains why invariance
leads to better generalization is not well-understood, limiting our ability to
select appropriate data transformations for a given dataset. This paper studies
the generalization benefit of model invariance by introducing the sample cover
induced by transformations, i.e., a representative subset of a dataset that can
approximately recover the whole dataset using transformations. Based on this
notion, we refine the generalization bound for invariant models and
characterize the suitability of a set of data transformations by the sample
covering number induced by transformations, i.e., the smallest size of its
induced sample covers. We show that the generalization bound can be tightened
for suitable transformations that have a small sample covering number.
Moreover, our proposed sample covering number can be empirically evaluated,
providing a practical guide for selecting transformations to develop model
invariance for better generalization. We evaluate the sample covering numbers
for commonly used transformations on multiple datasets and demonstrate that the
smaller sample covering number for a set of transformations indicates a smaller
gap between the test and training error for invariant models, thus validating
our propositions.
