Home / Curated / Algorithms / Moniqua Modulo Quantized Communication for Decentralized SGD

Moniqua Modulo Quantized Communication for Decentralized SGD

Algorithms AIMech:MoniquaModuloQuantizedCommunicationForDecentralizedSgd DRAFT

Aliases: Moniqua, Modulo Quantized Communication in Decentralized SGD, Moniqua Decentralized Quantized SGD

A zero-additional-memory communication-quantization algorithm for decentralized stochastic optimization (Moniqua) that exploits an a priori inter-worker consensus bound ||x_{k,i} - x_{k,j}||_infty < theta_k and modular arithmetic z mod a in [-a/2, a/2) by transmitting only the quantized scaled modulo residue q_{k,i} = Q_delta((x_{k,i} / B_{theta_k}) mod 1) with B_{theta_k} = 2*theta_k / (1 - 2*delta) and reconstructing neighbor models via x_hat_{k,j} = (q_{k,j} * B_{theta_k} - x_{k,i}) mod B_{theta_k} + x_{k,i} with local bias cancellation x_{k+1/2,i} = x_{k,i} + sum_{j in N_i} (x_hat_{k,j} - x_hat_{k,i}) W_{ji}.

Identity Notes & Concept Scope Introduced by Yucheng Lu and Christopher De Sa (ICML 2020, PMLR Vol. 119, pp. 6415-6425; arXiv:2002.11787). Distinct from Choco-SGD (Koloskova et al., ICML 2019) and DCD/ECD-PSGD (Tang et al., NeurIPS 2018), which maintain neighbor model replicas incurring Theta(m * d) additional memory overhead; and distinct from DeepSqueeze / DoubleSqueeze (Tang et al., 2019), which maintain error-compensation buffers incurring Theta(n * d) memory overhead rather than memoryless modular-arithmetic residue quantization.

Claims & Grounded Evidence

4 Claims

Mechanism #moniqua-modular-residue-quantization-and-bias-cancellation-mechanism

Given ||x_{k,i} - x_{k,j}||_infty < theta_k and a quantizer Q_delta on [-1/2, 1/2)^d with L_infty error at most delta < 1/2, Moniqua sets B_{theta_k} = 2*theta_k / (1 - 2*delta), broadcasts q_{k,i} = Q_delta((x_{k,i} / B_{theta_k}) mod 1), reconstructs x_hat_{k,j} = (q_{k,j} * B_{theta_k} - x_{k,i}) mod B_{theta_k} + x_{k,i} with error ||x_hat_{k,j} - x_{k,j}||_infty <= delta * B_{theta_k} = theta_k * 2*delta / (1 - 2*delta), and subtracts the local self-quantization term x_hat_{k,i} = q_{k,i} * B_{theta_k} - (x_{k,i} mod B_{theta_k}) + x_{k,i} so that global model averages remain unbiased.

supports Source: Moniqua: Modulo Quantized Communication in Decentralized SGD · Locator: Section 4 Algorithm 1, Equation (5), Lemma 2, & Appendix B, pp. 4-5, 15-16

Scope #moniqua-zero-extra-memory-asymptotic-rate-and-1bit-scope

Requires zero additional memory beyond baseline D-PSGD, supports biased and 1-bit quantizers (via slack mixing matrix W_bar = gamma * W + (1 - gamma) * I in Theorem 3) as well as non-constant step sizes and extensions to D^2 (Theorem 4) and asynchronous AD-PSGD (Theorem 5), achieving the same O(sigma / sqrt(n*K)) asymptotic non-convex convergence rate as full-precision D-PSGD with O(log log n) bits per coordinate.

supports Source: Moniqua: Modulo Quantized Communication in Decentralized SGD · Locator: Table 1, Section 4 Theorems 2-3 & Corollary 1, Section 5 Theorems 4-5, pp. 3, 6-8

Limitation #moniqua-apriori-discrepancy-bound-wraparound-limitation

Correct modular recovery requires the actual inter-worker coordinate difference |x_{k,i} - x_{k,j}| to remain strictly below the a priori bound theta_k; if theta_k is underestimated, modular wrap-around introduces O(B_{theta_k}) reconstruction errors unless detected by hash verification.

supports Source: Moniqua: Modulo Quantized Communication in Decentralized SGD · Locator: Section 4 Lemma 2 & Section 6 Choosing theta empirically, pp. 5, 11

Application #moniqua-low-bandwidth-cifar-resnet-vgg-application

Applied to 1-bit, 2-bit, and 8-bit quantized decentralized training of ResNet-20, ResNet-110, and VGG-16 on CIFAR-10 across bandwidth- and latency-constrained networks, including heterogeneous D^2 and asynchronous AD-PSGD.

supports Source: Moniqua: Modulo Quantized Communication in Decentralized SGD · Locator: Section 6 Experiments, Figures 1-2 & Table 2, pp. 8-10

⚠️ Curated Limitations & Negative Results

Sensitive to underestimation of the inter-worker discrepancy bound theta_k, which can cause modular wrap-around.
Theoretical analysis assumes uniform L_infty gradient bound ||g_tilde_{k,i}||_infty <= G_infty.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:FederatedLearning` Federated Learning	related_match	AIO:FederatedLearning covers distributed learning with communication constraints, whereas Moniqua is a memoryless modular-arithmetic communication-quantization protocol for decentralized gossip SGD.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`r555-primary-pdf`	Moniqua: Modulo Quantized Communication in Decentralized SGD Yucheng Lu, Christopher De Sa	primary paper full_text	ID: https://dblp.org/rec/conf/icml/LuS20 sha256:8f8280653587…
`r555-arxiv-abs`	Moniqua: Modulo Quantized Communication in Decentralized SGD (arXiv abstract) Yucheng Lu, Christopher De Sa	primary paper abstract_only	ID: https://arxiv.org/abs/2002.11787 sha256:e1e1d0e9d0da…
`r555-metadata-cr`	Moniqua: Modulo Quantized Communication in Decentralized SGD (Crossref metadata) Yucheng Lu, Christopher De Sa	primary paper abstract_only	ID: https://dblp.org/rec/conf/icml/LuS20 sha256:347047c9e8a0…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

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

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

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