When fractional quasi p-norms concentrate

Ivan Yu. Tyukin, Bogdan Grechuk, Evgeny M. Mirkes, Alexander N. GorbanarXiv 2025 · DOI · arXiv

Introduction: The Curse of Dimensionality

In high-dimensional spaces, distance-based algorithms like $k$-Nearest Neighbors ($k$-NN) and clustering often encounter the "concentration of measure" phenomenon. As the number of dimensions ($n$) increases, the distance between any two random points tends to converge to a single value. This makes every point appear "equally far" from every other point, rendering distance a poor metric for discrimination.

A seminal 2001 study suggested that using fractional quasi $p$-norms (where $p \in (0, 1)$) could mitigate this effect. However, subsequent research produced conflicting results. This paper resolves the controversy by identifying the exact mathematical conditions under which fractional norms succeed or fail to "de-concentrate" distances.

Theoretical Framework and the "Zero Factor"

The authors employ a rigorous framework using Chernoff’s inequality and Cramer’s theorem to derive exponential concentration bounds for $p$-norms. Their analysis reveals a critical distinction between "uniform concentration" and "anti-concentration."

Summary of theoretical concentration results for different $p$ ranges.

The most significant finding is the "Zero Factor": fractional norms only provide a benefit if the data distribution is sparse at the coordinate level—specifically, if there is a non-zero probability that an attribute is exactly zero ($P(x_i = 0) > 0$). For standard continuous distributions like Gaussians or Uniform distributions that do not touch zero, the concentration of distances is uniform in $p$. This means that reducing $p$ does not significantly slow the rate at which distances collapse as dimensions grow.

Empirical Evidence and Practical Implications

The paper validates these theoretical insights through extensive experiments on over 30 real-world datasets from the UCI repository and synthetic benchmarks.

Empirical probability of distance concentration across dimensions $n$ and distance parameters $p$.

As shown in the empirical analysis, the probability of distance concentration typically increases with both the dimension $n$ and the parameter $p$. However, in cases where the "Zero Factor" is present, the "anti-concentration" behavior allows $p$ to effectively control the distance spread, delaying the collapse of distances even as $n$ grows.

Interestingly, common data pre-processing steps like dummy encoding (converting categorical variables to 0/1) or zero-filling missing values inadvertently create the mathematical conditions necessary for fractional norms to work. This explains why $p < 1$ norms appeared effective in some previous studies but not others.

Key Results and Conclusion

The study concludes that fractional quasi $p$-norms are not a universal "silver bullet" for high-dimensional data.

  • Theoretical Proof: For broad classes of continuous distributions, concentration bounds are independent of $p$, ruling out optimal $p$ tuning.
  • Anti-Concentration Theorem: Mitigation of concentration is possible only for distributions with an atom at zero.
  • Empirical Confirmation: In $k$-NN tests, fractional norms only outperformed standard Euclidean ($p=2$) or Manhattan ($p=1$) distances on specific sparse datasets like Madelon.

For practitioners, these results suggest that the choice of distance metric should be informed by the sparsity of the data. Future work may focus on developing automated checks to determine the optimal norm based on data distribution characteristics.

Summary updated

Abstract

Concentration of distances in high dimension is an important factor for the development and design of stable and reliable data analysis algorithms. In this paper, we address the fundamental long-standing question about the concentration of distances in high dimension for fractional quasi $p$-norms, $p\in(0,1)$. The topic has been at the centre of various theoretical and empirical controversies. Here we, for the first time, identify conditions when fractional quasi $p$-norms concentrate and when they don't. We show that contrary to some earlier suggestions, for broad classes of distributions, fractional quasi $p$-norms admit exponential and uniform in $p$ concentration bounds. For these distributions, the results effectively rule out previously proposed approaches to alleviate concentration by "optimal" setting the values of $p$ in $(0,1)$. At the same time, we specify conditions and the corresponding families of distributions for which one can still control concentration rates by appropriate choices of $p$. We also show that in an arbitrarily small vicinity of a distribution from a large class of distributions for which uniform concentration occurs, there are uncountably many other distributions featuring anti-concentration properties. Importantly, this behavior enables devising relevant data encoding or representation schemes favouring or discouraging distance concentration. The results shed new light on this long-standing problem and resolve the tension around the topic in both theory and empirical evidence reported in the literature.
BibTeX
@misc{tyukin2025when,
  author = {Ivan Yu. Tyukin and Bogdan Grechuk and Evgeny M. Mirkes and Alexander N. Gorban},
  title = {{When fractional quasi p-norms concentrate}},
  year = {2025},
  eprint = {2505.19635},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.19635},
}
Figure