acceptodds
Under review as a conference paper at ICLR 2027

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\left(\sum_m w_m^3/2 \sigma_m\gamma_m/\lambda_m\right)^2/3, \] for clients with weight , noise , arrival rate , and drift rate on a domain of diameter . 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.

Primary area:
optimization
Keywords:
federated learning, non-stationary optimization, distribution drift

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_pXKVOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper theoretically investigates the benefits of assigning client-specific memory window sizes, rather than using a shared window size across all clients, in federated learning with continuously arriving data. Specifically, the authors propose a client-specific data refresh with reset stochastic solve algorithm. They first establish an upper bound on the performance gain over a common memory window and then derive a minimax lower bound that matches the upper bound up to a constant factor. Furthermore, by comparing the risks of the two approaches within a specified estimator class, they demonstrate that the risk ratio can be unbounded. When drift bounds are unavailable, the authors address this issue through validation samples and expert aggregation. Experiments in two settings, involving temperature stations and clinics, show that client-specific memory windows outperform a common memory window, although the performance gains diminish as drift heterogeneity decreases.

Critical strengths
  1. Interesting problem formulation and theoretical analysis. The scenario in which clients with different drift rates maintain client-specific memory window sizes is interesting and well-formalized theoretically. The proposed method addresses the issue of reusing retained samples through a reset accelerated solve procedure and disjoint batches.
  2. Tight theoretical bounds. The paper establishes not only an upper bound but also a minimax lower bound that matches the upper bound up to a constant factor, providing a tight characterization of the theoretical guarantees.
  3. Additional theoretical and methodological support. The paper further supports the proposed approach by analyzing the actual risk ratio within a specified estimator class and introducing an expert aggregation strategy for settings where drift bounds are unknown.
Critical weaknesses
  1. Limited empirical evidence. Although client-specific memory windows appear to offer performance improvements over a common memory window, the results of the recorded-order experiment on temperature stations and the comparison with the data-floored common-window baseline in the clinic experiments raise questions about the robustness and significance of these gains.
  2. Limited characterization of client drift. It is unclear whether the bound on the client’s population gradient in Eq. (2) is sufficient to adequately characterize client drift, particularly in settings with more complex temporal patterns, such as the seasonal drift observed in the clinic experiments.
  3. Unrealistic initialization assumption. The theoretical analysis assumes that each optimization problem is initialized from a fixed point. This assumption differs from typical continual federated learning settings, where optimization proceeds from previously learned models as new data arrive, potentially limiting the applicability of the theoretical results to practical scenarios.
Questions for authors
  1. Practical implications of the theoretical analysis. While the proposed method appears theoretically advantageous over using a common memory window, the experimental results suggest that these benefits may be limited in more realistic settings.
  2. Characterization of client drift. Different types of client drift, such as seasonal or periodic drift, may require different strategies. However, the current drift bound does not appear to account for such temporal patterns. Could this limitation reduce the practical effectiveness of the proposed method?
  3. Discrepancy from standard federated learning settings. Several assumptions in the proposed framework appear to differ substantially from typical continual federated learning settings, including initialization from a fixed point for each optimization problem, communication with all clients at every refresh, and the ability to directly transmit data to the server. What motivates these assumptions, and to what extent can the proposed method be applied when these assumptions do not hold?
3 comments

pXKV , thank you for review!

Limited empirical evidence. Although client-specific memory windows appear to offer performance improvements over a common memory window, the results of the recorded-order experiment on temperature stations and the comparison with the data-floored common-window baseline in the clinic experiments raise questions about the robustness and significance of these gains.

We added experiments that choose windows from earlier observations and vary the minimum durations and timing of drift (Appendix I.6, Table 4). With the same drift timing and minimum window durations corresponding to 16 records, client-specific windows reduce the mean gap by 7.39% relative to the common rule. Client-specific windows still improve on the common rule after the stationary clinics receive identical buffers. Other settings favor the common rule or have a difference whose interval includes zero. Appendix O adds tests using only earlier weather observations and clinic outcomes available after 90 days. The December weather interval excludes zero, the July interval includes zero, and the common rule has the lower mean gap in the regenerated clinic study.

Practical implications of the theoretical analysis. While the proposed method appears theoretically advantageous over using a common memory window, the experimental results suggest that these benefits may be limited in more realistic settings.

Section 8 now explains when a common window with a minimum duration for each client is a simpler choice. Selecting windows from earlier observations gives nearly identical windows for the two methods in the outbreak and seasonal tests. Varying the minimum durations and drift timing produces both improvements and cases where client-specific windows perform worse. The abstract limits the empirical claim to the tested settings.

Limited characterization of client drift. It is unclear whether the bound on the client’s population gradient in Eq. (2) is sufficient to adequately characterize client drift, particularly in settings with more complex temporal patterns, such as the seasonal drift observed in the clinic experiments.

We added a discussion in Section 8 and an example with sinusoidal drift in Appendix M.3. Smooth periodic changes can satisfy Eq. (2), but the bound limits only how quickly the gradient changes. It does not use the timing or repetition of a seasonal cycle. Appendix I.6 adds four recurring clinic patterns with different cycle lengths and an additional oscillation.

Characterization of client drift. Different types of client drift, such as seasonal or periodic drift, may require different strategies. However, the current drift bound does not appear to account for such temporal patterns. Could this limitation reduce the practical effectiveness of the proposed method?

Section 8 now explains that the drift bound does not take advantage of recurrence and recommends trying long windows and full history. Appendix I.8 clarifies that the bound on bias increases with the age of observations, although averaging over earlier cycles can reduce the actual bias. In the original clinic experiment, separate tuning for each clinic selects full history for pediatrics and primary care. Appendix I.6 adds the comparison under more complex recurring patterns.

Unrealistic initialization assumption. The theoretical analysis assumes that each optimization problem is initialized from a fixed point. This assumption differs from typical continual federated learning settings, where optimization proceeds from previously learned models as new data arrive, potentially limiting the applicability of the theoretical results to practical scenarios.

We added this limitation in Section 8, final paragraph, and Appendix M.3, under “Reset point.” Resetting makes the first gradient query independent of the retained data. Each later query uses a batch that has not yet been used in that solve. Starting from a model trained on records still in the buffer can violate this independence, so the present proof does not cover that case.

Discrepancy from standard federated learning settings. Several assumptions in the proposed framework appear to differ substantially from typical continual federated learning settings, including initialization from a fixed point for each optimization problem, communication with all clients at every refresh, and the ability to directly transmit data to the server. What motivates these assumptions, and to what extent can the proposed method be applied when these assumptions do not hold?

Section 8 and Appendix M.3 now explain why these assumptions are used. Resetting allows the proof to justify reusing retained observations. Regular arrivals and participation by every client provide the batches needed at each round. Algorithm 1 can keep records local and send gradients. The present guarantee does not cover starting from a model trained on retained records, missing client rounds, or limiting message sizes.

Thank you for your detailed response and the additional experiments.

While these revisions help clarify the scope of the theoretical guarantees and provide additional empirical evidence, I remain concerned that the proposed method and evaluation settings are primarily aimed at validating the theoretical findings rather than demonstrating practical effectiveness in realistic continual federated learning scenarios.

Therefore, I will maintain my positive assessment, but do not see sufficient grounds to raise my score further.

Dear reviewer pXKV, thank you for your work and positive evaluation!

Reviewer_fWQjOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This is a theory paper. It asks the question that how much past data each client should keep when its data distribution changes over time. It shows, through worst-case bounds, that giving each client its own window is never worse than a single shared window and is especially better when clients differ in how noisy and fast they change.

Critical strengths

For a theory paper, the problem is well motivated and clearly formulated. On a simple setup, the experimental results support the theoretical statement of when client-specific windows should help and when they shouldn't. However, the gain of using the client specific window on a more realistic setup is less obvious possibly due to the difficulty in estimating the drift. Still, I find these results interesting, and it would also be valuable to see a controled comparison of steady, sudden, and recurring drift in the future work.

Critical weaknesses

For a theory paper, I think it is fine to use a simple dataset to show consistent statements as the theory suggests. However, I am still curious about the practical implications. A separate paragraph summarizing them would be helpful, e.g., what to do when drift is sudden or recurring and what to do when the model forgets too much.

Questions for authors

In Figure 1, the common tuned window seems to perform slightly worse than one common window, some clarification on this would be helpful.

3 comments

Thank you for review!

For a theory paper, I think it is fine to use a simple dataset to show consistent statements as the theory suggests. However, I am still curious about the practical implications. A separate paragraph summarizing them would be helpful, e.g., what to do when drift is sudden or recurring and what to do when the model forgets too much.

We added practical guidance in Section 8. A minimum window duration limits how much data is discarded after startup. Including long windows and full history among the candidates allows the method to retain earlier cycles when drift recurs. Short windows discard data from before a sudden change sooner, but Eq. (2) gives no guarantee on recovery time. A common window with a minimum duration for each client is simpler when it retains similar data and gives similar loss.

Still, I find these results interesting, and it would also be valuable to see a controled comparison of steady, sudden, and recurring drift in the future work.

We added the controlled comparison in Appendix N, Table 8, and the clinic outbreak tests and tests of recurring seasonal changes in Appendix I.6. Appendix N keeps noise, arrival rates, candidate windows, and random seeds the same. One client stays stationary while the other changes at a constant rate, undergoes a smooth transition, follows a recurring pattern, or jumps. Section 8 summarizes the results.

In Figure 1, the common tuned window seems to perform slightly worse than one common window, some clarification on this would be helpful.

We clarified Figure 1's caption and Appendix J.1. The tuned window is chosen using four seeds from a grid whose successive lengths differ by a factor of 1.8. The length minimizing the theoretical bound lies between grid points. On twelve separate evaluation seeds, the mean gap difference, tuned minus bound-optimal, is 0.00032 in December (95% interval [−0.00053, 0.00116]) and 0.00088 in July ([0.00027, 0.00149]).

Thank you for addressing each one of my concerns and questions. I believe the discussion of the practical implication could be interesting to a broader audience. Therefore, I am leaning toward accepting.

Dear reviewer fWQj, thank you for your positive evaluation!

Reviewer_qTk8OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies how much past data each client should retain when its distribution changes over time. It derives a tracking bound using each client's drift, noise and arrival rate, gives lower bounds, and proposes validation-based selection without known drift. Experiments use temperature streams and a synthetic clinic network.

Critical strengths
  1. The main novelty is the clientwise tracking quantity and the lower bound that keeps each client's drift limit fixed. These explain what is lost by combining all clients into one drift bound. The result gives a useful reason to keep more history at stable, noisy clients, beyond the familiar single-stream bias-variance tradeoff.

  2. The sample-reuse argument seems reasonable. Resets and disjoint batches avoid assuming that reused samples remain unbiased at arbitrary queries. I did not find a clear error in the main upper or lower bound. Separate tuning seeds, paired comparisons and reported failure cases also strengthen the evaluation.

Critical weaknesses
  1. The fixed-window rule needs known drift and noise bounds over the whole parameter domain. The clinic study instead evaluates them along the exact optimal trajectory and tunes a window multiplier using population gaps (Appendix I). Section 6 avoids known drift, but a full joint grid has exponentially many experts and is not tested. Practical window selection remains unclear.

  2. The strongest gains use independently resampled weather or synthetic clinic records, with scalar quadratic or logistic losses. In recorded weather order, gains largely disappear (Appendix J.2). With Algorithm 1, the clinic result is within 1% of a common window with a minimum sample count per client (Figure 4). The practical advantage needs stronger evidence.

  3. The model assumes independent samples, uniformly regular arrivals and full participation. Storage and computation are free, messages have no size limit, and raw data can be pooled. These choices isolate the statistical problem, but leave the result far from typical FL constraints.

  4. The abstract says the result is never worse than any common window and strictly better with uneven clients. Equation (5) only compares terms in upper bounds, not actual risks. Proposition 5.2 proves an actual separation only for a restricted estimator class. The abstract should make this distinction.

Questions for authors
  1. How well does the rule work when drift and noise inputs are estimated only from past data, without the exact optimal trajectory or population gaps? How sensitive is it to errors in these inputs?

  2. Can you evaluate Section 6 against the common-window baseline with a per-client sample floor and an adaptive forgetting baseline, and report the computation and storage required?

4 comments

Dear reviewer qTk8, Thank you for review!

The abstract says the result is never worse than any common window and strictly better with uneven clients. Equation (5) only compares terms in upper bounds, not actual risks. Proposition 5.2 proves an actual separation only for a restricted estimator class. The abstract should make this distinction.

We clarified paragraph 2 of the abstract. The comparison concerns the leading term in the error bound, with strict inequality when the two vectors in Eq. (4) are not proportional (Eq. (5), Lemma C.2). Proposition 5.2 gives a separate comparison of actual errors for methods that minimize loss over completed windows, giving observations within each client's window equal weight.

The fixed-window rule needs known drift and noise bounds over the whole parameter domain. The clinic study instead evaluates them along the exact optimal trajectory and tunes a window multiplier using population gaps (Appendix I). Section 6 avoids known drift, but a full joint grid has exponentially many experts and is not tested. Practical window selection remains unclear.

We added a clinic experiment that chooses windows from earlier observations (Appendix I.6, summarized in Section 8). We estimate drift and noise from gradients observed before week 36, choose window lengths using prediction losses during weeks 36–52, and keep them fixed during testing. Table 5 tests a mixture of 24 models with different window choices. Appendix M.2 gives the computation and storage needed to evaluate every combination of candidate windows. The guarantee in Section 6 still requires known noise bounds.

How well does the rule work when drift and noise inputs are estimated only from past data, without the exact optimal trajectory or population gaps?

We added tests that estimate both inputs using only observations available before each prediction (Appendix O, summarized in Section 8). For weather, the common window is chosen using earlier prediction losses. Table 10 reports the mean loss difference, client-specific minus common, as −0.000467 in December (descriptive 95% interval [−0.000676, −0.000257]) and −0.000072 in July ([−0.000268, 0.000123]).

For clinics, visits enter the estimates and model fits only after their 90-day outcome period has ended. Table 12 gives mean gaps of 0.004245 for client-specific windows, 0.004173 for a common window with a minimum duration for each client, and 0.004343 for full history. Appendix O.2 explains how we regenerated the patients and reconstructed the changing proportions of the two patient groups. The separate experiment in Appendix I.6 assumes outcomes are available immediately.

How sensitive is it to errors in these inputs?

We added Proposition M.1, summarized in Section 8. When each positive drift and variance input is within a factor of two of its true value, window lengths before imposing a minimum duration differ from those computed with the correct inputs by at most a factor of 2.52. The part of the error bound due to drift and limited data is at most 1.899 times its minimum. The proposition also states how enforcing minimum window durations changes this bound. It does not cover estimating positive drift as zero.

Can you evaluate Section 6 against the common-window baseline with a per-client sample floor and an adaptive forgetting baseline, and report the computation and storage required?

We added the comparison in Appendix N (Tables 8–9), summarized in Section 8. Across four drift patterns and 40 paired runs, combining SGD models with client-specific windows reduces the mean gap by 7.5–13.7% compared with combining models that use common windows and the same minimum durations. Adaptive exponential forgetting, which gradually reduces the weight of older data, has the lowest mean gap in every case.

Per run, the two SGD methods require work equivalent to 4,525,218 and 844,830 gradient evaluations on individual records. Each retains 3,902 training records. Exponential forgetting makes 25,641 updates to sums of weighted observations and sums of weights, using 24 stored numbers. Appendix N also reports the cost of scoring candidates, the additional memory used to combine their predictions, and running times.

The strongest gains use independently resampled weather or synthetic clinic records, with scalar quadratic or logistic losses. In recorded weather order, gains largely disappear (Appendix J.2). With Algorithm 1, the clinic result is within 1% of a common window with a minimum sample count per client (Figure 4). The practical advantage needs stronger evidence.

We added experiments varying the minimum window durations and the timing of drift (Appendix I.6, Table 4). With the same drift timing and minimum window durations corresponding to 16 records, client-specific windows reduce the mean gap by 7.39% relative to the common rule. Giving stationary clinics identical buffers under both methods still leaves client-specific windows with a lower mean gap by 0.00015440 (95% interval [0.00010990, 0.00019890]). Other settings favor the common rule or have a difference whose interval includes zero. Section 8 summarizes these results. Appendix O adds weather tests using only earlier observations and clinic tests that wait 90 days for outcomes.

The model assumes independent samples, uniformly regular arrivals and full participation. Storage and computation are free, messages have no size limit, and raw data can be pooled. These choices isolate the statistical problem, but leave the result far from typical FL constraints.

We added an explanation of these assumptions in Section 8, final paragraph, and Appendix M.3. Clients can keep records local and send gradients. The proof still assumes independent observations, regular arrivals, and participation by every client at every round. It places no limits on message size, storage, or computation. The current guarantee does not cover missing clients, limited messages, or privacy constraints.

I would like to thank the authors to address my comments very carefully. Most of my comments have been addressed. The rest such as the ideal assumptions are really the limitation of this work rather than critical weaknesses. I raised my score to 3.

Dear reviewer qTk8, thank you very much for your review and positive evaluation!

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.