Generalization Error of Invariant Classifiers

By Jure Sokolić, Raja Giryes, Guillermo Sapiro, Miguel Raul Dias Rodrigues. 2016

82 citations recorded by the source corpus.

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.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Robust Large Margin Deep Neural Networks (2016, neutral): “The extension of our results to invariant DNN is provided in [37].”
Exploring Generalization in Deep Learning (2017, background): “Unlike existing generalization bounds [4, 18, 13, 28, 25], our sharpness based bound does not suffer from exponential dependence on depth.”
Generalization in Deep Learning (2017, methodology): “Recently, this idea was applied to deep learning (Sokolic et al., 2017a,b), producing insightful and effective generalization bounds, while still suffering from the curse of the dimensionality of the priori-known fixed input manifold.”
FreeLB: Enhanced Adversarial Training for Natural Language Understanding (2019, methodology): “We observe that it is unnecessary to perform shallow-layer updates on the adversary as YOPO for our case, and FreeLB results in improved robustness and generalization compared with PGD. Importance of Reusing Mask Table 4 (columns 2 to 4) compares the results of FreeLB with and without reusing the sa”
Deep Scale-spaces: Equivariance Over Scale (2019, unknown): “The overall effect is to improve sample complexity and thus reduce generalization error [Sokolic et al., 2017].”
Learning to Convolve: A Generalized Weight-Tying Approach (2019, background): “As such, CNNs have improved sample complexity (Sokolic et al., 2017) and thus better generalization compared to their non-symmetric cousins.”
Implicit Regularization in Deep Learning (2017, background): “Unlike existing generalization bounds [28, 58, 29, 30, 31], our sharpness based bound does not suffer from exponential dependence on depth.”
Generalization and Representational Limits of Graph Neural Networks (2020, methodology): “Note that previous works were conﬁned to dealing with permutation-invariance at a global level (Sannai and Imaizumi (2019); Sokolic et al. (2017)).”
Understanding Generalization through Visualizations (2019, unknown): “Finish (minimizer)”
Mathematics of Deep Learning (2017, background): “Furthermore, a relationship between the generalization error, the invariance in the data and the network is formally characterized in [29].”