TL;DR
This paper introduces the Pairwise Distortion Distribution (PDD), a novel tool for analyzing data geometry and predicting compression performance. By generalizing the classical correlation integral to arbitrary distortion measures, the authors provide a computationally efficient way to lower-bound quantization error and estimate the "true" intrinsic dimension of a dataset without the need for expensive model training.
What Problem Does This Paper Address?
In data compression and representation learning, a recurring headache is choosing the right latent dimension. If the dimension is too high, you waste bits; if it's too low, you lose critical information. Traditionally, engineers find this "sweet spot" through exhaustive hyperparameter optimization—essentially training multiple models and seeing which one works best—which is both computationally expensive and provides little geometric insight.
Information theory offers a concept called Intrinsic Dimension (ID), which represents the minimum number of variables needed to describe the data. However, existing definitions like the Renyi Information Dimension (RID) are often difficult to estimate from finite data or are tied strictly to Euclidean distances. The authors set out to create a more flexible, practical metric that works with general distortion measures (like $p$-norms) and directly informs quantization performance.
Methods
The authors introduce two key concepts:
- Pairwise Distortion Distribution (PDD): This is the cumulative distribution function of the distortion between two independent samples drawn from the same data distribution. Essentially, it asks: "If I pick two random points, what is the probability that the 'distance' (distortion) between them is less than $r$?"
- Pairwise Dimension (PD): This is the asymptotic limit of the PDD as the distortion $r$ approaches zero. It captures how the "volume" of the data scales at very small scales.
The mathematical heavy lifting in the paper proves that:
- PD bounds RID: For power-of-norm distortions, the Pairwise Dimension provides a lower bound for the Renyi Information Dimension.
- Performance Lower Bound: The PDD can be used to calculate a theoretical lower bound on the expected distortion of a Random Codebook Quantization (RCQ) scheme. This is significant because RCQ serves as a baseline for how well any quantization system can perform.
Crucially, PDD is easy to estimate empirically. Instead of training a neural network, you can simply take pairs of samples from your dataset and calculate their mutual distortion to build an estimate of the PDD.
Datasets
The researchers evaluated their framework using two types of data:
- Synthetic Gaussian Vectors: Independent vectors drawn from $\mathcal{N}(0, 1)$ with ambient dimensions $N=2$ and $N=10$. This allowed them to compare PDD against analytically known optimal rate-distortion curves.
- MNIST: The classic database of 70,000 handwritten digits. Each image is $28 \times 28$ pixels (ambient dimension $N=784$), but the data is known to lie on a much lower-dimensional manifold.
Key Insights and Ideas
- Geometry Predicts Performance: The "aha moment" is that the distribution of distances between random pairs of points contains enough geometric information to predict the limits of compression. You don't need to see the whole "shape" of the data at once; the statistics of pairs are sufficient.
- Generalization Beyond Euclidean: Unlike the traditional correlation integral, PDD works with any distortion measure $\rho(x, y)$. This makes it applicable to a wider variety of real-world engineering problems where "distance" isn't just a straight line.
- Asymptotic Alignment: The PDD-derived curves are almost parallel to optimal rate-distortion curves. This means that even if the PDD doesn't give you the exact error, it correctly captures the scaling behavior (how much error drops per additional bit).
Key Results
The empirical results demonstrate that PDD is a powerful predictor:
- Gaussian Scaling: For synthetic data, the PDD curves correctly captured the intrinsic dimension $N$. As shown in the left panel of Figure 1, the PDD lower bound tracks the slope of the optimal rate-distortion curve perfectly.
- MNIST Prediction: For the MNIST dataset, the authors compared the PDD lower bound against a high-performance Vision Transformer-based Autoencoder (ViT-AE). They found that the PDD upper bound provided a remarkably accurate approximation of the actual Mean Squared Error (MSE) observed across different latent dimensions ($d \in \{8, 16, 32\}$).

As seen in the right panel of Figure 1, the PDD estimates (red and blue lines) effectively "sandwich" the performance of the actual autoencoder (black triangles), especially at lower bit rates. This suggests that engineers can use PDD to anticipate the necessary latent dimension and expected MSE before starting a single training run.
Limitations and Future Work
The primary limitation noted is sample efficiency. To estimate the PDD accurately for very small values of distortion ($r \to 0$), you need a very large number of sample pairs ($K \geq 1/F_{\rho}(r)$). If the probability of two points being very close is tiny, you might need millions of samples to see it happen even once.
The authors suggest that future work could employ importance sampling techniques to increase the efficiency of estimating the PDD at these small scales. Additionally, while the current work focuses on random codebooks, extending these bounds to more structured or learned codebooks remains an open area for exploration.
Summary updated