Multi-agent learning

Thesis

Machine learning models are often trained on data stored across multiple computers connected by a network. Due to network stability, it is then often infeasible for a single central-hub computer to process and disseminate information. A solution to overcome this bottleneck is to consider a decentralised network akin to peer-to-peer and ad-hoc wireless networks. Namely, computers communicate to a sub-set of other computers at a time, with information then naturally propagating through the network.

This thesis investigates the statistical performance of models produced in such a decentralised framework. By modelling the network of computers as agents in a graph, we investigate two different statistical settings: homogeneous, when the data stored across the computers follows the same distribution; and heterogeneous, when the distributions are different.

In the homogeneous setting, and motivated by the problem of empirical risk minimisation, we consider the learning performance of a simple decentralised algorithm: Distributed Gradient Descent. Specifically, we demonstrate that guarantees on learning performance can be achieved through implicit regularisation alongside, in the case of non-parametric regression, a linear speed up in computational runtime for any network topology provided computers have a sufficient amount of data. In contrast, prior work has focused on optimisation performance through the more general consensus optimisation framework, which does not encode the finer statistical structure behind the scenes. More precisely, we demonstrate that this structure can be leveraged to both: allow model complexity to be controlled implicitly through algorithmic parameters; and that the information held by agents can be similar owing the phenomena of statistical concentration.

In the heterogeneous case a setting motivated by hyperspectral unmixing is considered. Specifically, we consider simultaneously recovering a collection of sparse signals (associated to agents), that are related in a manner reflecting the network topology. In short, the differences in the underlying distributions are encoded through a total variation penalty reflecting the network. Our approach then yields sample complexity savings over group lasso style methods when the signals are sufficiently related.

Authors: Richards, D

• DOI: 10.5287/ora-konqbvgy5
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: Gradient Descent; Machine Learning; Implicit Regularisation; Statistical Learning Theory; Distributed Machine Learning
• Subjects: Mathematics; Statistics