mlsanityData to 14 Oct 2026

Computational Separation Between Convolutional and Fully-Connected Networks

arXiv 2010.01369 ↗First posted 3 Oct 2020cs.LG stat.MLcited by 20

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 7; 2022: 4; 2023: 4; 2024: 2; 2025: 2; 2026: 1.

20 papers.

Sort:

By area:

  1. 2021Video Super-Resolution Transformercited by 121
  2. 2023Patch-level Routing in Mixture-of-Experts is Provably Sample-efficient for Convolutional Neural Networkscited by 35
  3. 2021Approximation and Learning with Deep Convolutional Models: a Kernel Perspectivecited by 31
  4. 2021On the Power of Differentiable Learning versus PAC and SQ Learningcited by 28
  5. 2021Locality defeats the curse of dimensionality in convolutional teacher-student scenarioscited by 26
  6. 2023Provable Advantage of Curriculum Learning on Parity Targets with Mixed Inputscited by 22
  7. 2021Learning with convolution and pooling operations in kernel methodscited by 21
  8. 2024A Provably Effective Method for Pruning Experts in Fine-tuned Sparse Mixture-of-Expertscited by 21
  9. 2023A Mathematical Model for Curriculum Learning for Paritiescited by 19
  10. 2022On the non-universality of deep learning: quantifying the cost of symmetrycited by 18
  11. 2021Eigenspace Restructuring: a Principle of Space and Frequency in Neural Networkscited by 17
  12. 2022What Can Be Learnt With Wide Convolutional Neural Networks?cited by 16
8 more
  1. 2021On the Sample Complexity of Learning under Invariance and Geometric Stabilitycited by 13
  2. 2022An initial alignment between neural network and target is needed for gradient descent to learncited by 12
  3. 2022A Kernel Perspective of Skip Connections in Convolutional Networkscited by 12
  4. 2025Beyond Statistical Learning: Exact Learning Is Essential for General Intelligencecited by 6
  5. 2024Role of Locality and Weight Sharing in Image-Based Tasks: A Sample Complexity Separation between CNNs, LCNs, and FCNscited by 5
  6. 2023Kernels, Data & Physicscited by 0
  7. 2025Towards High-Fidelity Gaussian Splatting with Queried-Convolution Neural Networkscited by 0
  8. 2026An all-transistor physical-learning transformer can be trained to perform in-context learningcited by 0