Home / Curated / Algorithms / ATOMO (Atomic Sparsification for Communication-Efficient Distributed Learning)

ATOMO (Atomic Sparsification for Communication-Efficient Distributed Learning)

Algorithms AIMech:AtomoAtomicSparsificationForDistributedLearning DRAFT

Aliases: ATOMO, Atomic Sparsification for Distributed Learning, Spectral-Atomo and Entry-wise Atomo

A general unbiased gradient sparsification framework (Wang et al. 2018, Section 3, Algorithm 1) that expresses a gradient tensor g in R^d in an atomic basis A = {a_i}_{i=1}^n (||a_i|| = 1) as g = sum_{i=1}^n lambda_i a_i (covering entry-wise coordinate bases, singular-value rank-1 outer-product bases, and Fourier/wavelet bases), samples each atom independently via t_i ~ Bernoulli(p_i) under a total sparsity budget sum_{i=1}^n p_i <= s to form the unbiased estimator g_hat = sum_{i=1}^n (lambda_i t_i / p_i) a_i, and computes the exact variance-minimizing inclusion probabilities p_i^* in closed form via KKT water-filling.

Identity Notes & Concept Scope Distinct from deterministic low-rank power-iteration compression PowerSGD (AIMech:PowerSgdLowRankGradientCompressionWithErrorFeedback, Vogels et al. 2019), which computes a biased fixed-rank approximation via orthogonalized power iteration and requires error feedback, and from coordinate-only quantization QSGD (AIMech:QsgdQuantizedStochasticGradientDescentWithEliasCoding, Alistarh et al. 2017), which is restricted to the standard Euclidean coordinate basis rather than general atomic/spectral decompositions with KKT water-filling probabilities.

Claims & Grounded Evidence

4 Claims

Mechanism #r420-kkt-water-filling-variance-minimization-and-s-balanced-closed-form

Minimizing E[||g - g_hat||^2] = sum_{i=1}^n lambda_i^2 (1 / p_i - 1) (Lemma 2) subject to 0 < p_i <= 1 and sum_{i=1}^n p_i <= s yields p_i = min(1, |lambda_i| s / ||lambda||_1) with minimum variance ||lambda||_1^2 / s - ||lambda||_2^2 whenever lambda is s-balanced (s <= ||lambda||_1 / ||lambda||_infty, Lemma 4), and otherwise solves the exact water-filling active set in O(n log n) time by sorting |lambda_{(1)}| >= ... >= |lambda_{(n)}| and capping leading atoms at p_i = 1 (Algorithm 1, Theorem 5).

supports Source: ATOMO: Communication-efficient Learning via Atomic Sparsification · Locator: Section 3.1 Minimizing Variance (Lemmas 2-4, Theorem 5, Algorithm 1) & Appendix A.1-A.4

Mechanism #r420-spectral-atomo-nuclear-norm-dominance-over-entrywise-sparsification

For a matrix gradient X in R^{n x m} with singular value decomposition X = sum_{i=1}^{min(n,m)} sigma_i u_i v_i^T, Spectral-Atomo achieves variance ||X||_*^2 / s_2 - ||X||_F^2 (Theorem 7), and Lemma 8 proves ||X||_* <= ||X||_{1,1} <= sqrt(n m) ||X||_* with equality ||X||_* = ||X||_{1,1} / sqrt(n + m) on rank-1 flat matrices, establishing up to an O(n + m) communication reduction at equal estimator variance over Entry-wise Atomo.

supports Source: ATOMO: Communication-efficient Learning via Atomic Sparsification · Locator: Section 5 Entry-wise vs. SVD Sparsification (Theorem 7, Lemma 8) & Appendix A.6

Limitation #r420-svd-decomposition-computational-overhead-limitation

Spectral-Atomo requires computing the singular value decomposition of each layer's gradient matrix on every worker at each iteration, incurring O(min(m n^2, m^2 n)) local computation overhead.

supports Source: ATOMO: Communication-efficient Learning via Atomic Sparsification · Locator: Section 5-6 Discussion of SVD Overhead and Truncated SVD

Application #r420-distributed-resnet18-vgg11-and-svm-training-application

Applied to distributed synchronous SGD training of ResNet-18, VGG-11, and multi-class SVMs on CIFAR-10, CIFAR-100, SVHN, and ImageNet, reducing communication time and faster wall-clock convergence than QSGD and TernGrad.

supports Source: ATOMO: Communication-efficient Learning via Atomic Sparsification · Locator: Section 6 Experiments (Figures 1-4, Table 1), pp. 9856-9859

⚠️ Curated Limitations & Negative Results

Computing exact full SVD per layer in Spectral-Atomo is computationally expensive for high-dimensional weight matrices.
Unbiased variance grows as ||lambda||_1^2 / s when the atomic budget s is very small and no error-feedback buffer is used.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:SparseLearning` Sparse Learning	related_match	ATOMO performs variance-optimal randomized atomic and spectral sparsification of gradient tensors for distributed learning.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`r420-primary-pdf`	ATOMO: Communication-efficient Learning via Atomic Sparsification Hongyi Wang, Scott Sievert, Shengchao Liu, Zachary Charles, Dimitris Papailiopoulos, Stephen Wright	primary paper full_text	ID: https://papers.nips.cc/paper/2018/hash/33b3214d792caf311e1f00fd22b392c5-Abstract.html sha256:58220aa6b204…
`r420-arxiv-abs`	ATOMO: Communication-efficient Learning via Atomic Sparsification (arXiv abstract) Hongyi Wang, Scott Sievert, Shengchao Liu, Zachary Charles, Dimitris Papailiopoulos, Stephen Wright	primary paper abstract_only	ID: https://arxiv.org/abs/1806.04090 sha256:42f631cd1c59…
`r420-metadata-cr`	ATOMO: Communication-efficient Learning via Atomic Sparsification (Crossref metadata) Hongyi Wang, Scott Sievert, Shengchao Liu, Zachary Charles, Dimitris Papailiopoulos, Stephen Wright	primary paper abstract_only	ID: https://papers.nips.cc/paper/2018/hash/33b3214d792caf311e1f00fd22b392c5-Abstract.html sha256:42fbb1752d6d…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

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

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

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