Home / Curated / Algorithms / GradSkip and GradSkip+ Communication-Accelerated Local Gradient Methods with Gradient Skipping

GradSkip and GradSkip+ Communication-Accelerated Local Gradient Methods with Gradient Skipping

Algorithms AIMech:GradSkipAndGradSkipPlusCommunicationAcceleratedLocalGradientMethodsWithGradientSkipping DRAFT

Aliases: GradSkip, GradSkip+, GradSkip Local Gradient Skipping Algorithm, Communication-Accelerated Local Gradient Method with Gradient Skipping

A family of communication-accelerated distributed local gradient methods (GradSkip in Algorithm 2 and its generalized compression-operator formulation GradSkip+ in Algorithm 3) that augment ProxSkip/Scaffnew's randomized consensus-skipping probability p with client-specific local gradient skipping probabilities q_i in (0, 1], whereby client i skips computing its true local gradient nabla f_i(x_i^t) with probability 1 - q_i (substituting its local shift control variate h_i^t for a fake local step hat{x}_i^{t+1} = x_i^t) and reduces expected per-client local gradient evaluations per communication round from 1/p to min{1/p, 1/(1 - q_i)} without degrading the accelerated O(sqrt(kappa_max) log(1/eps)) communication complexity.

Identity Notes & Concept Scope Distinct from ProxSkip / Scaffnew (Mishchenko et al., ICML 2022; which sets q_i = 1 for all clients and forces every client to compute 1/p local gradients per communication round regardless of local condition number kappa_i = L_i / mu). GradSkip and GradSkip+ (Maranjyan, Safaryan, & Richtarik, arXiv:2210.16402) decouple local gradient computation frequency q_i from communication frequency p.

Claims & Grounded Evidence

4 Claims

Mechanism #gradskip-coupled-bernoulli-communication-and-local-gradient-skipping-mechanism

In GradSkip (Algorithm 2), at each iteration t the server flips a global coin theta_t ~ Bernoulli(p); when theta_t = 1 (communication round), every client i sets lambda_i^t = 1, evaluates nabla f_i(x_i^t), takes step hat{x}_i^{t+1} = x_i^t - gamma (nabla f_i(x_i^t) - h_i^t), averages x_i^{t+1} = (1/n) sum_j (hat{x}_j^{t+1} - (gamma/p) h_j^t), and updates its control variate h_i^{t+1} = h_i^t + (p/gamma)(x_i^{t+1} - hat{x}_i^{t+1}); when theta_t = 0 (local round), each client independently flips eta_i^t ~ Bernoulli(q_i) and skips computing nabla f_i(x_i^t) whenever eta_i^t = 0 by substituting tilde{g}_i^t = h_i^t so hat{x}_i^{t+1} = x_i^t.

supports Source: GradSkip: Communication-Accelerated Local Gradient Methods with Better Computational Complexity · Locator: Section 4 Algorithm 2 & Lemma 4.1 pp. 5-6

Scope #gradskip-heterogeneous-condition-number-computational-reduction-scope

For L_i-smooth mu-strongly convex local objectives with condition numbers kappa_i = L_i / mu and kappa_max = max_i kappa_i (Theorem 4.3 & Section 4.3 Equations 11-13), choosing gamma = 1 / L_max, p = 1 / sqrt(kappa_max), and q_i = (1 - 1/kappa_max)(kappa_i / kappa_max) contracts the Lyapunov function Psi^t at rate (1 - 1/kappa_max), preserving Scaffnew's accelerated O(sqrt(kappa_max) log(1/eps)) communication rounds while reducing client i's expected local gradient computations per communication round to E[tau_i] = (1 - p(1 - q_i)) / (p + q_i - p q_i) <= min{1/p, 1/(1 - q_i)} (Lemma B.1).

supports Source: GradSkip: Communication-Accelerated Local Gradient Methods with Better Computational Complexity · Locator: Section 4.2 Theorem 4.3, Section 4.3 Equations (11)-(13) pp. 6-7 & Appendix B Lemma B.1 p. 14
supports Source: GradSkip: Communication-Accelerated Local Gradient Methods with Better Computational Complexity (arXiv abstract) · Locator: Abstract

Limitation #gradskip-strong-convexity-and-synchronized-communication-trigger-limitation

The linear convergence rate O(sqrt(kappa_max) log(1/eps)) and condition-number-matched skipping schedule q_i require mu-strong convexity (Assumption 3.2) and a shared global Bernoulli communication coin theta_t ~ Bernoulli(p) across participating clients.

supports Source: GradSkip: Communication-Accelerated Local Gradient Methods with Better Computational Complexity · Locator: Section 3 Assumptions 3.1-3.2 p. 4 & Algorithm 2 Line 4 p. 5

Application #gradskip-heterogeneous-federated-optimization-with-unequal-client-compute-application

Applied to federated regularized logistic regression across clients with heterogeneous data smoothness constants L_i and unequal local computational speeds.

supports Source: GradSkip: Communication-Accelerated Local Gradient Methods with Better Computational Complexity · Locator: Section 6 Experiments pp. 9-10

⚠️ Curated Limitations & Negative Results

Requires mu-strong convexity for the accelerated linear convergence rate and condition-number-matched local gradient skipping probabilities.
Relies on a shared global Bernoulli communication coin across participating clients.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:FederatedLearning` Federated Learning	related_match	GradSkip and GradSkip+ are communication-accelerated federated local gradient methods with client-adaptive local gradient skipping.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`r562-primary-pdf`	GradSkip: Communication-Accelerated Local Gradient Methods with Better Computational Complexity Artavazd Maranjyan, Mher Safaryan, Peter Richtarik	primary paper full_text	ID: https://api.openalex.org/works/https://doi.org/10.48550/arXiv.2210.16402 sha256:561cb129942c…
`r562-arxiv-abs`	GradSkip: Communication-Accelerated Local Gradient Methods with Better Computational Complexity (arXiv abstract) Artavazd Maranjyan, Mher Safaryan, Peter Richtarik	primary paper abstract_only	ID: https://arxiv.org/abs/2210.16402 sha256:bcc259afcad4…
`r562-metadata-cr`	GradSkip: Communication-Accelerated Local Gradient Methods with Better Computational Complexity (Crossref metadata) Artavazd Maranjyan, Mher Safaryan, Peter Richtarik	primary paper abstract_only	ID: https://api.openalex.org/works/https://doi.org/10.48550/arXiv.2210.16402 sha256:36b3eceb98a7…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

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

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

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