acceptodds
Under review as a conference paper at ICLR 2027

Beyond Staleness Decay: History-Enhanced Residual Acceleration in Asynchronous Federated Learning

Abstract

Asynchronous federated learning produces a stream of client updates computed from stale model snapshots. We introduce History-Enhanced Residual Acceleration (HERA), a server-side method that reuses this stream as a short residual history for Anderson mixing. Lagged RMS stabilization balances the residual geometry, while a base-anchored update controls the full displacement of each history proposal. Our analysis separates base-update drift, delay, history amplitude, and client-selection bias. With bounded delay, uniform sampling, and a stepsize-scaled anchor, local-SGD residuals attain the nonconvex stationarity rate; nonuniform arrivals and fixed anchors contribute explicit residual terms. A local error bound relates proposal quality to residual fitting, map conditioning, and evaluation mismatch. A four-way MNIST ablation examines the interaction between RMS stabilization and history correction, with their combination improving mean final accuracy over RMS alone in all five settings. Across ten CIFAR scenarios, HERA attains the highest mean final validation accuracy in eight, including all six non-IID settings.

Primary area:
optimization
Keywords:
Asynchronous Federated Learning, Anderson Acceleration, Staleness-Aware Optimization, Nonconvex Optimization

Reviews

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

This paper primarily studies the staleness issue in asynchronous federated learning and proposes HERA. On the server side, HERA maintains a history of short residuals arriving with different delays. It constructs candidate updates using Anderson mixing / residual fitting. In addition, it introduces lagged RMS stabilization to stabilize the residual geometry, and employs an acceptance mechanism anchored on the current base update to control “extrapolation corrections” based on past information. The paper provides theoretical analysis at the residual level, including decompositions of base-update drift, delay effects, history amplitude, and client selection bias. Experiments on multiple asynchronous / non-IID settings for MNIST and CIFAR-10/100 include ablations and comparisons, showing higher final accuracy across several scenarios. Overall, the work is solid, but the boundaries relative to existing methods should be strengthened.

Critical strengths

This paper studies the staleness issue in asynchronous federated learning. Instead of merely suppressing stale updates, the algorithm organizes delayed client updates into a short residual history that can be used to accelerate training more effectively. The algorithm and its analysis are fairly tightly coupled, there is a clear correspondence between the key mechanisms (residual-history construction, stabilization of the residual geometry, and an acceptance rule anchored on the current state) and the theoretical error decomposition. In addition, factors such as drift, delay, history magnitude, and client-selection bias are discussed separately, and the analysis is acceptable.

Critical weaknesses

In federated learning, Anderson acceleration as a classic residual-based acceleration method is not new; the ways to handle staleness in asynchronous FL (e.g., reweighting/buffering, delay mixing, correction) have also been extensively studied. What this paper emphasizes is combining and stabilizing the two specifically stabilizing and anchoring the acceptance rule to form a short residual history. As a result, it’s unclear how HERA differs from recent work in federated or asynchronous settings that has introduced similar “history, fitting , acceleration” ideas, because the analysis does not make this comparison explicit. The convergence or stationarity results rely on several conditions (for example, bounded RMS denominators, delay assumptions, uniform sampling, a contractive neighborhood, a positive descent margin, etc.). To what extent are these conditions operationally checkable or verifiable in real asynchronous federated learning?

Questions for authors

How long is the residual history window used in HERA? Under different delay distributions, is there an optimal range for the window length? Can the paper provide a small scale sensitivity study (e.g., on MNIST or CIFAR-10)? What are the acceptance or rejection rates of the base-anchored acceptance mechanism? When proposals are rejected, does it fall back to the base update, or does it apply some scaling to the candidate? Is there any evidence in the experiments for a relationship between proposal quality and residual fitting quality for example, can the paper plot a correlation curve such as a residual fit ratio or track a metric like λ over the course of training?

2 comments
AuthorsOpenReview ↗

Response to Reviewer vPwE

Thank you for the constructive comments. We have clarified HERA’s positioning, the operational meaning of its assumptions, and the requested implementation and diagnostic results. The corresponding revisions are in Sections 2.3--3, the extended related-work discussion in Appendix F, the MNIST settings in Appendix C.1, and the mechanism diagnostics in Appendix G.

Positioning relative to existing Anderson and asynchronous-FL methods. HERA turns the update stream generated by asynchronous training into a usable acceleration history. Each arrival carries a client-dependent update computed from a stale server snapshot, a local objective, and a stochastic local trajectory. HERA organizes these arrivals as a short residual history: RMS stabilization places the residuals in a comparable geometry, affine fitting constructs the history proposal, and base-anchored acceptance controls the complete displacement, including drift from stale server states. This is the central distinction from federated Anderson methods that actively construct acceleration steps from a coherent sequence of iterates or residuals, and from asynchronous-FL methods that primarily reweight, buffer, or correct stale updates. We have made this distinction explicit in Section 2.3 and in the FedOSAA comparison in Appendix F.

History-window sensitivity. The main HERA experiments use four stored candidate--residual pairs. We additionally reran the original HERA implementation on all five MNIST settings used in Table 1 with W∈{2,4,8}W\in\{2,4,8\} and three fixed seeds per setting. Appendix G now gives the complete 15-row table. The diagnostic protocol keeps the same partitions, arrival patterns, local training, and evaluation procedure; its learning rate is 10−310^{-3} and its upper RMS denominator bound is 2, both stated explicitly in Appendices C.1 and G. Averaged over the five settings, the final accuracy is 83.28%83.28\%, 84.06%84.06\%, and 84.13%84.13\% for W=2,4,8W=2,4,8, respectively. The corresponding mean acceptance rates are 97.7%97.7\%, 36.3%36.3\%, and 17.3%17.3\%. Thus, increasing the window from 2 to 4 yields a 0.780.78-point accuracy gain, while increasing it from 4 to 8 yields only an additional 0.070.07 points and substantially lowers acceptance. We therefore use W=4W=4 as the default accuracy--acceptance trade-off. A longer window is useful in the high-delay IID setting, where accuracy increases from 89.00%89.00\% at W=4W=4 to 89.40%89.40\% at W=8W=8, but this gain does not generalize to all five settings.

Acceptance, rejection, and fallback. When a history proposal is unavailable or fails any numerical, direction, or step check, HERA discards the proposal and applies the base candidate bkb_k. When the proposal passes, HERA combines it with bkb_k according to the anchor rule; if the proposed correction exceeds the anchor budget, its contribution is reduced. Appendix G reports accepted proposals, rejected proposals that fall back to bkb_k, and insufficient-history events separately. These results show that HERA applies history selectively: W=2W=2 accepts nearly every available proposal, whereas longer windows filter proposals more aggressively according to the arrival and data regime. Together with the accuracy results, this supports W=4W=4 as the default window: it retains substantial history correction while avoiding the very low acceptance observed for W=8W=8. In the high-delay IID setting, W=8W=8 provides an additional accuracy gain, so the longer window is useful when delayed arrivals make a longer history informative.

Fit quality and proposal quality. Regarding the question of whether proposal quality is related to residual-fitting quality, our answer is yes. We use the normalized fitted-residual ratio gkg_k to measure fitting quality and the proposal acceptance rate to measure whether the resulting candidate passes the complete checks. Appendix G reports both quantities and the final accuracy for all 15 setting-window groups, together with a scatter plot. The Pearson and Spearman correlations between gkg_k and the acceptance rate are 0.8000.800 and 0.6540.654, respectively. These results provide the requested experimental evidence of a relationship between residual fitting and proposal acceptance. Section 4 provides the corresponding analytical link through residual fitting, map conditioning, stale-history mismatch, and candidate-processing error.

Checkability of the theoretical assumptions. We make the relevant assumptions explicit and relate them to the asynchronous implementation. The RMS denominator bounds and delay limits are set by the server and logged during training. The client-arrival sequence can be examined for uniformity; when arrivals are nonuniform, Theorem 4.2 accounts for the resulting selection bias. The smoothness, bounded-moment, contractive-neighborhood, and positive-descent-margin conditions are analytical assumptions; they cannot be directly verified by a finite training run and define the regime in which the theoretical guarantees apply.

The rebuttal is received with thanks. I think I have no further comments at this stage.

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

This paper proposes History-Enhanced Residual Acceleration (HERA), a server-side optimization method for asynchronous federated learning. The main idea is to reuse historical client updates as residual information for Anderson-type mixing, rather than treating stale updates solely as a source of optimization error.

To address the inconsistency of residuals arising from stale model snapshots and heterogeneous client training, the proposed method combines lagged RMS stabilization, regularized Anderson fitting, and a base-anchored acceptance mechanism. The paper also provides convergence analysis under several assumptions, including bounded delays and conditions on the history correction, together with local improvement results for the Anderson proposal.

Experiments on MNIST, CIFAR-10, and CIFAR-100 compare the proposed method with asynchronous federated learning baselines and examine the contributions of RMS stabilization and history reuse. The reported results show improvements in several settings, particularly under non-IID data distributions.

Critical strengths

1. Meaningful motivation for history reuse in asynchronous federated learning.

The paper explores an interesting direction by considering whether stale client updates can provide useful historical information for accelerating optimization, rather than only being treated as delayed updates requiring correction or downweighting. I think this motivation is relevant to asynchronous federated learning, where the server naturally accumulates updates computed from different model states.

2. Substantial theoretical and experimental effort.

The authors provide a relatively extensive convergence analysis, including the effects of delayed updates, history corrections, and nonuniform client arrivals. The experimental evaluation also considers multiple asynchronous settings, different levels of data heterogeneity, and comparisons with several existing methods. The reported improvements under non-IID conditions are encouraging and suggest that the proposed combination of mechanisms may be practically useful.

Critical weaknesses

1. Insufficient connection between the proposed mechanism, the theoretical analysis, and the claimed acceleration benefits.

(a) Clarity of presentation. Although the paper presents a clear motivation for reusing stale updates in asynchronous federated learning, the overall narrative is not sufficiently coherent. In particular, the transition from the identified problem to Anderson acceleration feels somewhat abrupt. The paper does not adequately explain why Anderson mixing is a natural and promising approach to exploiting stale update history, or how its properties relate to the specific challenges of asynchronous federated learning. As a result, the proposed method feels more like a collection of technical components than a solution developed step by step from the underlying motivation. A more intuitive introduction to Anderson acceleration and a stronger connection between the problem formulation and the method design would substantially improve the presentation.

(b) Organization of the proposed method. Section 3 introduces RMS stabilization, regularized Anderson fitting, and base-anchored acceptance, but the connections among these components and their respective roles could be explained more systematically. The section currently presents the mechanisms without sufficiently developing the reasoning behind their integration.

(c) Limitations of the convergence analysis. The global convergence results mainly establish convergence properties under bounded history corrections, rather than demonstrating a faster convergence rate than the first-order asynchronous baseline. Therefore, the theoretical analysis does not directly establish the claimed acceleration benefits of Anderson mixing.

(d) Gap between the local improvement guarantee and the practical acceptance criterion. Theorem 4.3 establishes a conditional improvement guarantee when the Anderson proposal is already closer to the local solution than the base candidate. However, the practical acceptance criterion in Section 3.3 checks directional alignment and step magnitude rather than directly verifying this condition. Consequently, the analysis does not establish that accepted Anderson proposals are necessarily better than the base candidate. A clearer connection between the theoretical improvement condition and the practical acceptance rule would strengthen the justification of the method.

2. Limited experimental evidence isolating the contribution of Anderson acceleration.

(a) Dominant contribution of RMS stabilization in some settings. The MNIST ablation in Table 1 raises questions about the source of the reported improvements. RMS-only already achieves substantial gains over the first-order asynchronous baseline, particularly in the IID settings, whereas history-only provides relatively limited improvements.

(b) Insufficient isolation of the Anderson mechanism. Although the complete HERA method performs better than RMS-only, with particularly encouraging additional gains under non-IID conditions, the current ablation does not fully isolate the respective contributions of Anderson fitting and the acceptance mechanism. As a result, it remains unclear how much of the improvement can be attributed specifically to Anderson acceleration rather than to RMS stabilization and the other safeguards.

(c) Missing acceptance-rate analysis. The paper does not report the acceptance rate of Anderson proposals or provide a detailed analysis of how frequently the history correction is actually used. Such information is important for understanding whether and to what extent the proposed history-based acceleration mechanism contributes to the observed improvements.

Overall, appreciate the substantial effort invested in the theoretical analysis and the encouraging empirical results, particularly in heterogeneous settings. However, I believe the paper still requires revisions to better connect its theoretical guarantees with the practical acceptance mechanism and to isolate the contribution of Anderson acceleration. I would be willing to reconsider my rating if these concerns are adequately addressed in the rebuttal.

Questions for authors

1. Relationship between the acceptance criterion and the local improvement guarantee.

Theorem 4.3 establishes an improvement over the base candidate when the Anderson proposal satisfies θk<1\theta_k < 1. However, the practical acceptance rule in Eq. (5) checks directional alignment and step magnitude. Could the authors clarify whether these practical conditions provide any theoretical or empirical indication that θk<1\theta_k < 1 is likely to hold? In particular, under what conditions should an accepted Anderson proposal be expected to outperform the base candidate?

2. Acceptance rate and actual contribution of history corrections.

Could the authors report the acceptance rates of the Anderson proposals across the experimental settings? It would also be helpful to distinguish how often a history proposal is attempted, accepted, rejected, or unavailable due to insufficient history. How do these statistics change over training, and how much does the accepted history correction contribute to the final server update?

3. Isolating the contribution of Anderson acceleration.

Table 1 shows that RMS-only already provides substantial improvements, while history-only produces relatively small changes. Could the authors provide additional controlled ablations separating RMS stabilization, Anderson fitting, and base-anchored acceptance? In particular, comparisons involving RMS + Anderson without acceptance, and RMS with the same safeguards but without Anderson fitting, would help clarify whether the gains arise from the proposed acceleration mechanism or primarily from stabilization.

4. Convergence guarantees versus acceleration.

The global convergence analysis establishes an O(K−1/2)O(K^{-1/2}) stationarity rate under the stated assumptions, but this does not appear to demonstrate a faster asymptotic rate than standard first-order stochastic optimization. Could the authors clarify whether their theoretical contribution is primarily a convergence guarantee for a safely bounded history correction, or whether a stronger acceleration result can be established under additional assumptions?

5. Applicability of the theoretical assumptions to the experimental configuration.

The paper distinguishes the stepsize-scaled anchor used in the asymptotic analysis from the fixed anchor employed in the CIFAR experiments. Could the authors further clarify which theoretical guarantees apply directly to the experimental configuration and whether the required residual conditions can be verified or empirically supported?

2 comments
AuthorsOpenReview ↗

Response to Reviewer zghr

We thank the reviewer for this thoughtful comment, which helped us clarify the central motivation and improve the coherence of the presentation.

Response to Comment 1: Connecting the Motivation, Method Design, Theory, and Acceleration Claims

1(a) We agree that this motivation was not made sufficiently explicit. However, HERA is not a collection of independent technical components. Its central observation is that an asynchronous server naturally receives stale updates, which form a short history of the server trajectory. Rather than treating these arrivals only as errors to be downweighted, HERA reuses their residual information to construct an accelerated proposal. The individual components follow from this single motivation: RMS stabilization makes heterogeneous stale residuals comparable, Anderson fitting extracts their directional information, and acceptance with base anchoring controls the resulting history drift. Thus, HERA is designed as a coherent solution to reuse the historical information already generated by asynchronous training. We made this connection explicit in the revised opening of Section 1 and the method overview in Section 3.

1(b) We thank the reviewer for pointing this out. We revised the overview of Section 3 and added explicit transitions at the beginning of Sections 3.1–3.3. The revised organization now follows one sequence: RMS stabilization makes stale residuals comparable, regularized Anderson fitting constructs a proposal from the stabilized history, and acceptance with base anchoring controls its complete displacement and history drift. These components therefore address successive consequences of asynchronous staleness rather than functioning as independent techniques.

1(c) We agree that our global convergence results do not establish a faster asymptotic rate than the first-order asynchronous baseline. The role of the theory is to provide convergence guarantees under bounded history corrections and to characterize when residual fitting can improve the local proposal. The acceleration benefits of Anderson mixing are therefore conditional and local at the theoretical level, and are supported empirically rather than claimed as a universally faster global convergence rate.

1(d) We clarify that the practical acceptance criterion and the solution-dependent condition θk<1\theta_k<1 serve different purposes. The directional-alignment and step-magnitude checks control the complete proposal displacement and the drift caused by stale history; they do not by themselves prove that every accepted proposal improves upon the base candidate. Under the local coherence and mismatch conditions in Corollary 4.2, a sufficiently effective residual fit can imply θk<1\theta_k<1, after which Theorem 4.3 yields local improvement of the accepted mixture. Otherwise, the method falls back to the base update without claiming universal improvement.

Response to Comment 2: Isolating the Contribution of Anderson Acceleration

2(a,b) We agree that RMS stabilization contributes substantially, especially in IID settings. However, HERA still improves over RMS-only by 1.01, 10.55, 9.08, 3.00, and 0.99 percentage points across the five settings in Table 1. RMS stabilization makes the stale residuals usable, and history correction converts them into an effective server update.

2(c) Appendix G reports the proposed, accepted, fallback, and insufficient-history counts for all five settings and history windows 2, 4, and 8. The results show a clear window-dependent trade-off. In the Dirichlet setting, the acceptance rate decreases from 96.8% to 69.8% and 37.0% as the window grows from 2 to 4 and 8. Under high-delay IID, it decreases from 96.1% to 21.9% and 5.9%. Longer windows produce smaller fitted-residual ratios but also more fallback updates because the complete proposal is harder to accept under heterogeneous delays.

AuthorsOpenReview ↗

Anwser to questions

  1. The practical rule in Section 3.3 and Eq. (5) controls directional alignment, step magnitude, and the complete history-induced displacement. The local analysis in Section 4 and Appendix B connects this controlled proposal to improvement. When the retained history is locally coherent, evaluation and processing mismatches are bounded, and the fitted residual satisfies the sufficient residual-reduction condition, the solution-dependent ratio θk\theta_k satisfies θk<1\theta_k<1. Theorem 4.3 then gives improvement over the base candidate.

  2. Appendix G, Table 9, reports proposed, accepted, fallback, and insufficient-history counts for five settings and history windows W∈{2,4,8}W\in\{2,4,8\}. For W=2W=2, acceptance rates range from 96.1% to 100.0%; for W=4W=4, from 0.1% to 74.1%; and for W=8W=8, from 0% to 40.0%. Insufficient-history events are reported separately as 3, 9, and 21 per three-seed setting group for W=2W=2, W=4W=4, and W=8W=8, respectively. Accepted and fallback counts quantify how frequently history proposals enter the committed server updates.

  3. Section 5 and Table 1 compare first-order asynchronous updates, RMS-only, History-only, and HERA. HERA improves over RMS-only by 1.01, 10.55, 9.08, 3.00, and 0.99 percentage points across the five settings. These results quantify the additional benefit of stabilized residual history beyond RMS stabilization. Appendix G reports the corresponding fitting ratios and proposal-use statistics for the same settings and three fixed seeds.

  4. The global analysis establishes the standard O(K−1/2)O(K^{-1/2}) stationarity guarantee under bounded history corrections. The local analysis characterizes proposal improvement when the residual history is informative and the stated coherence and mismatch conditions hold. Thus, the theoretical acceleration result is a conditional local proposal-improvement result, complemented by the empirical accuracy gains in Table 1.

  5. The asymptotic stationarity result uses the stepsize-scaled anchor. For the fixed anchor used in the CIFAR configuration, Appendix A gives a finite-budget residual bound that retains explicit anchor and base-drift terms. Its applicability is determined by the stated residual-moment, cache-mismatch, RMS-denominator, and positive-margin conditions. The experimental protocol specifies the anchor, delay, history, and denominator safeguards used in the experiments.

Reviewer_1qATOpenReview ↗
Rating
1(−1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
1(−1)
Read review
Paper summary

This paper proposed HERA, a server-side residual-history method for asynchronous federated learning. It leverages the history information of federated learning for better acceleration, using the Anderson mixing for candidate selection. The paper conducted some related theoretical analysis on the convergence rate, with empirical validation on CIFAR and MNIST.

Critical strengths

This paper novelly separating the mismatch to be two terms under Anderson mixing theory in section 2.3. Detecting the problem that residual can only tackle the second term while leaving the historical drift.

Critical weaknesses

1, The experiment settings are problematic in component control. According to appendix C.2, no experiments comparing the on-off of history correlation only. Thus the performance comparison can not be responsibly contribute to the history acceleration introduced by HERA.

2, the experiment settings are vague. No explicit formula about the "calibrated using stored client updates (line 1492)", no historical update policy ,no lambda value is given etc.

3, by theorem 4.3, the improvement cannot be made under non-iid arrivals. From the assumption 4.5, a trivial corollary is Ψk(x⋆)=x⋆\Psi_k(x^\star)=x^\star , which can be broken by a simple non-iid arrival case when

f_2(x)=\tfrac12(x+1)^2$$
Questions for authors

1, can the authors give more controlled experiments in the historical info only case? without adding any additional component for performance gain.

2, can authors give the clear experiment settings?

3, can the authors give additional analysis on the non-iid arrival cases? Can the convergence/advantage still hold?

2 comments
AuthorsOpenReview ↗

Response to Reviewer 1qAT

Thank you for recognizing the two-term decomposition in Section 2.3. Below we provide the requested controlled comparisons, exact implementation, and analysis of the non-IID example.

  1. We agree that the contribution of history correction should be separated explicitly from RMS stabilization. We therefore clarify the three columns in Table 1 as RMS-only (history correction disabled), History-only (RMS disabled), and HERA (RMS + history correction). The complete comparison is: | Setting | RMS | Hist. | HERA | Gain | |:--|--:|--:|--:|--:| | Base IID | 97.19 | 89.36 | 98.20 | +1.01 | | Label Non-IID | 82.90 | 73.73 | 93.45 | +10.55 | | Dirichlet Non-IID | 87.71 | 81.25 | 96.79 | +9.08 | | High-delay IID | 95.17 | 90.29 | 98.17 | +3.00 | | 20-worker IID | 96.62 | 81.89 | 97.61 | +0.99 | HERA improves over RMS-only in all five settings. The additional gains are particularly large under the two non-IID partitions, where HERA improves over RMS-only by 10.55 and 9.08 percentage points, respectively. These results show that the improvement is not attributable to RMS stabilization alone. The same table also shows that history correction is most effective when combined with RMS stabilization: History-only is substantially weaker than HERA in every setting.

  2. We have revised Appendices C.1 and C.2 to make the implementation fully explicit. Appendix C.1 now specifies the MNIST configuration, including the history window size (4), ridge parameter λ=10−4\lambda=10^{-4}, RMS coefficient β=0.9\beta=0.9, εrms=10−8\varepsilon_{\rm rms}=10^{-8}, denominator bounds [0.1,10][0.1,10], directional threshold 0.10.1, step cap 22, and anchor budget 10ηk10\eta_k.

    Appendix C.2 now gives the complete CIFAR calibration equation and history-update policy. It specifies the cache-age weighting rule with decay scale H=20H=20, buffer size B=5B=5, and the use of distinct clients in the history buffer. The appendix also states that the cache is updated after each aggregation, history fitting is refreshed every 20 base aggregations after warm-up, at most four history columns are retained, records older than 40 refreshes are discarded, and the history remains unchanged when a proposal is rejected or numerically invalid.

    For the CIFAR difference-coordinate solve, we now explicitly report λ=0\lambda=0, a Moore--Penrose pseudoinverse with relative tolerance 10−410^{-4}, and a condition-number threshold of 10410^4. These are the exact settings used to generate the reported results.

  3. We instantiate our existing nonuniform-arrival analysis for the two-client example in Section 4.2.

    For f1(x)=12(x−1)2f_1(x)=\frac{1}{2}(x-1)^2 and f2(x)=12(x+1)2f_2(x)=\frac{1}{2}(x+1)^2, the equal-weight objective has minimizer x⋆=0x^\star=0. The individual client update maps are

    \Psi_2(x)=(1-\eta)x-\eta.$$ Neither individual map fixes $x^\star$. Under uniform client sampling, their mean map is $$\Psi(x)=\frac{1}{2}\Psi_1(x)+\frac{1}{2}\Psi_2(x)=(1-\eta)x.$$ Therefore, $x^\star=0$ is a fixed point of the mean map, and the map is contractive for $0<\eta<2$. Deviations of the realized stored client pairs from this common mean map are captured by the history-error term $\varepsilon_{j,k}$. For nonuniform arrivals, let client 1 be selected with probability $p$ and client 2 with probability $1-p$. The mean map becomes $$\Psi_p(x)=(1-\eta)x+\eta(2p-1).$$ The term $\eta(2p-1)$ represents the selection bias induced by nonuniform arrivals. In this example, the quantities in our nonuniform-arrival bound reduce to $$\zeta^2=1,\qquad \chi^2=(2p-1)^2,$$ so the squared selection-bias contribution is $$\zeta^2\chi^2=(2p-1)^2.$$ Thus, the effect of nonuniform arrivals is explicitly included in the existing global analysis. For the local improvement analysis, we recenter the mean map as $$F(x)=\Psi_p(x)-\Psi_p(0)=(1-\eta)x.$$ The constant shift $$\Psi_p(0)=\eta(2p-1)$$ is retained as an evaluation-mismatch term. For $0<\eta<1$, the resulting sufficient condition for actual improvement is $$(1-\eta)\bigl(\|r_k\|-\|R\alpha\|\bigr) > (A+1)\bigl(\bar{\varepsilon}+\eta|2p-1|\bigr)+\eta\omega,$$ where $A=\|\alpha\|_1$, $\bar{\varepsilon}$ bounds the history mismatch, and $\omega$ measures the additional candidate-processing error. This condition shows how nonuniform arrivals affect the guarantee. When $p=1/2$, the selection-bias term vanishes. As the arrival distribution becomes more imbalanced, the sufficient condition becomes more stringent. Hence, the theory does not require every individual client map to fix the global minimizer. Instead, it separates the common mean dynamics, history mismatch, and selection bias, and gives a conditional local-improvement guarantee after accounting for these effects.

Response to Rebuttal

The rebuttal does not resolve my main concern, and the revision makes it worse. My original review said the experiments add components beyond the proposed method. The revised Appendix C.2 also shows this problem. The CIFAR base update is CA2FL's cached-update calibration, and the paper never attributes it to CA2FL. The method reported as HERA is CA2FL plus RMS plus a history term, yet its margin over CA2FL is credited to history correction. HERA is also tuned per scenario while CA2FL gets one learning rate per dataset, and results are reported on the same validation split used for tuning.

I consider this a research-integrity concern. A'+B+C >A cannot prove that A' >A, and to hide the contribution of B and C is not ethical. Without a CIFAR run that switches history on and off with everything else fixed, these results say nothing about the proposed method.

The authors' own data point the same way. In Table 1, history alone changes accuracy by at most 1.53 points, within one standard deviation. In the new Table 9, 20-Worker IID gives 82.07 when all history proposals are accepted and 82.27 when none are.

The theory does not help. Assumption 4.2 requires the arriving client to be uniform given sks_k, but the paper's scheduler makes sks_k determine the client, so Theorem 4.1 covers none of the experiments.

Thus I raise an ethical concern and lower my rating to 1.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.