acceptodds
Withdrawn from ICLR 2027

ZO-COSMO: Index-Free One-Hop Mixing for Decentralized Zeroth-Order Optimization

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Sparse communication in decentralized zeroth-order learning requires compatible peer-state coordinates. We characterize this one-hop condition and develop ZO-COSMO, coupling two-query estimation with average-preserving masked consensus using 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 synthetic agents and eight logical Qwen LoRA workers. At matched payload budgets, Qwen2-7B QNLI gains accuracy points over explicit-index Rand-; edge-local updates gain and points over all-neighbor mixing on eight-worker complete and ring graphs. A matched-first-step ablation gives a -point momentum benefit. Seed-aware and same-matching controls distinguish encoding, scheduling, and query correlation.

Primary area:
optimization
Keywords:
Decentralized optimization, Zeroth-order optimization, Communication-efficient learning, Index-free communication, Public randomness, Masked consensus

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_Fd8gOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies decentralized zeroth-order optimization with sparse communication. Its central observation is that the coordinates required for exact one-hop peer-state mixing are coupled to the sparse query support: to recover a target coordinate block from ordered value messages, every positive-weight neighbor's message support must contain that target block. Building on this condition, the paper proposes ZO-COSMO, which aligns the sparse query direction with the coordinates used for mixing, so each active link sends only ordered values and no recurring coordinate indices. An edge-local matching variant assigns supports per active edge and reduces per-node payload relative to global-support mixing. The paper analyzes matching contraction and matching-class optimality, and gives convergence results for global-support, matching, and sparse-momentum updates. Communication accounting compares value-only payloads with indexed sparse and dense alternatives. Experiments include Rosenbrock synthetic tests, direction-correlation and heterogeneity studies, Qwen2-7B LoRA experiments on QNLI/SST-2, and a single-worker full-model sparse ZO study. The paper claims that removing coordinate-index overhead buys additional optimization rounds under a fixed bit budget and yields fixed-budget gains in decentralized LLM fine-tuning, although the LLM evidence is limited to 2--8 logical workers and two tasks.

Critical strengths

1.The support-compatibility characterization is clear and useful. Theorem 1 gives a sharp condition for when a receiver can recover selected coordinates of a one-hop neighbor average from ordered value messages alone, and it identifies the worst-case coordinate error when the condition fails. This turns “which coordinates must be communicated” into a precise protocol design question rather than a generic compression issue.

2.The index-free, edge-local design has concrete communication value, and the empirical controls are informative. By aligning query and mixing supports, ZO-COSMO removes the recurring coordinate-index field and charges only value payloads per active link; the edge-local matching variant further reduces per-node payload. The experiments include indexed controls that isolate representation cost, direction-correlation controls, placement audits for logical workers, and reproducibility details, making the empirical claims more interpretable than a simple end-to-end comparison.

Critical weaknesses

Weakness 1: Empirical evidence for the central LLM claim is not yet strong enough.

The authors report several key accuracy contrasts whose 95%95\% CIs include zero, e.g., ZO-COSMO vs.\ seed-aware Rand-kk (−1.08-1.08, 95%95\% CI [−5.85,3.67][-5.85, 3.67]; Section 5.3, Appendix D.3, Tables 13--14) and the N=4N=4 edge-local gain (+1.05+1.05, 95%95\% CI [−2.00,4.10][-2.00, 4.10]; Appendix D.3). The placement audit further confirms that sharing a frozen backbone does not alter the simulated trajectories (Appendix D.3). These defenses are valid, but the abstract and conclusion still present value-only communication as yielding gains in decentralized LLM fine-tuning, whereas the Qwen evidence covers only 2--8 logical workers, two tasks, and a single-worker full-model run (Section 5.3; Appendix D.3). ZO-MARINA-type results are reported at initialization because its first dense refresh exceeds the fixed budget (Appendix C.5; Appendix D.3), and the momentum benefit reverses at a larger step size (Section 5.2; Appendix B.10). The claim should therefore be downgraded or supported by stronger evidence.

Weakness 2: The theory relies on idealized public information and lacks a robustness analysis for support mismatch and asynchrony.

The authors explicitly state the ideal public-coin model (Appendix A.4) and provide seed amortization and transfer checks (Appendix C.2--C.4), which is appropriate. What remains unaddressed is how the exact-mixing condition of Theorem 1 (Section 4.3) degrades when seed desynchronization, round misalignment, packet loss, private supports, or non-uniform supports violate K⊆SjiK\subseteq S_{ji}. Theorem~1 only gives a worst-case coordinate error wijRw_{ij}R; the paper does not provide an expectation or high-probability error bound, nor does it analyze how such mismatch affects convergence. The main comparisons charge the value payload qBvalqB_{\rm val} (Section 4.3; Appendix C), and although Appendix C.4 notes that a missed round recovers the support but not the missed values or optimizer state, the effect of synchronization failure and retransmission on exact mixing is not incorporated into the theory or the main experiments. Therefore, the practical extrapolation of ``exact mixing'' lacks stated boundaries.

Questions for authors

On Weakness 1 (empirical evidence and scope) For the key LLM contrasts whose 95% CIs include zero---e.g., ZO-COSMO vs.\ seed-aware Rand-kk (−1.08-1.08, CI [−5.85,3.67][-5.85, 3.67]; Section 5.3, Appendix D.3, Tables 13--14) and the N=4N=4 edge-local gain (+1.05+1.05, CI [−2.00,4.10][-2.00, 4.10]; Appendix D.3)---please report per-seed paired differences, multiple-comparison correction, and a power analysis. If the primary CI still crosses zero, do the authors agree to downgrade the claim from gains in decentralized LLM fine-tuning to more rounds under a fixed bit budget, with task-dependent accuracy gains?

The Qwen evidence covers only 2--8 logical workers, two tasks, and a single-worker full-model run (Section 5.3; Appendix D.3). Please add real multi-process, non-IID, and at least one additional-task evidence, or state the extrapolation boundary explicitly in the limitations. In particular, does the placement audit establish simulation equivalence only, rather than sufficiency of scale and task coverage?

Please separate ``infeasible under budget'' baselines from equal-round comparisons. For ZO-MARINA-type, whose first dense refresh exceeds the fixed budget (Appendix C.5; Appendix D.3), please clarify that it is not an effective baseline under the QNLI fixed-budget setting, and report the equal-round result separately. Also provide a step-size sensitivity grid and failure-run statistics for the momentum gain, given that the comparison reverses at a larger step (Section~5.2; Appendix B.10).

On Weakness 2 (theory boundary and communication modeling) Theorem 1 only gives a worst-case coordinate error wijRw_{ij}R when k∈K∖Sjik\in K\setminus S_{ji} (Section 4.3). Please provide an expectation or high-probability error bound under support mismatch, or at least a sensitivity experiment measuring disagreement and accuracy degradation. Without such a bound, how should readers interpret ``exact mixing'' beyond the ideal public-coin model?

Please state precisely which results hold only under the synchronous public-seed model, and whether Theorems 2, 4, and 5 remain valid under seed desynchronization, round misalignment, packet loss, or private/non-uniform supports. If they do not, please give a counterexample or explicit conditions.

The main comparisons charge value payload qBvalqB_{\rm val} (Section 4.3; Appendix C), while Appendix C.4 notes that a missed round recovers the support but not the missed values or optimizer state. Please provide an end-to-end communication trace including seed initialization, synchronization/retransmission, and headers, or explicitly restrict the communication advantage to the synchronous reliable-delivery model.

Reviewer_pNAWOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes ZO-COSMO, a communication-efficient decentralized zeroth-order optimization (ZOO) algorithm that eliminates the need to transmit coordinate indices. The proposed method employs publicly shared random seeds to coordinate sparse zeroth-order gradient estimation and model mixing among neighboring nodes. It further introduces an edge-local mixing scheme that allows each matched pair of nodes to use different coordinate supports. Theorem 4 establishes a convergence rate for ZO-COSMO under nonconvex objectives. Furthermore, Proposition 1 investigates how correlations among zeroth-order estimation directions affect gradient estimation errors and consensus disagreement under heterogeneous objectives, showing that sharing estimation directions across all node pairs can reduce the average gradient estimation error when gradient heterogeneity is sufficiently large. Experimental results on synthetic optimization problems and practical tasks, including Qwen2-7B LoRA fine-tuning, demonstrate performance improvements over several baselines under fixed communication budgets.

Critical strengths

S1. Simple, practical, communication-efficient design for decentralized ZOO. The proposed method provides a simple and practical approach to reducing communication costs by eliminating the need to transmit coordinate indices.

S2. Experimental evaluations in practical scenarios. This paper evaluates the proposed method in practical scenarios, including zeroth-order fine-tuning of a large language model (Qwen2-7B). These experiments demonstrate the potential applicability of the proposed method to large-scale natural language tasks under communication constraints.

Critical weaknesses

W1. Limited algorithmic novelty and insufficient differentiation from existing works.

The proposed method may appear closely related to existing works for communication-efficient decentralized learning, such as SAPS-PSGD (Tang et al., 2020) and GossipFL (Tang et al., 2023), which also employ sparse model communication and coordinated coordinate selection among neighboring nodes. Moreover, coordinate-based zeroth-order optimization may have already been studied, such as ZOOM (Zhang et al., 2022). Although ZO-COSMO combines sparse ZO gradient estimation with support-aligned model mixing, it remains unclear whether this combination introduces fundamentally new algorithmic challenges beyond those addressed in prior work. These relevant studies are not sufficiently discussed, making it difficult to assess the novelty and significance of the proposed method.

W2. Limited novelty in the main theoretical results and insufficient emphasis on more substantial theoretical contributions.

Although this paper provides several theoretical results, I find the novelty and analytical challenges of Theorems 1–4 somewhat limited, as they appear to rely largely on standard analytical techniques for decentralized optimization. In contrast, Proposition 1 and Theorem 6 (Appendix B.5) appear to offer more nontrivial theoretical insights.

Proposition 1 provides an interesting characterization of how correlations among ZO estimation directions affect gradient estimation errors and consensus disagreement under heterogeneous objectives. However, its novelty and relationship to existing studies on correlated compression deserve further discussion. In addition, Theorem 6 establishes correlation-dependent convergence bounds, including an improved rate of O(T−2/3)\mathcal{O}(T^{-2/3}) when all node pairs share the same estimation direction, compared with the general O(T−1/2)\mathcal{O}(T^{-1/2}) bound for other correlation schemes under deterministic nonconvex objectives.

I believe these results represent more important theoretical contributions and deserve greater emphasis in the main paper. Furthermore, it would be valuable to provide experimental evidence specifically supporting the findings of Theorem 6, particularly by comparing different direction-correlation schemes under deterministic settings with varying degrees of gradient heterogeneity.

W3. Unclear advantage in test accuracy on Qwen2-7B LoRA fine-tuning.

Although this paper includes practical experiments involving Qwen2-7B LoRA fine-tuning, the effectiveness of ZO-COSMO remains somewhat unclear. While ZO-COSMO improves QNLI accuracy over explicit-index Rand-k under a fixed communication budget, this improvement appears largely attributable to eliminating coordinate-index overhead. Compared with seed-aware Rand-k, which also eliminates this overhead, ZO-COSMO does not demonstrate a clear advantage in test accuracy.

Questions for authors

See the comments in the Weaknesses.

Reviewer_LSkEOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper proposes ZO-COSMO, a communication-efficient decentralized zeroth-order optimization framework that eliminates coordinate-index transmission through publicly coordinated sparse supports. It establishes conditions for exact one-hop mixing, derives communication-aware contraction and convergence guarantees, and analyzes the effects of direction correlation and gradient heterogeneity. Experiments on synthetic problems and Qwen2-7B fine-tuning demonstrate communication savings and improved performance under fixed bit budgets.

Critical strengths
  1. The paper addresses a practical communication bottleneck in high-dimensional decentralized zeroth-order optimization.
  2. The theoretical analysis is comprehensive, including exact support compatibility, matching-based contraction bounds, convergence guarantees, and the impact of direction correlation.
  3. The experiments include meaningful ablation studies and demonstrate communication-budget improvements on synthetic benchmarks and LLM fine-tuning tasks.
Critical weaknesses
  1. The novelty of index-free communication is somewhat limited, as public-seed-based sparse encoding is already applicable to existing methods. The main novelty appears to lie in support coordination and mixing.
  2. The seed-aware Rand-k baseline achieves comparable or slightly better QNLI accuracy than ZO-COSMO, raising questions about the practical optimization benefits beyond index removal.
  3. The optimality result is restricted to a specific class of matching-based mixing operators, limiting its generality to broader decentralized optimization settings.
  4. The theoretical analysis relies on relatively restrictive assumptions, including bounded stochastic gradient moments and third-order smoothness, while the convergence guarantees do not clearly improve upon existing decentralized zeroth-order methods.
  5. The LLM experiments primarily use logical workers and communication-bit accounting rather than fully distributed deployments, leaving end-to-end scalability and runtime efficiency insufficiently validated.
Questions for authors
  1. Beyond eliminating coordinate indices, under what conditions does ZO-COSMO outperform seed-aware independent Rand-k in terms of optimization performance?
  2. Can the contraction optimality result be extended to more general communication operators or arbitrary sparse network topologies?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.