FedSplit: An algorithmic framework for fast federated optimization

Federated learning is a rapidly evolving application of distributed optimization for estimation and learning problems in large-scale networks of remote clients [13]. These systems present new challenges, as they are characterized by heterogeneity in computational resources and data across the network, unreliable communication, massive scale, and privacy constraints [16]. A typical application is for developers of cell phones and cellular applications to model the usage of software and devices across millions or even billions of users. Distributed optimization has a rich history and extensive literature (e.g., see the sources [2, 5, 8, 31, 15, 24] and references therein), and federated learning has led to a flurry of interest in the area. A number of different procedures have been proposed for federated learning and related problems, using methods based on stochastic gradient methods or proximal procedures. Notably, McMahan et al. [18] introduced the FedSGD and FedAvg algorithms, which both adapt the classical stochastic gradient method to the federated setting, considering the possibility that clients may fail and may only be subsampled on each round of computation. Another recent proposal has been to use regularized local problems to mitigate possible issues that arise with device heterogeneity and failures [17]. These authors propose the FedProx procedure, an algorithm that applied averaged proximal updates to solve federated minimization problems. Currently, the convergence theory and correctness of these methods is currently lacking, and practitioners have documented failures of convergence in certain settings (e.g., see Figure 3 and related discussion in the work [18]).