On the Convergence of Federated Optimization in Heterogeneous Networks

Modern networks of remote devices, such as mobile phones, wearable devices, and autonomous vehicles, generate massive amounts of data each day. Federated learning involves training statistical models directly on these devices, and introduces novel statistical and systems challenges that require a fundamental departure from standard methods designed for distributed optimization in data center environments. From a statistical perspective, each device collects data in a non-identical and heterogeneous fashion, and the number of data points on each device may also vary significantly. Federated optimization methods must therefore be designed in a robust fashion in order to provably converge when dealing with heterogeneous statistical data. From a systems perspective, the size of the network and high cost of communication impose two additional constraints on federated optimization methods: (i) limited network participation, and (ii) high communication costs. In terms of participation, at each communication round, proposed methods should only require a small number of devices to be active. As most devices have only short windows of availability, communicating with the entire network at once can be prohibitively expensive. In terms of communication, proposed methods should allow for Preprint.