Rates of convergence for robust geometric inference

Frédéric Chazal, Pascal Massart, Bertrand MichelarXiv 2015 · arXiv

Topological Data Analysis (TDA) has emerged as a powerful framework for extracting the underlying shape of complex datasets. However, real-world data is frequently contaminated with outliers that can catastrophically disrupt traditional geometric methods. This paper by Chazal, Massart, and Michel provides a rigorous statistical foundation for the Distance to Measure (DTM), a robust alternative to standard distance functions. By deriving tight convergence rates, the authors link statistical performance directly to the local geometry of the data distribution.

The Challenge of Robustness in TDA

In TDA, researchers typically study the "sublevel sets" of a distance function—essentially examining the union of balls around data points to infer the underlying manifold. A significant limitation of the standard distance-to-set function is its extreme sensitivity to outliers; even a single point far from the main cluster can drastically alter the inferred topology, a phenomenon known as the Hausdorff distance problem.

To mitigate this, the Distance to Measure (DTM) was introduced. Rather than calculating the distance to the single nearest point, DTM averages the distances to a fraction $m$ of the total probability mass. While DTM is known to be stable in a global sense (using Wasserstein metrics), a precise understanding of its statistical convergence rates was previously missing. Earlier bounds were often too loose to explain how the mass parameter $m$ affects error in practical applications.

Methodology: A Local Perspective

The authors move beyond global stability arguments, adopting a local analysis of empirical processes. Their technical innovation centers on three key components:

  1. Quantile Reformulation: They demonstrate that the DTM can be expressed as an integral of the quantile function of the distance distribution from a point $x$ to the data. This allows the use of univariate statistical tools to solve a multivariate geometric problem.
  2. Local Empirical Process Theory: Instead of analyzing how the entire distribution shifts, the authors focus on the "tails" near zero—the points closest to $x$. They utilize sharp concentration inequalities, including the Dvoretzky-Kiefer-Wolfowitz (DKW) inequality and specialized bounds for uniform empirical processes, to bound the deviation between the empirical DTM and the true DTM.
  3. Geometric Linking: The authors connect the "regularity" (smoothness) of the quantile function to classical geometric concepts such as $(a,b)$-standard measures, which describe the distribution of mass on a manifold.

Experimental Validation

The paper validates its theoretical findings using several synthetic geometric experiments designed to represent common challenges in TDA:

  • Segment Experiment: A 1D line segment in $\mathbb{R}$.
  • 2D Shape Experiment: A complex, hand-drawn closed curve in $\mathbb{R}^2$.
  • Fish Experiment: A 2D surface point cloud of approximately 217,000 points in $\mathbb{R}^3$.
  • Tangle Cube Experiment: A complex 3D manifold defined by an algebraic equation.

For each shape, three generative models were tested: Noiseless (uniform sampling), Clutter Noise (adding uniform background outliers), and Gaussian Convolution (adding "blur" to the points).

Key Insights and Results

Local Regularity and Convergence Rates

The speed at which an estimate improves as more data is added depends almost entirely on the "modulus of continuity" of the quantile function at zero. If the data is dense near the support, the DTM converges rapidly. While Wasserstein-based bounds often predict a slow rate of $n^{-1/d}$ (where $d$ is the dimension), this paper proves that a faster parametric rate of $1/\sqrt{n}$ is achievable under reasonable local assumptions.

The Role of the Mass Parameter $m$

The parameter $m$ acts as a smoothing factor. When $m$ is very small (often used to "clean" outliers), the error is dominated by local geometry. As $m$ increases, the estimate becomes more stable but potentially introduces more bias. The authors provide explicit upper bounds for the expected error of the empirical DTM, showing it is roughly proportional to $\frac{\omega_x(k/n)}{\sqrt{k}}$, where $n$ is the number of points, $k$ is the number of neighbors considered ($k \approx nm$), and $\omega_x$ is the local regularity.

Optimality

Using Le Cam’s lemma, the authors prove that their obtained rates are essentially optimal for small values of $k$. Numerical simulations across different noise models and dimensions confirm that their theoretical complexity function perfectly matches the observed error monotonicity.

Limitations and Future Work

While the paper provides a sup-norm bound, much of the analysis remains pointwise. Extending these results to more complex topological descriptors, such as persistence diagrams, is a natural next step. Additionally, choosing the "optimal" $m$ remains a challenge; because the error does not follow a simple monotonic path (often appearing U-shaped depending on noise), standard model selection tools are difficult to apply. Finally, while the current work assumes Euclidean space, the authors suggest the results can be adapted to general metric spaces, though explicit geometric constants would require re-derivation.

Summary updated

Abstract

Distances to compact sets are widely used in the field of Topological Data Analysis for inferring geometric and topological features from point clouds. In this context, the distance to a probability measure (DTM) has been introduced by Chazal et al. (2011) as a robust alternative to the distance a compact set. In practice, the DTM can be estimated by its empirical counterpart, that is the distance to the empirical measure (DTEM). In this paper we give a tight control of the deviation of the DTEM. Our analysis relies on a local analysis of empirical processes. In particular, we show that the rates of convergence of the DTEM directly depends on the regularity at zero of a particular quantile fonction which contains some local information about the geometry of the support. This quantile function is the relevant quantity to describe precisely how difficult is a geometric inference problem. Several numerical experiments illustrate the convergence of the DTEM and also confirm that our bounds are tight.
BibTeX
@misc{chazal2015rates,
  author = {Frédéric Chazal and Pascal Massart and Bertrand Michel},
  title = {{Rates of convergence for robust geometric inference}},
  year = {2015},
  eprint = {1505.07602},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1505.07602},
}
Figure