A note on stochastic subgradient descent for persistence-based functionals: convergence and practical aspects

Mathieu Carrière, Frédéric Chazal, Marc Glisse, Yuichi Ike, Hariprasad Kannan

Abstract

Solving optimization tasks based on functions and losses with a topological flavor is a very active, growing field of research in data science and Topological Data Analysis, with applications in non-convex optimization, statistics and machine learning. However, the approaches proposed in the literature are usually anchored to a specific application and/or topological construction, and do not come with theoretical guarantees. To address this issue, we study the differentiability of a general map associated with the most common topological construction, that is, the persistence map. Building on real analytic geometry arguments, we propose a general framework that allows us to define and compute gradients for persistence-based functions in a very simple way. We also provide a simple, explicit and sufficient condition for convergence of stochastic subgradient methods for such functions. This result encompasses all the constructions and applications of topological optimization in the literature. Finally, we provide associated code, that is easy to handle and to mix with other non-topological methods and constraints, as well as some experiments showcasing the versatility of our approach.

Introduction

Persistent homology has emerged as a powerful tool for capturing the "shape" of data—identifying holes, loops, and voids across multiple scales. However, integrating these topological descriptors into standard machine learning pipelines as loss functions has historically lacked a rigorous theoretical foundation. Persistence diagrams, the primary output of Topological Data Analysis (TDA), are discrete descriptors generated through sorting and thresholding processes, making them generally non-convex and non-differentiable.

While empirical "hacks" for computing gradients have allowed for some progress, there was no formal proof that such optimizations would converge to stable points. This paper bridges the gap between abstract TDA and practical gradient-based optimization by providing the first formal convergence guarantees for optimizing functions that depend on persistence diagrams using stochastic subgradient descent (SGD).

Theoretical Framework

The authors' approach rests on two theoretical pillars that tame the inherent complexity of topological maps:

  1. O-minimal Geometry: To address non-differentiability, the authors employ the framework of "o-minimal structures." They demonstrate that the map from a filtration (input data) to a persistence diagram is semi-algebraic. This "tameness" ensures the function does not oscillate infinitely and can be partitioned into smooth, well-behaved components.
  2. Persistence as a Permutation: A crucial insight is that the persistence map essentially functions as a re-indexing or permutation of input coordinates. Computing a persistence diagram involves identifying specific "birth" and "death" values from the input. Consequently, the gradient is straightforward: it is either 1 for the coordinate responsible for a feature's creation/destruction or 0 otherwise.

Optimization and Convergence

By combining the "tameness" of these functions with established results in optimization theory, the paper proves that standard SGD converges almost surely to a critical point. This holds true even though the functions are not globally differentiable. The authors implemented this framework in a Python library compatible with Gudhi, TensorFlow, and PyTorch, enabling seamless integration of topological layers into deep learning architectures.

Experimental Validation

The framework was validated across several diverse tasks, demonstrating both the versatility and the effectiveness of topological optimization:

  • MNIST: Used for image classification and "filter selection," where the optimal direction to "scan" an image for topological features is learned.
  • Graph Benchmarks: Tested on 10 standard datasets (e.g., PROTEINS, MUTAG) for graph classification.
  • Synthetic Data: Dimension reduction and denoising tasks using nested circles and noisy point clouds.
  • 3D Shapes: Shape-matching and functional optimization using human pose datasets.
Evolution of point clouds from epoch 0 to 1000 alongside the corresponding loss convergence.

Key Results and Insights

The experiments yielded several significant findings:

  • Convergence: Mathematical proof and empirical evidence confirm that SGD on persistence-based functions reliably reaches critical points.
  • Accuracy Gains: In MNIST filter selection, optimizing scan directions led to dramatic improvements, such as increasing accuracy from 61.3% to 99.0% in specific sub-tasks.
  • Enhanced Embeddings: Topological Autoencoders using 1D homology (loops) successfully disentangled nested circles that standard methods failed to separate.
  • Denoising Robustness: The method effectively denoises images by penalizing short-lived topological features (noise) while preserving long-lived signals.
Convergence of the loss function over the optimization process.

Discussion and Limitations

While the paper provides a solid theoretical footing, some practical challenges remain. The functions are highly non-convex, meaning optimization can still settle in local minima. Additionally, computing persistent homology is computationally more intensive than standard layers, though techniques like "vineyards" for incremental updates offer potential speedups. Finally, the authors emphasize the necessity of regularization; topological losses often require pairing with spatial penalties to prevent "explosive" results, such as point clouds expanding infinitely to maximize a hole's size.

Summary updated

Abstract

Solving optimization tasks based on functions and losses with a topological flavor is a very active, growing field of research in data science and Topological Data Analysis, with applications in non-convex optimization, statistics and machine learning. However, the approaches proposed in the literature are usually anchored to a specific application and/or topological construction, and do not come with theoretical guarantees. To address this issue, we study the differentiability of a general map associated with the most common topological construction, that is, the persistence map. Building on real analytic geometry arguments, we propose a general framework that allows us to define and compute gradients for persistence-based functions in a very simple way. We also provide a simple, explicit and sufficient condition for convergence of stochastic subgradient methods for such functions. This result encompasses all the constructions and applications of topological optimization in the literature. Finally, we provide associated code, that is easy to handle and to mix with other non-topological methods and constraints, as well as some experiments showcasing the versatility of our approach.
BibTeX
@misc{carriere2020note,
  author = {Mathieu Carrière and Frédéric Chazal and Marc Glisse and Yuichi Ike and Hariprasad Kannan},
  title = {{A note on stochastic subgradient descent for persistence-based functionals: convergence and practical aspects}},
  year = {2020},
  eprint = {2010.08356},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2010.08356},
}
Figure