Gossip es una forma eficiente de compartir información a través de grandes redes y tiene aplicaciones inesperadas para resolver otros problemas matemáticos y de aprendizaje automático.

Al observar los algoritmos de chismes clásicos desde una perspectiva novedosa, El profesor de KAUST, Peter Richtarik, ha encontrado una manera de acelerar significativamente el intercambio de información basada en chismes, y en el proceso, descubrió nuevas aplicaciones para este eficiente enfoque matemático.

El chisme implica el intercambio de información entre individuos en una red y se puede aplicar matemáticamente tanto en redes sociales humanas como en redes de datos. como sensores distribuidos.

"Una red es una colección de nodos, cada uno conectado a otros nodos a través de enlaces, "explica Richtarik". En las redes sociales, por ejemplo, los individuos están conectados con otros a través de vínculos de amistad. En redes de sensores, los sensores podrían conectarse si están lo suficientemente cerca para comunicarse a través de una conexión inalámbrica ".

En muchas aplicaciones del mundo real, a menudo es útil realizar cálculos basados ​​en los datos almacenados por todos los nodos en una red, como calcular el promedio de los datos privados almacenados por cada nodo, que se conoce como el problema de consenso promedio. Sin embargo, porque la comunicación se limita a enlaces directos entre nodos, en la práctica, esto es muy desafiante.

"La idea de los algoritmos de chismes es realizar este cálculo mediante la comunicación por pares entre amigos seleccionados al azar y repetir este proceso hasta que todas las personas conozcan el resultado, "dice Richtarik." Esto imita la forma en que funciona el chisme entre los humanos. Es sorprendente que sea posible demostrar matemáticamente que esta simple estrategia de comunicación puede resolver un problema global, problema en toda la red ".

En colaboración con Nicolas Loizou de la Universidad de Edimburgo en Escocia, Richtarik ha estado estudiando los algoritmos de chismes aleatorios y sus conexiones con otras ramas de las matemáticas y la informática.

Su estudio teórico reveló una conexión profunda entre los algoritmos de chismes aleatorios y una rama de las matemáticas llamada álgebra lineal. que implica resolver sistemas de muchas ecuaciones con muchas incógnitas. También establecieron un vínculo profundo directo con uno de los algoritmos más famosos en aprendizaje automático, el método de descenso de gradiente estocástico, que se utiliza para entrenar los modelos de aprendizaje profundo empleados en casi todas las aplicaciones industriales. Estos conocimientos ayudaron a los investigadores a desarrollar protocolos de chismes nuevos y mucho más rápidos.

"Pudimos desarrollar un algoritmo de chismes acelerado que necesita muchas menos rondas de chismes para alcanzar el valor de consenso promedio, "dice Richtarik." Nuestro método solo necesita la raíz cuadrada del número de rondas necesarias para un algoritmo de chismes clásico, son 100 rondas en lugar de 10, 000. Probamos esto matemáticamente y también observamos esta aceleración en la práctica ".