Generalization Error of Invariant Classifiers

Abstract

This paper studies the generalization error of invariant classifiers. In particular, we consider the common scenario where the classification task is invariant to certain transformations of the input, and that the classifier is constructed (or learned) to be invariant to these transformations. Our approach relies on factoring the input space into a product of a base space and a set of transformations. We show that whereas the generalization error of a non-invariant classifier is proportional to the complexity of the input space, the generalization error of an invariant classifier is proportional to the complexity of the base space. We also derive a set of sufficient conditions on the geometry of the base space and the set of transformations that ensure that the complexity of the base space is much smaller than the complexity of the input space. Our analysis applies to general classifiers such as convolutional neural networks. We demonstrate the implications of the developed theory for such classifiers with experiments on the MNIST and CIFAR-10 datasets.

Accepted to AISTATS. This version has updated references

References in corpus (3)

• Wide Residual Networks
• Robust Large Margin Deep Neural Networks
• Inductive Bias of Deep Convolutional Networks through Pooling Geometry

Cited by in corpus (19)

• Exploring Generalization in Deep Learning
• Robust Large Margin Deep Neural Networks
• Generalization in Deep Learning
• Implicit Regularization in Deep Learning
• Understanding Generalization through Visualizations
• Quantifying the generalization error in deep learning in terms of data distribution and neural network smoothness
• Understanding Generalization in Deep Learning via Tensor Methods
• Provably Strict Generalisation Benefit for Equivariant Models
• CNNs Avoid Curse of Dimensionality by Learning on Patches
• Random Noise Defense Against Query-Based Black-Box Attacks
• Improved Generalization Bounds of Group Invariant / Equivariant Deep Networks via Quotient Feature Spaces
• Optimal Machine Intelligence at the Edge of Chaos
• Learning Compressed Transforms with Low Displacement Rank
• Understanding the Generalization Benefit of Model Invariance from a Data Perspective
• Equivariant Imaging: Learning Beyond the Range Space
• Capacity of Group-invariant Linear Readouts from Equivariant Representations: How Many Objects can be Linearly Classified Under All Possible Views?
• The role of invariance in spectral complexity-based generalization bounds
• Recent Advances in Large Margin Learning
• Provably Strict Generalisation Benefit for Invariance in Kernel Methods