Research map / Learning theory and algorithms / Sample complexity
Role of Locality and Weight Sharing in Image-Based Tasks: A Sample Complexity Separation between CNNs, LCNs, and FCNs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces the Dynamic Signal Distribution (DSD) task and proves, for orthogonally equivariant gradient-descent-style algorithms, sample complexity separations between FCNs, LCNs, and CNNs (FCN ~k^2 d, LCN ~k(k+d), CNN ~k+d).
Problem
Existing sample-complexity separations between CNNs, locally connected networks (LCNs), and fully connected networks (FCNs) either ignore the optimizer, give only upper bounds, or use data models that do not capture locality and translation invariance of vision tasks.
Approach
A translation-invariant "dynamic signal" classification task where a d-sparse signal vector appears in one of k patches amid Gaussian noise; under equivariant algorithms, lower bounds are derived via a simulation/decomposition argument and a Fano variant for randomized algorithms, and matching gradient-descent upper bounds are given for LCNs and CNNs.
Key results
- FCNs under any equivariant algorithm need Omega(sigma^2 k^2 d) samples, versus Otilde(sigma^2 k(k+d)) for LCNs
- LCNs need Omega(sigma^2 kd) samples versus Otilde(sigma^2 (k+d)) for CNNs
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add locality by replacing an FCN with an LCN | FCN · DSD | sample complexity: Ω(σ²k²d) -> tilde{O}(σ²k(k+d)) | Helped |
| add weight sharing by replacing an LCN with a CNN | LCN · DSD | sample complexity: Ω(σ²kd) -> tilde{O}(σ²(k+d)) | Helped |
Surprising findings
- The k+d factor in LCN and CNN upper bounds (rather than d) is an artifact of gradient descent analysis, possibly reflecting an algorithmic cost
Limitations
- Only one-hidden-layer networks are analyzed
- Only a single signal appears in the input; multi-signal and depth effects are not covered
- Upper bounds carry an extra k+d factor rather than d
Experimental setup
Datasets: DSD (synthetic Dynamic Signal Distribution)
Metrics: sample complexity expected risk (squared loss)
Baselines: FCN LCN CNN
Builds on: Fano's Theorem equivariant algorithms (Abbe et al.) CNN sample complexity separation (Wang & Wu)
Closest papers by meaning
- Theoretical Analysis of the Inductive Biases in Deep Convolutional Networks (NeurIPS 2023 · similarity 0.92)
- On the Connection between Local Attention and Dynamic Depth-wise Convolution (ICLR 2022 · similarity 0.88)
- Locality in Image Diffusion Models Emerges from Data Statistics (NeurIPS 2025 · similarity 0.87)
- CAM Back Again: Large Kernel CNNs from a Weakly Supervised Object Localization Perspective (CVPR 2024 · similarity 0.86)
- An Image is Worth More Than 16x16 Patches: Exploring Transformers on Individual Pixels (ICLR 2025 · similarity 0.85)
- LSNet: See Large, Focus Small (CVPR 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.