CS Paper Radar

Beyond Aggregate Drift: Optimal Client-Specific Windows in Federated Learning

Yuriy Dorn, Dmitrii Vishovan, Kirill Novoselov, Ilya Kuruzov, Darina Dvinskikh, Alexander Gasnikov

cs.LG math.OC ·submitted 2026-10-11 11:34 UTC · v1
theory

Abstract

We study federated learning from continuously arriving data: each client samples from its own distribution, these distributions drift over time, and the server must track the minimizer of the clients' weighted average loss. Clients are not alike as they collect data at different rates, with different noise, and change at different speeds. The main question is how much history should each one keep? A single shared window must serve every client at once, and so makes a fast-changing client carry the sampling noise of a slow, nearly stationary one. We give each client a memory of its own, sized to that client's noise, arrival rate, and drift, and refresh it by restarted accelerated method that starts from a common point. The tracking error is then bounded by \[ R\left(\sum_m w_m^{3/2}\,σ_m\sqrt{γ_m/λ_m}\right)^{2/3}, \] for clients with weight $w_m$, noise $σ_m$, arrival rate $λ_m$, and drift rate $γ_m$ on a domain of diameter $R$. This is never worse than what any common window can achieve, and strictly better whenever noise and drift are spread unevenly across clients. A lower bound that puts different groups of clients on different drift clocks shows this quantity is the right one. The two bounds agree up to a constant whenever the clients occupy boundedly many refresh scales, and in general differ only by the sixth root of the number of scales. Experiments show the gain comes from the memory rather than from the solver: it persists across accelerated, stochastic-gradient, and one-step methods, and against a separately tuned common-memory baseline.

Closest papers

Nearest neighbours by meaning across the whole index.

Characterizing Client-Independent Stationary Bias for SCAFFOLD and FedAvg in Federated Learning

cs.LG math.ST ·2026-08-27 ·Yi-Ping Tang, Guan-Ju Peng
similarity 0.70
Abstract

Even when all clients optimize the same strongly convex objective, the global model parameters produced by constant-step federated learning may still have a stationary mean that differs from the minimizer. Does increasing the number of clients eliminate this bias, or can some components persist? Answering this question clarifies the limits of client averaging. To this end, we study two federated learning algorithms, \Scaf{} and matched \FedAvg{}, under full participation, a sufficiently smooth objective, and independent bounded additive gradient noise. Analyzing global stationary balance and within-round local fluctuations yields multidimensional expansions with a shared $γ/N$ term and explicit client-independent $γ^2$ coefficients, where $γ$ is the step size and $N$ is the client count. The \Scaf{} coefficient combines the ordinary local-update contribution found in \FedAvg{} with an additional persistent-control contribution. Although zero-sum controls cancel from the direct server increment, they change local second moments, which interact with third-order curvature to shift the stationary mean. For fixed dimension $d$ and local-step count $H$, a remainder of $O_{H,d}(γ^2/N+γ^3)$, uniform in $N$ for sufficiently small $γ$, identifies the second-order coefficients along arbitrary joint small-step, large-client limits after removing the shared leading term. Controlled experiments assess the predicted coefficients. In real-data analyses, finite-tail mean displacement can account for a substantial share of averaged-model parameter error, and a post-hoc comparison shows directional agreement with the derived curvature--noise structure.

0.27

Resilience Beyond Stationary Client Unavailability: Unlocking Efficient and Unbiased Federated Learning

cs.LG cs.DCmath.OC ·2026-09-04 ·Ming Xiang, Stratis Ioannidis, Edmund Yeh, Carlee Joe-Wong, Lili Su
similarity 0.69
Abstract · Journal of Machine Learning Research

Due to resource constraints or external and internal uncertainties, clients in real-world federated learning systems are often intermittently available edge devices. In highly dynamic environments, the parameter server lacks prior real-time knowledge of clients' availability, making it challenging to adapt traditional federated learning algorithms to be resilient to uncertainties in client availability. If not carefully addressed, complex client availability can introduce significant bias, potentially harming the performance of the trained model. Most prior work either fails to account for non-stationary client availability dynamics or demands significant memory and computational overhead. This paper aims to develop efficient federated learning algorithms that are provably resilient to heterogeneous and non-stationary stochastic client availability. We propose FedSWE, which admits novel algorithmic structures to (i) compensate for missed computations, (ii) stabilize and diffuse the global updates over rounds, and (iii) evenly mix the local updates through implicit gossiping, despite being agnostic to non-stationary dynamics. Compared with the standard FedAvg, FedSWE introduces light additional memory and computation overhead. We show that FedSWE converges to a stationary point of non-convex objectives while achieving the desired linear speedup property in certain special cases. We corroborate our analysis with numerical experiments over diversified client unavailability dynamics on real-world data sets.

0.19

CTP-FL: Common-Trajectory Gradient Prediction for Federated Learning

cs.LG cs.AI ·2026-09-28 ·Junkang Liu
similarity 0.68
Abstract

Communication-efficient federated optimization commonly spends several gradient evaluations between server updates. Existing local-update methods use this computation to advance an independent model on each client. Under heterogeneous data, however, these models evaluate gradients at different locations, making the aggregated update difficult to interpret as a gradient of the global objective. We study an alternative use of the same computation budget: \emph{evaluate the global objective along a shared, predicted path}. We propose Common-Trajectory Predictive Federated Learning (\texttt{CTP-FL}). At each round, all clients construct the same sequence of query points from the current global model and the previous aggregated direction, evaluate $K$ stochastic gradients along this sequence, and upload their average. The server then performs a single global update. Thus, \texttt{CTP-FL} uses $K$ mini-batch gradients per client and one model-sized vector in each communication direction, matching the per-round computation and communication of full-participation FedAvg-M. Shared query points make the aggregated direction an unbiased estimator of the average \emph{global} gradient along the predicted path. The remaining discrepancy from the gradient at the current model is controlled by the path length, without assuming bounded client-gradient dissimilarity or bounded gradients. For smooth non-convex objectives, we establish an $\mathcal{O}\!\left( \sqrt{LΔσ^2/(NKR)}+LΔ/R \right)$ average-stationarity bound under full participation. The analysis isolates a testable trade-off: extending the prediction path provides more forward-looking gradient information but increases its displacement bias.

0.18

Federated Continual Learning as a Distributed Drift-Plus-Penalty Control Problem

cs.LG ·2026-08-21 ·Nazreen Shah, Naveen Kumar Reddy Somireddy, Zubair Shaban, Ranjitha Prasad, B. N. Bharath
published similarity 0.67
Abstract · Accepted at 5th Conference on Lifelong Learning Agents, 2026

Federated Continual Learning (FCL) is fundamental to real-world distributed learning systems, requiring models to adapt to sequential, non-IID data across clients while mitigating catastrophic forgetting and client drift. Existing approaches formulate continual learning (CL) as a sequence of per-task optimization problems, applied locally at each client and coupled through aggregation, using heuristic mechanisms such as replay, regularization, or projection-based constraints. However, forgetting in FCL is inherently a long-term, distributed phenomenon, arising from the interaction of temporal task evolution and cross-client heterogeneity, which is not explicitly regulated. In this work, we cast FCL as a stochastic control problem and propose Federated Queue-regulated Continual Learning (FedQCL), a framework based on Lyapunov drift-plus-penalty (DPP) optimization. FedQCL introduces virtual queues to track the accumulation of forgetting across tasks and clients, enabling explicit control of the stability-plasticity trade-off. By optimizing a DPP objective, the method jointly improves current-task performance while the queue-based formulation provides an interpretable and tunable mechanism to balance adaptation and retention through a single parameter, without requiring gradient projection or additional communication overhead. Empirical evaluations on standard benchmarks, including Split-CIFAR-10, Split-CIFAR-100, and Split-TinyImageNet, demonstrate that FedQCL outperforms state-of-the-art baselines with respect to accuracy while significantly reducing forgetting under heterogeneous data distributions.

0.21

Personalized Rollout Allocation for Federated LQR Policy Optimization under Heterogeneous Process Noise

cs.MA cs.LG ·2026-10-31 ·Mohammadreza Rostami, Shahriar Talebi, Solmaz S. Kia
similarity 0.66
Abstract

We study federated model-free learning of a common linear quadratic regulator (LQR) gain under a limited uplink communication budget, with clients that share dynamics and costs but experience different process-noise levels. Conventionally, clients transmit gradient matrices whose dimension equals the number of controller parameters. Exploiting the structure of two-point zeroth-order estimates, we consider an implementation in which clients transmit only one scalar cost-difference coefficient per rollout pair, while the server regenerates the associated perturbation directions from shared seeds. Communication thus scales with the number of rollout pairs rather than the controller dimension, turning the uplink budget into a rollout budget. Because noise heterogeneity produces gradient estimates of widely differing variance and every client carries equal weight in the fleet objective, uniform rollout allocation allows noisy clients to dominate the aggregated update and increases the probability of destabilizing updates. We propose a rollout-allocation scheme that assigns rollout pairs in proportion to the standard deviation of each client's estimates and show that it minimizes the variance of the aggregated update. The scheme is implemented exactly through a greedy integer allocation rule whose weights are estimated from the communicated scalars. We further prove that a single allocation factor quantifies its improvement over uniform allocation in a one-round instability bound, the certified step size, and the error floor of a joint stability and convergence guarantee. Simulations show that, under the same communication budget, personalized allocation reduces the one-step instability rate from $37\%$ to $0.3\%$.

0.14

FedeRage: Provably Convergent Agnostic Federated Learning under General Client Drift

cs.LG cs.DCeess.SPeess.SY ·2026-09-17 ·Herlock Rahimi, Dionysis Kalogerias
theory similarity 0.66
Abstract

Federated learning (FL) enables collaborative model training without sharing raw data, but its performance degrades under non-IID data and stochastic client participation. Remedies built on classical Federated Averaging (FedAvg) typically presuppose that client participation probabilities are known to the server, which is rarely the case in deployed systems. We first discuss and then characterize the optimization problem that \emph{distributionally agnostic} FedAvg actually solves when participation is entirely unknown, possibly highly skewed, and of variable size across rounds: uniform aggregation is shown to minimize a well-defined stochastic objective, weighted by the participation-induced marginal, at a standard $\mathcal{O}(1/\sqrt{T})$ rate for convex and possibly nonsmooth losses. Building on this characterization, we propose \emph{Federated Risk-Averse Averaging} (\textsc{FedeRage}), a risk-averse extension of FedAvg that embeds the \emph{Conditional Value-at-Risk} (CVaR) into the local objective within a natural distributionally robust optimization (DRO) framework. \textsc{FedeRage} implicitly upweights high-loss and infrequently participating clients while adding only a \emph{single scalar per-client}, and admits an $\mathcal{O}(κ/\sqrt{T})$ rate in which the factor $κ$ is the upper bound on the ``price" of risk aversion. In contrast with aggregation-alignment schemes based on optimal transport, which require the availability distribution as an input, \textsc{FedeRage} remains agnostic to it. Several experiments on three heterogeneous benchmarks indicate consistent improvements over state-of-the-art methods in accuracy, fairness, and convergence speed.

0.22

Joint Optimization for Federated Learning and Transmission over Unreliable Wireless Networks with Heterogeneous Data

cs.DC cs.LG ·2026-09-13 ·Changheng Wang, Xianchao Zhang, Zhiqing Wei, Lingzhu Zhao, Zhongming Yang +1 more
theory similarity 0.66
Abstract

In wireless federated learning (FL), data heterogeneity and multiple local updates induce client drift, degrading model convergence. It is further affected by unreliable wireless links, as transmission errors may invalidate model updates. To address these challenges, we propose a federated random walk averaging (FedRW) framework, which is a variant of federated averaging (FedAvg) that mitigates data heterogeneity by updating models along random walk (RW) paths and aggregating them at the server. Model parameters are transmitted in packets with retransmission support to improve training quality by mitigating wireless errors along RW paths. Meanwhile, wireless transmission delays hinder the exploration of FedRW. To this end, we formulate a joint optimization problem that integrates learning, RW path selection, and transmission parameter tuning, aiming to minimize the training loss under delay constraints. By deriving an upper bound on the expected convergence of FedRW over unreliable wireless networks, we reduce the problem to a general form agnostic to task type and model architecture. A distributed solution is then proposed, in which the server or clients optimize packet size and maximum number of retransmissions locally, and efficiently select reliable and expandable next-hop nodes via a resilience-aware beam search with dynamic pruning. Simulation results show that FedRW achieves 2.26%-9% higher accuracy than state-of-the-art baselines under high data heterogeneity. Furthermore, the jointly optimized FedRW yields at least 2.78% higher accuracy and faster convergence compared to baselines.

0.09

Breaking the $\sqrt{d}$ Communication Barrier in Federated Sampling with Adaptive Hamiltonian Monte Carlo

cs.LG stat.ML ·2026-11-09 ·Jiajun Liang, Linxuan Wang, Guang Lin, Qifan Song
theorycode/data similarity 0.64
Abstract

This work proposes the Adaptive Federated Hamiltonian Monte Carlo (AFHMC) for Bayesian federated learning (FL) tasks. The prior work on HMC applications for FL achieves $O(\sqrt{d}/ε)$ communication cost under log-convex distributions, already demonstrating its advantage over the Langevin dynamic-based counterpart. Based on a refined analysis, this paper further reveals the benefit of HMC for the FL regime by incorporating a control mechanism for local node shifts. We prove that AFHMC at most requires $O(\{d/ε^2\}^{1/3})$ communication cost up to a logarithmic term, which is significantly better than the existing results. Moreover, the proposed method adapts to client heterogeneity. Under low-heterogeneity settings (i.e., the target sampling precision $ε^2$ is higher than the heterogeneity level), the communication rate of AFHMC can be as good as $O(\log(d/ε^2))$, resembling the communication costs for FL optimization tools. To the best of our knowledge, this provides the first logarithmic communication complexity result for federated sampling, even though it requires low heterogeneity. Numerically, we also justify AFHMC's advantage under the low-heterogeneity regime. Our code is available at https://github.com/laaaarrywang/Adaptive-Federated-HMC

0.47