The Effect of Manifold Entanglement and Intrinsic Dimensionality on Learning

Daniel Kienitz, Ekaterina Komendantskaya, Michael A. LonesAAAI 2022 · DOI

Introduction

In the field of deep learning, "sample complexity"—the amount of data required for a model to achieve a specific performance level—is a critical metric. A long-standing assumption, known as the manifold hypothesis, suggests that natural data (such as images) resides on low-dimensional manifolds embedded within high-dimensional spaces. Consequently, researchers often attribute the difficulty of learning a task to its intrinsic dimensionality (ID): the minimum number of variables needed to describe the data.

However, this paper argues that ID is only part of the equation. The authors introduce and investigate manifold entanglement—the geometric complexity or "twistedness" of the boundary between classes—as a primary driver of sample complexity. Their findings suggest that while ID matters, its impact is conditional on the level of entanglement present in the data.

Defining and Measuring Entanglement

To study this phenomenon, the authors propose two distinct proxies for measuring entanglement:

  1. Global Measure (LSVC Accuracy): They use the accuracy of a Linear Support Vector Classifier (LSVC). If a simple linear boundary cannot separate two classes, the manifolds are considered globally entangled.
  2. Local Measure (Hessian Curvature): They analyze the Hessian of the network's decision function. High singular values in the Hessian matrix indicate high curvature at the decision boundary, signifying local entanglement.

Controlled Experiments on Synthetic Data

The researchers first utilized synthetic datasets to independently manipulate ID, extrinsic dimensionality (ED), and entanglement. They used two primary structures: Archimedean spirals (1D manifolds) and step-functions (2D manifolds).

Synthetic datasets (Archimedean spirals and Step-functions) with varying degrees of entanglement (Σ).

As shown in the figure above, increasing the parameter $\Sigma$ directly increases the "twistedness" or frequency of the patterns, providing a clear visual representation of increasing entanglement. Through regression analysis, the authors found that for Archimedean spirals, the entanglement coefficient was significantly higher ($≈ 167$) than the ID coefficient ($≈ 10$), demonstrating that entanglement is the dominant factor in determining how much data a ReLU network needs to learn.

Real-World Benchmarks and the Interdependence Effect

When applying these measures to standard image benchmarks, a clear hierarchy emerged. Based on LSVC accuracy, the datasets rank in increasing order of entanglement: MNIST < Fashion-MNIST < SVHN < CIFAR-10. This ranking perfectly aligns with the perceived difficulty of these tasks.

LSVC accuracy across different datasets as a proxy for global manifold entanglement.

Crucially, the study revealed an interdependence effect. The impact of intrinsic dimensionality is not constant; it is magnified by entanglement. If entanglement is low (as in MNIST), increasing the ID has a negligible effect on sample complexity. However, if entanglement is high (as in CIFAR-10), increasing the ID causes the required sample size to skyrocket. Conversely, extrinsic dimensionality (the total number of pixels) was found to have almost no effect on sample complexity, provided the network is sufficiently deep.

Conclusion and Implications

This research shifts the focus from purely dimensional explanations of model performance to geometric ones. By using a gradient-based heuristic to remove samples near the decision boundary (effectively "un-tangling" the manifolds), the authors demonstrated that the impact of intrinsic noise became statistically insignificant.

While the study focuses on binary classification with ReLU networks, it provides a robust framework for understanding why certain datasets are inherently "harder" than others. Future work may explore how these geometric properties apply to multi-class problems or different network architectures, potentially leading to more data-efficient training strategies.

Summary updated

BibTeX
@inproceedings{kienitz2022effect,
  author = {Daniel Kienitz and Ekaterina Komendantskaya and Michael A. Lones},
  title = {{The Effect of Manifold Entanglement and Intrinsic Dimensionality on Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i7.20676},
}
Figure