# Learning with convolution and pooling operations in kernel methods

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 61 references that are in the map.
- First posted on arXiv 16 Nov 2021.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [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)
- [Just Interpolate: Kernel "Ridgeless" Regression Can Generalize](https://mlsanity.com/paper/1808.00387/) (2018)
- [Spectral Bias and Task-Model Alignment Explain Generalization in Kernel Regression and Infinitely Wide Neural Networks](https://mlsanity.com/paper/2006.13198/) (2020)
- [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)
- [Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity](https://mlsanity.com/paper/1602.05897/) (2016)
- [Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration](https://mlsanity.com/paper/2101.10588/) (2021)
- [Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime](https://mlsanity.com/paper/2105.15004/) (2021)
- [Learning with invariances in random features and kernel models](https://mlsanity.com/paper/2102.13219/) (2021)
- [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)
- [Deep vs. shallow networks : An approximation theory perspective](https://mlsanity.com/paper/1608.03287/) (2016)
- [Neural Kernels Without Tangents](https://mlsanity.com/paper/2003.02237/) (2020)
- [Kernel Alignment Risk Estimator: Risk Prediction from Training Data](https://mlsanity.com/paper/2006.09796/) (2020)
- [Inductive Bias of Deep Convolutional Networks through Pooling Geometry](https://mlsanity.com/paper/1605.06743/) (2016)
- [Convolutional Kernel Networks](https://mlsanity.com/paper/1406.3332/) (2014)
- [Why Are Convolutional Nets More Sample-Efficient than Fully-Connected Nets?](https://mlsanity.com/paper/2010.08515/) (2020)
- [Convolutional Rectifier Networks as Generalized Tensor Decompositions](https://mlsanity.com/paper/1603.00162/) (2016)
- [Approximation and Learning with Deep Convolutional Models: a Kernel Perspective](https://mlsanity.com/paper/2102.10032/) (2021)
- [End-to-End Kernel Learning with Supervised Convolutional Kernel Networks](https://mlsanity.com/paper/1605.06265/) (2016)
- [Locality defeats the curse of dimensionality in convolutional teacher-student scenarios](https://mlsanity.com/paper/2106.08619/) (2021)
- [Computational Separation Between Convolutional and Fully-Connected Networks](https://mlsanity.com/paper/2010.01369/) (2020)
- [The Unreasonable Effectiveness of Patches in Deep Convolutional Kernels Methods](https://mlsanity.com/paper/2101.07528/) (2021)
- [Harmonic Decompositions of Convolutional Networks](https://mlsanity.com/paper/2003.12756/) (2020)

## Built on by (most cited first, 21 of 21)

- [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)
- [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)
- [Data-driven emergence of convolutional structure in neural networks](https://mlsanity.com/paper/2202.00565/) (2022)
- [Dimension-free deterministic equivalents and scaling laws for random feature regression](https://mlsanity.com/paper/2405.15699/) (2024)
- [Fast Rates for Noisy Interpolation Require Rethinking the Effects of Inductive Bias](https://mlsanity.com/paper/2203.03597/) (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)
- [On the non-universality of deep learning: quantifying the cost of symmetry](https://mlsanity.com/paper/2208.03113/) (2022)
- [U-Nets as Belief Propagation: Efficient Classification, Denoising, and Diffusion in Generative Hierarchical Models](https://mlsanity.com/paper/2404.18444/) (2024)
- [On the Spectral Bias of Convolutional Neural Tangent and Gaussian Process Kernels](https://mlsanity.com/paper/2203.09255/) (2022)
- [What Can Be Learnt With Wide Convolutional Neural Networks?](https://mlsanity.com/paper/2208.01003/) (2022)
- [Optimal Rate of Kernel Regression in Large Dimensions](https://mlsanity.com/paper/2309.04268/) (2023)
- [Strong inductive biases provably prevent harmless interpolation](https://mlsanity.com/paper/2301.07605/) (2023)
- [Controlling the Inductive Bias of Wide Neural Networks by Modifying the Kernel's Spectrum](https://mlsanity.com/paper/2307.14531/) (2023)
- [Which Frequencies do CNNs Need? Emergent Bottleneck Structure in Feature Learning](https://mlsanity.com/paper/2402.08010/) (2024)
- [Pseudo-keypoint RKHS Learning for Self-supervised 6DoF Pose Estimation](https://mlsanity.com/paper/2311.09500/) (2023)
- [High-Dimensional Kernel Methods under Covariate Shift: Data-Dependent Implicit Regularization](https://mlsanity.com/paper/2406.03171/) (2024)
- [On the Pinsker bound of inner product kernel regression in large dimensions](https://mlsanity.com/paper/2409.00915/) (2024)
- [On the Saturation Effects of Spectral Algorithms in Large Dimensions](https://mlsanity.com/paper/2503.00504/) (2025)
- [Towards High-Fidelity Gaussian Splatting with Queried-Convolution Neural Networks](https://mlsanity.com/paper/2512.12898/) (2025)

## Abstract (arXiv)

Recent empirical work has shown that hierarchical convolutional kernels inspired by convolutional neural networks (CNNs) significantly improve the performance of kernel methods in image classification tasks. A widely accepted explanation for their success is that these architectures encode hypothesis classes that are suitable for natural images. However, understanding the precise interplay between approximation and generalization in convolutional architectures remains a challenge. In this paper, we consider the stylized setting of covariates (image pixels) uniformly distributed on the hypercube, and characterize exactly the RKHS of kernels composed of single layers of convolution, pooling, and downsampling operations. We use this characterization to compute sharp asymptotics of the generalization error for any given function in high-dimension. In particular, we quantify the gain in sample complexity brought by enforcing locality with the convolution operation and approximate translation invariance with average pooling. Notably, these results provide a precise description of how convolution and pooling operations trade off approximation with generalization power in one layer convolutional kernels.