Understanding the Generalization Benefit of Model Invariance from a Data Perspective

Sicheng Zhu, Bang An, Furong Huang

Abstract

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.

Introduction

Machine learning models that are invariant to data transformations, such as rotation or cropping, often exhibit superior generalization. However, the theoretical underpinnings of this benefit remain poorly understood, and selecting the optimal transformations for a specific dataset typically involves exhaustive trial-and-error. This paper addresses this gap by introducing the sample covering number, a training-free, data-driven metric that quantifies how effectively a transformation compresses a dataset. By utilizing this metric, researchers can predict the generalization gains of various augmentation strategies prior to model training.

The challenge lies in the fact that existing theoretical frameworks often rely on restrictive mathematical assumptions, such as group structures, which do not apply to many common transformations like cropping. Furthermore, these explanations are frequently tied to specific architectures. This research proposes a model-agnostic, mathematically grounded approach to evaluate the generalization benefits of any data transformation by focusing on the data itself.

Methods: The Sample Covering Number

The core of this approach is the concept of a sample cover induced by transformations. This concept asks: if we are permitted to apply a set of transformations to a small subset of "anchor" images, how many such anchors are required to approximately reconstruct the entire dataset? The minimum size of this subset is defined as the sample covering number.

Comparison of sample covers with and without transformations.

The authors prove that a transformation yielding a small sample covering number results in a tighter Rademacher complexity bound for invariant models, which directly translates to a smaller generalization gap. To estimate this NP-hard value empirically, a three-step algorithm is employed:

  1. Direct Orbit Distance: Measuring the proximity of images under transformation.
  2. Shortest Path Computation: Determining distances between all image pairs based on transformation paths.
  3. Clustering: Using k-medoids to group images and estimate the covering number.

Key Results

Empirical evaluations across several datasets, including CIFAR-10, CIFAR-100, ShapeNet, and Restricted ImageNet, validate the proposed theory. Transformations that produce a lower estimated sample covering number consistently lead to models with smaller generalization gaps.

Empirical sample covering numbers for CIFAR-10 and ShapeNet.

On the CIFAR-10 dataset, cropping was found to induce the smallest sample covering number. Consequently, a ResNet18 model trained with cropping invariance achieved a generalization gap of 7.48%, significantly lower than the baseline (14.57%) or models using flipping (10.33%) and rotation (10.05%). In the case of ShapeNet, 3D-view transformations drastically reduced the sample covering number compared to 2D alternatives, leading to a massive reduction in the generalization gap from 8.18% to 3.09%. Notably, these rankings can be accurately determined using only a small random subset of the data (800-1000 images), making the metric highly efficient.

Discussion and Future Work

The sample covering number offers a training-free, model-agnostic heuristic for selecting data augmentations. It suggests that generalization is linked to a form of data compression: transformations that capture the core variance of the data allow models to ignore spurious features.

Despite its promise, the metric has limitations. It assumes that transformations preserve labels; a transformation that destroys label information might reduce the generalization gap but will also degrade overall accuracy. Additionally, the current algorithm's $O(n^3)$ complexity for shortest path calculations limits its scalability to massive datasets without subsampling. Future research will focus on improving algorithmic efficiency and investigating the interplay between model architecture biases and these data-driven bounds.

Summary updated

Abstract

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.
BibTeX
@inproceedings{zhu2021understanding,
  author = {Sicheng Zhu and Bang An and Furong Huang},
  title = {{Understanding the Generalization Benefit of Model Invariance from a Data Perspective}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=d87PBvj7LA7},
}

Loading related content...

Figure