Optimizing persistent homology based functions

Mathieu Carrière, Frédéric Chazal, Marc Glisse, Yuichi Ike, Hariprasad Kannan, Yuhei UmedaICML 2021 · OpenReview

Topological Data Analysis (TDA) allows researchers to quantify the "shape" of data—such as holes, loops, and connected components—through a process called persistent homology. Recently, there has been a surge of interest in using these topological features not just as descriptors, but as loss functions. For example, one might want to optimize a neural network so that its latent space preserves the circularity of the input data.

However, persistent homology is fundamentally combinatorial. The map from data to a "persistence diagram" is often non-convex and non-differentiable. Until now, researchers have used ad-hoc gradient descent methods without knowing if they would actually converge or if the gradients were even well-defined. This paper fills that gap by providing the first rigorous theoretical framework for optimizing functions that depend on persistent homology, acting as a mathematical "safety manual" for topological optimization.

The "Taming" of Topological Data Analysis

The authors' core contribution is proving that the persistence map is "tame" in the language of o-minimal geometry. The "nasty" non-differentiable nature of persistence diagrams isn't a dealbreaker. As long as the function is "definable" (which almost all practical TDA functions are), it is well-behaved enough for gradient-based optimization.

  1. Persistence as a Permutation: The authors show that computing a persistence diagram is essentially just a re-indexing (permutation) of the input filtration values. If you change the input slightly, the pairing of features might stay the same, making the map locally linear.
  2. O-minimal Geometry: They prove the persistence map is semi-algebraic (or more generally, "definable"). This is a significant breakthrough because definable functions, while potentially non-smooth, are differentiable almost everywhere and have a finite number of "kinks."
  3. Convergence Guarantees: By establishing this tameness, they apply recent results in optimization theory to show that Stochastic Subgradient Descent (SGD)—the workhorse of modern machine learning—will converge almost surely to a critical point of the topological loss function.
  4. Automatic Differentiation Compatibility: Because the persistence map is a coordinate permutation, complex gradient derivations are unnecessary. Standard automatic differentiation frameworks can handle it by tracking which input simplex "caused" which point in the persistence diagram.

Key Results and Applications

The authors demonstrate their framework on several tasks, proving the stability and utility of topological optimization.

Dimensionality Reduction

Using "Topological Autoencoders," the authors applied a 1D-homology loss to embed nested circles from $\mathbb{R}^3$ into a lower-dimensional latent space. The topological loss perfectly separated the nested circles, whereas standard methods or 0D-homology methods failed to capture the intrinsic structure.

Example of dimension reduction with autoencoders. The 1-dimensional topology clearly separates the nested circles better than standard methods.

Point Cloud Optimization

To demonstrate the stability of the optimization, the authors successfully "grew" holes in random point clouds. By minimizing a topological penalty, the algorithm rearranged points from random noise into a structured grid of holes.

Illustration of point cloud optimization. Starting from random noise, the algorithm creates a structured grid of holes to minimize the topological loss.

MNIST Classification

Using the classic handwritten digit dataset, the authors showed how "filter selection" (choosing the best direction to look at an image) can improve classification accuracy. By optimizing the direction of the height function used to generate topological features, they improved classification accuracy significantly. For instance, on the "digit 0 vs digit 1" task, optimization moved accuracy from 61.3% to 99.0%.

Limitations and Future Directions

While this framework provides robust guarantees, there are practical limitations to consider:

  • Local Minima: The paper guarantees convergence to a critical point, but not necessarily the global minimum. Because these losses are highly non-convex, the quality of the result still heavily depends on initialization.
  • Computational Complexity: Calculating persistent homology and Wasserstein distances in every iteration of a training loop remains computationally expensive.
  • Regularization: Topological losses often require standard geometric penalties to prevent "runaway" behavior, such as points flying off to infinity to artificially make a hole "larger."

Future work will likely explore "vineyards"—a technique to update persistence diagrams more efficiently as data changes—to speed up the optimization process. The authors also aim to apply this framework to regularizing deep classifiers, opening new doors for topology-aware machine learning.

Summary updated

Abstract

Solving optimization tasks based on functions and losses with a topological flavor is a very active and growing field of research in data science and Topological Data Analysis, with applications in...
BibTeX
@inproceedings{carriere2021optimizing,
  author = {Mathieu Carrière and Frédéric Chazal and Marc Glisse and Yuichi Ike and Hariprasad Kannan and Yuhei Umeda},
  title = {{Optimizing persistent homology based functions}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=4LchLwjShW7},
}
Figure