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:
- 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.
- 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