Continuous-Time Analysis of Federated Averaging

Tom Overman, Diego Klabjan · 2025

Read Continuous-Time Analysis of Federated Averaging by Tom Overman, Diego Klabjan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-18870.txt.

Introduction

Tom Overman and Diego Klabjan re-examine the workhorse algorithm of federated learning as a smooth, continuous process, in this 2025 paper. Federated averaging trains a shared model across many devices, each keeping its data at home: phones or hospitals compute updates locally, and a server averages them. Its convergence has been proven step by discrete step.

The authors instead let the shared weights flow under a stochastic differential equation, the continuous mathematics of noisy motion. From that vantage they prove convergence for broad families of loss functions, in some cases wider than the step-by-step theory allows. They also give conditions under which the server's updates look statistically like simple bell-curve noise. The continuous view exposes new facts about how the averaged model generalizes to fresh data, a perspective discrete analysis had not produced.

Catalog record

CREATORTom Overman, Diego Klabjan
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE76 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-18870

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Continuous-Time Analysis of Federated Averaging Tom Overman, Diego Klabjan Abstract Federated averaging (FedAvg) is a popular algorithm for horizontal federated learning (FL), where samples are gathered across different clients and are not shared with each other or a central server. Extensive convergence analysis of FedAvg exists for the discrete iteration setting, guaranteeing convergence for a range of loss functions and varying levels of data heterogeneity. We extend this analysis to the continuous-time setting where the global weights evolve according to a multivariate stochastic differential equation (SDE), which is the first time FedAvg has been studied from the continuous-time perspective. We use techniques from stochastic processes to establish convergence guarantees under different loss functions, some of which are more general than existing work in the discrete setting. We also provide conditions for which FedAvg updates to the server weights can be approximated as normal random variables. Finally, we use the continuous-time formulation to reveal generalization properties of FedAvg. 1 Introduction Federated learning (FL) is a popular privacy-preserving machine learning framework allowing a server to train a central model without accessing data locked on clients. In FL, each client holds a subset of the overall data and is not willing to share this data with the server; however, the clients can send model weights to the server. In horizontal FL studied herein, each client holds a subset of samples but each client has access to all features. A popular algorithm for horizontal FL is FedAvg ( McMahan et al., 2017 ) , which is the focus in this work. FedAvg works by averaging the model weights of all clients periodically. Specifically, each client trains a local model for a specific number of iterations using only the data on the client. Typically, this local training is done using batch stochastic gradient descent. Then, the clients send their local model weights to the server, where the server averages the model weights and sends them back to the clients. Understanding the conditions for FedAvg to converge and what factors influence convergence and generalization is of great interest to federated learning practitioners and has been the focus of significant work ( Li et al., 2019 ; Karimireddy et al., 2020 ) . A major challenge in FL is dealing with non-IID data across clients (heterogeneous setting). The local updates on each client significantly diverge due to the different data distributions they are trained on, resulting in slower convergence. Many improvements to FedAvg exist, such as SCAFFOLD ( Karimireddy et al., 2020 ) , which reduces the impact of the data drift during local training and speeds up training in heterogeneous settings, and RADFed ( Xue et al., 2022 ) , which handles non-IID data by delaying aggregation with specialized redistribution rounds. Despite the abundance of new algorithms being introduced to tackle new challenges in FL, FedAvg remains an important algorithm that is the foundation of most new approaches. The continuous-time perspective of stochastic gradient descent (SGD) has provided a framework for developing more compact proofs of convergence than the discrete process ( Orvieto & Lucchi, 2019 ) and has allowed the study of generalization properties. Specifically, it has been shown through the continuous-time representation of SGD how the learning rate and batch size influence the width of local minima converged to during SGD ( Jastrzebski et al., 2018 ) . This local minima width impacts the model’s generalization ability to unseen data ( Keskar et al., 2017 ) . The continuous-time representation also allows for studying first exit times of SGD from local minima and how this depends on the width of the local minima ( Nguyen et al., 2019 ) . Our work is focused on developing a continuous-time representation of FedAvg. It is our hope that this formulation provides a framework for new interesting analyses, just as the continuous-time representation did for SGD. We focus on a theoretical analysis of FedAvg. We formulate a continuous-time representation of FedAvg in the form of a stochastic differential equation (SDE) and use this formulation to prove convergence properties. The convergence proofs are relatively compact and the proof framework may be extended to other FL algorithms. We show convergence of FedAvg to a stationary point for general, non-convex loss functions and demonstrate that it is likely not sufficient for only the server learning rate to decay; it is necessary that the client-side learning rate must decay at certain rates. We show convergence of FedAvg to the global minimum for weakly quasi-convex loss functions. To the best of our knowledge, weak quasi-convexity has not been studied for FedAvg up to this point. Next, we show that the server weight updates in FedAvg can be approximated as normal random variables under certain assumptions, even for heterogeneous data with extensive local updates before averaging. This is a surprising result and can assist in further analyses of FL algorithms. Finally, we use our continuous-time approach with a quadratic single variate form of each clients’ loss landscape to determine how different FedAvg hyperparameters affect the trade-off between minimizing expected loss and ability to escape poorly-generalizing local minima. Our contributions are as follows. 1. We are the first to formulate an SDE that models the evolution of server weights in continuous time during FedAvg. Existing work ( Zhang et al., 2023 ) for modeling distributed learning algorithms uses ordinary differential equations without stochasticity. 2. Using the continuous-time formulation, we devise convergence proofs of FedAvg in deterministic and stochastic cases. We show convergence under a certain normality assumption to a stationary point for non-convex loss functions and convergence to a global minimum for weakly quasi-convex functions. To the best of our knowledge, no other works in either deterministic or stochastic regimes have shown global convergence of FedAvg for weakly quasi-convex loss functions, which are more general than convex functions and allow for locally concave regions. The new proof framework we provide allows for relatively compact proofs of FedAvg and can inspire compact proofs of other FL algorithms. 3. We show that the server weight updates converge in distribution to a normal distribution as the number of clients grow, even in non-IID data settings with many local client iterations without server averaging. This justifies the normality assumption in the convergence results. We demonstrate this through the Lyapunov central limit theorem. 4. Using a quadratic single variate loss function for each client’s loss landscape, we uncover dynamics of how various hyperparameters in FedAvg affect the trade-off between generalization and the optimality gap of the expected loss in the continuous-time setting. In Section 2 , we discuss related work on the analysis of FedAvg in the discrete case and continuous-time analysis of SGD. In Section 3 , we formulate the SDE that models the evolution of server weights during FedAvg. In Section 4 , we provide convergence guarantees of FedAvg for non-convex and weakly quasi-convex loss functions using the SDE formulation. In Section 5 , we provide conditions for which the server weight updates can be approximated as normally distributed; this is a key assumption for the SDE formulation to be an Itô process. In Section 6 , we analyze the case where each client’s local loss function is a quadratic; this allows us to examine how various

Read the complete text