Home / Curated / Algorithms / FedShuffle and FedShuffleMVR Objective-Consistent Local Random Reshuffling for Federated Learning

FedShuffle and FedShuffleMVR Objective-Consistent Local Random Reshuffling for Federated Learning

Algorithms AIMech:FedShuffleAndFedShuffleMvrObjectiveConsistentLocalRandomReshufflingForFederatedLearning DRAFT

Aliases: FedShuffle, FedShuffleMVR, FedShuffleGen, Federated Random Reshuffling with Step-Size Scaling and Unbiased Aggregation

A family of federated local-epoch optimization algorithms with without-replacement Random Reshuffling (FedShuffle in Algorithm 1/3, its Momentum Variance Reduction extension FedShuffleMVR in Section 5.1, and the unifying parametrization FedShuffleGen in Algorithm 4) that eliminates objective inconsistency under heterogeneous client dataset sizes |D_i| and arbitrary proper client sampling S^r ~ S (with inclusion probabilities p_i = Pr[i in S]) by scaling each client i's local learning rate inversely by its dataset size (eta_{l,i}^r = eta_l^r / (E_i |D_i|)) and aggregating client updates with unbiased Horvitz-Thompson weights Delta^r = sum_{i in S^r} (w_i / p_i) Delta_i^r.

Identity Notes & Concept Scope Distinct from FedAvg with Random Reshuffling (FedAvgRR, which uses unscaled local step sizes and biased Sum-One aggregation w_i / sum_{j in S^r} w_j and converges to a mismatched objective), FedNova (Wang et al., NeurIPS 2020; which rescales aggregation weights rather than local step sizes, forcing a smaller worst-case local step size and not analyzing random reshuffling), and FedRR / LocalRR (which assume full client participation and identical dataset sizes).

Claims & Grounded Evidence

4 Claims

Mechanism #fedshuffle-inverse-dataset-step-size-scaling-and-horvitz-thompson-aggregation-mechanism

In each communication round r (Algorithm 1 & Algorithm 4), each sampled client i in S^r ~ S executes E_i local epochs over random permutations Pi_{i,e}^r of its local dataset D_i using scaled local step size eta_{l,i}^r = eta_l^r / (E_i |D_i|) (update y_{i,e,j}^r = y_{i,e,j-1}^r - (eta_l^r / |D_i|) nabla f_{i, Pi_{i,e,j-1}^r}(y_{i,e,j-1}^r)), and the server aggregates Delta_i^r = y_{i,E_i,|D_i|}^r - x^r via Delta^r = sum_{i in S^r} (w_i / p_i) Delta_i^r so that the effective optimized objective hat{f}(x) = sum_i hat{w}_i f_i(x) in Theorem E.1 Eq. (31) satisfies hat{w}_i = w_i exactly while permitting larger local step sizes than FedNova (Remark E.2).

supports Source: FedShuffle: Recipes for Better Use of Local Work in Federated Learning · Locator: Section 4.1-4.2 pp. 6-8 & Appendix E.1-E.2 Theorem E.1 / Remark E.2 pp. 34-36

Scope #fedshuffle-and-fedshufflemvr-reshuffling-variance-and-hessian-similarity-convergence-scope

Under L-smoothness and (sigma_i, P_i)-bounded variance (Theorem 5.1), FedShuffle reduces the local stochastic variance term to O(sigma^2 / (R^2 eta_g^2 E^2)) in strongly convex and O(sigma^{2/3} / (R^{2/3} eta_g^{2/3} E^{2/3})) in general convex and nonconvex regimes; furthermore, under delta-Hessian similarity (Assumption 3.5), FedShuffleMVR (Theorem 5.2) incorporates server momentum variance reduction Eq. (13)-(14) to achieve O((delta^{2/3} F^{2/3} (G^2 + sigma^2)^{1/3}) / R^{2/3} + (delta F + G^2) / R) nonconvex stationarity with E >= L / delta.

supports Source: FedShuffle: Recipes for Better Use of Local Work in Federated Learning · Locator: Section 5 Theorem 5.1 & Section 5.1 Theorem 5.2 pp. 8-10
supports Source: FedShuffle: Recipes for Better Use of Local Work in Federated Learning (arXiv abstract) · Locator: Abstract

Limitation #fedshuffle-uninterrupted-epoch-completion-or-hybrid-update-rescaling-limitation

Pure step-size scaling in FedShuffle assumes that participating clients complete their predefined number of local epochs E_i; if system timeouts truncate local epochs mid-round, hybrid post-hoc update rescaling via FedShuffleGen (Section 4.3 & Appendix F.1) is required to restore objective consistency.

supports Source: FedShuffle: Recipes for Better Use of Local Work in Federated Learning · Locator: Section 4.3 p. 8 & Appendix F.1 Figure 4 pp. 43-44

Application #fedshuffle-heterogeneous-cross-device-language-and-vision-training-application

Applied to heterogeneous cross-device federated training of LSTM character models on Shakespeare and ResNet18 classifiers on CIFAR-100 with imbalanced local datasets and without-replacement epoch shuffling.

supports Source: FedShuffle: Recipes for Better Use of Local Work in Federated Learning · Locator: Section 6.2 Tables 2-3 & Figure 2 pp. 11-12

⚠️ Curated Limitations & Negative Results

Pure local step-size scaling requires clients to finish their scheduled local epochs E_i; mid-epoch client timeouts require hybrid FedShuffleGen update rescaling.
Unbiased aggregation w_i / p_i requires knowing each participating client's sampling probability p_i.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:FederatedLearning` Federated Learning	narrow_match	FedShuffle and FedShuffleMVR are federated learning algorithms incorporating local random reshuffling, dataset-size step scaling, and unbiased client-sampling aggregation.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`r565-primary-pdf`	FedShuffle: Recipes for Better Use of Local Work in Federated Learning Samuel Horvath, Maziar Sanjabi, Lin Xiao, Peter Richtarik, Michael Rabbat	primary paper full_text	ID: https://api.openalex.org/works/https://doi.org/10.48550/arXiv.2204.13169 sha256:8fc921fcd2da…
`r565-arxiv-abs`	FedShuffle: Recipes for Better Use of Local Work in Federated Learning (arXiv abstract) Samuel Horvath, Maziar Sanjabi, Lin Xiao, Peter Richtarik, Michael Rabbat	primary paper abstract_only	ID: https://arxiv.org/abs/2204.13169 sha256:9c1edf8ae2f4…
`r565-metadata-cr`	FedShuffle: Recipes for Better Use of Local Work in Federated Learning (Crossref metadata) Samuel Horvath, Maziar Sanjabi, Lin Xiao, Peter Richtarik, Michael Rabbat	primary paper abstract_only	ID: https://api.openalex.org/works/https://doi.org/10.48550/arXiv.2204.13169 sha256:1871336b7685…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

Created: 2026-10-19T10:48:00Z

Updated: 2026-10-19T10:48:00Z

Source File: data/curated/FedShuffleAndFedShuffleMvrObjectiveConsistentLocalRandomReshufflingForFederatedLearning.yaml · Schema: curated_concept.yaml

Explore across X-Mech

Related computational & biological Mechs: Embedding Map Network Graph ProteinTraitsMech (ESM-2 pLM) DUFMech (Domain pLM) TraitMech CultureMech All 14 X-Mech Repositories