Abstract
We study the sample complexity of learning one-hidden-layer convolutional neural networks (CNNs) with non-overlapping filters. We propose a novel algorithm called approximate gradient descent for training CNNs, and show that, with high probability, the proposed algorithm with random initialization grants a linear convergence to the ground-truth parameters up to statistical precision. Compared with existing work, our result applies to general non-trivial, monotonic and Lipschitz continuous activation functions including ReLU, Leaky ReLU, Sigmod and Softplus etc. Moreover, our sample complexity beats existing results in the dependency of the number of hidden nodes and filter size. In fact, our result matches the information-theoretic lower bound for learning one-hidden-layer CNNs with linear activation functions, suggesting that our sample complexity is tight. Our theoretical analysis is backed up by numerical experiments.
Introduction
Deep learning's practical success often outpaces its theoretical understanding. While Convolutional Neural Networks (CNNs) are fundamental to computer vision, establishing rigorous guarantees on the amount of data required to learn their parameters—known as sample complexity—has proven challenging. Most existing theoretical frameworks are restricted to specific activation functions like ReLU or suffer from loose bounds that do not reflect the optimal efficiency possible.
The core challenge lies in the non-convex nature of neural network loss landscapes, which are typically riddled with local minima and saddle points. This paper addresses the problem of parameter recovery: can a "student" network find the exact weights of a "teacher" network from a finite set of samples? The authors introduce a unified framework that provides tight sample complexity bounds for a wide class of activation functions.
Approximate Gradient Descent (AGD)
To overcome the limitations of standard optimization techniques, the authors propose Approximate Gradient Descent (AGD). In standard gradient descent, the update rule involves the derivative of the activation function ($\sigma'$), which can be complex to analyze and may lead to vanishing or exploding gradients.
The key innovation in AGD is replacing the $\sigma'$ term with a carefully chosen constant ($\xi^{-1}$), derived from the expected behavior of the activation function under Gaussian input. This simplification ensures that the update direction remains sufficiently aligned with the true gradient to guarantee progress while making the mathematical analysis tractable. Additionally, the algorithm incorporates iterative weight normalization for the convolutional filters and learns both the filters and the output layer weights simultaneously, a significant advancement over previous methods that often assumed a fixed second layer.
Comparison with Prior Work
The primary contribution of this work is achieving "tight" sample complexity. The derived bound of $\tilde{O}((r + k) \cdot \epsilon^{-2})$, where $r$ is the filter size and $k$ is the number of filters, matches the information-theoretic lower bound for linear networks. This suggests that the proposed algorithm is statistically optimal for the given architecture.
As shown in the table above, AGD outperforms previous algorithms like Convotron and Double Convotron by supporting a broader range of activation functions and achieving a more efficient sample complexity. While prior works were often limited to ReLU or linear activations, AGD's guarantees extend to any non-trivial, monotonic, and Lipschitz continuous function, including Sigmoid and Softplus.
Experimental Results
The theoretical findings are supported by experiments on synthetic datasets where inputs are drawn from a standard Gaussian distribution. The labels are generated by a teacher network with added sub-Gaussian noise.
Key empirical observations include:
- Linear Convergence: The error between the learned weights and the ground truth decreases exponentially over time, even starting from random initialization.
- Robustness to Activations: Unlike the Double Convotron algorithm, which fails to converge for Sigmoid and Tanh activations, AGD demonstrates smooth convergence across various functions.
- Statistical Precision: The algorithm consistently reaches the "noise floor" determined by the statistical precision of the training data, confirming its robustness to noise.
Conclusion and Future Directions
This paper provides a significant step forward in the theoretical understanding of CNNs by establishing tight sample complexity bounds for one-hidden-layer networks. By introducing the AGD algorithm, the authors demonstrate that optimal learning is possible for a wide variety of activation functions under a unified framework.
However, several challenges remain. The current analysis assumes non-overlapping filters, whereas practical CNNs utilize overlapping strides. Furthermore, extending these tight bounds to deep, multi-layer architectures and relaxing the Gaussian input assumption are critical areas for future research.
Summary updated