Learnability of convolutional neural networks for infinite dimensional input via mixed and anisotropic smoothness

Sho Okumoto, Taiji SuzukiICLR 2022 · OpenReview

This paper provides a rigorous theoretical foundation for why Convolutional Neural Networks (CNNs) are so effective at processing high-dimensional data—like images and audio—without falling victim to the "curse of dimensionality."

Overview

The authors prove that CNNs can learn functions with infinite-dimensional inputs at a "dimension-independent" rate, provided the target function exhibits mixed or anisotropic smoothness. They further demonstrate that dilated convolutions are mathematically superior when the important features of a function are sparsely distributed across a large input space.

The Curse of Dimensionality in Deep Learning

In classical statistical learning theory, the "curse of dimensionality" is a major hurdle. It suggests that as the number of input features ($d$) increases, the number of samples ($n$) needed to learn a function grows exponentially. For an image with thousands of pixels, theory would predict we need an astronomical amount of data to learn anything useful.

However, in the real world, CNNs perform exceptionally well on high-dimensional data with relatively modest datasets. There is a gap between this practical success and existing theory, which often assumes $d$ is much smaller than $n$. The authors set out to answer: Can we prove that CNNs are "learnable" even when the input dimension is effectively infinite?

Smoothness and Network Architectures

The researchers tackle this gap by defining specific "smoothness" conditions for functions:

  • Anisotropic Smoothness: The idea that a function is "smoother" (less sensitive) in some directions than others. For example, in an image, global structure (low frequency) might be more important than individual pixel noise (high frequency).
  • Mixed Smoothness: A condition where the function's complexity is constrained even when multiple input variables interact.

They analyze three types of architectures using the framework of Besov spaces extended to infinite dimensions:

  1. Fully Connected Networks (FNNs): Used as a baseline.
  2. Standard CNNs: Analyzed for their ability to handle inputs where smoothness increases with the coordinate index.
  3. Dilated CNNs: Analyzed for their ability to perform "coordinate selection" when the important features are scattered sparsely across a long input sequence.

Key Insights

  • Smoothness Beats the Curse: The "curse of dimensionality" isn't an inherent property of the input size, but of the function space. If we assume the target function is smoother in "higher" dimensions (meaning fine-grained details at the end of a sequence matter less), the error rates become independent of $d$.
  • CNNs as Automatic Feature Selectors: The paper shows that CNNs naturally "extract" the relevant low-frequency or high-smoothness components of an infinite-dimensional input, effectively ignoring the "infinite" noise.
  • The Necessity of Dilation: A standard CNN is effective if the "important" parts of the data are at the beginning of the sequence. But if the important features are sparse and far apart, dilated convolutions are required. The authors prove that dilated CNNs can capture long-range dependencies and maintain optimal convergence rates where standard CNNs would fail.

Theoretical Results and Validation

The core contribution of the paper is the mathematical derivation of approximation errors (how well a network can represent a function) and estimation errors (how well it does learn from finite samples).

  • Dimension-Independent Convergence: The authors derived a polynomial estimation error bound that depends only on the smoothness of the target function, not the input dimension.
  • Optimal Rates: For anisotropic smoothness, the error rate matches the (near) minimax optimal rate of $n^{-\frac{2\tilde{a}}{2\tilde{a}+1}}$, where $\tilde{a}$ represents the average smoothness across all dimensions.
Comparison of theoretical estimation error rates

While primarily a theoretical paper, the authors included numerical experiments on synthetic functions to verify their theorems. By training CNNs and Dilated CNNs on functions with specific smoothness properties, they demonstrated that the estimation error remains almost constant as the input dimension $d$ increases from 100 to 1000. This empirically confirms that the model's performance is truly independent of the input's dimensionality.

Limitations and Future Work

  • Stationarity Assumptions: The current theory assumes that the "importance" of coordinates is tied to their index (e.g., the first few elements are the most important). In real-world images, important features can appear anywhere.
  • Fixed Smoothness Configuration: The authors suggest that future work should explore cases where the smoothness depends on the location of the input (non-stationary smoothness), which would better capture the nature of complex visual scenes.
  • Architecture Scope: The analysis focuses on ReLU activations and specific dilated structures; it does not yet account for other modern staples like Attention mechanisms or Batch Normalization.

Summary updated

Abstract

Among a wide range of success of deep learning, convolutional neural networks have been extensively utilized in several tasks such as speech recognition, image processing, and natural language processing, which require inputs with large dimensions. Several studies have investigated function estimation capability of deep learning, but most of them have assumed that the dimensionality of the input is much smaller than the sample size. However, for typical data in applications such as those handled by the convolutional neural networks described above, the dimensionality of inputs is relatively high or even infinite. In this paper, we investigate the approximation and estimation errors of the (dilated) convolutional neural networks when the input is infinite dimensional. Although the approximation and estimation errors of neural networks are affected by the curse of dimensionality in the existing analyses for typical function spaces such as the \Holder and Besov spaces, we show that, by considering anisotropic smoothness, they can alleviate exponential dependency on the dimensionality but they only depend on the smoothness of the target functions. Our theoretical analysis supports the great practical success of convolutional networks. Furthermore, we show that the dilated convolution is advantageous when the smoothness of the target function has a sparse structure.
BibTeX
@inproceedings{okumoto2022learnability,
  author = {Sho Okumoto and Taiji Suzuki},
  title = {{Learnability of convolutional neural networks for infinite dimensional input via mixed and anisotropic smoothness}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=dgxFTxuJ50e},
}
Figure