Towards Scalable Persistence-Based Topological Optimization

Sintesi Tecnica: Verso un'Ottimizzazione Topologica Basata sulla Persistenza Scalabile

Enunciato del Problema
L'ottimizzazione topologica basata sulla persistenza mira a deformare una nuvola di punti $X \subset \mathbb{R}^d$ per minimizzare obiettivi della forma $L(X) = \ell(\text{Dgm}(X))$, dove $\text{Dgm}(X)$ è un diagramma di persistenza. Sebbene teoricamente fondata grazie alla stabilità dell'omologia persistente, l'implementazione pratica incontra due colli di bottiglia accoppiati:

1. Necessità di Sottocampionamento: Il calcolo dell'omologia persistente su grandi nuvole di punti è computazionalmente proibitivo, rendendo necessario il sottocampionamento. Tuttavia, il sottocampionamento uniforme standard introduce un bias di densità, sovracampionando spesso le regioni dense mentre trascura le aree sparse ai bordi, critiche per le caratteristiche topologiche.
2. Sparsità del Gradiente: Il gradiente topologico è altamente sparso; solo un piccolo insieme di punti "ancora" (quelli coinvolti nei simplessi critici di nascita/morte) riceve aggiornamenti non nulli. La maggior parte dei punti ha gradienti nulli, rallentando l'ottimizzazione.
3. Scalabilità del Livellamento: Una recente soluzione, l'interpolazione diffeomorfa (Carrière et al., 2024), estende i gradienti sparsi a un campo vettoriale ambientale liscio utilizzando l'interpolazione nello Spazio di Hilbert a Kernel Riproducente (RKHS). Tuttavia, ciò richiede la risoluzione di un sistema lineare a kernel ad ogni iterazione, che diventa computazionalmente dominante ($O(|I|^3)$) in contesti su larga scala.

Metodologia
Gli autori propongono una pipeline scalabile che affronta sia il problema del sottocampionamento che quello dell'estensione del gradiente attraverso due componenti principali:

1. Sottocampionamento tramite Taglio Casuale:
   Invece del campionamento uniforme, gli autori introducono un campionatore strutturato ispirato al trasporto ottimo tagliato.

   • Meccanismo: Ad ogni iterazione, viene estratta una direzione casuale $u$. I punti vengono proiettati su questa linea 1D ($t_i = \langle x_i, u \rangle$) e ordinati. Il sottocampione è formato selezionando punti a ranghi equidistanti in questa lista ordinata.
   • Vantaggio: Ciò garantisce una copertura geometrica globale e mitiga il bias di densità. Imponendo una stratificazione dei ranghi, il metodo impedisce ai cluster densi di monopolizzare il budget del campione, assicurando che le regioni sparse (ad esempio, i confini tra i cluster) siano rappresentate in modo coerente.

2. Convoluzione Gaussiana Nadaraya-Watson (NW):
   Per sostituire la costosa risoluzione del kernel RKHS, gli autori propongono l'uso di un veloce stimatore NW per livellare i gradienti sparsi delle ancora in un campo vettoriale globale.

   • Meccanismo: Dati i punti ancora $x_i$ con gradienti $g_i$, il campo in un qualsiasi punto $x$ è definito come una media pesata: $\bar{v}(x) = \sum_{i \in I} w_i(x) g_i$, dove i pesi $w_i(x)$ sono affinità gaussiane normalizzate $\exp(-\|x-x_i\|^2 / 2\sigma^2)$.
   • Vantaggi:
     • Efficienza Computazionale: Evita la risoluzione di un sistema lineare, riducendo significativamente il costo.
     • Comportamento Geometrico: A differenza dell'interpolazione RKHS, che utilizza kernel non normalizzati e può causare la scomparsa della magnitudine del campo lontano dalle ancora, il livellamento NW impone una combinazione convessa ($\sum w_i = 1$). Ciò garantisce che il campo rimanga non nullo e si comporti come una media baricentrica locale, fornendo una propagazione più robusta dei segnali sparsi attraverso il dominio.
   • Garanzie Teoriche: Il lavoro fornisce limiti sull'errore di approssimazione delle ancora e stabilisce la continuità di Lipschitz globale per il campo NW, mostrando che la costante di Lipschitz scala con $1/\sigma^2$.

3. Apprendimento Adattivo della Larghezza di Banda:
   Riconoscendo che il parametro di larghezza di banda $\sigma$ impatta criticamente le prestazioni, gli autori propongono di apprendere $\sigma$ online tramite backpropagation. Parametrizzano $\sigma(\theta) = \sigma_0 \exp(\theta)$ e aggiornano $\theta$ per minimizzare una perdita di previsione, permettendo alla scala di livellamento di adattarsi al regime di ottimizzazione locale.

Contributi Chiave

• Taglio Casuale: Uno schema di sottocampionamento leggero che migliora la copertura geometrica e riduce il bias di densità senza richiedere clustering o campionamento dal punto più lontano.
• Livellamento NW: Una sostituzione per l'interpolazione esatta del kernel che offre una convoluzione gaussiana rapida e normalizzata per estendere i gradienti topologici sparsi, evitando risoluzioni lineari di tempo cubico.
• Analisi Teorica: Dimostrazioni di limiti di approssimazione delle ancora e stime di Lipschitz globali per l'operatore di livellamento NW.
• Validazione Empirica: Dimostrazione di accelerazioni e valori obiettivo migliorati su compiti 2D e 3D.

Risultati Sperimentali
Gli autori hanno valutato il loro metodo su un compito di aumento topologico 3D utilizzando la nuvola di punti Stanford Bunny ($n \approx 36.000$), mirando a rafforzare le caratteristiche topologiche 2D (cavità).

• Baseline: Confronto contro (i) Discesa del gradiente sparsa "Vanilla" (senza livellamento), (ii) Interpolazione Diffeomorfa a Kernel Esatto, e (iii) Il metodo proposto NW-Convolution.
• Prestazioni:
  • Valore dell'Obiettivo: Il metodo NW-Convolution ha raggiunto una perdita significativamente inferiore ($-0,01869$) rispetto sia al metodo Vanilla ($-0,00026$) che a quello Kernel ($-0,00151$).
  • Tempo di Esecuzione: Il metodo NW ha mantenuto un tempo di esecuzione per epoca ($2,573$s) comparabile alla baseline Vanilla ($2,044$s) ed è stato un ordine di grandezza più veloce del metodo Kernel ($19,979$s).
• Sensibilità: Esperimenti su un cerchio 2D rumoroso hanno dimostrato un'alta sensibilità alla larghezza di banda $\sigma$, motivando l'uso della strategia di apprendimento adattivo proposta.

Significato e Affermazioni
Il lavoro afferma di affrontare un collo di bottiglia pratico centrale nell'ottimizzazione basata sulla persistenza: il compromesso tra la sparsità dei gradienti topologici e il costo computazionale del loro livellamento. Combinando il taglio casuale con il livellamento NW, gli autori forniscono una pipeline che è sia scalabile che efficace.

Gli autori mantengono un tono modesto riguardo al loro contributo. Affermano che il loro lavoro è principalmente un passo verso la resa dell'ottimizzazione guidata dalla persistenza più scalabile e pratica per contesti che coinvolgono grandi insiemi di punti e calcoli ripetuti di PH. Notano esplicitamente che la loro valutazione attuale è limitata a benchmark sintetici controllati e geometrie standard (Stanford Bunny, forme 2D) e che non dimostrano ancora un impatto end-to-end su compiti reali downstream. Il lavoro è posizionato come un miglioramento metodologico del ciclo di ottimizzazione stesso piuttosto che come un nuovo dominio di applicazione.