Home / Curated / Algorithms / FetchSGD (Count-Sketch Gradient Compression with Server Momentum and Error Accumulation)

FetchSGD (Count-Sketch Gradient Compression with Server Momentum and Error Accumulation)

Algorithms AIMech:FetchSgdCountSketchGradientCompressionWithServerMomentumAndErrorAccumulation DRAFT

Aliases: FetchSGD, FedSketchedSGD, Communication-Efficient Federated Learning with Count Sketching, Stateless Sketched SGD with Server-Side Momentum and Error Feedback

A stateless communication-efficient federated optimization algorithm (FetchSGD, Algorithm 1) in which each participating client i in [W] computes a local stochastic gradient g_i^t in R^d and uploads a linear Count Sketch S_i^t = S(g_i^t) (Algorithm 2); by exploiting the exact linearity S(g_1 + g_2) = S(g_1) + S(g_2), the central aggregator combines client sketches S^t = (1/W) sum_{i=1}^W S(g_i^t) = S((1/W) sum_i g_i^t) and maintains both heavy-ball momentum S_u^t = rho S_u^{t-1} + S^t and biased-compression error accumulation S_e^t = eta S_u^t + S_e^{t-1} directly inside server-side Count Sketches before extracting a k-sparse model update Delta^t = Top-k(U(S_e^t)) via median unsketching U, updating S_e^{t+1} = S_e^t - S(Delta^t) and w^{t+1} = w^t - Delta^t.

Identity Notes & Concept Scope Distinct from client-stateful error-feedback compression methods such as Sparsified SGD with Error Memory (AIMech:SparsifiedSgdWithErrorMemoryForKContractiveGradientCompression), PowerSGD (AIMech:PowerSgdLowRankGradientCompressionWithErrorFeedback), and EF21 (AIMech:Ef21MarkovCompressorErrorFeedbackForHeterogeneousNonconvexOptimization), which apply a non-linear biased compressor on each client and therefore must store per-client error accumulation vectors that are never re-introduced when federated clients participate only once, and from multi-step local update methods such as FedAvg and MIME (AIMech:MimeMimickingCentralizedStochasticAlgorithmsInFederatedLearning, which transmit uncompressed full-dimensional parameter vectors).

Claims & Grounded Evidence

4 Claims

Mechanism #r409-sketch-linearity-server-momentum-and-error-feedback-commutativity

Because the Count Sketch compression operator S: R^d -> R^{r x c} is linear (S(g_1 + g_2) = S(g_1) + S(g_2)) and bias is introduced only at the server during Top-k(U(S_e^t)) extraction, carrying out momentum S_u^t = rho S_u^{t-1} + S^t and error accumulation S_e^{t+1} = eta S_u^t + S_e^t - S(Delta^t) inside server-side sketches is mathematically equivalent to maintaining momentum and error feedback before compression across all clients while keeping clients completely stateless and invariant to partitioning N samples across 1 client or N single-sample clients.

supports Source: FetchSGD: Communication-Efficient Federated Learning with Sketching · Locator: Section 3.2 Algorithm (Algorithm 1), Section 5 Evaluation, and Appendix B.1 (Virtual Sequence Proof), pp. 4-5, 7, 21-22

Mechanism #r409-nonconvex-smooth-convergence-under-heavy-hitter-and-sliding-window-regimes

For L-smooth nonconvex objectives with bounded stochastic gradient norm G on non-IID client distributions, Theorem 1 proves that under Scenario 1 (tau-heavy hitters in q^t = eta(rho u^{t-1} + g^{t-1}) + e^{t-1}, Assumption 1) FetchSGD with step size eta = (1 - rho)/(2 L sqrt(T)) and O(log(dT/delta)/tau)-byte sketches achieves min_{t in [T]} E||nabla f(w^t)||^2 <= (4 L (f(w^0) - f^*) + G^2)/sqrt(T) + 2(1+tau)^2 G^2 / ((1-tau) tau^2 T), while Theorem 2 proves O(T^{-1/3}) convergence under Scenario 2 ((I, tau)-sliding heavy gradients, Definition 1 and Assumption 2) using sliding-window error accumulation sketches of size Theta(log(dT/delta)/tau^2).

supports Source: FetchSGD: Communication-Efficient Federated Learning with Sketching · Locator: Section 4.1-4.2 (Assumption 1, Theorem 1, Definition 1, Assumption 2, Theorem 2) & Appendix B.1-B.2, pp. 5-7, 21-27

Limitation #r409-heavy-hitter-assumption-and-unsketch-variance-limitation

Dimension-free O(T^{-1/2}) and O(T^{-1/3}) convergence rates in Theorems 1 and 2 rely on the existence of (tau, l_2^2)-heavy hitters along the optimization trajectory (without heavy hitters, worst-case unsketching variance scales as Theta(d), yielding O(d / sqrt(T)) in Appendix B.3), and practical deployment uses momentum factor masking and zeroing of extracted coordinates in S_e^t to stabilize ReLU networks.

supports Source: FetchSGD: Communication-Efficient Federated Learning with Sketching · Locator: Section 4.1-4.2, Section 5 Evaluation, and Appendix B.3, pp. 5-7, 27

Application #r409-non-iid-cifar10-cifar100-femnist-and-personachat-gpt2-application

Evaluated on extreme non-IID single-class-per-client CIFAR-10 (10,000 clients, ResNet9) and CIFAR-100 (50,000 clients, 1 image/client), FEMNIST (3,500 clients, 40M-parameter ResNet101), and one-shot PersonaChat language modeling (17,568 clients, 124M-parameter GPT2-small), achieving 3.9x-7.3x overall compression and 10x-100x upload compression while outperforming FedAvg and local Top-k.

supports Source: FetchSGD: Communication-Efficient Federated Learning with Sketching · Locator: Section 5.1-5.3 (Figures 3-5) & Appendix A (Table 1, Figures 6-9), pp. 7-9, 14-20

⚠️ Curated Limitations & Negative Results

Dimension-independent convergence rates depend on the presence of l2-heavy hitters in gradients or sliding windows.
Requires server-side unsketching over d parameters to identify the top-k update coordinates each round.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:FederatedLearning` Federated Learning	narrow_match	FetchSGD is a communication-efficient stateless FederatedLearning optimization algorithm based on linear Count Sketches.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`r409-primary-pdf`	FetchSGD: Communication-Efficient Federated Learning with Sketching Daniel Rothchild, Ashwinee Panda, Enayat Ullah, Nikita Ivkin, Ion Stoica, Vladimir Braverman, Joseph Gonzalez, Raman Arora	primary paper full_text	ID: https://proceedings.mlr.press/v119/rothchild20a.html sha256:10527fb7ba1b…
`r409-arxiv-abs`	FetchSGD: Communication-Efficient Federated Learning with Sketching (arXiv abstract) Daniel Rothchild, Ashwinee Panda, Enayat Ullah, Nikita Ivkin, Ion Stoica, Vladimir Braverman, Joseph Gonzalez, Raman Arora	primary paper abstract_only	ID: https://arxiv.org/abs/2007.07682 sha256:f0c942977872…
`r409-metadata-cr`	FetchSGD: Communication-Efficient Federated Learning with Sketching (Crossref metadata) Daniel Rothchild, Ashwinee Panda, Enayat Ullah, Nikita Ivkin, Ion Stoica, Vladimir Braverman, Joseph Gonzalez, Raman Arora	primary paper abstract_only	ID: https://proceedings.mlr.press/v119/rothchild20a.html sha256:77fa1da14aba…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

Created: 2026-10-19T08:12:00Z

Updated: 2026-10-19T08:12:00Z

Source File: data/curated/FetchSgdCountSketchGradientCompressionWithServerMomentumAndErrorAccumulation.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