The sampling complexity of learning invertible residual neural networks

Yuanyuan Li, Philipp Grohs, Philipp PetersenarXiv 2024 · DOI · arXiv

Abstract

This paper investigates the fundamental limits of learning modern neural network architectures, specifically Invertible Residual Networks (i-ResNets) and Invertible Convolutional ResNets. Despite their specialized structures designed for stability and reversibility, the authors prove that these architectures do not bypass the "curse of dimensionality." Using approximation theory and complexity analysis, the study establishes that the number of samples required to achieve high uniform accuracy grows exponentially with the input dimension. These results provide rigorous lower bounds for both deterministic and stochastic learning algorithms, demonstrating that structural constraints like invertibility and translation invariance are insufficient to overcome the inherent sampling complexity of high-dimensional function approximation.

Introduction

In the field of supervised learning, the primary objective is to approximate an unknown function based on a finite set of point samples. As the dimensionality ($d$) of input data increases—common in tasks involving high-resolution imagery or complex physical simulations—the number of samples ($m$) required to maintain a specific level of accuracy typically grows exponentially. This phenomenon, known as the "curse of dimensionality," represents a significant barrier to the scalability of machine learning models.

While previous research has demonstrated that standard feedforward ReLU networks are subject to this curse when seeking high uniform accuracy ($L^\infty$ norm), there remained a hope that more specialized, modern architectures might offer a solution. This paper specifically examines Invertible Residual Networks (i-ResNets), which are foundational to generative modeling and inverse problem-solving due to their mathematical guarantees of reversibility and stability. The authors investigate whether these rigid structural constraints simplify the learning problem enough to bypass the curse of dimensionality.

Methodology

The authors employ a theoretical framework rooted in approximation theory and complexity analysis to derive lower bounds for learning errors. The core of their proof relies on the construction of specialized "hat functions."

1. Architecture-Specific Construction

The researchers mathematically designed localized "bump" functions (hat functions) that can be perfectly represented by a single i-ResNet or i-Conv-ResNet block. A critical aspect of this construction is ensuring that these functions respect the strict Lipschitz constraints—limits on the function's maximum slope—required to maintain invertibility within the residual framework.

2. Adversarial Function Sets

By strategically placing these hat functions in regions of the input space that remain unsampled by a learning algorithm, the authors create a set of functions that appear identical to a learner based on its training data but differ significantly in reality. This approach allows for the identification of the "optimal error" achievable by any possible learning algorithm.

3. Lower Bound Derivation

The study establishes mathematical lower bounds that apply to both deterministic and stochastic (randomized) learning methods, such as Stochastic Gradient Descent (SGD). This ensures that the findings are applicable to the average-case performance of practical training methods used in contemporary AI development.

Key Insights

The Persistence of the Curse

The study concludes that structural constraints are not a "silver bullet" for high-dimensional learning. While forcing a network to be invertible or residual limits the space of possible functions, it still allows for enough local variation (via the constructed hat functions) to make learning intractable without massive datasets.

The Uniform Norm Bottleneck

The curse of dimensionality is most severe when demanding uniform accuracy across the entire input domain. If an application requires a guarantee that the model is accurate everywhere, rather than just on average, i-ResNets do not provide a shortcut. This has significant implications for safety-critical applications where edge-case performance is vital.

Convolutional Layers and Translation Invariance

Notably, the paper finds that even the translation-invariant structure of convolutional layers (i-Conv-ResNets) suffers from the same fundamental complexity bottleneck as fully connected layers. Despite their efficiency in feature extraction, they do not inherently reduce the sampling requirements for high-dimensional function approximation.

Results

The paper provides rigorous lower bounds for the error of learning i-ResNets from $m$ samples in a $d$-dimensional space. The primary findings are:

  • The Error Bound: For both general i-ResNets and convolutional i-ResNets, the optimal error is lower bounded by a factor proportional to $m^{-1/d}$.
  • Exponential Scaling: This result implies that to maintain a constant error as the dimension $d$ increases, the number of samples $m$ must grow at a rate of $O(e^d)$.
  • Universal Applicability: These limits apply to any learning algorithm, confirming that the bottleneck is a property of the architecture and the dimensionality itself, not the specific optimization technique.

Conclusion and Future Work

This research establishes that i-ResNets and their convolutional counterparts are subject to the same fundamental sampling limitations as simpler models in high-dimensional spaces. While invertibility is a powerful tool for density estimation and generative tasks, it does not simplify the underlying learning problem under the $L^\infty$ norm.

Future research may explore whether these architectures can avoid the curse of dimensionality under different error metrics or by adopting the "manifold hypothesis," which assumes that high-dimensional data actually lies on a lower-dimensional surface. Additionally, the search continues for novel architectures that might possess the necessary properties to finally bypass the $L^\infty$ curse of dimensionality in practical applications.

Summary updated

BibTeX
@misc{li2024sampling,
  author = {Yuanyuan Li and Philipp Grohs and Philipp Petersen},
  title = {{The sampling complexity of learning invertible residual neural networks}},
  year = {2024},
  eprint = {2411.05453},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2411.05453},
}
Figure