# Why Are Convolutional Nets More Sample-Efficient than Fully-Connected Nets?

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

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Oct 2020.

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

- [What Happens after SGD Reaches Zero Loss? --A Mathematical Framework](https://mlsanity.com/paper/2110.06914/) (2021)
- [Learning with invariances in random features and kernel models](https://mlsanity.com/paper/2102.13219/) (2021)
- [Theory for Equivariant Quantum Neural Networks](https://mlsanity.com/paper/2210.08566/) (2022)
- [Why Do You Grok? A Theoretical Analysis of Grokking Modular Addition](https://mlsanity.com/paper/2407.12332/) (2024)
- [Approximation and Learning with Deep Convolutional Models: a Kernel Perspective](https://mlsanity.com/paper/2102.10032/) (2021)
- [The Exact Sample Complexity Gain from Invariances for Kernel Regression](https://mlsanity.com/paper/2303.14269/) (2023)
- [When can transformers reason with abstract symbols?](https://mlsanity.com/paper/2310.09753/) (2023)
- [Learning with convolution and pooling operations in kernel methods](https://mlsanity.com/paper/2111.08308/) (2021)
- [Theoretical Analysis of Inductive Biases in Deep Convolutional Networks](https://mlsanity.com/paper/2305.08404/) (2023)
- [On the non-universality of deep learning: quantifying the cost of symmetry](https://mlsanity.com/paper/2208.03113/) (2022)
- [Eigenspace Restructuring: a Principle of Space and Frequency in Neural Networks](https://mlsanity.com/paper/2112.05611/) (2021)
- [Convolutional Visual Prompt for Robust Visual Perception](https://mlsanity.com/paper/2303.00198/) (2023)
- [U-Nets as Belief Propagation: Efficient Classification, Denoising, and Diffusion in Generative Hierarchical Models](https://mlsanity.com/paper/2404.18444/) (2024)
- [On the Sample Complexity of Learning under Invariance and Geometric Stability](https://mlsanity.com/paper/2106.07148/) (2021)
- [Data-dependent Generalization Bounds via Variable-Size Compressibility](https://mlsanity.com/paper/2303.05369/) (2023)
- [Which Frequencies do CNNs Need? Emergent Bottleneck Structure in Feature Learning](https://mlsanity.com/paper/2402.08010/) (2024)
- [Ensembles provably learn equivariance through data augmentation](https://mlsanity.com/paper/2410.01452/) (2024)
- [Model-agnostic Measure of Generalization Difficulty](https://mlsanity.com/paper/2305.01034/) (2023)
- [Synergy and Symmetry in Deep Learning: Interactions between the Data, Model, and Inference Algorithm](https://mlsanity.com/paper/2207.04612/) (2022)
- [On Learning Verifiers and Implications to Chain-of-Thought Reasoning](https://mlsanity.com/paper/2505.22650/) (2025)
- [Role of Locality and Weight Sharing in Image-Based Tasks: A Sample Complexity Separation between CNNs, LCNs, and FCNs](https://mlsanity.com/paper/2403.15707/) (2024)
- [Towards Exact Computation of Inductive Bias](https://mlsanity.com/paper/2406.15941/) (2024)
- [Why self-attention is Natural for Sequence-to-Sequence Problems? A Perspective from Symmetries](https://mlsanity.com/paper/2210.06741/) (2022)
- [Does Sparse Connectivity Improve Generalization? Convolutional Networks Below the Edge of Stability](https://mlsanity.com/paper/2603.04807/) (2026)
- [Hard labels sampled from sparse targets mislead rotation invariant algorithms](https://mlsanity.com/paper/2603.20967/) (2026)
- [Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/2103.01887/) (2021)
- [Beyond Linear Subspace Clustering: A Comparative Study of Nonlinear Manifold Clustering Algorithms](https://mlsanity.com/paper/2103.10656/) (2021)
- [Kernels, Data & Physics](https://mlsanity.com/paper/2307.02693/) (2023)
- [Noise misleads rotation invariant algorithms on sparse targets](https://mlsanity.com/paper/2403.02697/) (2024)
- [Stability Analysis of Equivariant Convolutional Representations Through The Lens of Equivariant Multi-layered CKNs](https://mlsanity.com/paper/2408.04277/) (2024)

## Abstract (arXiv)

Convolutional neural networks often dominate fully-connected counterparts in generalization performance, especially on image classification tasks. This is often explained in terms of 'better inductive bias'. However, this has not been made mathematically rigorous, and the hurdle is that the fully connected net can always simulate the convolutional net (for a fixed task). Thus the training algorithm plays a role. The current work describes a natural task on which a provable sample complexity gap can be shown, for standard training algorithms. We construct a single natural distribution on ℝd×± 1 on which any orthogonal-invariant algorithm (i.e. fully-connected networks trained with most gradient-based methods from gaussian initialization) requires Omega(d2) samples to generalize while O(1) samples suffice for convolutional architectures. Furthermore, we demonstrate a single target function, learning which on all possible distributions leads to an O(1) vs Omega(d2/varepsilon) gap. The proof relies on the fact that SGD on fully-connected network is orthogonal equivariant. Similar results are achieved for ℓ2 regression and adaptive training algorithms, e.g. Adam and AdaGrad, which are only permutation equivariant.