Towards Scalable Persistence-Based Topological Optimization

Resumo Técnico: Rumo à Otimização Topológica Baseada em Persistência Escalável

Enunciado do Problema
A otimização topológica baseada em persistência busca deformar uma nuvem de pontos $X \subset \mathbb{R}^d$ para minimizar objetivos da forma $L(X) = \ell(\text{Dgm}(X))$, onde $\text{Dgm}(X)$ é um diagrama de persistência. Embora teoricamente sólida devido à estabilidade da homologia persistente, a implementação prática enfrenta dois gargalos acoplados:

1. Necessidade de Subamostragem: Calcular homologia persistente em grandes nuvens de pontos é computacionalmente proibitivo, tornando necessária a subamostragem. No entanto, a subamostragem uniforme padrão introduz viés de densidade, frequentemente superamostrando regiões densas enquanto perde áreas de fronteira esparsas críticas para características topológicas.
2. Esparsidade do Gradiente: O gradiente topológico é altamente esparso; apenas um pequeno conjunto de pontos "âncora" (aqueles envolvidos em símplices críticos de nascimento/morte) recebe atualizações não nulas. A maioria dos pontos possui gradientes zero, o que retarda a otimização.
3. Escalabilidade do Suavizamento: Um remédio recente, a interpolação difeomórfica (Carrière et al., 2024), estende gradientes esparsos a um campo vetorial ambiente suave usando interpolação em Espaço de Hilbert de Núcleo Reprodutor (RKHS). No entanto, isso requer a resolução de um sistema linear de núcleo a cada iteração, o que se torna computacionalmente dominante ($O(|I|^3)$) em configurações de grande escala.

Metodologia
Os autores propõem um pipeline escalável que aborda tanto os problemas de subamostragem quanto de extensão de gradiente através de dois componentes principais:

1. Subamostragem via Corte Aleatório:
   Em vez de amostragem uniforme, os autores introduzem um amostrador estruturado inspirado no transporte ótimo fatiado.

   • Mecanismo: Em cada iteração, uma direção aleatória $u$ é sorteada. Os pontos são projetados nesta linha 1D ($t_i = \langle x_i, u \rangle$) e ordenados. A subamostra é formada selecionando pontos em ranks uniformemente espaçados nesta lista ordenada.
   • Benefício: Isso garante cobertura geométrica global e mitiga o viés de densidade. Ao impor estratificação de ranks, o método impede que aglomerados densos monopolizem o orçamento da amostra, garantindo que regiões esparsas (por exemplo, fronteiras entre aglomerados) sejam consistentemente representadas.

2. Convolução Gaussiana de Nadaraya-Watson (NW):
   Para substituir o custoso solve de núcleo RKHS, os autores propõem usar um estimador NW rápido para suavizar os gradientes de âncora esparsos em um campo vetorial global.

   • Mecanismo: Dados pontos âncora $x_i$ com gradientes $g_i$, o campo em qualquer ponto $x$ é definido como uma média ponderada: $\bar{v}(x) = \sum_{i \in I} w_i(x) g_i$, onde os pesos $w_i(x)$ são afinidades Gaussianas normalizadas $\exp(-\|x-x_i\|^2 / 2\sigma^2)$.
   • Vantagens:
     • Eficiência Computacional: Evita resolver um sistema linear, reduzindo significativamente o custo.
     • Comportamento Geométrico: Diferentemente da interpolação RKHS, que usa núcleos não normalizados e pode fazer com que a magnitude do campo desapareça longe das âncoras, o suavizamento NW impõe uma combinação convexa ($\sum w_i = 1$). Isso garante que o campo permaneça não nulo e se comporte como uma média baricêntrica local, proporcionando uma propagação mais robusta de sinais esparsos através do domínio.
   • Garantias Teóricas: O artigo fornece limites sobre o erro de aproximação de âncora e estabelece continuidade Lipschitz global para o campo NW, mostrando que a constante Lipschitz escala com $1/\sigma^2$.

3. Aprendizado Adaptativo de Largura de Banda:
   Reconhecendo que o parâmetro de largura de banda $\sigma impacta criticamente o desempenho, os autores propõem aprender$\sigma$ online via retropropagação. Eles parametrizam $\sigma(\theta) = \sigma_0 \exp(\theta)$ e atualizam $\theta$ para minimizar uma perda de previsão, permitindo que a escala de suavização se adapte ao regime de otimização local.

Contribuições Principais

• Corte Aleatório: Um esquema de subamostragem leve que melhora a cobertura geométrica e reduz o viés de densidade sem exigir agrupamento ou amostragem do ponto mais distante.
• Suavizamento NW: Uma substituição para a interpolação exata de núcleo que oferece uma convolução Gaussiana rápida e normalizada para estender gradientes topológicos esparsos, evitando solves lineares de tempo cúbico.
• Análise Teórica: Provas de limites de aproximação de âncora e estimativas Lipschitz globais para o operador de suavizamento NW.
• Validação Empírica: Demonstração de acelerações e valores de objetivo melhorados em tarefas 2D e 3D.

Resultados Experimentais
Os autores avaliaram seu método em uma tarefa de aumento topológico 3D usando a nuvem de pontos Stanford Bunny ($n \approx 36.000$), visando fortalecer características topológicas 2D (cavidades).

• Baselines: Comparado contra (i) Descida de gradiente esparsa Vanilla (sem suavizamento), (ii) Interpolação Difeomórfica de Núcleo Exato e (iii) O método proposto de Convolução NW.
• Desempenho:
  • Valor do Objetivo: O método de Convolução NW alcançou uma perda significativamente menor ($-0,01869$) comparado tanto ao Vanilla ($-0,00026$) quanto ao método de Núcleo ($-0,00151$).
  • Tempo de Execução: O método NW manteve um tempo de execução por época ($2,573$s) comparável à baseline Vanilla ($2,044$s) e foi uma ordem de magnitude mais rápido que o método de Núcleo ($19,979$s).
• Sensibilidade: Experimentos em um círculo 2D ruidoso demonstraram alta sensibilidade à largura de banda $\sigma$, motivando o uso da estratégia de aprendizado adaptativo proposta.

Significado e Alegações
O artigo afirma abordar um gargalo prático central na otimização baseada em persistência: o trade-off entre a esparsidade dos gradientes topológicos e o custo computacional de suavizá-los. Ao combinar corte aleatório com suavizamento NW, os autores fornecem um pipeline que é tanto escalável quanto eficaz.

Os autores mantêm um tom modesto em relação à sua contribuição. Eles afirmam que seu trabalho é principalmente um passo rumo a tornar a otimização impulsionada por persistência mais escalável e prática para configurações envolvendo grandes conjuntos de pontos e cálculos repetidos de PH. Eles notam explicitamente que sua avaliação atual é limitada a benchmarks sintéticos controlados e de geometria padrão (Stanford Bunny, formas 2D) e que ainda não demonstram impacto de ponta a ponta em tarefas do mundo real subsequentes. O trabalho é posicionado como uma melhoria metodológica no próprio loop de otimização, em vez de um novo domínio de aplicação.