Computational separation between convolutional and fully-connected networks
E Malach, S Shalev-Shwartz - arXiv preprint arXiv:2010.01369, 2020 - arxiv.org
arXiv preprint arXiv:2010.01369, 2020•arxiv.org
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 …
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 …
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.
arxiv.org