Minimax optimality of convolutional neural networks for infinite dimensional input-output problems and separation from kernel methods

Yuto Nishimura, Taiji SuzukiICLR 2024 · OpenReview

Deep learning has achieved remarkable success in complex, high-dimensional tasks such as text-to-image generation and audio processing. However, classical statistical theory often struggles to explain these successes due to the "curse of dimensionality"—the phenomenon where the amount of data needed to learn a function explodes exponentially as the number of input features grows.

While recent theoretical work has shown how neural networks can bypass this curse for high-dimensional inputs, most of these studies assume a simple, one-dimensional (scalar) output. In practice, systems like Stable Diffusion or Whisper deal with "infinite-dimensional" problems on both ends: mapping long sequences of text or audio to high-resolution images or transcripts.

This paper bridges the gap between practice and theory by investigating whether dilated Convolutional Neural Networks (CNNs) can efficiently learn mappings between two infinite-dimensional spaces, and crucially, whether they fundamentally outperform classical linear methods in doing so.

Theoretical Framework: Dilated CNNs and Smooth Spaces

To rigorously analyze these high-dimensional mappings, the authors utilize a mathematical framework based on $\\gamma$-smooth spaces. This approach treats data as an infinite sequence of components (analogous to frequency bands in audio), where different components exhibit varying levels of "smoothness."

The study focuses specifically on dilated CNNs. In these architectures, convolutional filters contain "gaps" (dilation), allowing the network to capture long-range dependencies across high-dimensional inputs without a massive increase in parameters. The authors evaluate these networks through a two-step analytical process:

  1. Approximation and Estimation Analysis: Calculating how well a dilated CNN can represent a complex infinite-to-infinite mapping and determining the sample complexity required to learn it.
  2. Minimax Optimality and Linear Separability: Determining the theoretical "speed limit" (minimax rate) for any possible estimator and comparing the CNN's performance against the entire class of linear estimators, including Kernel Ridge Regression and $k$-Nearest Neighbors ($k$-NN).

Key Findings: Minimax Optimality and the "Kernel Gap"

The paper's theoretical analysis yields several profound insights into why deep learning architectures succeed where classical methods fail.

Smoothness Over Dimension

The authors mathematically prove that the error rate of a dilated CNN does not depend on the "infinite" number of dimensions. Instead, it relies entirely on the smoothness of the target function and the decay rate of the output components. If the critical parts of the output decay quickly enough, the network can effectively ignore the infinite "tail" of noise. Dilated convolutions prove particularly adept at this, efficiently skipping over less relevant data to extract important coordinates.

Minimax Optimal Convergence

Dilated CNNs are shown to achieve the minimax optimal rate of convergence. The error scales approximately as: $$ \\text{Error} \\approx n^{-\\frac{(2-r)a^\\dagger}{2a^\\dagger+1}} $$ where $n$ is the number of samples, $a^\\dagger$ represents the smoothness, and $r$ represents the decay rate of the output. Notably, CNNs achieve this adaptively—they do not need to know the smoothness of the target function in advance; they discover the right features during training.

The "Kernel Gap" and Provable Superiority

Perhaps the most significant contribution of the paper is a formal "separation" result. The authors prove that for certain classes of functions, the worst-case error of any linear estimator is strictly worse than that of a dilated CNN. Linear methods like kernels are inherently "blind" to the underlying structure of the data because they rely on fixed representations. As important features become more spread out across dimensions, linear methods fail. In contrast, the adaptive feature-learning capabilities of CNNs allow them to remain robust and achieve faster convergence rates than any linear method could theoretically manage.

Limitations and Future Directions

As a purely theoretical paper, the analysis relies on specific mathematical constraints. The proofs currently assume that the function space parameters ($p$) are at least 2, and that observation noise follows a Gaussian distribution with bounded variance. Extending these proofs to a wider range of spaces remains an open challenge.

Furthermore, while dilated CNNs are a foundational component of the deep learning toolkit, high-dimensional tasks are increasingly dominated by Transformer architectures. Extending this "infinite-to-infinite" theoretical analysis to Transformers represents a vital next step in fully understanding the mathematical foundations of modern generative AI.

Summary updated

Abstract

Recent deep learning applications, exemplified by text-to-image tasks, often involve high-dimensional inputs and outputs. While several studies have investigated the function estimation capabilities of deep learning, research on dilated convolutional neural networks (CNNs) has mainly focused on cases where input dimensions are infinite but output dimensions are one-dimensional, similar to many other studies. However, many practical deep learning tasks involve high-dimensional (or even infinite dimensional) inputs and outputs. In this paper, we investigate the optimality of dilated CNNs for estimating a map between infinite-dimensional input and output spaces by analyzing their approximation and estimation abilities. For that purpose, we first show that approximation and estimation errors depend only on the smoothness and decay rate with respect to the infinity norm of the output, and their estimation accuracy actually achieve the {\it minimax optimal} rate of convergence. Second, we demonstrate that the dilated CNNs outperform {\it any} linear estimators including kernel ridge regression and $k$-NN estimators in a minimax error sense, highlighting the usefulness of feature learning realized by deep neural networks. Our theoretical analysis particularly explains the success of deep learning in recent high-dimensional input-output tasks.
BibTeX
@inproceedings{nishimura2024minimax,
  author = {Yuto Nishimura and Taiji Suzuki},
  title = {{Minimax optimality of convolutional neural networks for infinite dimensional input-output problems and separation from kernel methods}},
  booktitle = {International Conference on Learning Representations},
  year = {2024},
  url = {https://openreview.net/forum?id=EW8ZExRZkJ},
}
Figure