AdaComp (Adaptive Residual Gradient Compression)
Algorithms AIMech:AdaCompAdaptiveResidualGradientCompression DRAFT
Aliases: AdaComp, Adaptive Residual Gradient Compression, AdaComp Gradient Compression, Adaptive Residual Gradient Compression Scheme
An O(N) sorting-free residual gradient compression algorithm for data-parallel distributed deep learning that updates each layer's accumulated residual gradient G = residue + dW and forms a soft-threshold comparison vector H = G + dW = residue + 2 dW, uniformly partitions G into fixed-length bins of size L_T, computes each bin's local maximum absolute value g_max(i) = max_{j in bin i} |G(index)|, transmits and quantizes all bin entries satisfying |H(index)| >= g_max(i) into a sign bit times a single layer-wide scale factor equal to the mean of g_max across all bins, and retains the quantization error G(index) - G_q(index) and all untransmitted bin entries in residue(index) for the next mini-batch.
Identity Notes & Concept Scope
Distinct from 1-bit SGD (AIMech:OneBitStochasticGradientDescent, Seide et al. 2014) and TernGrad (AIMech:TernGradTernaryGradients, Wen et al. 2017), which quantize dense gradient vectors without local-bin sparsity selection and either diverge on convolutional layers when combined with FC compression or cap compression at 16x. Distinct from fixed-threshold compression (Strom 2015), fixed-percentage global top-k sorting (Dryden et al. 2016), and Deep Gradient Compression (AIMech:DeepGradientCompression, Lin et al. 2018), which rely on global thresholding or sorting rather than O(N) localized bin sampling with the self-adjusting soft threshold |residue + 2 dW| >= g_max(i).
Claims & Grounded Evidence
4 Claims
Mechanism
#r629-local-bin-soft-threshold-and-mean-gmax-quantization
For each layer, AdaComp computes the updated residual gradient G = residue + dW and the doubled-gradient probe H = G + dW = residue + 2 dW, divides G into uniform bins of length L_T, finds each bin's local maximum magnitude g_max(i), and transmits every element satisfying |H(index)| >= g_max(i) quantized as G_q(index) = sign(G(index)) * s where s = (1 / B) sum_{i=1}^B g_max(i) is the layer-wide mean of the bin maxima, updating residue(index) <- G(index) - G_q(index) for transmitted elements and residue(index) <- G(index) for untransmitted elements in O(N) time without sorting (Algorithm 2).
Mechanism
#r629-self-adjusting-sparsity-prevents-residual-explosion
Unlike hard Local Selection (LS) without a soft threshold—which transmits only a fixed number of bin maxima and suffers a positive-feedback loop at L_T >= 300 where untransmitted residual gradients (RG) and weight gradients (dW) grow exponentially to [-240K, 239K] and cause model divergence—AdaComp's soft threshold |residue + 2 dW| >= g_max(i) automatically transmits more elements in early epochs (when residues are small relative to dW) and drains clusters of near-maximal residues together, bounding residual gradients within [-0.015, 0.015] even at L_T = 5000 (~2000x compression, Figures 4-6).
Application
#r629-conv-40x-and-fc-lstm-200x-compression-across-optimizers
Using fixed bin sizes of L_T = 50 for convolutional layers (encoded with 8-bit sparse-indexed ternarized representations for L_T < 64) and L_T = 500 for fully-connected and recurrent layers (encoded with 16-bit sparse-indexed ternarized representations), AdaComp selects an average of up to 5 elements per bin to achieve ~40x effective compression on convolutional layers and ~200x effective compression on fully-connected and LSTM layers across MNIST-CNN, CIFAR10-CNN (up to 128 learners), AlexNet, ResNet18, ResNet50 on ImageNet, BN50-DNN speech recognition, and Shakespeare LSTM under both momentum SGD and Adam without noticeable accuracy degradation (Table 2, Figures 2-3).
Limitation
#r629-minibatch-size-activity-and-variable-message-length
Increasing the per-learner mini-batch size increases input feature activity across bins so that more residues satisfy |residue + 2 dW| >= g_max(i), reducing the achievable effective compression rate at fixed accuracy (Figure 7a), and the number of transmitted elements varies dynamically across bins, layers, and epochs rather than guaranteeing a fixed per-step message size.
⚠️ Curated Limitations & Negative Results
- Achievable compression rate decreases as the local mini-batch size per learner increases due to higher input feature activity across bins (Figure 7a).
- Because the soft threshold |residue + 2 dW| >= g_max(i) adapts to local gradient activity, the number of transmitted non-zero elements varies across bins and mini-batches rather than producing a constant-size communication buffer.
- Requires selecting layer-type bin sizes L_T (empirically L_T = 50 for convolutional layers and L_T = 500 for fully-connected and LSTM layers) and switchover from 8-bit to 16-bit sparse index representations when L_T >= 64.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:ArtificialNeuralNetwork
Artificial Neural Network
|
related_match | AdaComp is a distributed gradient compression method for data-parallel training of convolutional, recurrent, and fully-connected neural networks. |
Evidence Sources & Primary Literature
3 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
r629-primary-pdf
|
Chia-Yu Chen, Jungwook Choi, Daniel Brand, Ankur Agrawal, Wei Zhang, Kailash Gopalakrishnan
|
primary paper
full_text
|
ID: https://dblp.org/rec/conf/aaai/ChenCBAZG18
sha256:d35279b484d6…
|
r629-arxiv-abs
|
Chia-Yu Chen, Jungwook Choi, Daniel Brand, Ankur Agrawal, Wei Zhang, Kailash Gopalakrishnan
|
primary paper
abstract_only
|
ID: https://arxiv.org/abs/1712.02679
sha256:9803b3d6d0c4…
|
r629-metadata-cr
|
Chia-Yu Chen, Jungwook Choi, Daniel Brand, Ankur Agrawal, Wei Zhang, Kailash Gopalakrishnan
|
primary paper
abstract_only
|
ID: https://dblp.org/rec/conf/aaai/ChenCBAZG18
sha256:e48915beec8f…
|
Ontology & Grounding Topology
Open in interactive network graph →Curation Provenance
Curator: Antigravity
Method: ai_assisted
Model: Gemini
Created: 2026-10-19T11:52:00Z
Updated: 2026-10-19T11:52:00Z
Source File:
data/curated/AdaCompAdaptiveResidualGradientCompression.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