Beyond Aggregate Drift: Optimal Client-Specific Windows in Federated Learning
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(∑m wm3/2 σm√(γm/λm))2/3, for clients with weight wm, 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.
Related
- Optimal Rates for Federated Variational Inequalities under different relaxations of bounded variance assumption
- Learning Behavioral Parameters of Network Equilibrium Models from Aggregate Mobility Data
- Progressive-Resolution Secure Aggregation for Federated Learning
- Personalized Federated Learning through Global Knowledge Distillation and Local Head Adaptation
- Geographically Regularized AUC-Maximizing Personalized Federated Learning
BibTeX
@misc{dorn2026beyond,
title = {{Beyond Aggregate Drift: Optimal Client-Specific Windows in Federated Learning}},
author = {Yuriy Dorn and Dmitrii Vishovan and Kirill Novoselov and Ilya Kuruzov and Darina Dvinskikh and Alexander Gasnikov},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.15543},
eprint = {2610.15543},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.15543},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Beyond Aggregate Drift: Optimal Client-Specific Windows in Federated Learning
AU - Yuriy Dorn
AU - Dmitrii Vishovan
AU - Kirill Novoselov
AU - Ilya Kuruzov
AU - Darina Dvinskikh
AU - Alexander Gasnikov
PY - 2026
DA - 2026/10/11
PB - arXiv
DO - 10.48550/arxiv.2610.15543
UR - https://arxiv.org/abs/2610.15543
AB - 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(∑_m w_m^3/2 σ_m√(γ_m/λ_m))^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.
ER -