Towards Scalable Persistence-Based Topological Optimization

Résumé Technique : Vers une Optimisation Topologique Basée sur la Persistance Évolutif

Énoncé du Problème
L'optimisation topologique basée sur la persistance vise à déformer un nuage de points $X \subset \mathbb{R}^d$ afin de minimiser des objectifs de la forme $L(X) = \ell(\text{Dgm}(X))$, où $\text{Dgm}(X)$ est un diagramme de persistance. Bien que théoriquement fondée sur la stabilité de l'homologie persistante, sa mise en œuvre pratique se heurte à deux goulots d'étranglement couplés :

1. Nécessité de l'échantillonnage : Le calcul de l'homologie persistante sur de grands nuages de points est prohibitif en termes de calcul, rendant l'échantillonnage nécessaire. Cependant, l'échantillonnage uniforme standard introduit un biais de densité, suréchantillonnant souvent les régions denses tout en manquant les zones de bordure clairsemées, pourtant critiques pour les caractéristiques topologiques.
2. Sparsité du gradient : Le gradient topologique est hautement épars ; seul un petit ensemble de points « ancrage » (ceux impliqués dans les simplexes critiques de naissance/décès) reçoit des mises à jour non nulles. La plupart des points ayant un gradient nul, l'optimisation est ralentie.
3. Évolutivité du lissage : Un remède récent, l'interpolation difféomorphique (Carrière et al., 2024), étend les gradients épars à un champ vectoriel ambiant lisse en utilisant l'interpolation dans un Espace de Hilbert à Noyau Reproductible (RKHS). Cependant, cela nécessite de résoudre un système linéaire à noyau à chaque itération, ce qui devient dominant en termes de calcul ($O(|I|^3)$) dans des contextes à grande échelle.

Méthodologie
Les auteurs proposent un pipeline évolutif qui résout à la fois les problèmes d'échantillonnage et d'extension du gradient grâce à deux composantes principales :

1. Échantillonnage par Tranchage Aléatoire :
   Au lieu d'un échantillonnage uniforme, les auteurs introduisent un échantillonneur structuré inspiré du transport optimal tranché.

   • Mécanisme : À chaque itération, une direction aléatoire $u$ est tirée. Les points sont projetés sur cette ligne 1D ($t_i = \langle x_i, u \rangle$) et triés. L'échantillon est formé en sélectionnant les points à des rangs régulièrement espacés dans cette liste triée.
   • Avantage : Cela assure une couverture géométrique globale et atténue le biais de densité. En imposant une stratification par rang, la méthode empêche les clusters denses de monopoliser le budget d'échantillonnage, garantissant que les régions clairsemées (par exemple, les frontières entre les clusters) sont systématiquement représentées.

2. Convolution Gaussienne de Nadaraya-Watson (NW) :
   Pour remplacer la coûteuse résolution de noyau RKHS, les auteurs proposent d'utiliser un estimateur NW rapide pour lisser les gradients d'ancrage épars en un champ vectoriel global.

   • Mécanisme : Étant donnés les points d'ancrage $x_i$ avec leurs gradients $g_i$, le champ en tout point $x$ est défini comme une moyenne pondérée : $\bar{v}(x) = \sum_{i \in I} w_i(x) g_i$, où les poids $w_i(x)$ sont des affinités gaussiennes normalisées $\exp(-\|x-x_i\|^2 / 2\sigma^2)$.
   • Avantages :
     • Efficacité computationnelle : Cela évite de résoudre un système linéaire, réduisant considérablement le coût.
     • Comportement géométrique : Contrairement à l'interpolation RKHS, qui utilise des noyaux non normalisés et peut entraîner la disparition de l'amplitude du champ loin des ancres, le lissage NW impose une combinaison convexe ($\sum w_i = 1$). Cela garantit que le champ reste non nul et se comporte comme une moyenne barycentrique locale, assurant une propagation plus robuste des signaux épars à travers le domaine.
   • Garanties théoriques : L'article fournit des bornes sur l'erreur d'approximation des ancres et établit la continuité de Lipschitz globale pour le champ NW, montrant que la constante de Lipschitz évolue avec $1/\sigma^2$.

3. Apprentissage Adaptatif de la Bande Passante :
   Reconnaissant que le paramètre de bande passante $\sigma$ impacte crucialement les performances, les auteurs proposent d'apprendre $\sigma$ en ligne par rétropropagation. Ils paramétrisent $\sigma(\theta) = \sigma_0 \exp(\theta)$ et mettent à jour $\theta$ pour minimiser une perte anticipée, permettant à l'échelle de lissage de s'adapter au régime d'optimisation local.

Contributions Clés

• Tranchage Aléatoire : Un schéma d'échantillonnage léger qui améliore la couverture géométrique et réduit le biais de densité sans nécessiter de clustering ni d'échantillonnage par point le plus éloigné.
• Lissage NW : Un remplacement pour l'interpolation exacte par noyau offrant une convolution gaussienne normalisée rapide pour étendre les gradients topologiques épars, évitant les résolutions de systèmes linéaires de complexité cubique.
• Analyse Théorique : Preuves des bornes d'approximation des ancres et des estimations de Lipschitz globales pour l'opérateur de lissage NW.
• Validation Empirique : Démonstration de gains de vitesse et d'amélioration des valeurs d'objectif sur des tâches 2D et 3D.

Résultats Expérimentaux
Les auteurs ont évalué leur méthode sur une tâche d'augmentation topologique 3D utilisant le nuage de points du Stanford Bunny ($n \approx 36\,000$), visant à renforcer les caractéristiques topologiques 2D (cavités).

• Lignes de base : Comparaison avec (i) la descente de gradient épars « Vanilla » (sans lissage), (ii) l'interpolation difféomorphique exacte par noyau, et (iii) la méthode proposée par convolution NW.
• Performance :
  • Valeur de l'objectif : La méthode par convolution NW a atteint une perte significativement plus faible ($-0,01869$) comparée aux méthodes Vanilla ($-0,00026$) et Noyau ($-0,00151$).
  • Temps d'exécution : La méthode NW a maintenu un temps d'exécution par époque ($2,573$s) comparable à la ligne de base Vanilla ($2,044$s) et a été un ordre de grandeur plus rapide que la méthode Noyau ($19,979$s).
• Sensibilité : Des expériences sur un cercle 2D bruité ont démontré une forte sensibilité à la bande passante $\sigma$, motivant l'utilisation de la stratégie d'apprentissage adaptatif proposée.

Signification et Revendications
L'article revendique de s'attaquer à un goulot d'étranglement pratique central dans l'optimisation basée sur la persistance : le compromis entre la sparsité des gradients topologiques et le coût computationnel de leur lissage. En combinant le tranchage aléatoire avec le lissage NW, les auteurs fournissent un pipeline à la fois évolutif et efficace.

Les auteurs adoptent un ton modeste concernant leur contribution. Ils affirment que leur travail est principalement une étape vers la mise à l'échelle et la praticabilité de l'optimisation pilotée par la persistance pour des contextes impliquant de grands ensembles de points et des calculs répétés d'homologie persistante. Ils notent explicitement que leur évaluation actuelle se limite à des benchmarks synthétiques contrôlés et de géométrie standard (Stanford Bunny, formes 2D) et qu'ils ne démontrent pas encore d'impact de bout en bout sur des tâches réelles en aval. Le travail est positionné comme une amélioration méthodologique de la boucle d'optimisation elle-même plutôt que comme un nouveau domaine d'application.