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

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

math.OCOct 11, 2026

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

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

Organizations: Lomonosov Moscow State University · Innopolis University · Moscow Independent Research Institute of Artificial Intelligence · Higher School of Economics ·

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.

Figures & tables

Figure 1: Temperature stations: time-averaged gap over twelve evaluation seeds with

95\%

intervals (Appendix J.1 ). “One common window” has the bound-optimal length; client-specific windows follow Corollary 4.2 without tuning; per-station tuning is an oracle. December has

g=0.32

, July

g=0.066

; subtitles give paired differences.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Meaning	Where
$M$ , $m$ , $w_{m}$	number of clients, client index, public weights ( $\sum_{m}w_{m}=1$ )	Sec. 3
$\mathcal{X}$ , $d$ , $D$ , $\Pi_{\mathcal{X}}$	compact convex domain in $\mathbb{R}^{d}$ , its diameter, Euclidean projection	Sec. 3
$\ell(x;\xi)$ , $\mathcal{D}_{m}^{t}$	public sample loss; law of a sample of client $m$ generated at time $t$	Sec. 3
$f_{m}^{t}$ , $F^{t}$	population objective of client $m$ and weighted objective at time $t$	Sec. 3
$L$ , $G$	smoothness constant of $F^{t}$ ; public bound on $\\|\nabla F^{t}\\|$	Sec. 3
$\lambda_{m}$ , $\lambda_{\min}$ , $N_{m}(t)$	arrival rate, smallest rate, arrival count of client $m$	Sec. 3

Appendix

Table 1: Symbols of the model, the algorithm, and the upper bounds.

Symbol	Meaning	Where
$\mathsf{N}$ , $\mathfrak{P}_{T}(\mathsf{N};\gamma)$ , $\mathfrak{A}_{T}(\mathsf{N})$	schedule, admissible instances, causal rules	Sec. 5
$\mathcal{X}_{D}$ , $\mathcal{R}_{T}(\mathsf{A},\mathsf{P}\mid\mathsf{N})$ , $\mathcal{R}_{T}^{\star}(\gamma)$	segment $[-D/2,D/2]\times\{0\}^{d-1}$ , risk of rule $\mathsf{A}$ on instance $\mathsf{P}$ , minimax risk	Sec. 5
$\mathcal{J}_{j}$ , $J$ , $q_{m}$ , $Q_{j}$	client groups (dyadic bins), their number, memory scale $\sqrt{b_{m}/a_{m}}$ , bin information rate	Cor. 5.1
$T_{j}$ , $A_{m}$ , $C_{j}$ , $\mathcal{S}_{j}$ , $c_{\rm het}$	block length and amplitudes of group $j$ , $\sum_{m\in\mathcal{J}_{j}}w_{m}A_{m}$ , bin mass $\sum_{m\in\mathcal{J}_{j}}\sqrt{a_{m}b_{m}}$ , constant	Thm. B.2
$\Lambda$ , $\Lambda_{j}(t)$ , $\varsigma_{j,k}$ , $\varsigma_{j}(t)$	triangular profile, its block version, block signs	App. E
$\zeta_{j}(t)$ , $\Theta(t)$ , $\mathcal{F}_{t}$ , $\bar{\varsigma}_{j}(t)$	$C_{j}\Lambda_{j}(t)$ , population coefficient, pooled transcript, posterior mean of the sign	App. E

Appendix

Table 2: Symbols of the lower bounds, the selection procedure, and the periodic streams.

Figure 2: Complete upper guarantees divided by

D\mathcal{H}_{\gamma}

. Left: Corollary 4.2 on the family ( 48 ), including its conservative count-floor surcharge even though the floors are inactive; the dashed line is the no-data midpoint guarantee

GD/2

, which is smaller at all shown scales. Right: Theorem 4.1 at the selected heterogeneous windows of the three original synthetic cases, where no separate floor surcharge arises; the stationary case has a substantial finite-horizon transient. These are evaluations of inequalities, not observed errors, and not evidence that the upper and lower numerical constants are close.

Specialty	Patients seen	Surge cohort	Shape of the drift	Visits per week (urban / rural)
Pediatrics	age below 18	recent acute care	ILINet, youngest age group	60 / 25
Emergency	emergency encounters	recent acute care	COVID-19 hospital admissions	120 / 40
Primary care	adults at wellness, ambulatory and outpatient visits	recent acute care	weighted ILINet activity	80 / 30
Cardiology	age 40 or older with hypertension, heart failure or coronary disease	recent acute care	slow ageing trend with winter peaks	40 / 15
Endocrinology	diabetes or prediabetes	none	stationary	8 / 3
Oncology	active cancer diagnosis	none	stationary	3 / 1.5

Appendix

Table 3: The twelve clinics. The surge cohort is defined by a variable the model does not observe. Urban and rural sites follow surveillance curves from different regions. All clinics have weight

w_{m}=1/12

Figure 3: The network. (a) Share of the surge cohort in each drifting clinic; solid lines are urban sites, dashed lines rural ones. (b) Visits per week. (c) Drift bound

\gamma_{m}

along the optimal trajectory; the four specialized clinics are stationary. Drift speeds span two orders of magnitude and are not ordered like the visit rates, which is what makes a single memory length a compromise.

Figure 4: Time-averaged gap after start-up, mean over twenty evaluation streams with 95% intervals. Left: exact minimization of the buffered risk. Right: Algorithm 1 with

K=8

. The label in each baseline bar is the change obtained by client-specific windows relative to that baseline.

Figure 5: Memory lengths selected for each clinic. Hatched bars mean that the whole history is kept. Diamonds mark the per-clinic oracle, dashes the minimum length

2K/\lambda_{m}

needed to form

K

batches.

Figure 6: Current gap over time under exact minimization, after start-up; two-week rolling mean over the evaluation streams. The lower panel repeats the surge shares of the urban clinics. The full history and the one common window coincide because the common window selects the whole history.

Figure 7: Contribution of each clinic to the gap after start-up under exact minimization, on a symmetric logarithmic scale. Negative values mean that the clinic fits better than at the joint optimum.

Reference and result	Assumptions and criterion	Clock and decisive distinction
Marfoq et al. (2023) , Thms. 4.1–4.4	Fixed local laws; bounded convex smooth sample losses, bounded domain, a stated pseudo-dimension condition; terminal population excess risk.	Client arrivals and finite caches; the optimization theorem uses full participation and full batches. Our populations drift under separate clientwise bounds.
Ganguly and Aggarwal (2024) , Master-FL	Bounded convex Lipschitz losses and near-stationary base guarantees; dynamic regret for changing empirical losses.	Federated rounds with drift detection and restarts. Its target uses current data-size weights; ours fixes population weights and models noisy samples arriving over time.
Tyurin (2025) , Thms. H.11–H.12	Fixed convex smooth objective; unbiased local gradients with bounded variance; terminal expected objective gap.	Heterogeneous gradient-computation times. Our clocks govern reusable data from changing populations.
Cutler et al. (2023) , Thm. 8	Strong convexity; fixed convex regularizer; second-moment drift/noise and decorrelation conditions; current gap of an averaged iterate.	One current stochastic gradient per iteration. We use a merely convex target and separate client drifts and arrival rates.
Mazzetto and Upfal (2023b) , Thms. 4.2, 4.9	Independent finite-support observations; regular endpoint drift for terminal TV risk, bounded successive drift for long-run average TV risk.	Observation index. Our criterion is convex suboptimality of a weighted client aggregate, with unequal group clocks.
This work, Thms. 4.1 , B.2	Compact convex domain; public clientwise gradient-drift bounds; expected time-average current-objective gap.	Exogenous arrivals and paid synchronization; reset solves and sample splitting permit reuse. Local computation is uncharged.

Appendix

Table 5: Selected theorem assumptions and observation clocks. TV denotes total variation. Each guarantee retains the conditions of its cited theorem.

Federated Learning

Federated learning trains shared models across data holders without requiring them to pool their raw data.

See all 906 papers

Adaptive Data Admission and Retention for Streaming Federated Learning
Jul 27, 2026Zhuoyi Zhao, Ben LiangAdaptive Sampling Federated Learning
University of Toronto · Toronto, ON, Canada
FedeRage: Provably Convergent Agnostic Federated Learning under General Client Drift
Sep 17, 2026Herlock Rahimi, Dionysis KalogeriasFederated Learning Federated Learning Aggregation
Latent Information Sharing for Accelerating Federated Learning
Oct 1, 2026Seungjun Lee, Ensieh Khazaei, Dimitrios Hatzinakos +2Federated Learning Aggregation Federated Learning
Inha University · University of Toronto · University of Birmingham

Jul 27, 2026J/K move · Enter open · S save

Adaptive Data Admission and Retention for Streaming Federated Learning

Zhuoyi Zhao, Ben Liang

University of Toronto · Toronto, ON, Canada

Adaptive Sampling Federated Learning Streaming Algorithms

Open paper AskPDF arXiv

We study streaming federated learning with limited client memory, where newly generated training data incur time-varying sampling costs and must be selectively admitted and retained over time. We consider a joint server-side admission and client-side memory-management framework with the objective of minimizing the cumulative excess population risk under a sampling-cost budget and buffer constraints. We first derive a learning-error bound that explicitly captures the effects of instantaneous training sample size, distinct-sample growth, and reuse imbalance through a characterization of the effective sample size. Through a surrogate penalty obtained from this bound, we develop an Active-Constraint Drift-Plus-Penalty (ACDPP) policy that combines a structured client-side

K

-step retention rule with a server-side online admission rule and a time-varying rectangular admission region. We further present a sequence of comparison arguments, via an auxiliary constant-admission policy, that connects the ACDPP learning bound to a costless oracle benchmark. This yields explicit guarantees in terms of sublinear regret and sampling-cost violation, while the buffer-occupancy violation is controlled through offline selection of the retention horizon. Experiments on multiple datasets demonstrate that the proposed policy remains close to the oracle benchmark while satisfying the sampling-cost and buffer constraints.

Abstract

Federated Learning

Explore similar work

Adaptive Data Admission and Retention for Streaming Federated Learning

FedeRage: Provably Convergent Agnostic Federated Learning under General Client Drift

Latent Information Sharing for Accelerating Federated Learning