AdaCGD and Ada3PC Adaptive Three-Point Compression for Distributed Optimization
Algorithms AIMech:AdaCgdAndAda3PcAdaptiveThreePointCompressionForDistributedOptimization DRAFT
Aliases: Ada3PC, AdaCGD, 3PC-BD, Adaptive Three Point Compressor, Adaptive Compressed Gradient Descent
An adaptive communication compression framework and family of distributed optimization methods introduced by Makarenko, Gasanov, Islamov, Sadiev, and Richtárik (2022) that dynamically select the compression operator or compression level at every iteration and worker. Given a bank of m Three Point Compressors (3PC) {C_{h,y}^j}_{j=1}^m with parameters {(A_j, B_j)}_{j=1}^m and arbitrary user-specified trigger predicates {P_j(h, y, x)}_{j=1}^{m-1}, the Adaptive Three Point Compressor (Ada3PC, Definition 3) selects C_{h,y}^{ad}(x) = C_{h,y}^j(x) for the first index j where P_j(h, y, x) holds (or C_{h,y}^m(x) otherwise), and Adaptive Compressed Gradient Descent (AdaCGD, Definition 4) instantiates Ada3PC with m sorted EF21 contractive compressors (alpha_1 <= ... <= alpha_m) and lazy relative-variation predicates ||x - C_{h,y}^{EF,j}(x)||^2 <= zeta ||x - y||^2 to adaptively adjust the transmitted message size.
Identity Notes & Concept Scope
Distinct from fixed-parameter Three Point Compressors (3PC, Richtárik et al. 2022, which use a single static 3PC operator or a single binary lazy-aggregation threshold) and distinct from heuristic adaptive gradient compression schemes lacking error-feedback convergence guarantees: Ada3PC proves closure of the 3PC class under arbitrary data-dependent switching among m distinct 3PC compressors with worst-case constants A_min = min_j A_j and B_max = max_j B_j (Lemma 2), and further extends 3PC to convex objectives (Theorem 5) and bidirectional server-and-worker 3PC compression (3PC-BD, Algorithm 2, Theorem 6).
Claims & Grounded Evidence
4 Claims
Mechanism
#ada3pc-closure-under-arbitrary-predicate-switching
Given m Three Point Compressors {C_{h,y}^j}_{j=1}^m satisfying E[||C_{h,y}^j(x) - x||^2] <= (1 - A_j)||h - y||^2 + B_j||x - y||^2 with A_j in (0, 1] and B_j >= 0, Lemma 2 proves that the adaptive selector C_{h,y}^{ad}(x) (Definition 3) is itself a valid Three Point Compressor for any choice of switching predicates {P_j(h, y, x)}_{j=1}^{m-1}, with parameters A_min = min_{j in [m]} A_j and B_max = max_{j in [m]} B_j.
Mechanism
#adacgd-multi-level-ef21-lazy-variation-trigger-design
AdaCGD (Definition 4) orders m contractive compressors {C_j}_{j=1}^m by increasing contractivity 0 < alpha_1 <= alpha_2 <= ... <= alpha_m <= 1, wraps each into an EF21 compressor C_{h,y}^{EF,j}(x) = h + C_j(x - h), first tests the zero-communication skip condition ||x - h||^2 <= zeta ||x - y||^2, and otherwise selects the most aggressive (smallest j) compressor satisfying ||x - C_{h,y}^{EF,j}(x)||^2 <= zeta ||x - y||^2 (defaulting to C_{h,y}^{EF,m}(x) if none satisfies the threshold), which by Corollary 1 is a 3PC compressor with A_min = 1 - sqrt(1 - alpha_1) and B_max = max(zeta, (1 - alpha_1)/(1 - sqrt(1 - alpha_1))).
Scope
#three-pc-convex-and-bidirectional-nonconvex-convergence-theorems
Theorem 5 establishes the first general convex convergence rate E[f(x^T) - f(x*)] = O(1/T) for 3PC methods under L_i-smooth convex functions with step size gamma in (0, 1/(L + L_max sqrt(B/A))), while Algorithm 2 (3PC-BD) applies 3PC compressors C^w on workers (A_w, B_w) and C^M on the master broadcast (A_M, B_M), achieving O(1/T) nonconvex stationarity E[||nabla f(hat{x}^T)||^2] = O(1/T) under Theorem 6.
Limitation
#adacgd-trial-compression-overhead-and-worst-case-step-size-limitation
Evaluating the AdaCGD trigger condition ||x - C_{h,y}^{EF,j}(x)||^2 <= zeta ||x - y||^2 requires computing candidate compressed vectors across up to m compression levels locally on each worker (though for Top-k families a single coordinate-magnitude sort suffices for all k_1 < ... < k_m), and the theoretical step-size bound in Lemma 2 depends on the worst-case constants A_min = min_j A_j and B_max = max_j B_j across the compressor bank.
⚠️ Curated Limitations & Negative Results
- Theoretical step-size and complexity bounds via Lemma 2 depend on the worst-case constants A_min = min_j A_j and B_max = max_j B_j of the compressor bank.
- Evaluating the adaptive predicate P_j(h, y, x) across m general compressors can incur up to m local compression evaluations per step unless the bank shares a common sorting/quantization structure such as Top-k.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:FederatedLearning
Federated Learning
|
related_match | Ada3PC, AdaCGD, and 3PC-BD provide adaptive uplink and bidirectional gradient compression for distributed and federated optimization. |
Evidence Sources & Primary Literature
3 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
r568-primary-pdf
|
Maksim Makarenko, Elnur Gasanov, Rustem Islamov, Abdurakhmon Sadiev, Peter Richtárik
|
primary paper
full_text
|
ID: https://api.openalex.org/works/W4308015852
sha256:5adbb553c5bb…
|
r568-arxiv-abs
|
Maksim Makarenko, Elnur Gasanov, Rustem Islamov, Abdurakhmon Sadiev, Peter Richtárik
|
primary paper
abstract_only
|
ID: https://arxiv.org/abs/2211.00188
sha256:5986f6b1517a…
|
r568-metadata-cr
|
Maksim Makarenko, Elnur Gasanov, Rustem Islamov, Abdurakhmon Sadiev, Peter Richtárik
|
primary paper
abstract_only
|
ID: https://api.openalex.org/works/W4308015852
sha256:db15676a0493…
|
Ontology & Grounding Topology
Open in interactive network graph →Curation Provenance
Curator: Antigravity
Method: ai_assisted
Model: Gemini
Created: 2026-10-19T10:51:00Z
Updated: 2026-10-19T10:51:00Z
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