Home / Curated / Algorithms / CompressedScaffnew

CompressedScaffnew

Algorithms AIMech:CompressedScaffnewDoublyAcceleratedLocalTrainingAndCompression DRAFT

Aliases: CompressedScaffnew Algorithm, Doubly Accelerated Scaffnew with Permutation Mask Compression

A doubly accelerated distributed and federated optimization algorithm for minimizing f(x) = (1/n) sum_{i=1}^n f_i(x) across n heterogeneous clients without any data-similarity assumption. CompressedScaffnew integrates Scaffnew/ProxSkip probabilistic local gradient updates x_hat_i^t = x_i^t - gamma (nabla f_i(x_i^t) - h_i^t) with a shared random column-permuted binary template mask Q^t in {0,1}^{d x n} having exactly s in {2, ..., n} active ones per coordinate row when communication is triggered (with probability p in (0, 1]). At communication rounds, each client i transmits only the entries of x_hat_i^t where q_{k,i}^t = 1, the server broadcasts the row average x_bar_k^t = (1/s) sum_{j=1}^n q_{k,j}^t x_hat_{j,k}^t, and each client updates its local control variate entry h_{i,k}^{t+1} = h_{i,k}^t + (p eta / gamma)(x_bar_k^t - x_hat_{i,k}^t) only on its active coordinates (q_{k,i}^t = 1), preserving sum_{i=1}^n h_i^t = 0 and achieving O(d * sqrt(kappa * n / (s (s - 1))) log(1/epsilon)) communicated floats.

Identity Notes & Concept Scope Distinct from uncommitted or uncompressed Scaffnew/ProxSkip (which requires full d-dimensional vector communication at every triggered sync round) and from independent random sparsifiers (which break Scaffnew's zero-sum control-variate invariant sum_{i=1}^n h_i^t = 0). CompressedScaffnew couples local training with a shared s-active-per-row permutation mask so that the control-variate updates sum to zero coordinatewise while compressing uplink communication by factor s/n.

Claims & Grounded Evidence

4 Claims

Mechanism #shared-row-regular-permutation-mask-and-zero-sum-control-variates

At each communication event (theta^t = 1 with probability p), CompressedScaffnew samples a binary mask Q^t = (q_1^t, ..., q_n^t) in {0,1}^{d x n} by uniformly permuting the columns of a template matrix having exactly s ones in every row (sum_{i=1}^n q_{k,i}^t = s for all k = 1..d) and balanced column sums in {floor(s d / n), ceil(s d / n)}. Because the server averages x_bar_k^t = (1/s) sum_{j: q_{k,j}^t=1} x_hat_{j,k}^t and only active clients update h_{i,k}^{t+1} = h_{i,k}^t + (p eta / gamma)(x_bar_k^t - x_hat_{i,k}^t), the invariant sum_{i=1}^n h_i^t = 0 holds exactly for all t >= 0 whenever initialized with sum_{i=1}^n h_i^0 = 0.

supports Source: Doubly Accelerated Federated Learning: Improved Rate with Local Training and Communication Compression · Locator: Section 2, Algorithm 1, Figure 1, and Equations (5)-(7), pp. 4-6

Mechanism #linear-lyapunov-contraction-with-coupled-local-and-compression-factor

Theorem 1 proves that for L-smooth, mu-strongly convex local functions f_i, stepsize 0 < gamma < 2/L, mixing parameter 0 < eta <= (n (s - 1)) / (s (n - 1)), and s >= 2, the Lyapunov potential Psi^t = (1/gamma) sum_{i=1}^n ||x_i^t - x^*||^2 + (gamma / (p^2 eta)) ((n - 1) / (s - 1)) sum_{i=1}^n ||h_i^t - h_i^*||^2 contracts linearly as E[Psi^{t+1} | F^t] <= rho Psi^t with rho = max{(1 - gamma mu)^2, (gamma L - 1)^2, 1 - (p^2 eta (s - 1)) / (n - 1)} < 1.

supports Source: Doubly Accelerated Federated Learning: Improved Rate with Local Training and Communication Compression · Locator: Section 3.1, Theorem 1, p. 7, Equations (8)-(10)

Application #double-acceleration-in-condition-number-and-dimension

By choosing gamma = Theta(1/L), eta = (n (s - 1)) / (s (n - 1)), and communication probability p = min{1, sqrt((mu / L) * (s (n - 1)^2) / (n (s - 1)^2))}, CompressedScaffnew achieves iteration complexity O((kappa + (n - 1)/(s - 1) + sqrt(kappa * (n/s) * ((n - 1)/(s - 1))^2)) log(1/epsilon)) and uplink communication complexity O((d + (d s / n) sqrt(kappa * n / (s (s - 1)))) log(1/epsilon)) floats per client (which reduces to O((d + (d / n) sqrt(kappa n)) log(1/epsilon)) for constant s >= 2).

supports Source: Doubly Accelerated Federated Learning: Improved Rate with Local Training and Communication Compression · Locator: Section 1.2, Table 1, p. 3; Section 3.1, Corollary 1 and Remark 1, pp. 7-8
supports Source: Doubly Accelerated Federated Learning: Improved Rate with Local Training and Communication Compression (Crossref metadata) · Locator: Bibliographic record

Limitation #minimum-two-active-clients-per-coordinate-requirement

CompressedScaffnew requires at least s >= 2 active clients per coordinate row at every communication event so that the inter-client difference x_bar_k^t - x_hat_{i,k}^t is non-zero and eta = (n (s - 1)) / (s (n - 1)) > 0; if s = 1, x_bar_k^t equals the single active client's entry and consensus cannot progress.

supports Source: Doubly Accelerated Federated Learning: Improved Rate with Local Training and Communication Compression · Locator: Section 2, p. 6 and Section 3.1, Theorem 1, p. 7

⚠️ Curated Limitations & Negative Results

Requires at least s >= 2 clients to transmit each coordinate at every communication round so that inter-client differences can update the control variates.
Requires shared randomness (or a synchronized seed) across clients to generate the column-permuted template mask Q^t.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:FederatedLearning` Federated Learning	broad_match	CompressedScaffnew is a federated optimization algorithm combining local client training and uplink communication compression.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`r576-primary-pdf`	Doubly Accelerated Federated Learning: Improved Rate with Local Training and Communication Compression Laurent Condat, Ivan Agarsky, Peter Richtarik	primary paper full_text	ID: https://dblp.org/search/publ/api?q=CompressedScaffnew&format=json sha256:b1e7148496cf…
`r576-arxiv-abs`	Doubly Accelerated Federated Learning: Improved Rate with Local Training and Communication Compression (arXiv abstract) Laurent Condat, Ivan Agarsky, Peter Richtarik	primary paper abstract_only	ID: https://arxiv.org/abs/2210.13277 sha256:93c6a02944c3…
`r576-metadata-cr`	Doubly Accelerated Federated Learning: Improved Rate with Local Training and Communication Compression (Crossref metadata) Laurent Condat, Ivan Agarsky, Peter Richtarik	primary paper abstract_only	ID: https://dblp.org/search/publ/api?q=CompressedScaffnew&format=json sha256:ac2b9151a3b3…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

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

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

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