# When is a Convolutional Filter Easy To Learn?

arXiv: https://arxiv.org/abs/1709.06129 · HTML: https://mlsanity.com/paper/1709.06129/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Sep 2017.

## Built on by (most cited first, 21 of 21)

- [Scan and Snap: Understanding Training Dynamics and Token Composition in 1-layer Transformer](https://mlsanity.com/paper/2305.16380/) (2023)
- [Benign Overfitting in Two-layer Convolutional Neural Networks](https://mlsanity.com/paper/2202.06526/) (2022)
- [JoMA: Demystifying Multilayer Transformers via JOint Dynamics of MLP and Attention](https://mlsanity.com/paper/2310.00535/) (2023)
- [Over-Parameterization Exponentially Slows Down Gradient Descent for Learning a Single Neuron](https://mlsanity.com/paper/2302.10034/) (2023)
- [From Local Pseudorandom Generators to Hardness of Learning](https://mlsanity.com/paper/2101.08303/) (2021)
- [Parameter identifiability of a deep feedforward ReLU neural network](https://mlsanity.com/paper/2112.12982/) (2021)
- [Learning a Single Neuron with Bias Using Gradient Descent](https://mlsanity.com/paper/2106.01101/) (2021)
- [On the hardness of learning under symmetries](https://mlsanity.com/paper/2401.01869/) (2024)
- [ReLU Regression with Massart Noise](https://mlsanity.com/paper/2109.04623/) (2021)
- [Stable Recovery of Entangled Weights: Towards Robust Identification of Deep Neural Networks from Minimal Samples](https://mlsanity.com/paper/2101.07150/) (2021)
- [Learning and generalization of one-hidden-layer neural networks, going beyond standard Gaussian data](https://mlsanity.com/paper/2207.03615/) (2022)
- [How Does a Deep Learning Model Architecture Impact Its Privacy? A Comprehensive Study of Privacy Attacks on CNNs and Transformers](https://mlsanity.com/paper/2210.11049/) (2022)
- [Finite-Sample Analysis of Learning High-Dimensional Single ReLU Neuron](https://mlsanity.com/paper/2303.02255/) (2023)
- [On the Provable Generalization of Recurrent Neural Networks](https://mlsanity.com/paper/2109.14142/) (2021)
- [How does promoting the minority fraction affect generalization? A theoretical study of the one-hidden-layer neural network on group imbalance](https://mlsanity.com/paper/2403.07310/) (2024)
- [Magnitude and Angle Dynamics in Training Single ReLU Neurons](https://mlsanity.com/paper/2209.13394/) (2022)
- [Finite Sample Identification of Wide Shallow Neural Networks with Biases](https://mlsanity.com/paper/2211.04589/) (2022)
- [Global Convergence and Rich Feature Learning in L-Layer Infinite-Width Neural Networks under μP Parametrization](https://mlsanity.com/paper/2503.09565/) (2025)
- [Structured Directional Pruning via Perturbation Orthogonal Projection](https://mlsanity.com/paper/2107.05328/) (2021)
- [Demystifying the Global Convergence Puzzle of Learning Over-parameterized ReLU Nets in Very High Dimensions](https://mlsanity.com/paper/2206.03254/) (2022)
- [Linear RNNs Provably Learn Linear Dynamic Systems](https://mlsanity.com/paper/2211.10582/) (2022)

## Abstract (arXiv)

We analyze the convergence of (stochastic) gradient descent algorithm for learning a convolutional filter with Rectified Linear Unit (ReLU) activation function. Our analysis does not rely on any specific form of the input distribution and our proofs only use the definition of ReLU, in contrast with previous works that are restricted to standard Gaussian input. We show that (stochastic) gradient descent with random initialization can learn the convolutional filter in polynomial time and the convergence rate depends on the smoothness of the input distribution and the closeness of patches. To the best of our knowledge, this is the first recovery guarantee of gradient-based algorithms for convolutional filter on non-Gaussian input distributions. Our theory also justifies the two-stage learning rate strategy in deep neural networks. While our focus is theoretical, we also present experiments that illustrate our theoretical findings.