Computational Separation Between Convolutional and Fully-Connected Networks
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.
Cite
Text
Malach and Shalev-Shwartz. "Computational Separation Between Convolutional and Fully-Connected Networks." International Conference on Learning Representations, 2021.Markdown
[Malach and Shalev-Shwartz. "Computational Separation Between Convolutional and Fully-Connected Networks." International Conference on Learning Representations, 2021.](https://mlanthology.org/iclr/2021/malach2021iclr-computational/)BibTeX
@inproceedings{malach2021iclr-computational,
title = {{Computational Separation Between Convolutional and Fully-Connected Networks}},
author = {Malach, Eran and Shalev-Shwartz, Shai},
booktitle = {International Conference on Learning Representations},
year = {2021},
url = {https://mlanthology.org/iclr/2021/malach2021iclr-computational/}
}