Learning with invariances in random features and kernel models

Abstract

A number of machine learning tasks entail a high degree of invariance: the data distribution does not change if we act on the data with a certain group of transformations. For instance, labels of images are invariant under translations of the images. Certain neural network architectures -- for instance, convolutional networks -- are believed to owe their success to the fact that they exploit such invariance properties. With the objective of quantifying the gain achieved by invariant architectures, we introduce two classes of models: invariant random features and invariant kernel methods. The latter includes, as a special case, the neural tangent kernel for convolutional networks with global average pooling. We consider uniform covariates distributions on the sphere and hypercube and a general invariant target function. We characterize the test error of invariant methods in a high-dimensional regime in which the sample size and number of hidden units scale as polynomials in the dimension, for a class of groups that we call `degeneracy $\alpha$', with $\alpha \le 1$. We show that exploiting invariance in the architecture saves a $d^{\alpha }$ factor ($d$ stands for the dimension) in sample size and number of hidden units to achieve the same test error as for unstructured architectures. Finally, we show that output symmetrization of an unstructured kernel estimator does not give a significant statistical improvement; on the other hand, data augmentation with an unstructured kernel estimator is equivalent to an invariant kernel estimator and enjoys the same improvement in statistical efficiency.

63 pages, 6 figures

References in corpus (14)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Understanding Deep Convolutional Networks
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Gradient Descent Finds Global Minima of Deep Neural Networks
• Generalization Properties of Learning with Random Features
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Enhanced Convolutional Neural Tangent Kernels
• When Do Neural Networks Outperform Kernel Methods?
• Towards a Mathematical Understanding of Neural Network-Based Machine Learning: what we know and what we don't
• Kernel Alignment Risk Estimator: Risk Prediction from Training Data
• Why Are Convolutional Nets More Sample-Efficient than Fully-Connected Nets?
• Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration
• Deep Equals Shallow for ReLU Networks in Kernel Regimes

Cited by in corpus (12)

• Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges
• Locality defeats the curse of dimensionality in convolutional teacher-student scenarios
• Machine learning and invariant theory
• Learning with convolution and pooling operations in kernel methods
• Leveraging SO(3)-steerable convolutions for pose-robust semantic segmentation in 3D medical data
• The Three Stages of Learning Dynamics in High-Dimensional Kernel Methods
• Some observations on the ambivalent role of symmetries in Bayesian inference problems
• Data efficiency in graph networks through equivariance
• Deep Networks Provably Classify Data on Curves
• Neural Contextual Bandits without Regret
• Symmetry-driven graph neural networks
• Provably Strict Generalisation Benefit for Invariance in Kernel Methods