Improved Generalization Bounds of Group Invariant / Equivariant Deep Networks via Quotient Feature Spaces

Abstract

Numerous invariant (or equivariant) neural networks have succeeded in handling invariant data such as point clouds and graphs. However, a generalization theory for the neural networks has not been well developed, because several essential factors for the theory, such as network size and margin distribution, are not deeply connected to the invariance and equivariance. In this study, we develop a novel generalization error bound for invariant and equivariant deep neural networks. To describe the effect of invariance and equivariance on generalization, we develop a notion of a \textit{quotient feature space}, which measures the effect of group actions for the properties. Our main result proves that the volume of quotient feature spaces can describe the generalization error. Furthermore, the bound shows that the invariance and equivariance significantly improve the leading term of the bound. We apply our result to specific invariant and equivariant networks, such as DeepSets (Zaheer et al. (2017)), and show that their generalization bound is considerably improved by $\sqrt{n!}$, where $n!$ is the number of permutations. We also discuss the expressive power of invariant DNNs and show that they can achieve an optimal approximation rate. Our experimental result supports our theoretical claims.

arXiv commentOld title: "Improved Generalization Bound of Permutation Invariant Deep Neural Networks"

References in corpus (16)

• Spectral Networks and Locally Connected Networks on Graphs
• Deep Convolutional Networks on Graph-Structured Data
• Group Equivariant Convolutional Networks
• Machine Learning Energies of 2 M Elpasolite (ABC${}_2$D${}_6$) Crystals
• Uniform convergence may be unable to explain generalization in deep learning
• SO-Net: Self-Organizing Network for Point Cloud Analysis
• Group Equivariant Capsule Networks
• Norm-Based Capacity Control in Neural Networks
• Dynamical Mass Measurements of Contaminated Galaxy Clusters Using Machine Learning
• On Learning Sets of Symmetric Elements
• Universal approximations of permutation invariant/equivariant functions by deep neural networks
• Generalization Error of Invariant Classifiers
• Tropical Geometry of Deep Neural Networks
• Estimating Cosmological Parameters from the Dark Matter Distribution
• Universal Equivariant Multilayer Perceptrons
• On Universal Equivariant Set Networks

Cited by in corpus (2)

• Provably Strict Generalisation Benefit for Equivariant Models
• Understanding the Generalization Benefit of Model Invariance from a Data Perspective