A fofoca é uma maneira eficiente de compartilhar informações em grandes redes e tem aplicações inesperadas na solução de outros problemas matemáticos e de aprendizado de máquina.

Ao olhar para algoritmos de fofoca clássicos de uma nova perspectiva, O professor Peter Richtarik da KAUST encontrou uma maneira de acelerar significativamente o compartilhamento de informações com base em fofocas, e no processo, ele descobriu novas aplicações para esta abordagem matemática eficiente.

A fofoca envolve o compartilhamento de informações entre os indivíduos em uma rede e pode ser aplicada matematicamente em redes sociais humanas e redes de dados, como sensores distribuídos.

"Uma rede é uma coleção de nós, cada um conectado a outros nós por meio de links, "explica Richtarik." Nas redes sociais, por exemplo, indivíduos são conectados a outros por meio de laços de amizade. Em redes de sensores, os sensores podem ser conectados se estiverem próximos o suficiente para se comunicarem por meio de uma conexão sem fio. "

Em muitos aplicativos do mundo real, muitas vezes é útil realizar cálculos com base nos dados armazenados por todos os nós em uma rede, como calcular a média dos dados privados armazenados por cada nó, que é conhecido como o problema do consenso médio. Contudo, porque a comunicação é limitada a links diretos entre os nós, na prática, isso é muito desafiador.

"A ideia dos algoritmos de fofoca é realizar esse cálculo por comunicação entre pares entre amigos selecionados aleatoriamente e repetir esse processo até que todos os indivíduos saibam o resultado, "diz Richtarik." Isso imita a forma como a fofoca funciona entre os humanos. É surpreendente que seja possível mostrar matematicamente que esta estratégia de comunicação simples pode resolver um problema global, problema de toda a rede. "

Em colaboração com Nicolas Loizou da Universidade de Edimburgo, na Escócia, Richtarik tem estudado os algoritmos de fofoca aleatórios e suas conexões com outros ramos da matemática e da ciência da computação.

Seu estudo teórico revelou uma profunda conexão entre algoritmos de fofoca aleatórios e um ramo da matemática chamado álgebra linear, que envolve a resolução de sistemas de muitas equações com muitas incógnitas. Eles também estabeleceram um link direto direto com um dos algoritmos mais famosos de aprendizado de máquina, o método de descida gradiente estocástico, que é usado para treinar os modelos de aprendizado profundo empregados em quase todas as aplicações industriais. Essas percepções ajudaram os pesquisadores a desenvolver protocolos de fofoca novos e muito mais rápidos.

"Fomos capazes de desenvolver um algoritmo de fofoca acelerado que precisa de muito menos rodadas de fofoca para atingir o valor médio de consenso, "diz Richtarik." Nosso método precisa apenas da raiz quadrada do número de rodadas necessárias para um algoritmo de fofoca clássico, são 100 rodadas em vez de 10, 000. Provamos isso matematicamente e observamos essa aceleração na prática também. "