mlsanityData to 7 Oct 2026

Learning with convolution and pooling operations in kernel methods

arXiv 2111.08308 ↗First posted 16 Nov 2021stat.ML cs.LGcited by 21

Not on the map. Why?

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.

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

Builds on

30 of 61 references.

References · 30

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  3. 2018On Lazy Training in Differentiable Programmingcited by 671
  4. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  5. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  6. 2019On Exact Computation with an Infinitely Wide Neural Netcited by 572
  7. 2018Just Interpolate: Kernel "Ridgeless" Regression Can Generalizecited by 190
  8. 2020Spectral Bias and Task-Model Alignment Explain Generalization in Kernel Regression and Infinitely Wide Neural Networkscited by 166
  9. 2019Linearized two-layers neural networks in high dimensioncited by 155
  10. 2020When Do Neural Networks Outperform Kernel Methods?cited by 150
  11. 2018Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networkscited by 139
  12. 2016Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivitycited by 138
18 more
  1. 2021Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentrationcited by 110
  2. 2021Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regimecited by 95
  3. 2021Learning with invariances in random features and kernel modelscited by 89
  4. 2018On the Convergence Rate of Training Recurrent Neural Networkscited by 82
  5. 2019Enhanced Convolutional Neural Tangent Kernelscited by 76
  6. 2016Deep vs. shallow networks : An approximation theory perspectivecited by 63
  7. 2020Neural Kernels Without Tangentscited by 56
  8. 2020Kernel Alignment Risk Estimator: Risk Prediction from Training Datacited by 54
  9. 2016Inductive Bias of Deep Convolutional Networks through Pooling Geometrycited by 53
  10. 2014Convolutional Kernel Networkscited by 47
  11. 2016Convolutional Rectifier Networks as Generalized Tensor Decompositionscited by 32
  12. 2020Why Are Convolutional Nets More Sample-Efficient than Fully-Connected Nets?cited by 32
  13. 2021Approximation and Learning with Deep Convolutional Models: a Kernel Perspectivecited by 31
  14. 2016End-to-End Kernel Learning with Supervised Convolutional Kernel Networkscited by 28
  15. 2021Locality defeats the curse of dimensionality in convolutional teacher-student scenarioscited by 26
  16. 2020Computational Separation Between Convolutional and Fully-Connected Networkscited by 19
  17. 2021The Unreasonable Effectiveness of Patches in Deep Convolutional Kernels Methodscited by 8
  18. 2020Harmonic Decompositions of Convolutional Networkscited by 6

Built on by

Cited by year

Citing papers per year: 2022: 6; 2023: 8; 2024: 5; 2025: 2.

21 papers.

Sort:

By area:

  1. 2022Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regressioncited by 42
  2. 2023The SSL Interplay: Augmentations, Inductive Bias, and Generalizationcited by 40
  3. 2023What can a Single Attention Layer Learn? A Study Through the Random Features Lenscited by 39
  4. 2022Data-driven emergence of convolutional structure in neural networkscited by 29
  5. 2024Dimension-free deterministic equivalents and scaling laws for random feature regressioncited by 23
  6. 2022Fast Rates for Noisy Interpolation Require Rethinking the Effects of Inductive Biascited by 21
  7. 2023Theoretical Analysis of Inductive Biases in Deep Convolutional Networkscited by 21
  8. 2023Six Lectures on Linearized Neural Networkscited by 19
  9. 2022On the non-universality of deep learning: quantifying the cost of symmetrycited by 17
  10. 2024U-Nets as Belief Propagation: Efficient Classification, Denoising, and Diffusion in Generative Hierarchical Modelscited by 17
  11. 2022What Can Be Learnt With Wide Convolutional Neural Networks?cited by 16
  12. 2022On the Spectral Bias of Convolutional Neural Tangent and Gaussian Process Kernelscited by 15
9 more
  1. 2023Optimal Rate of Kernel Regression in Large Dimensionscited by 10
  2. 2023Strong inductive biases provably prevent harmless interpolationcited by 9
  3. 2023Controlling the Inductive Bias of Wide Neural Networks by Modifying the Kernel's Spectrumcited by 9
  4. 2024Which Frequencies do CNNs Need? Emergent Bottleneck Structure in Feature Learningcited by 9
  5. 2023Pseudo-keypoint RKHS Learning for Self-supervised 6DoF Pose Estimationcited by 4
  6. 2024High-Dimensional Kernel Methods under Covariate Shift: Data-Dependent Implicit Regularizationcited by 4
  7. 2025On the Saturation Effects of Spectral Algorithms in Large Dimensionscited by 2
  8. 2024On the Pinsker bound of inner product kernel regression in large dimensionscited by 1
  9. 2025Towards High-Fidelity Gaussian Splatting with Queried-Convolution Neural Networkscited by 0