Geometry-Aware Decentralized Sinkhorn for Wasserstein Barycenters

Resumen Técnico: Sinkhorn Descentralizado Consciente de la Geometría para Barycentros de Wasserstein

1. Planteamiento del Problema

Los sistemas distribuidos a menudo enfrentan el desafío de fusionar distribuciones de probabilidad locales heterogéneas en un resumen global sobre redes de comunicación escasas e poco fiables. Los algoritmos de consenso tradicionales suelen tratar las distribuciones como vectores euclidianos y calcular promedios aritméticos. Los autores argumentan que este enfoque ignora la estructura geométrica inherente de los espacios de probabilidad, lo que puede conducir a resultados engañosos (por ejemplo, promediar dos distribuciones con soporte en ubicaciones opuestas produce un punto medio que puede ser una ubicación imposible).

Si bien los barycentros de Wasserstein ofrecen una alternativa consciente de la geometría al minimizar los costos de transporte óptimo, su cálculo estándar mediante el algoritmo de Sinkhorn depende de un paso de media geométrica centralizado. Los enfoques descentralizados existentes o bien retienen un coordinador, intercambian información dual densa a través de rutinas de optimización generales, o no logran descentralizar directamente el paso específico de media geométrica de Sinkhorn. El artículo aborda la necesidad de un método totalmente descentralizado y eficiente en ancho de banda que preserve las propiedades geométricas del barycentro sin un coordinador central.

2. Metodología

La solución propuesta es un algoritmo de Sinkhorn totalmente descentralizado que reformula la media geométrica centralizada como un promedio aritmético en el dominio logarítmico. La metodología procede a través de tres mecanismos centrales:

• Reformulación en el Dominio Logarítmico: La actualización estándar de Sinkhorn para el vector de escalado compartido $v$ implica una media geométrica de los términos locales $K^\top u_i$. Al definir un mensaje logarítmico $s_i = \log(K^\top u_i)$, la media geométrica se convierte en una media aritmética: $\log v = \frac{1}{N} \sum s_i$. Esta transformación permite reemplazar el paso de agregación global por un promedio local.
• Chismorreaje Descentralizado: Los agentes aproximan la media aritmética global de los mensajes logarítmicos mediante protocolos de chismorreaje ponderados. Cada agente mantiene una estimación local $z_i$ y la actualiza utilizando los paquetes más recientes de sus vecinos. Esto entrelaza las actualizaciones de escalado local (calculando $u_i$) con fases de consenso para imitar las iteraciones centralizadas.
• Optimización del Ancho de Banda: Para abordar las restricciones de comunicación, el algoritmo integra:
  • Transmisión Activada por Eventos: Los agentes transmiten mensajes solo cuando el cambio en su mensaje logarítmico supera un umbral $\delta$ ($\|s_i - s_{i, last}\|_\infty > \delta$).
  • Recorte y Cuantización: Los mensajes se recortan a un rango finito $[s_{min}, s_{max}]$ y se cuantizan a $b$ bits antes de la transmisión. Los cálculos locales mantienen precisión completa, mientras que solo los paquetes transmitidos se cuantizan.
  • Asincronía y Pérdida de Paquetes: El protocolo está diseñado para acomodar actualizaciones asíncronas y pérdida de paquetes reutilizando paquetes en caché hasta que lleguen nuevos.

3. Contribuciones Clave

El artículo afirma tres contribuciones principales:

1. Algorítmica: Un algoritmo de Sinkhorn totalmente descentralizado que elimina la coordinación central reformulando las medias geométricas como consenso aritmético distribuido en el espacio logarítmico.
2. Comunicación: El diseño de protocolos activados por eventos y cuantizados que reducen el uso de ancho de banda en órdenes de magnitud mientras preservan las garantías de convergencia.
3. Teórica: Una prueba de convergencia a una vecindad del barycentro entrópico centralizado. El análisis establece que el sesgo (error) depende linealmente de la tolerancia de consenso ($\tau$), el umbral de activación ($\delta$) y el error de cuantización ($\Delta_q$). Se demuestra que la tasa de convergencia es lineal (geométrica) con un factor dependiente del parámetro de regularización entrópica $\varepsilon$.

4. Resultados

Los autores evaluaron el algoritmo en una red de cuadrícula de 4x4 ($N=16$) con un tamaño de soporte de $d=64$.

• Precisión: Las simulaciones demuestran que las iteraciones descentralizadas permanecen en una pequeña vecindad $\ell_1$ de la solución centralizada. El barycentro descentralizado es visualmente indistinguible del centralizado sobre los modos dominantes.
• Comportamiento de Convergencia: El consenso del bucle interno exhibe el perfil de sierra esperado (contracción rápida seguida de pequeños saltos en las actualizaciones externas). La activación por eventos introduce perturbaciones acotadas pero no altera el régimen de contracción.
• Complejidad: El recuento total de mensajes escala casi linealmente ($O(N)$) con el tamaño de la red en grafos de cuadrícula, superando significativamente las líneas base de escala cuadrática ($O(N^2)$). El tiempo de ejecución aumenta monótonamente con el tamaño de la red, como predice el análisis del costo por iteración.
• Compensaciones: Los resultados confirman que el algoritmo logra una precisión cercana a la centralizada con significativamente menos mensajes en diversas topologías y condiciones.

5. Significado y Afirmaciones

El artículo posiciona su trabajo como una solución a la limitación fundamental del promedio euclidiano en la fusión de probabilidades distribuidas. Al aprovechar la identidad del dominio logarítmico, los autores afirman haber implementado con éxito el paso de media geométrica de Sinkhorn como un promedio logarítmico entre pares, una capacidad no lograda previamente en entornos descentralizados sin un coordinador.

El significado radica en el control explícito de compensaciones: el método proporciona parámetros ajustables (umbrales de activación, bits de cuantización) para equilibrar la precisión frente a los costos de comunicación, haciéndolo adecuado para redes con enlaces escasos e poco fiables. Las garantías teóricas aseguran que la desviación de la solución centralizada óptima está acotada y es predecible según los parámetros del sistema. Los autores concluyen que este enfoque permite el promedio consciente de la geometría en sistemas distribuidos (como robots autónomos o redes de sensores) sin necesidad de compartir datos crudos o infraestructura central, manteniendo al mismo tiempo la robustez frente a la asincronía y la pérdida de paquetes.