Computational Separation Between Convolutional and Fully-Connected Networks
arXiv:2010.01369
Abstract
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.
References in corpus (18)
- Spectral Networks and Locally Connected Networks on Graphs
- Neural Architecture Search: A Survey
- Gradient Descent Provably Optimizes Over-parameterized Neural Networks
- Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
- Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks
- Bayesian Deep Convolutional Networks with Many Channels are Gaussian Processes
- Quantifying Translation-Invariance in Convolutional Neural Networks
- SGD Learns the Conjugate Kernel Class of the Network
- Failures of Gradient-Based Deep Learning
- Inductive Bias of Deep Convolutional Networks through Pooling Geometry
- How far can we go without convolution: Improving fully-connected networks
- Analysis and Design of Convolutional Networks via Hierarchical Tensor Decompositions
- A Provably Correct Algorithm for Deep Learning that Actually Works
- A Corrective View of Neural Networks: Representation, Memorization and Learning
- Learning Parities with Neural Networks
- Towards Learning Convolutions from Scratch
- Weight Sharing is Crucial to Succesful Optimization
- Deep Learning and Hierarchal Generative Models