ZO-COSMO: Index-Free One-Hop Mixing for Decentralized Zeroth-Order Optimization
Abstract
Sparse communication in decentralized zeroth-order learning requires compatible peer-state coordinates. We characterize this one-hop condition and develop \textsf{ZO-COSMO}, coupling two-query estimation with average-preserving masked consensus using q values per active link. Global supports serve all-neighbor mixing; matching updates require agreement only within each pair. We derive a sharp contraction-per-scalar bound within the matching class and convergence guarantees for the core and sparse-momentum updates. At fixed matching, exact moment identities characterize how shared directions preserve gradient-heterogeneity cancellation and redistribute estimation error and disagreement. Mechanism experiments cover unequal curvatures, noise, and sparse momentum. Further tests span $64$ synthetic agents and eight logical Qwen LoRA workers. At matched payload budgets, Qwen2-7B QNLI gains $3.65$ accuracy points over explicit-index Rand-k; edge-local updates gain $3.42$ and $2.53$ points over all-neighbor mixing on eight-worker complete and ring graphs. A matched-first-step ablation gives a $3.92$-point momentum benefit. Seed-aware and same-matching controls distinguish encoding, scheduling, and query correlation.
Related
- From Mixing to Tearing: Graph Decomposition in Decentralized Optimization via Message Passing
- Accelerated Stochastic Zeroth-Order Quasar-Convex Optimization
- Stochastic Lie-Bracket Approximations for Zeroth-Order Optimization on Manifolds
- Differentially Private Distributed Optimization via the Intrinsic Randomness of Zeroth-Order Estimators: Sampling Geometry, Convergence, and Privacy Guarantees
- Training with ML-labeled Data via Stochastic First- and Zeroth-Order Optimization
BibTeX
@misc{zhang2026zocosmo,
title = {{ZO-COSMO: Index-Free One-Hop Mixing for Decentralized Zeroth-Order Optimization}},
author = {Shengjun Zhang and Tingyi Liu and Heng Zhang and Dong Xie},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.27199},
eprint = {2609.27199},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.27199},
}
RIS
TY - UNPB
TI - ZO-COSMO: Index-Free One-Hop Mixing for Decentralized Zeroth-Order Optimization
AU - Shengjun Zhang
AU - Tingyi Liu
AU - Heng Zhang
AU - Dong Xie
PY - 2026
DA - 2026/09/23
PB - arXiv
DO - 10.48550/arxiv.2609.27199
UR - https://arxiv.org/abs/2609.27199
AB - Sparse communication in decentralized zeroth-order learning requires compatible peer-state coordinates. We characterize this one-hop condition and develop \textsf{ZO-COSMO}, coupling two-query estimation with average-preserving masked consensus using q values per active link. Global supports serve all-neighbor mixing; matching updates require agreement only within each pair. We derive a sharp contraction-per-scalar bound within the matching class and convergence guarantees for the core and sparse-momentum updates. At fixed matching, exact moment identities characterize how shared directions preserve gradient-heterogeneity cancellation and redistribute estimation error and disagreement. Mechanism experiments cover unequal curvatures, noise, and sparse momentum. Further tests span $64$ synthetic agents and eight logical Qwen LoRA workers. At matched payload budgets, Qwen2-7B QNLI gains $3.65$ accuracy points over explicit-index Rand-k; edge-local updates gain $3.42$ and $2.53$ points over all-neighbor mixing on eight-worker complete and ring graphs. A matched-first-step ablation gives a $3.92$-point momentum benefit. Seed-aware and same-matching controls distinguish encoding, scheduling, and query correlation.
ER -