Approximation Analysis of CNNs from a Feature Extraction View

Feng Han, Jianfei Li, Ding‐Xuan ZhouSSRN 2022 · DOI

Abstract

This paper provides a rigorous mathematical foundation for the efficiency of Convolutional Neural Networks (CNNs) in processing high-dimensional data. By analyzing CNNs through the lens of feature extraction and approximation theory, the authors demonstrate that deep multi-channel CNNs can extract complex linear features with significantly fewer parameters than fully connected networks, requiring only logarithmic depth relative to input size.

Introduction

While deep learning has achieved massive empirical success, a complete theoretical "blueprint" explaining why specific architectures—like the convolutional layers in a CNN—outperform generic fully connected networks (FNNs) has been elusive. FNNs suffer from the "curse of dimensionality," requiring a staggering number of parameters to learn simple features from high-dimensional inputs. CNNs mitigate this through local connectivity and weight sharing. This paper bridges the gap between practice and theory by analyzing CNNs as efficient feature extractors and function approximators.

Methodology

The authors employ a constructive mathematical approach, demonstrating how to build a CNN that performs specific tasks. A key innovation is the Hierarchical Matrix Partitioning method. To analyze 2D CNNs, the authors developed a specialized vectorization operator $T$ that maps 2D spatial structures into 1D sequences. This mapping preserves the mathematical properties of convolutions, allowing the researchers to extend 1D theoretical results to 2D image data.

Hierarchical partitioning and vectorization of a 2D input matrix into a 1D sequence to preserve spatial properties for convolutional analysis.

The network is modeled as a two-part system: a deep multi-channel CNN "front-end" for dimensionality reduction (feature extraction) followed by a shallow FNN "back-end" for final function approximation. They use harmonic analysis to show how a deep stack of small filters can represent complex, large-scale linear transformations.

Key Insights and Ideas

The paper establishes several critical theoretical properties of CNNs:

  • CNNs as Efficient Dictionary Learners: The authors prove that a CNN can be constructed to exactly compute the inner product of an input with a "dictionary" of feature vectors, making them more powerful than traditional Fourier or Wavelet transforms.
  • Logarithmic Depth Advantage: A CNN only needs a depth of $O(\log d)$ (where $d$ is the input dimension) for effective feature extraction, far more efficient than the linear depth $O(d)$ suggested by previous theories.
  • Beating the Curse of Dimensionality: For data lying on an $m$-dimensional manifold, the total parameter count depends primarily on the intrinsic dimension $m$ and only logarithmically on the ambient dimension $d$. This explains why CNNs are so effective at identifying low-dimensional structures in high-dimensional image data.
Representation of data supported on low-dimensional manifolds within a high-dimensional space.
  • SVD via CNN: The authors demonstrate that a 2D CNN can extract the singular values of an input matrix, suggesting that CNNs inherently perform a form of non-linear Principal Component Analysis (PCA).

Key Results

The theoretical analysis yields impressive bounds on parameter efficiency and approximation accuracy:

  • Parameter Efficiency: The total number of free parameters required for a CNN to extract $m$ features from a $d$-dimensional input is bounded by $8md$, a massive reduction compared to the $d^2$ requirements of FNNs.
  • Approximation Rates: A CNN-FNN hybrid can approximate smooth functions with an error rate of $O(n^{-1/2})$, where $n$ is the number of neurons in the final layer, matching the best-known rates for shallow networks while leveraging the CNN's superior feature extraction.

Limitations and Future Work

While providing a strong foundation, the paper identifies several areas for further research. The analysis primarily focuses on linear feature extraction; the full power of non-linear interactions in intermediate layers remains to be fully explored. Additionally, the proofs are constructive—they show a solution exists but do not guarantee that standard training algorithms like Stochastic Gradient Descent (SGD) will converge to it. Future work could extend these results to 3D convolutions for video data or more complex architectures like Transformers.

Summary updated

BibTeX
@misc{han2022approximation,
  author = {Feng Han and Jianfei Li and Ding‐Xuan Zhou},
  title = {{Approximation Analysis of CNNs from a Feature Extraction View}},
  year = {2022},
  eprint = {2210.09041},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2210.09041},
  howpublished = {SSRN},
}
Figure