# Learning with invariances in random features and kernel models

arXiv: https://arxiv.org/abs/2102.13219 · HTML: https://mlsanity.com/paper/2102.13219/

## Key facts

- Cited by 89 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 41 references that are in the map.
- First posted on arXiv 25 Feb 2021.

## Builds on (most cited first, 22 of 22)

- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers](https://mlsanity.com/paper/1811.04918/) (2018)
- [Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data](https://mlsanity.com/paper/1808.01204/) (2018)
- [Just Interpolate: Kernel "Ridgeless" Regression Can Generalize](https://mlsanity.com/paper/1808.00387/) (2018)
- [On the Inductive Bias of Neural Tangent Kernels](https://mlsanity.com/paper/1905.12173/) (2019)
- [Towards moderate overparameterization: global convergence guarantees for training shallow neural networks](https://mlsanity.com/paper/1902.04674/) (2019)
- [Generalization Properties of Learning with Random Features](https://mlsanity.com/paper/1602.04474/) (2016)
- [Linearized two-layers neural networks in high dimension](https://mlsanity.com/paper/1904.12191/) (2019)
- [When Do Neural Networks Outperform Kernel Methods?](https://mlsanity.com/paper/2006.13409/) (2020)
- [Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks](https://mlsanity.com/paper/1811.08888/) (2018)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration](https://mlsanity.com/paper/2101.10588/) (2021)
- [Towards a Mathematical Understanding of Neural Network-Based Machine Learning: what we know and what we don't](https://mlsanity.com/paper/2009.10713/) (2020)
- [Deep Equals Shallow for ReLU Networks in Kernel Regimes](https://mlsanity.com/paper/2009.14397/) (2020)
- [On the Convergence Rate of Training Recurrent Neural Networks](https://mlsanity.com/paper/1810.12065/) (2018)
- [Enhanced Convolutional Neural Tangent Kernels](https://mlsanity.com/paper/1911.00809/) (2019)
- [Kernel Alignment Risk Estimator: Risk Prediction from Training Data](https://mlsanity.com/paper/2006.09796/) (2020)
- [Why Are Convolutional Nets More Sample-Efficient than Fully-Connected Nets?](https://mlsanity.com/paper/2010.08515/) (2020)
- [On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels](https://mlsanity.com/paper/1908.10292/) (2019)

## Built on by (most cited first, 30 of 89)

- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Scalars are universal: Equivariant machine learning, structured like classical physics](https://mlsanity.com/paper/2106.06610/) (2021)
- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [Approximation-Generalization Trade-offs under (Approximate) Group Equivariance](https://mlsanity.com/paper/2305.17592/) (2023)
- [Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regression](https://mlsanity.com/paper/2204.10425/) (2022)
- [Equivariant Frames and the Impossibility of Continuous Canonicalization](https://mlsanity.com/paper/2402.16077/) (2024)
- [Equivariant quantum circuits for learning on weighted graphs](https://mlsanity.com/paper/2205.06109/) (2022)
- [Neural Contextual Bandits without Regret](https://mlsanity.com/paper/2107.03144/) (2021)
- [The SSL Interplay: Augmentations, Inductive Bias, and Generalization](https://mlsanity.com/paper/2302.02774/) (2023)
- [What can a Single Attention Layer Learn? A Study Through the Random Features Lens](https://mlsanity.com/paper/2307.11353/) (2023)
- [How rotational invariance of common kernels prevents generalization in high dimensions](https://mlsanity.com/paper/2104.04244/) (2021)
- [Provably Strict Generalisation Benefit for Invariance in Kernel Methods](https://mlsanity.com/paper/2106.02346/) (2021)
- [SceneTrilogy: On Human Scene-Sketch and its Complementarity with Photo and Text](https://mlsanity.com/paper/2204.11964/) (2022)
- [Data-driven emergence of convolutional structure in neural networks](https://mlsanity.com/paper/2202.00565/) (2022)
- [Sample Efficiency of Data Augmentation Consistency Regularization](https://mlsanity.com/paper/2202.12230/) (2022)
- [The Exact Sample Complexity Gain from Invariances for Kernel Regression](https://mlsanity.com/paper/2303.14269/) (2023)
- [Locality defeats the curse of dimensionality in convolutional teacher-student scenarios](https://mlsanity.com/paper/2106.08619/) (2021)
- [A Comprehensive Survey of Data Augmentation in Visual Reinforcement Learning](https://mlsanity.com/paper/2210.04561/) (2022)
- [The good, the bad and the ugly sides of data augmentation: An implicit spectral regularization perspective](https://mlsanity.com/paper/2210.05021/) (2022)
- [Lie Algebra Canonicalization: Equivariant Neural Operators under arbitrary Lie Groups](https://mlsanity.com/paper/2410.02698/) (2024)
- [The Three Stages of Learning Dynamics in High-Dimensional Kernel Methods](https://mlsanity.com/paper/2111.07167/) (2021)
- [Learning with convolution and pooling operations in kernel methods](https://mlsanity.com/paper/2111.08308/) (2021)
- [A Theory of PAC Learnability under Transformation Invariances](https://mlsanity.com/paper/2202.07552/) (2022)
- [Theoretical Analysis of Inductive Biases in Deep Convolutional Networks](https://mlsanity.com/paper/2305.08404/) (2023)
- [Six Lectures on Linearized Neural Networks](https://mlsanity.com/paper/2308.13431/) (2023)
- [Data Augmentation as Feature Manipulation](https://mlsanity.com/paper/2203.01572/) (2022)
- [On the non-universality of deep learning: quantifying the cost of symmetry](https://mlsanity.com/paper/2208.03113/) (2022)
- [Optimization Dynamics of Equivariant and Augmented Neural Networks](https://mlsanity.com/paper/2303.13458/) (2023)
- [Emergent Equivariance in Deep Ensembles](https://mlsanity.com/paper/2403.03103/) (2024)
- [Eigenspace Restructuring: a Principle of Space and Frequency in Neural Networks](https://mlsanity.com/paper/2112.05611/) (2021)

## Abstract (arXiv)

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 α', with α ≤ 1. We show that exploiting invariance in the architecture saves a dα 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.