The population model is a standard way to represent large-scale decentralized distributed systems, in which agents with limited computational power interact in randomly chosen pairs, in order to collectively solve global computational tasks.
In contrast with synchronous gossip models, nodes are anonymous, lack a common notion of time, and have no control over their scheduling.
In this talk, I will describe recent work examining whether large-scale distributed optimization can be performed in this extremely restrictive setting.

I will introduce and analyze natural decentralized variants of the classical stochastic gradient descent (SGD) procedure, in which every node maintains a local estimate of the optimal set of parameters, and is able to compute stochastic gradients with respect to this parameter.
Every pair-wise node interaction performs a stochastic gradient step at each agent, followed by averaging of the two models.
I will show that, under standard assumptions, SGD can converge even in this extremely loose, decentralized setting. Moreover, surprisingly, the algorithm can achieve linear speedup in the number of nodes n.
In addition, I will show experimental results showing that PopSGD can achieve convergence and speedup for large-scale distributed learning tasks in a supercomputing environment.