Distributed and Decentralised Learning: Generalisation and Order-Optimal Gossip

Abstract:

In distributed machine learning data is stored and processed in multiple locations by different agents. Each agent is represented by a node in a graph, and communication is allowed between neighbours. In the decentralised setting typical of peer-to-peer networks, there is no central authority that can communicate with all the nodes. Agents cooperate by iteratively exchanging information with their peers to learn models that can perform better on new, unseen data.

In this talk, we present the first results on the generalisation capabilities of distributed stochastic gradient descent methods. Using algorithmic stability, we derive upper bounds for the test error and provide a principled approach to tune the learning rate as a function of the graph topology. We also present a new Gossip protocol for the aggregation step in distributed methods that can yield order-optimal communication and computational complexity. Based on non-reversible Markov chains, our protocol is local and does not require global routing, hence improving on existing methods. (Joint work with Dominic Richards)