Outwitting Outliers

A framework for computing persistence diagrams under adversarial contamination

Joint Mathematics Meetings 2025



Siddharth Vishwanath*
Kenji Fukumizu • Bharath Sriperumbudur • Satoshi Kuriki

$$ %%%%%%%%%%%%%%%%%%%%%%%%%%% % %%%%%%%%%%%%%%%%%%%%%%%%%%

% %

$$

Understanding Nanoscopic Structures

Electron clouds for the \(2p_z\) and \(3d_{z^2}\) orbitals

Understanding Nanoscopic Structures

\[ \begin{aligned} {\mathbb P}\Big( 2p_{z} \simeq \mathbb S^2 \vee \mathbb S^2 \Big) = ? && {\mathbb P}\Big( 3d_{z^2} \simeq \mathbb{T}^2 \vee \mathbb S^2 \vee \mathbb S^2 \Big) = ? \end{aligned} \]

Sufficient statistics may not suffice

Given a collection of points \({\mathbb{X}_n}= \left\{{\boldsymbol{x}}_1, {\boldsymbol{x}}_2, \dots, {\boldsymbol{x}}_n\right\} \subseteq {\mathbb R}^d\)
The shape of \({\mathbb{X}_n}\) is summarized in a persistence diagram \(\color{red}{\mathbf{D}[{{\mathbb{X}_n}}]}\)

Random Persistence Diagrams

When \({\mathbb{X}_n}= \left\{{\mathbf{X}}_1, \dots, {\mathbf{X}}_n\right\} \sim \text{Unif}({\mathbb{X}})\) the resulting persistence diagram \(\mathbf{D}_n = \mathbf{D}[{\mathbb{X}_n}]\) is also random

The population quantity of interest is \(\mathbf{D}[{\mathbb{X}}]\). How “close” is \(\mathbf{D}_n\) to \(\mathbf{D}[{\mathbb{X}}]\)?

Bottleneck Distance Given two persistence diagrams \(\mathbf{D}_1\) and \(\mathbf{D}_2\), \[ {W_{\infty}}(\mathbf{D}_1, \mathbf{D}_2) := \inf\limits_{\gamma: \mathbf{D}_1 \rightarrow \mathbf{D}_2} \ \ \sup_{v \in \mathbf{D}_1} \left\|\gamma(p) - p\right\|_\infty \]

\(\hspace{0.5em}\)

Random Persistence Diagrams

When \({\mathbb{X}_n}= \left\{{\mathbf{X}}_1, \dots, {\mathbf{X}}_n\right\} \sim \text{Unif}({\mathbb{X}})\) the resulting persistence diagram \(\mathbf{D}_n = \mathbf{D}[{\mathbb{X}_n}]\) is also random

The population quantity of interest is \(\mathbf{D}[{\mathbb{X}}]\). How “close” is \(\mathbf{D}_n\) to \(\mathbf{D}[{\mathbb{X}}]\)?



Concentration: \[ {\mathbb P}\Big\{ {W_{\infty}}\big(\mathbf{D}_n, \mathbf{D}[{\mathbb{X}}]\big) > \varepsilon\Big\} \le \frac{2}{\varepsilon^d} \exp( -n\varepsilon^d ) \]

Estimation: \[ {\mathbb E}\Big[ {W_{\infty}}\big(\mathbf{D}_n, \mathbf{D}[{\mathbb{X}}]\big) \Big] \lesssim {n^{-1/d}} \]

Adversarial Contamination

Stability \(\neq\) Robustness

Robust topological inference in the presence of outliers

Adversarial Contamination

Sampling Setting \((\mathcal{S})\) The data comprises of \(n\) samples \({\mathbb{X}_n}= \left\{X_1, X_2, \dots , X_n\right\}\) where:

\[ {\mathbb{X}_n}= {\mathbb{X}^*_{n-m}}\cup {\mathbb{Y}_m} \]

  1. \(m < n/2\) samples, \({\mathbb{Y}_m}\subset {\mathbb{X}_n}\), are contaminated with unknown outliers
    • No distributional assumption is made on these outliers

  2. The remaining \(n\text{-}m\) samples \({\mathbb{X}^*_{n-m}}\) are observed* \(iid\) from a “nice” distribution \({\mathbb P}\in \mathscr{P}\)

Minimax Lower Bound

For \({\mathbb{X}_n}= {\mathbb{X}^*_{n-m}}\cup {\mathbb{Y}_m}\) where \(\; {\mathbb{X}^*_{n-m}}\sim {\mathbb P}\; \text{and} \; {\mathbb{Y}_m}\sim \mathbb{Q}\) \[ {\mathbb E}\Big[ {W_{\infty}}\big(\widehat{\boldsymbol{\theta}}[{\mathbb{X}_n}], \mathbf{D}[{\mathbb{X}}]\big) \Big] \]

The risk for:

Minimax Lower Bound

For \({\mathbb{X}_n}= {\mathbb{X}^*_{n-m}}\cup {\mathbb{Y}_m}\) where \(\; {\mathbb{X}^*_{n-m}}\sim {\mathbb P}\; \text{and} \; {\mathbb{Y}_m}\sim \mathbb{Q}\) \[ \sup_{\mathbb{Q}}{\mathbb E}\Big[ {W_{\infty}}\big(\widehat{\boldsymbol{\theta}}[{\mathbb{X}_n}], \mathbf{D}[{\mathbb{X}}]\big) \Big] \]

The risk for:

  • For the most malicious adversary (\(\sup_{\mathbb{Q}}\))

Minimax Lower Bound

For \({\mathbb{X}_n}= {\mathbb{X}^*_{n-m}}\cup {\mathbb{Y}_m}\) where \(\; {\mathbb{X}^*_{n-m}}\sim {\mathbb P}\; \text{and} \; {\mathbb{Y}_m}\sim \mathbb{Q}\) \[ \sup_{{\mathbb P}\in \mathfrak{P}}\sup_{\mathbb{Q}}{\mathbb E}\Big[ {W_{\infty}}\big(\widehat{\boldsymbol{\theta}}[{\mathbb{X}_n}], \mathbf{D}[{\mathbb{X}}]\big) \Big] \]

The risk for:

  • For the most malicious adversary (\(\sup_{\mathbb{Q}}\))
  • For the worst case sampling scenario (\(\sup_{{\mathbb P}\in \mathfrak{P} }\))

Minimax Lower Bound

For \({\mathbb{X}_n}= {\mathbb{X}^*_{n-m}}\cup {\mathbb{Y}_m}\) where \(\; {\mathbb{X}^*_{n-m}}\sim {\mathbb P}\; \text{and} \; {\mathbb{Y}_m}\sim \mathbb{Q}\) \[ \inf_{\widehat{\boldsymbol{\theta}}}\sup_{{\mathbb P}\in \mathfrak{P}}\sup_{\mathbb{Q}}{\mathbb E}\Big[ {W_{\infty}}\big(\widehat{\boldsymbol{\theta}}[{\mathbb{X}_n}], \mathbf{D}[{\mathbb{X}}]\big) \Big] \]

The risk for:

  • For the most malicious adversary (\(\sup_{\mathbb{Q}}\))
  • For the worst case sampling scenario (\(\sup_{{\mathbb P}\in \mathfrak{P} }\))
  • And, for the best possible estimator (\(\inf_{\widehat{\boldsymbol{\theta}}}\))

Minimax Lower Bound

Theorem. For \({\mathbb{X}_n}= {\mathbb{X}^*_{n-m}}\cup {\mathbb{Y}_m}\) where \(\; {\mathbb{X}^*_{n-m}}\sim {\mathbb P}\; \text{and} \; {\mathbb{Y}_m}\sim \mathbb{Q}\)

\[ \inf_{\widehat{\boldsymbol{\theta}}}\sup_{{\mathbb P}\in \mathfrak{P}}\sup_{\mathbb{Q}}{\mathbb E}\Big[ {W_{\infty}}\big(\widehat{\boldsymbol{\theta}}[{\mathbb{X}_n}], \mathbf{D}[{\mathbb{X}}]\big) \Big] \gtrsim \Big(\frac{n/2-m}{m}\Big)^{-1/d} \]

The risk for:

  • For the most malicious adversary (\(\sup_{\mathbb{Q}}\))
  • For the worst case sampling scenario (\(\sup_{{\mathbb P}\in \mathfrak{P} }\))
  • And, for the best possible estimator (\(\inf_{\widehat{\boldsymbol{\theta}}}\))

Robustness via the Median-of-Means Principle

MoM Dist

Given \({\mathbb{X}_n}\) and \(\color{violet}{ Q \in [1, n]}\), let \(\left\{S_1, S_2, \dots, S_{\color{violet}Q}\right\}\) a partition of \({\mathbb{X}_n}\) into \(\color{violet}Q\) disjoint blocks.

(MoMDist) The \(\textsf{MoMDist}\) function \({\mathsf{d}_{n, Q}}: {\mathbb R}^d \rightarrow {\mathbb R}_{\ge 0}\) is defined as

\[ {\mathsf{d}_{n, Q}}({\boldsymbol{x}}) := \text{median}\left\{ d_{n, S_q}({\boldsymbol{x}}) : q \in [\color{violet}Q] \right\} = \text{median}\Big\{ \inf_{{\boldsymbol{y}}\in S_q} \|{\boldsymbol{x}}- {\boldsymbol{y}}\| : q \in \left\{1, 2, \dots, \color{violet}Q\right\} \Big\} \]

MoM Dist is Minimax-Optimal*

Minimax Lower Bound. For \({\mathbb{X}_n}= {\mathbb{X}^*_{n-m}}\cup {\mathbb{Y}_m}\) where \(\; {\mathbb{X}^*_{n-m}}\sim {\mathbb P}\; \text{and} \; {\mathbb{Y}_m}\sim \mathbb{Q}\)

\[ \inf_{\hat{\boldsymbol{\theta}}}\sup_{{\mathbb P}\in \mathfrak{P}}\sup_{\mathbb{Q}}{\mathbb E}\Big[ {W_{\infty}}\big(\widehat{\boldsymbol{\theta}}[{\mathbb{X}_n}], \mathbf{D}[{\mathbb{X}}]\big) \Big] \gtrsim \Big(\frac{n/2-m}{m}\Big)^{-1/d} \]

Theorem. For the MoM Dist persistence diagram \(\widehat{\mathbf{D}} = \mathbf{D}[d_{n, Q}, {\mathbb{X}_n}]\)

\[ \sup_{{\mathbb P}\in \mathfrak{P}}\sup_{\mathbb{Q}}{\mathbb E}\Big[ {W_{\infty}}\big(\widehat{\mathbf{D}}[{\mathbb{X}_n}], \mathbf{D}[{\mathbb{X}}]\big) \Big] \lesssim \Big(\frac{n/2-m}{m\log{n}}\Big)^{-1/d} \]

Signal Recovery

Signal Recovery

Signal Recovery

Code

github.com/sidv23/RobustTDA.jl

♫ With Autotuning hyperparameters 𝅘𝅥𝅮

Summary

We can perform topological inference with:

  • Robustness to outliers & adversarial contamination

  • Computational efficiency

  • Statistical consistency

  • And, free of tuning parameters

Thank you!
Questions?