# Why Are Convolutional Nets More Sample-Efficient than Fully-Connected Nets?

Source: [Why Are Convolutional Nets More Sample-Efficient than Fully-Connected Nets?](<https://www.sota2.com/research/paper/68fa69e91e209131cea24d25>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-27T06:07:38.365Z

Authors: Zhiyuan Li, Yi Zhang, Sanjeev Arora

Published: 2020-10-16T17:15:39.000Z

## Abstract

Convolutional neural networks often dominate fully-connected counterparts in generalization performance, especially on image classification tasks. This is often explained in terms of 'better inductive bias'. However, this has not been made mathematically rigorous, and the hurdle is that the fully connected net can always simulate the convolutional net (for a fixed task). Thus the training algorithm plays a role. The current work describes a natural task on which a provable sample complexity gap can be shown, for standard training algorithms. We construct a single natural distribution on $\\mathbb{R}^d\\times\\{\\pm 1\\}$ on which any orthogonal-invariant algorithm (i.e. fully-connected networks trained with most gradient-based methods from gaussian initialization) requires $\\Omega(d^2)$ samples to generalize while $O(1)$ samples suffice for convolutional architectures. Furthermore, we demonstrate a single target function, learning which on all possible distributions leads to an $O(1)$ vs $\\Omega(d^2/\\varepsilon)$ gap. The proof relies on the fact that SGD on fully-connected network is orthogonal equivariant. Similar results are achieved for $\\ell\_2$ regression and adaptive training algorithms, e.g. Adam and AdaGrad, which are only permutation equivariant.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2010.08515>)

[PDF](<https://arxiv.org/pdf/2010.08515.pdf>)
