Distributed Banach-Picard iteration with applications to inference problems

Francisco de Lima Andrade

Informações chave

Autores:

Francisco de Lima Andrade (Francisco de Lima Andrade)

Orientadores:

Mário Alexandre Teles de Figueiredo (Mário Alexandre Teles de Figueiredo); João Manuel de Freitas Xavier (João Manuel de Freitas Xavier)

Publicado em

28/07/2022

Resumo

A iteração de Banach-Picard é amplamente utilizada para encontrar pontos fixos de mapas localmente ou globalmente contractivos. O trabalho apresentado nesta tese estende a iteração de Banach-Picard a configurações distribuídas; específicamente, assumimos que o mapa cujo ponto fixo se pretende é uma média de mapas individuais (não necessariamente localmente ou globalmente contractivos) que pertencem a um conjunto de agentes ligados por uma rede de comunicações. Propomos um algoritmo distribuído, denominado distributed Banach-Picard iteration (DBPI), e provamos a sua convergência, de facto mostrando que se a média dos mapas individuais é um mapa localmente ou globalmente contractivo, então o mapa subjacente ao DBPI herda a propriedade correspondente. O desafio no caso de um mapa localmente contractivo (LC) é que não é assumido que este mapa emirja de um problema de optimização subjacente, o que impede a exploração de propriedades globais fortes como convexidade ou condições de Lipschitz. A segunda parte desta tese parte do DBPI e das suas guarantias de convergência local linear para fazer várias contribuições. Mostramos que o algoritmo de Sanger para análise de components principais (ACP) corresponde à iteração de um mapa LC que pode ser escrito como uma média de mapas locais, cada mapa sendo conhecido por um agente que detém um subjconjunto dos dados. De forma semelhante, mostramos que uma variante do algoritmo de expectativa-maximização (EM) para a estimação de um parâmetro, a partir de medidas com ruído e/ou defeituosas obtidas por uma rede de sensores, pode ser escrita como uma média de mapas locais, cada um dos quais pertencendo a um único sensor. Consequentemente, partir do DBPI, obtemos dois algoritmos distribuídos - EM distribuído e ACP distribuído - cujas guarantias de convergência local linear seguem das guarantias provadas para o DBPI. A verificação da condição LC para a variante do algoritmo EM não é trivial, dado que o operador subjacente depende de amostras aleatórias, implicando, portanto, que a condição LC seja de natureza probabilística. The Banach-Picard iteration is widely used to find fixed points of locally or globally contractive maps. The work presented in this thesis extends the Banach-Picard iteration to distributed settings; specifically, we assume the map of which the fixed point is sought to be the average of individual (not necessarily locally or globally contractive) maps held by a set of agents linked by a communication network. We propose a distributed algorithm, termed distributed Banach-Picard iteration (DBPI), and prove its convergence, in fact showing that if the average map is locally or globally contractive, then the map underlying DBPI inherits the corresponding property. The challenge in the locally contractive (LC) case is that the map is not assumed to come from an underlying optimization problem, which prevents exploiting strong global properties such as convexity or Lipschitzianity. The second part of this thesis builds upon the DBPI and its local linear convergence (LLC) guarantees to make several contributions. We show that Sanger’s algorithm for principal component analysis (PCA) corresponds to the iteration of a LC map that can be written as the average of local maps, each map known to an agent holding a subset of the data. Similarly, we show that a variant of the expectation-maximization (EM) algorithm for parameter estimation from noisy and faulty measurements in a sensor network can be written as the iteration of a LC map that is the average of local maps, each available at just one node. Consequently, via the DBPI, we derive two distributed algorithms – distributed EM and distributed PCA – whose LLC guarantees follow from those that we proved for the DBPI. The verification of the LC condition for the variant of the EM algorithm is challenging, as the underlying map depends on random samples, thus the LC condition is of probabilistic nature.