Approximation with CNNs in Sobolev Space: with Applications to Classification

Guohao Shen, Yuling Jiao, Yuanyuan Lin, Jian HuangNeurIPS 2022 · OpenReview

Convolutional Neural Networks (CNNs) are the undisputed workhorses of modern computer vision, yet the theoretical understanding of why they perform so well in high-dimensional spaces has lagged behind their empirical success. The NeurIPS 2022 paper, "Approximation with CNNs in Sobolev Space: with Applications to Classification," provides a rigorous mathematical foundation to bridge this gap.

Moving beyond basic "universal approximation" theorems, the authors derive explicit, non-asymptotic error bounds that explain how CNN architectures interact with the underlying geometry of data. Crucially, they prove that CNNs can circumvent the notorious "curse of dimensionality" when input data lies on or near a low-dimensional manifold.

The Problem: Gaps in CNN Theory

In deep learning theory, the curse of dimensionality dictates that as the number of input features ($d$) increases, the amount of data required to maintain a specific approximation accuracy grows exponentially. While Feedforward Neural Networks (FNNs) have been extensively studied in this context, CNNs have lacked similarly detailed theoretical guarantees.

Historically, CNN theory has suffered from three major limitations:

  1. Asymptotic Limits: Many proofs only hold true as the network depth approaches infinity, offering little guidance for practical, finite networks.
  2. Exponential Prefactors: Even when convergence rates were known, the constant factors (prefactors) in the error bounds often exploded exponentially with the dimension $d$, rendering the bounds practically meaningless for high-dimensional inputs like images.
  3. Lack of Manifold Results: There was limited formal proof that CNNs specifically benefit from data residing on low-dimensional manifolds (e.g., the "manifold of natural images").
Comparison of theoretical guarantees provided by this paper versus prior work.

Methodology: A Rigorous Framework

To address these gaps, the authors focus on ReLU-activated downsampled CNNs. Their theoretical framework is built on several key pillars:

  • Sobolev and Hölder Spaces: Instead of relying on simple continuity measures, the authors characterize the "smoothness" of target functions using Sobolev spaces ($W^{\beta,p}$). This measures both the size of a function and its derivatives, providing a much more realistic model for real-world signals.
  • Explicit Parameterization: Breaking from previous asymptotic work, they express error bounds explicitly in terms of tangible network attributes: depth ($L$), filter lengths ($s$), and total parameters ($S$).
  • Error Decomposition: For classification tasks, the "excess risk" (the gap between the model's performance and the theoretical optimum) is split into two components:
  • Stochastic Error: The penalty incurred from having a finite training dataset.
  • Approximation Error: The theoretical limit of how well the CNN architecture can fit the true underlying function.
  • The Manifold Assumption: They introduce a realistic condition where data is supported on a $\rho$-neighborhood of a $d_{\mathcal{M}}$-dimensional Riemannian submanifold, where the intrinsic dimension $d_{\mathcal{M}}$ is much smaller than the ambient dimension $d$.

Key Insights and Theoretical Breakthroughs

The paper delivers several major theoretical breakthroughs that explain CNN efficacy:

1. Polynomial vs. Exponential Prefactors

For functions in the Hölder space, the authors prove that the "prefactor" (the constant $C$ in the error formula) depends on the dimension $d$ polynomially, rather than exponentially. This is a massive leap forward, as it makes the theoretical bounds practically relevant for high-dimensional inputs.

2. Manifold Adaptation and Beating the Curse

The most significant finding is that CNNs are inherently "adaptive." If the data lives on a low-dimensional manifold, the approximation rate depends on the intrinsic dimension ($d_{\mathcal{M}}$) rather than the ambient dimension ($d$).

Mathematically, for a function with smoothness $\beta$, the standard approximation error is bounded by $O((NM)^{-2\beta/d})$. However, when data is on a manifold, the $d$ in the exponent's denominator is replaced by a much smaller $d_{\epsilon}$ (related to the manifold dimension). This significantly speeds up the theoretical convergence rate and perfectly explains why a CNN can effectively process a million-pixel image: it is learning the lower-dimensional "true" information.

3. Architecture Flexibility

The derived bounds are non-asymptotic and flexible. The authors demonstrate that the same error rate can be achieved by either increasing the depth of the network or increasing the length of the convolutional filters. This provides a solid theoretical basis for various architectural design choices.

4. Surrogate Loss Consistency

These theoretical guarantees are not fragile; the authors show that their bounds hold across a wide variety of common surrogate loss functions used in practice, including cross-entropy, hinge loss (SVMs), and logistic loss.

Limitations and Future Directions

While this paper represents a significant step forward, it is a purely theoretical work with a few notable boundaries:

  • Binary Classification: The current proofs are restricted to binary classification. Extending these bounds to multi-class problems remains a logical next step.
  • Inductive Biases: While the paper successfully justifies CNNs via manifold structures, it does not fully capture other critical "inductive biases" of CNNs, such as translation invariance or rotation symmetry.
  • The Optimization Gap: The proofs assume the ability to find the "empirical risk minimizer" (the absolute best weights). In reality, networks are trained via Stochastic Gradient Descent (SGD), meaning there is still a practical gap between what a network can theoretically represent and what it actually learns during training.

Summary updated

Abstract

We derive a novel approximation error bound with explicit prefactor for Sobolev-regular functions using deep convolutional neural networks (CNNs). The bound is non-asymptotic in terms of the network depth and filter lengths, in a rather flexible way. For Sobolev-regular functions which can be embedded into the H\"older space, the prefactor of our error bound depends on the ambient dimension polynomially instead of exponentially as in most existing results, which is of independent interest. We also establish a new approximation result when the target function is supported on an approximate lower-dimensional manifold. We apply our results to establish non-asymptotic excess risk bounds for classification using CNNs with convex surrogate losses, including the cross-entropy loss, the hinge loss (SVM), the logistic loss, the exponential loss and the least squares loss. We show that the classification methods with CNNs can circumvent the curse of dimensionality if input data is supported on a neighborhood of a low-dimensional manifold.
BibTeX
@inproceedings{shen2022approximation,
  author = {Guohao Shen and Yuling Jiao and Yuanyuan Lin and Jian Huang},
  title = {{Approximation with CNNs in Sobolev Space: with Applications to Classification}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=lZUZTyPUaxz},
}
Figure