Diffeomorphic interpolation for efficient persistence-based topological optimization

• URL: http://arxiv.org/abs/2405.18820v1
• Date: Wed, 29 May 2024 07:00:28 GMT
• Title: Diffeomorphic interpolation for efficient persistence-based topological optimization
• Authors: Mathieu Carriere, Marc Theveneau, Théo Lacombe,
• Abstract summary: Topological Data Analysis (TDA) provides a pipeline to extract quantitative topological descriptors from structured objects. We show that our approach combines efficiently with subsampling techniques, as the diffeomorphism derived from the gradient computed on a subsample can be used to update the coordinates of the full input object. We also showcase the relevance of our approach for black-box autoencoder (AE) regularization, where we aim at enforcing topological priors on the latent spaces associated to fixed, pre-trained, blackbox AE models.
• Score: 3.7550827441501844
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Topological Data Analysis (TDA) provides a pipeline to extract quantitative topological descriptors from structured objects. This enables the definition of topological loss functions, which assert to what extent a given object exhibits some topological properties. These losses can then be used to perform topological optimizationvia gradient descent routines. While theoretically sounded, topological optimization faces an important challenge: gradients tend to be extremely sparse, in the sense that the loss function typically depends on only very few coordinates of the input object, yielding dramatically slow optimization schemes in practice.Focusing on the central case of topological optimization for point clouds, we propose in this work to overcome this limitation using diffeomorphic interpolation, turning sparse gradients into smooth vector fields defined on the whole space, with quantifiable Lipschitz constants. In particular, we show that our approach combines efficiently with subsampling techniques routinely used in TDA, as the diffeomorphism derived from the gradient computed on a subsample can be used to update the coordinates of the full input object, allowing us to perform topological optimization on point clouds at an unprecedented scale. Finally, we also showcase the relevance of our approach for black-box autoencoder (AE) regularization, where we aim at enforcing topological priors on the latent spaces associated to fixed, pre-trained, black-box AE models, and where we show thatlearning a diffeomorphic flow can be done once and then re-applied to new data in linear time (while vanilla topological optimization has to be re-run from scratch). Moreover, reverting the flow allows us to generate data by sampling the topologically-optimized latent space directly, yielding better interpretability of the model.

Related papers

• A Practical Solver for Scalar Data Topological Simplification [7.079737824450954]
  This paper presents a practical approach for the optimization of topological simplification. We show that our approach leads to improvements over standard topological techniques for removing filament loops. We also show how our approach can be used to repair genus defects in surface processing.
  arXiv  Detail & Related papers  (2024-07-17T08:25:32Z)
• A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascent for Functional Minimax Optimization [90.87444114491116]
  This paper studies minimax optimization problems defined over infinite-dimensional function classes of overparametricized two-layer neural networks. We address (i) the convergence of the gradient descent-ascent algorithm and (ii) the representation learning of the neural networks. Results show that the feature representation induced by the neural networks is allowed to deviate from the initial one by the magnitude of $O(alpha-1)$, measured in terms of the Wasserstein distance.
  arXiv  Detail & Related papers  (2024-04-18T16:46:08Z)
• Differentially Private Optimization with Sparse Gradients [60.853074897282625]
  We study differentially private (DP) optimization problems under sparsity of individual gradients. Building on this, we obtain pure- and approximate-DP algorithms with almost optimal rates for convex optimization with sparse gradients.
  arXiv  Detail & Related papers  (2024-04-16T20:01:10Z)
• Neural Gradient Learning and Optimization for Oriented Point Normal Estimation [53.611206368815125]
  We propose a deep learning approach to learn gradient vectors with consistent orientation from 3D point clouds for normal estimation. We learn an angular distance field based on local plane geometry to refine the coarse gradient vectors. Our method efficiently conducts global gradient approximation while achieving better accuracy and ability generalization of local feature description.
  arXiv  Detail & Related papers  (2023-09-17T08:35:11Z)
• Topology-Preserving Dimensionality Reduction via Interleaving Optimization [10.097180927318703]
  We show how optimization seeking to minimize the interleaving distance can be incorporated into dimensionality reduction algorithms. We demonstrate the utility of this framework to data visualization.
  arXiv  Detail & Related papers  (2022-01-31T06:11:17Z)
• A Gradient Sampling Algorithm for Stratified Maps with Applications to Topological Data Analysis [0.0]
  We introduce a novel gradient descent algorithm extending the well-known Gradient Sampling methodology. We then apply our method to objective functions based on the persistent homology map computed over lower-star filters.
  arXiv  Detail & Related papers  (2021-09-01T14:07:44Z)
• Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problem [8.164433158925593]
  We investigate how analytically-based algorithms such as dynamical descent, its persistent gradient, and Langevin landscape descent can be studied. We apply statistical-field theory from statistical trajectories to these algorithms in their full-time limit, with a start, and for large system sizes.
  arXiv  Detail & Related papers  (2021-03-08T17:06:18Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  This work is on the iteration of zero-th-order (ZO) optimization which does not require first-order information. We show that with a graceful design in coordinate importance sampling, the proposed ZO optimization method is efficient both in terms of complexity as well as as function query cost.
  arXiv  Detail & Related papers  (2020-12-21T17:29:58Z)
• A Fast and Robust Method for Global Topological Functional Optimization [70.11080854486953]
  We introduce a novel backpropagation scheme that is significantly faster, more stable, and produces more robust optima. This scheme can also be used to produce a stable visualization of dots in a persistence diagram as a distribution over critical, and near-critical, simplices in the data structure.
  arXiv  Detail & Related papers  (2020-09-17T18:46:16Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  Adaptive algorithms perform gradient updates using the history of gradients and are ubiquitous in training deep neural networks. In this paper we analyze a variant of OptimisticOA algorithm for nonconcave minmax problems. Our experiments show that adaptive GAN non-adaptive gradient algorithms can be observed empirically.
  arXiv  Detail & Related papers  (2019-12-26T22:10:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.