# Computational Separation Between Convolutional and Fully-Connected Networks

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

## Key facts

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

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

- [Video Super-Resolution Transformer](https://mlsanity.com/paper/2106.06847/) (2021)
- [Patch-level Routing in Mixture-of-Experts is Provably Sample-efficient for Convolutional Neural Networks](https://mlsanity.com/paper/2306.04073/) (2023)
- [Approximation and Learning with Deep Convolutional Models: a Kernel Perspective](https://mlsanity.com/paper/2102.10032/) (2021)
- [On the Power of Differentiable Learning versus PAC and SQ Learning](https://mlsanity.com/paper/2108.04190/) (2021)
- [Locality defeats the curse of dimensionality in convolutional teacher-student scenarios](https://mlsanity.com/paper/2106.08619/) (2021)
- [Provable Advantage of Curriculum Learning on Parity Targets with Mixed Inputs](https://mlsanity.com/paper/2306.16921/) (2023)
- [Learning with convolution and pooling operations in kernel methods](https://mlsanity.com/paper/2111.08308/) (2021)
- [A Provably Effective Method for Pruning Experts in Fine-tuned Sparse Mixture-of-Experts](https://mlsanity.com/paper/2405.16646/) (2024)
- [A Mathematical Model for Curriculum Learning for Parities](https://mlsanity.com/paper/2301.13833/) (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)
- [What Can Be Learnt With Wide Convolutional Neural Networks?](https://mlsanity.com/paper/2208.01003/) (2022)
- [On the Sample Complexity of Learning under Invariance and Geometric Stability](https://mlsanity.com/paper/2106.07148/) (2021)
- [An initial alignment between neural network and target is needed for gradient descent to learn](https://mlsanity.com/paper/2202.12846/) (2022)
- [A Kernel Perspective of Skip Connections in Convolutional Networks](https://mlsanity.com/paper/2211.14810/) (2022)
- [Beyond Statistical Learning: Exact Learning Is Essential for General Intelligence](https://mlsanity.com/paper/2506.23908/) (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)
- [Kernels, Data & Physics](https://mlsanity.com/paper/2307.02693/) (2023)
- [Towards High-Fidelity Gaussian Splatting with Queried-Convolution Neural Networks](https://mlsanity.com/paper/2512.12898/) (2025)
- [An all-transistor physical-learning transformer can be trained to perform in-context learning](https://mlsanity.com/paper/2610.12571/) (2026)

## Abstract (arXiv)

Convolutional neural networks (CNN) exhibit unmatched performance in a multitude of computer vision tasks. However, the advantage of using convolutional networks over fully-connected networks is not understood from a theoretical perspective. In this work, we show how convolutional networks can leverage locality in the data, and thus achieve a computational advantage over fully-connected networks. Specifically, we show a class of problems that can be efficiently solved using convolutional networks trained with gradient-descent, but at the same time is hard to learn using a polynomial-size fully-connected network.