ReLU nets adapt to intrinsic dimensionality beyond the target domain

Alexander Cloninger, Timo KlockarXiv 2020 · arXiv · OpenReview

Abstract: We study the approximation of two-layer compositions $f(x) = g(\phi(x))$ via deep networks with ReLU activation, where $\phi$ is a geometrically intuitive, dimensionality reducing feature map. We focus on two intuitive and practically relevant choices for $\phi$: the projection onto a low-dimensional embedded submanifold and a distance to a collection of low-dimensional sets. We achieve near optimal approximation rates, which depend only on the complexity of the dimensionality reducing map $\phi$ rather than the ambient dimension. Since $\phi$ encapsulates all nonlinear features that are material to the function $f$, this suggests that deep nets are faithful to an intrinsic dimension governed by $f$ rather than the complexity of the domain of $f$. In particular, the prevalent assumption of approximating functions on low-dimensional manifolds can be significantly relaxed using functions of type $f(x) = g(\phi(x))$ with $\phi$ representing an orthogonal projection onto the same manifold.

Introduction

A fundamental challenge in high-dimensional machine learning is the curse of dimensionality, where the resources required to learn a function grow exponentially with the input dimension $D$. To explain why deep neural networks often bypass this issue, researchers frequently invoke the manifold hypothesis—the idea that high-dimensional data (such as natural images) actually resides on a much lower-dimensional ($d$) manifold.

However, real-world data is rarely perfectly constrained to a manifold; it is typically noisy and distributed throughout the ambient space. This paper provides a theoretical breakthrough by demonstrating that deep ReLU networks can achieve optimal approximation rates based on the intrinsic dimensionality of the function's structure, even when the input data is high-dimensional and noisy. The complexity of the task is driven by the function's local invariances rather than the complexity of its domain.

Theoretical Framework: ReLU Calculus and Function Classes

The authors utilize ReLU calculus—a framework for constructing complex functions by composing simple Rectified Linear Unit (ReLU) layers—to provide constructive proofs for two specific classes of functions where the target $f$ is a composition $g \circ \phi$:

Class 1: Projection-based Functions

These are functions of the form $f(x) = g(\pi_{\mathcal{M}}(x))$, where $\pi_{\mathcal{M}}$ is an orthogonal projection of a high-dimensional point $x$ onto a $d$-dimensional manifold $\mathcal{M}$. This model accounts for scenarios where the function is invariant to noise orthogonal to the manifold.

Illustration of an orthogonal projection $\pi_{\mathcal{M}}(x)$ of a point $x$ onto a manifold $\mathcal{M}$, representing the core mechanism of Class 1 functions.

Class 2: Distance-based Functions

These functions depend on the distance to a collection of low-dimensional sets (e.g., $f(x)$ is determined by the proximity of $x$ to certain "attractor" points or curves). This is particularly relevant for classification tasks where decision boundaries are defined by distances to specific clusters.

Distance-based structure where function values are determined by proximity to specific sets or clusters $C_1$ and $C_2$.

Key Results and Approximation Rates

The core of the methodology involves constructing a "partition of unity" using ReLU networks. By building small modules that identify local regions near the manifold and combining local Taylor approximations, the authors prove that for a function with intrinsic dimension $d$ and smoothness $\alpha$:

  • Near-Optimal Rates: A deep ReLU network can approximate the function to an accuracy of $\epsilon$ using approximately $O(\epsilon^{-d/\alpha})$ parameters. This rate matches the best possible rate for functions defined only on a $d$-dimensional space, despite the $D$-dimensional input.
  • Logarithmic Scaling: The number of parameters required scales only logarithmically with the ambient dimension $D$, but polynomially with the intrinsic dimension $d$.
  • Depth Advantage: The required network depth scales with $\log(1/\epsilon)$, confirming that deep architectures are uniquely suited to mimic the compositional structure ($f = g \circ \phi$) necessary to break the curse of dimensionality.

Discussion and Future Directions

This framework naturally handles the "noisy manifold hypothesis." Because the network is constructed to approximate a projection, it remains robust to data points pushed off the manifold by noise, provided they stay within a certain "tubular neighborhood" (the reach) of the manifold.

While this work proves the existence of efficient network representations, it does not address optimization—whether gradient descent can actually find these weights in practice. Future research will focus on the training dynamics and extending these guarantees to less regular, non-smooth geometric structures. This theoretical foundation suggests that deep networks are inherently faithful to the intrinsic dimension governed by the task, rather than the raw complexity of the input space.

Summary updated

Abstract

We study the approximation of two-layer compositions $f(x) = g(\phi(x))$ via deep networks with ReLU activation, where $\phi$ is a geometrically intuitive, dimensionality reducing feature map. We focus on two intuitive and practically relevant choices for $\phi$: the projection onto a low-dimensional embedded submanifold and a distance to a collection of low-dimensional sets. We achieve near optimal approximation rates, which depend only on the complexity of the dimensionality reducing map $\phi$ rather than the ambient dimension. Since $\phi$ encapsulates all nonlinear features that are material to the function $f$, this suggests that deep nets are faithful to an intrinsic dimension governed by $f$ rather than the complexity of the domain of $f$. In particular, the prevalent assumption of approximating functions on low-dimensional manifolds can be significantly relaxed using functions of type $f(x) = g(\phi(x))$ with $\phi$ representing an orthogonal projection onto the same manifold.
BibTeX
@misc{cloninger2020relu,
  author = {Alexander Cloninger and Timo Klock},
  title = {{ReLU nets adapt to intrinsic dimensionality beyond the target domain}},
  year = {2020},
  eprint = {2008.02545},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2008.02545},
}
Figure