Ming Xiang

Federated learning is a popular distributed learning approach for training a machine learning model without disclosing raw data. It consists of a parameter server and a possibly large collection of clients (e.g., in cross-device federated learning) that may operate in congested and changing environments. In this paper, we study federated learning in the presence of stochastic and dynamic communication failures wherein the uplink between the parameter server and client i is on with unknown probability p_i^t in round t. Furthermore, we allow the dynamics of p_i^t to be arbitrary. We first demonstrate that when the p_i^t’s vary across clients, the most widely adopted federated learning algorithm, Federated Average (FedAvg), experiences significant bias. To address this observation, we propose Federated Postponed Broadcast (FedPBC), a simple variant of FedAvg. It differs from FedAvg in that the parameter server postpones broadcasting the global model to the clients with active uplinks till the end of each training round. Despite uplink failures, we show that FedPBC converges to a stationary point of the original non-convex objective. On the technical front, postponing the global model broadcasts enables implicit gossiping among the clients with active links in round t. In spite of the time-varying nature of p_i^t, we can bound the perturbation of the global model dynamics using techniques to control gossip-type information mixing errors. Extensive experiments have been conducted on real-world datasets over diversified unreliable uplink patterns to corroborate our analysis.

Addressing intermittent client availability is critical for the real-world deployment of federated learning algorithms. Most prior work either overlooks the potential non-stationarity in the dynamics of client unavailability or requires substantial memory/computation overhead. We study federated learning in the presence of heterogeneous and non-stationary client availability, which may occur when the deployment environments are uncertain or the clients are mobile. The impacts of the heterogeneity and non-stationarity in client unavailability can be significant, as we illustrate using FedAvg, the most widely adopted federated learning algorithm. We propose FedAPM, which includes novel algorithmic structures that (i) compensate for missed computations due to unavailability with only O(1) additional memory and computation with respect to standard FedAvg, and (ii) evenly diffuse local updates within the federated learning system through implicit gossiping, despite being agnostic to non-stationary dynamics. We show that FedAPM converges to a stationary point of even non-convex objectives while achieving the desired linear speedup property. We corroborate our analysis with numerical experiments over diversified client unavailability dynamics on real-world data sets.

Federated learning (FL) is a decentralized machine learning framework wherein a parameter server (PS) and a collection of clients collaboratively trains a model. Communication bandwidth is a scarce resource. In each round, the PS aggregates the updates from a subset of clients only. In this paper, we consider non-uniform and time-varying communication between the PS and the clients. Specifically, in each round t, the link between the PS and client i is active with probability p_i^t, which is unknown to both the PS and the clients. This arises when the channel conditions are heterogeneous across clients and are changing over time. We show that when the p_i^t’s are not uniform (i.e., not identical over i), Federated Average (FedAvg) – the most widely adopted FL algorithm – fails to minimize the global objective. Observing this, we propose Federated Postponed Broadcast (FedPBC) which is a simple variant of FedAvg; it differs from FedAvg in that the PS postpones broadcasting the global model till the end of each round. FedPBC converges to a stationary point. Moreover, the staleness is mild and there is no significant slowdown. Both theoretical analysis and numerical results are provided. On the technical front, postponing the global model broadcasts enables implicit gossiping among the clients with active links at round t. Consequently, we are able to control the perturbation of the global model dynamics caused by non-uniform and time-varying p_i^t via the techniques of controlling gossip-type information mixing errors.