- 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
The rebuttal is received with thanks. I think I have no further comments at this stage.
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} 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−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%, 84.06%, and 84.13% for W=2,4,8, respectively. The corresponding mean acceptance rates are 97.7%, 36.3%, and 17.3%. Thus, increasing the window from 2 to 4 yields a 0.78-point accuracy gain, while increasing it from 4 to 8 yields only an additional 0.07 points and substantially lowers acceptance. We therefore use W=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% at W=4 to 89.40% at W=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 bk. When the proposal passes, HERA combines it with bk 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 bk, and insufficient-history events separately. These results show that HERA applies history selectively: W=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=4 as the default window: it retains substantial history correction while avoiding the very low acceptance observed for W=8. In the high-delay IID setting, W=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 gk 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 gk and the acceptance rate are 0.800 and 0.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.