PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Shengjun Zhang, Tingyi Liu, Heng Zhang, Dong Xie

arXiv:2609.27199v1cs.LGcs.SYeess.SYmath.OC

TL;DR

Sparse decentralized zeroth-order learning must communicate peer-state coordinates compatible with one-hop mixing, while high dimension makes estimation and communication costly. ZO-COSMO aligns query and mixing supports through masked consensus, and the analysis identifies uniform perfect matchings as optimal in contraction per scalar within the matching class.

  • Problem

    Sparse communication must provide peer-state coordinates compatible with one-hop mixing, while high dimension makes zeroth-order estimation and communication expensive.

    Source: §1 · pp. 1–2

  • Method

    ZO-COSMO couples two-query estimation to average-preserving masked consensus by coordinating query supports with global or matching-based mixing supports.

    Source: §1 · p. 2, §1.1 · p. 2, §3 · p. 3

  • Results

    Uniform perfect matchings on complete graphs attain the best contraction per scalar within the matching operator class.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Matching-based updates can use separate supports on disjoint edges, with q-value messages per active node, while the analysis characterizes estimation error and disagreement mechanisms.

    Source: §1 · p. 2, §1.1 · p. 2, §3 · p. 3

    Exactness covers coordinate recovery and the ideal arithmetic update; fixed-width scalar accounting does not provide a separate quantization-error guarantee.

    Source: §4 · p. 4

Abstract

from arXiv · show

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.

1 INTRODUCTION

The introduction identifies compatible peer-state coordinates as a requirement for sparse one-hop mixing and presents ZO-COSMO as a way to align query and mixing supports. Its contributions include support conditions, matching-based mixing analysis, and experiments on mechanisms and model-scale tasks.

1 INTRODUCTION

  • Coordinate-list encoding adds q⌈log2 d⌉ index bits to qBval value bits, nearly doubling value-only payload when an index is about as wide as a single-precision value.The passage frames this cost at billion-parameter scale.Source: §1 · p. 1
  • Theorem 1 characterizes the necessary and sufficient support condition for mixing arbitrary current peer states in one hop without stored peer histories.The introduction notes that public supports alone do not supply missing peer-state coordinates.Source: §1 · pp. 1–2
  • ZO-COSMO coordinates query and mixing supports: global supports serve masked Metropolis mixing, while matching updates allow separate supports on disjoint edges and q-value messages per active node.The introduction describes uniform perfect matchings on complete graphs as attaining the best contraction per scalar within this operator class.Source: §1 · p. 2

1.1 CONTRIBUTIONS •

  • The analysis derives optimal contraction per scalar in the matching class and uses pair invariance and conditional moments to characterize heterogeneity, oracle noise, and stored momentum.It also separates average-estimation error from disagreement injection and gives bit-budget and sparse-momentum convergence results.Source: §1.1 · p. 2, §1 · p. 2
  • Mechanism experiments vary curvature, noise, and momentum, while Qwen LoRA tests fixed-budget comparisons and controls; synthetic tests include 64 agents.The controls distinguish encoding, scheduling, and query-correlation effects.Source: §1.1 · p. 2

2 RELATED WORK

Prior work studies zeroth-order estimation, decentralized agreement, compression, and compact update representations. This paper focuses on which sparse messages permit exact one-hop mixing of current peer states alongside zeroth-order updates.

2 RELATED WORK

  • Zeroth-order methods estimate gradients from function queries, while decentralized methods address agreement across graph-connected local states; this work studies sparse messages that execute the mixing step exactly.The passage cites Ghadimi & Lan (2013), Nesterov & Spokoiny (2017), Shamir (2017), and Yuan & Ho (2015), among others.Source: §2 · p. 2
  • Compressed-learning work covers quantization, sparsification, sign compression, and error compensation, while coordinate lists add representation cost and PermK studies correlated compressors.ZO-COSMO studies both aggregate estimation error and disagreement because its query direction also selects peer-state coordinates for mixing.Source: §2 · p. 2
  • Seed-based methods reconstruct compact updates at a server or disseminate them graph-wide; ZO-COSMO instead sends q current-state values to complete one neighbor-mixing stage.The passage also places Com-DSZO with adaptive Top-k and a periodic-refresh comparator in its comparisons.Source: §2 · p. 2
  • Forward-only language-model adaptation uses loss queries and sparse or low-dimensional directions, while the Qwen experiments examine communication among separate worker states and data shards.The passage cites Malladi et al. (2023), Zhang et al. (2024), Liu et al. (2025), and Yu et al. (2025).Source: §2 · p. 3

3 ALGORITHM

ZO-COSMO reconstructs public supports, performs sparse two-query updates, and mixes the selected coordinates without sending coordinate indices. A public matching can assign different supports to disjoint edges, and the sparse-momentum variant changes the local direction while keeping the support and message rule unchanged.

3 ALGORITHM

  • The core update reconstructs a public support, takes two sparse queries, broadcasts q ordered values without indices, and mixes selected coordinates while unsent coordinates retain their local values.The implementation derives the support from synchronized seeds and round counters; decoding is pathwise exact.Source: §3 · p. 3
  • The network step is expressed using stacked node states and pre-mixing updates, with the support condition determining which coordinates messages must cover.ZO-COSMO uses that support for both queries and mixing.Source: §3 · p. 3
  • A public matching assigns each edge its own support, so disjoint pairs can use different coordinates while endpoints query and average on their shared support using one q-value message per active node.Theorem 2 gives the contraction for this matching-based update.Source: §3 · p. 3
  • Figure 1 contrasts protocols that know the supports but differ in whether their messages suffice for exact mixing on K = {1, 2}.The accompanying text identifies support compatibility as necessary and sufficient for mixing arbitrary current peer states without stored histories.Source: Figure 1 · p. 3, §3 · p. 3
  • The sparse-momentum variant replaces the local estimated direction with a momentum direction while leaving the public support, masked mixing rule, and transmitted message unchanged.The text reports convergence results for global and perfect-matching updates.Source: §3 · p. 3

4 THEORETICAL ANALYSIS

The analysis characterizes when one-hop coordinate messages permit exact mixing, then establishes matching-based mixing guarantees and convergence results. It also shows how direction correlation changes estimation error and disagreement, even with the schedule and payload fixed.

4.3 COMMUNICATION ACCOUNTING

  • Exact recovery of a receiver’s target coordinates is possible for every peer state if and only if each active neighbor sends a support containing those coordinates.With equal-sized target and message supports, they must match; a missing coordinate also yields a worst-case error of at least w_ijR when peer states are bounded by R.Source: §4.3 · p. 4

4.4 EDGE-LOCAL MIXING

  • Uniform rank-q supports on uniformly random perfect matchings of complete graphs attain the sharp contraction-per-scalar bound within the matching-based operator class.They attain equality with Cdir = Nq, using either common or independent edge supports.Source: §4.4 · p. 5

4.5 CONVERGENCE BOUND

  • Under a directed-link budget, the explicit 1/q factor in the network term cancels, while the spectral penalty remains; smaller q buys more rounds and queries.The same analysis identifies an unavoidable q/d one-step mixing slowdown.Source: §4.5 · p. 6

4.6 DIRECTION CORRELATION AND HETEROGENEITY

  • With a fixed matching, shared directions preserve cancellation among local gradient components, while independent directions average direction noise across pairs.For d > 1, independent directions have smaller estimation error when H2 < (m − 1)∥ā∥2; shared directions benefit on the other side of this threshold, with disagreement injection tracked separately.Source: §4.6 · p. 7

4.5 CONVERGENCE BOUND

  • Theorems 6 and 5 establish a sharper deterministic core rate for iid matchings and convergence for stochastic sparse-momentum updates, respectively.The momentum convergence analysis also bounds the distance between z_t and the average parameter iterate while accounting for the shared query–mixing mask.Source: §4.5 · p. 6, §4.6 · p. 7

4.6 DIRECTION CORRELATION AND HETEROGENEITY

  • With unequal quadratic Hessians, state disagreement controls the residual; pair invariance gives AV = V despite the shared query–mixing mask.The moment analysis also extends to oracle noise, stored momentum, and finite differences.Source: §4.6 · p. 7

5 EXPERIMENTS

Experiments test compact value-only communication, edge-local mixing, and sparse momentum in synthetic optimization and Qwen LoRA fine-tuning. The supplied results also state support-coding costs, one-hop compatibility requirements, and conditions on the public-randomness convergence analysis.

5.1 SYNTHETIC EXPERIMENTS

  • At 0.1M bits, removing repeated indices buys 15–17% more rounds, and ZO-COSMO has the lowest objective in all 15 paired seed–topology comparisons.On rings at 1 Mbit per node, edge-local mixing completes 1950 rounds versus 970 for global support; at N=64, its relative objective is 0.055 ± 0.0004 versus 0.159 ± 0.002 for flooding.Source: §5.1 · pp. 7–8

5.2 MECHANISM EXPERIMENT

  • With oracle noise at η=0.004, G ends at 1.06 × 10^-3 versus 9.60 × 10^-3 for I, but matching the first update reverses the momentum comparison.At the matched first-update scale, G ends at 1.30 ± 1.42 versus 0.131 ± 0.021 for I; noise leaves a nonzero floor.Source: §5.2 · p. 8

5.3 ZEROTH-ORDER FINE-TUNING FOR LARGE LANGUAGE MODELS

  • At matched budgets, QNLI accuracy gains 3.65 points over explicit-index Rand-k, while edge-local updates gain 3.42 points on complete and 2.53 on ring graphs over all-neighbor mixing.At 26.214 Mbit per link, ZO-COSMO completes 100 rounds versus 59 for explicit-index Rand-k; at 26.214 Mbit per node, matching permits 100 rounds versus 14 complete-graph and 50 ring all-neighbor rounds.Source: §5.3 · pp. 8–9
  • With support, communication, and first-update scale matched, sparse momentum raises QNLI accuracy by 3.92 points.Other controls report a −1.08-point paired difference against losslessly re-encoded seed-aware Rand-k, a 2.03× payload reduction for 6.53B-coordinate updates, and a 3.75-point gain from independent edge signs with matching and supports fixed.Source: §5.3 · pp. 8–9

A.1 PROOF STRUCTURE

  • The proof controls finite-difference error along the shared direction and disagreement after masked mixing, retaining their dependence in conditional expectations.The filtration treats each round’s public coin as fresh and independent of the past; oracle samples are conditionally independent across nodes.Source: §A.1 · p. 12

A.2 CONDITIONAL SUPPORT COST; A.3 PRIVATE-SUPPORT CODE LENGTH

  • A private support requires at least H(S_t | R_t) expected support bits, in addition to qBval value bits; publicly determined supports need no support field.For a reused adaptive mask, the support cost is amortized over the block, while coordinate lists cost q⌈log2 d⌉ bits and optimal private-support codes may be shorter.Source: §A.2 · p. 13, §A.3 · p. 14

A.4 PUBLIC-SUPPORT LIFTING

  • Seeded public supports decode messages and preserve averages exactly, but the contraction and convergence rates assume fresh uniform draws in the ideal public-coin model.Extending those stochastic rates to the pseudorandom implementation would require a separate randomness-approximation or cryptographic argument.Source: §A.4 · pp. 14–15

A.5 CONSEQUENCES OF ONE-HOP SUPPORT COMPATIBILITY; A.6 EDGE-LOCAL ZO-COSMO

  • One-hop compatibility is local to the active group: all-neighbor mixing needs a common target support, while matching requires agreement only between edge endpoints.The edge-local algorithm leaves unmatched nodes unchanged and requires a connected expected union graph for positive contraction.Source: §A.5 · p. 15, §A.6 · p. 15

A.7 PROOF OF THEOREM 2

The proof establishes average-preserving masked mixing and bounds its expected disagreement contraction under random coordinate supports. Matching-schedule constants distinguish independently sampled phases from deterministic alternation.

A.7 PROOF OF THEOREM 2

  • The masked update preserves the network average because its disagreement projector annihilates the consensus component.The edge projectors combine into an orthogonal projector, so the update removes only disagreement.Source: §A.7 · p. 16
  • Uniform q-coordinate supports contract expected disagreement according to the q/d activation probability, without requiring independence across matching edges.For uniform perfect matchings on a complete graph, the expected Laplacian has λ2 = N/(N −1).Source: §A.7 · p. 16
  • Random matching phases on an even ring have λ2 = 1 −cos(2π/N), whereas deterministic alternation is covered by a two-round bound.The q/d factor reflects activation of only a random coordinate subspace.Source: §A.7 · p. 16

A.8 PROOF OF THEOREM 3

The proof characterizes sharp matching-class contraction and a balanced public support schedule, then connects masked updates and sparse-direction moments to the optimization analysis.

A.8 PROOF OF THEOREM 3

  • Uniform perfect matchings with uniform marginal supports meet the pure-mixing equality criterion, and a disagreement eigenvector witnesses sharpness of the coefficient.Unequal coordinate coverage or an anisotropic expected Laplacian makes at least one inequality strict.Source: §A.8 · pp. 16–17

A.9 BALANCED PUBLIC SCHEDULE

  • The balanced public schedule activates every coordinate at least once per epoch, with maximum gap 2K −1 and average refresh time at most K.When q divides d, each block has size q and every coordinate appears exactly once per epoch.Source: §A.9 · p. 17

A.10 MASKED MATRIX FORM OF ZO-COSMO

  • The masked matrix update yields an exact network-average descent direction, with each estimator supported on the active mask.The update’s averaging identity uses the doubly stochastic mixing matrix.Source: §A.10 · p. 17

A.11 SPARSE DIRECTION IDENTITIES

  • A uniform signed q-sparse direction has covariance (q/d)I and exactly q nonzero entries of magnitude one.The sparse-direction identities supply moment calculations used in the estimator analysis.Source: §A.11 · p. 18

A.12 PROOF OF PROPOSITION 3

The estimator proof conditions its second-moment calculation on oracle randomness, while the averaged bounds distinguish independent oracle noise from shared directional randomness and account for decentralized gradient evaluation.

A.12 PROOF OF PROPOSITION 3

  • The second-moment proof conditions first on oracle noise and then applies the sparse-direction moment identity.This ordering establishes the stated second-moment result.Source: §A.12 · p. 19

A.13 AVERAGED ESTIMATOR BOUNDS

  • Only independent oracle noise is reduced by N in the averaged estimator; the public sparse direction contributes shared random-direction variance.The common direction remains in the averaged estimator rather than averaging away.Source: §A.13 · p. 20
  • Decentralization incurs a gradient-evaluation difference because local gradients are evaluated at xi,t rather than the network average.The resulting comparison is between local states and xbar_t.Source: §A.13 · p. 20

A.14 BASE DIRECTION FOR THE CONVERGENCE PROOF

This part develops convergence bounds and mixing identities for masked disagreement and sparse-momentum updates, relating parameter choices and direction coupling to optimization and network error under graph and objective assumptions. It also considers global, matching, and alternating-ring schedules and illustrates heterogeneity cancellation in a quadratic example.

A.16 PROOF OF THEOREM 4

  • Theorem 4’s proof bounds the actual descent direction’s second moment and alignment, absorbs positive descent terms under CLηd ≤ 1/4, and obtains rate (19) with η = cηT^-1/2.The descent absorption leaves stochastic, bias, and disagreement contributions, with graph dependence entering through the masked disagreement bound.Source: §A.14 · p. 21, §A.16 · p. 23, §A.17 · pp. 23–24

A.15 MASKED DISAGREEMENT ENERGY

  • Masked disagreement contracts at an effective rate of order (q/d)(1 − ρ^2), yielding a d/q slowdown and a squared spectral-gap factor; the q/d activation factor is tight.The averaged bound includes a transient that vanishes under equal initialization; the remaining slack comes from bounding disagreement injection and Young’s inequality.Source: §A.15 · p. 22

A.18 WORKER-SCALED RATE DERIVATION

  • The worker-scaled rate separates descent, averaged stochastic ZO noise, finite-difference bias, and sparse decentralized consensus; its finite-difference bias is O(T^-1).Because agents use the same public coordinates, worker averaging removes independent oracle noise but not sparse-coordinate sampling.Source: §A.18 · p. 24

A.19 PARAMETER CHOICE

  • Parameter selection exposes a tradeoff: larger q improves coverage and reduces d/q but raises payload, while the displayed communication-only bound favors smaller supports and has no interior optimum.In high-dimensional full-model tuning, the stability constraint can be more restrictive than stochastic balancing; at fixed value-only budget, coordinate exposure is approximately independent of q to first order.Source: §A.19 · p. 25

A.20 CONVERGENCE WITH SPARSE MOMENTUM

  • Under Theorem 5’s assumptions, global or perfect-matching ZO-COSMO with common initialization and zero initial momentum has vanishing average stationarity for fixed problem parameters, block length, contraction, and momentum.The stated choices are η = Θ(T^-1/2) and μ = Θ((dq)^-1/2 T^-1/4); the result also extends to alternating-ring momentum updates with common or independent edge supports.Source: §A.20 · pp. 26–27

B CORRELATION AND OPTIMIZATION

  • The correlation analysis studies how a shared direction jointly determines aggregate estimator variance and peer-state disagreement under a fixed matching schedule.It distinguishes aggregate from individual estimator error while analyzing the coupled disagreement update.Source: B CORRELATION AND OPTIMIZATION · p. 27

B.1 PROTOCOL AND COUPLINGS

  • The matching protocol gives both endpoints of each sampled pair the same direction; one listed cross-pair coupling uses a common support and sign vector.The excerpt introduces multiple cross-pair couplings but specifies only this global-support-and-sign case.Source: §B.1 · pp. 27–28
  • The couplings use two optimization queries and q outgoing value bits per active link, with public seeds and edge identifiers generating choices without recurring support metadata.Each run fixes its coupling while drawing fresh supports and signs each round.Source: §B.1 · p. 28

B.2 CONDITIONAL MOMENTS

  • For sparse Rademacher directions, E||D_e a||² = d||a||² and E|| (D_e − I)a||² = (d − 1)||a||²; G’s average-estimator variance is (d − 1)||ā||².The passage also cautions that a decrease in estimator variance is matched by an equal increase in update disagreement, so variance alone does not order optimization trajectories.Source: §B.2 · pp. 28–29

B.3 THE COUPLED MIXING STEP

  • Pair averaging preserves the network average and yields an exact disagreement-energy decomposition into pure mixing, gradient alignment, and update disagreement.Pair-constant updates give AV = V and the corresponding disagreement cross-term identity without requiring independence between V and the query–mixing mask.Source: §B.3 · p. 29

B.4 GRAPH AND OBJECTIVE ASSUMPTIONS

  • The analysis assumes deterministic, smooth, nonconvex objectives with bounded gradient heterogeneity and state-independent matching draws; pure-mixing contraction applies to the pre-query state.Uniform perfect matchings on complete graphs have χ = (N − 2)/(2(N − 1)); independently sampled matching phases on even rings have χ = (1 + cos(2π/N))/2.Source: §B.4 · p. 30

B.5 A CORRELATION-DEPENDENT CORE RATE

  • With G, η = Θ(T^-1/3) and μ = Θ((dq)^-1/2T^-1/6) yield an O(T^-2/3) upper bound; S and I admit an O(T^-1/2) bound.These rates hold for fixed problem and graph parameters under the theorem’s conditions; no matching lower bound is established for S or I.Source: §B.5 · pp. 30–31

B.5.1 PROOF OF THEOREM 6

  • The convergence proof uses pair invariance for the direction-dependent residual and applies pure-mixing contraction to the current state before the query-dependent update.It combines the descent and disagreement bounds to absorb disagreement under the theorem’s step-size conditions.Source: §B.5.1 · p. 31

B.6 A QUADRATIC CANCELLATION EXAMPLE

  • For G on shared-curvature quadratics, the network-average trajectory is independent of the matching sequence and individual linear terms.At consensus zero, one step with coupling s has expected squared average norm η²τ_s E_MH².Source: §B.6 · p. 32

B.7 MECHANISM EXPERIMENTS

The mechanism experiments relate direction coupling to estimation variance and optimization behavior, then characterize how curvature, oracle noise, and stored momentum affect network-average updates. Shared directions preserve deterministic heterogeneity cancellation, while independent oracle errors remain.

B.7 MECHANISM EXPERIMENTS

  • At M = 0, predicted average variances are 31, 13, and 7.75 for G, S, and I; at M = 15, they are 31, 103, and 124.All three predicted curves intersect at H^2 = 15.Source: §B.7 · p. 32
  • At η = 0.004 with ζ = 2, G ends at (1.160 ± 0.421) × 10^-7 versus 0.01118 ± 0.00309 for I; at zero heterogeneity, final means are close.The separation in the common-curvature example is attributed to heterogeneity cancellation.Source: §B.7 · pp. 32–33

B.8 CURVATURE HETEROGENEITY

  • With different Hessians, the network-average step has a residual controlled by state disagreement; the residual is zero under shared curvature or consensus.The identity holds for arbitrary quadratic states; applying Theorem 6 additionally requires its uniform gradient-heterogeneity assumption over R^d.Source: §B.8 · p. 35

B.9 ORACLE NOISE AND STORED MOMENTUM

  • Shared directions preserve deterministic heterogeneity cancellation, not cancellation of independent oracle errors.The conditional moment formulas cover noisy sparse momentum with finite differences, and Theorem 5 provides the corresponding convergence guarantee.Source: §B.9 · pp. 36–37

B.10 EXTENDED MECHANISM EXPERIMENTS

The extended mechanism tests find that global-support updates retain an advantage under unequal curvature and heterogeneity, while step size affects the first-step-matched momentum comparison. The accompanying communication analyses quantify representation overhead and distinguish one-hop mixing from flooding, refresh, and compressed-consensus alternatives.

B.10 EXTENDED MECHANISM EXPERIMENTS

  • With ω = 0.6, ζ = 2, and η0 = 0.004, G stays below S and I under deterministic, noisy, and sparse-momentum updates; its advantage reverses in the η = 0.04 first-step-matched control.On the complete graph, the deterministic final objective is (2.96 ± 1.13) × 10^-5 for G and (1.34 ± 0.48) × 10^-2 for I; on the ring, G's residual is (1.43 ± 0.49) × 10^-4.Source: §B.10 · p. 37

C COMMUNICATION ACCOUNTING DETAILS

  • With 32-bit values, indexed sparse messages spend slightly more than half their Qwen full-model payload on coordinate names; with 8-bit values, names exceed four-fifths.The same overhead pattern appears in LoRA-scale training.Source: Table 2 · p. 40, C COMMUNICATION ACCOUNTING DETAILS · p. 40

C.1 PUBLIC RANDOMNESS AND THE COMMUNICATION OPERATOR

  • Flooding delivers every source packet to every node, costing at least (N − 1)b per node; edge-local ZO-COSMO uses one link stage and keeps distinct local states.A seed–scalar pair can be smaller than q state values, making flooding attractive for small N or inexpensive multi-hop communication.Source: §C.1 · p. 41

C.2 SPARSE-MESSAGE SERIALIZATION CHECK

  • Even with ideal bit packing, indexed sparse communication exceeds value-only messages; ordinary integer-coordinate serialization makes the Qwen full-model indexed payload three times larger.The payload relation is independent of machine-dependent timing ratios.Source: Table 5 · p. 41, §C.2 · p. 42

C.3 TWO-PROCESS MESSAGE TRANSFER CHECK

  • Doubling the sparse payload increases median transfer time by 28%, while dense refresh carries 308× as many bits and takes 21.16× as long on the same-host transport.The authors report payload bits for method comparisons and treat these timings as a separate implementation measurement.Source: Table 6 · p. 42, §C.3 · p. 42

C.4 AMORTIZED COST OF THE SHARED SEED

  • Seed setup is amortized across rounds, whereas coordinate lists recur in every message.After a missed round, the round id and seed recover the support, not missed values or optimizer state; reliable delivery or explicit state recovery is still required.Source: §C.4 · p. 42

C.5 ZO-MARINA-TYPE BASELINE DEFINITION

  • For d = 2,523,136, q = 8192, and 32-bit values, the first dense packet costs 80.740 Mbit per link; the full-model Qwen refresh extrapolation is about 2.09 × 10^11 bits.Seed-aware sparse protocols are evaluated separately.Source: §C.5 · p. 43

C.6 COM-DSZO BASELINE DEFINITION

  • Com-DSZO combines a two-point ZO estimator with error-compensated compressed consensus; its comparison tests adaptive compression with error compensation.The instantiation uses Top-k innovation compression and also stores dense reconstruction and disagreement arrays.Source: §C.6 · p. 43

C.7 COMMUNICATION-BUDGET RATE

The communication-budget analysis translates affordable rounds into convergence bounds and quantifies how indexed encoding and periodic refreshes change the rounds available. Experimental reporting selects the latest logged checkpoint within each budget rather than interpolating across schedules.

C.7 COMMUNICATION-BUDGET RATE

  • After converting rounds to bits, the network term is first-order independent of q, while other displayed terms favor the additional rounds purchased by smaller supports.The communication-budget form of Theorem 4 substitutes the affordable number of rounds into the iteration bound.Source: §C.7 · p. 44
  • For the same update sequence, index metadata reduces the rounds affordable under a fixed bit budget; full-model Qwen with 32-bit values has a coordinate-list factor of 2.03 before dense refreshes.Long mask reuse can make metadata inexpensive when one stable subspace is adequate; ZO-COSMO addresses rotating supports without data-dependent mask-selection state.Source: §C.7 · p. 44
  • Periodic dense refresh adds both indexed sparse overhead and amortized refresh cost; under a fixed bit budget, ZO-COSMO can take approximately mMARINA times as many sparse rounds as the ZO-MARINA-type baseline.The refresh cost grows as d/(Kq).Source: §C.7 · pp. 44–45

D EXPERIMENTAL DETAILS AND REPRODUCIBILITY

  • Fixed-budget values use the latest logged checkpoint at or below the target cumulative communication, with no interpolation across schedules.Sparse baselines are charged for values and coordinate identifiers; ZO-COSMO is charged for values after the shared seed is fixed.Source: D EXPERIMENTAL DETAILS AND… · p. 45

D.1 FIXED-BUDGET EVALUATION PROTOCOL

The fixed-budget evaluation compares decentralized methods using cumulative per-node payload and logged checkpoints, alongside equal-round controls. Its topology stress test finds similar network-average objective reductions across graph families even as disagreement worsens on rings.

D.1 FIXED-BUDGET EVALUATION PROTOCOL

  • For each run and target budget, the evaluation selects the latest logged checkpoint whose cumulative bits do not exceed that budget, then aggregates the selected values over seeds.Values are used directly without interpolation; if no checkpoint fits, the run is excluded rather than extrapolated backwards.Source: §D.1 · pp. 45–46
  • The Rosenbrock comparison uses the same initialization, smoothing radius, value precision, graph, and oracle budget within each seed; its indexed control copies the ZO-COSMO trajectory and changes only message cost.Com-DSZO instead uses dense local ZO directions and Top-k innovation compression.Source: §D.1 · p. 46
  • At q = 1 and q = 2, both methods approach saturation at larger budgets; at q = 8 and q = 16, larger packets leave fewer rounds and the fixed-budget gap is clearer.Table 9 reports ZO-COSMO / indexed Rand-k, mean ± standard deviation over five seeds, with lower values better.Source: §D.1 · pp. 46–47, Table 9 · p. 46
  • At N = 64, complete, grid, and ring graphs all reduce the objective to about 6.1% of its initial value, while disagreement records the predicted deterioration on the ring.The network-average objective remains within 0.1% across graph families; their respective ρ values are 0, 0.9677, and 0.9968.Source: §D.1 · p. 47, Figure 14 · p. 47

D.2 SUPPORT-LOCALITY EXPERIMENT

Edge-local matching uses one q-value message per active node and has the lowest objective at every tested ring size. With scheduling fixed, objectives are close at N = 8 and 16, while common-support variants are unstable on one of five seeds at N = 4.

D.2 SUPPORT-LOCALITY EXPERIMENT

  • On even rings, edge-local updates alternate perfect matchings at 512 bits per node per round, half the 1024-bit cost of global-support mixing.The seed–scalar control uses ideal all-gather communication with a spanning-tree lower-bound charge.Source: §D.2 · p. 47
  • With a budget of 160 logged rounds, edge-local support is best at every tested N; global support is also one-hop but uses twice the ring payload to mix both neighbors per round.Source: §D.2 · p. 48
  • With the alternating matching fixed, common-support variants have close objectives at N = 8 and 16 but are unstable on one of five seeds at N = 4.Both matching variants use 512 bits per node per round and identical query counts, initialization, and η = 4×10^-4.Source: §D.2 · p. 48, Table 11 · p. 48

D.3 QWEN2-7B EXPERIMENTS

Qwen2-7B experiments assess optimization and payload use with logical workers, comparing QNLI accuracy at matched communication budgets and examining edge-local updates alongside controls for topology, momentum, query correlation, and sparse-update payload. Function-value access and decentralized execution alone provide no privacy guarantee.

D.3 QWEN2-7B EXPERIMENTS

  • +3.65 points: ZO-COSMO exceeds explicit-index Rand-k on QNLI, while its −1.08-point contrast with seed-aware Rand-k has an accuracy interval spanning zero.The seed-aware control preserves the independent-support trajectories while removing recurring index costs; its mean query loss is lower by 0.091.Source: §D.3 · p. 49, Table 13 · p. 49, Table 14 · p. 49
  • On SST-2, ZO-COSMO and Indexed Rand-k reach 94.13 ± 0.42% and 94.56 ± 0.75%, while their replicas remain exactly synchronized in every run.ZO-COSMO has lower interval query loss (0.741 ± 0.165 versus 0.843 ± 0.065); the matched-first-step control reports a 3.92-point momentum gain.Source: §D.3 · pp. 49–50, Table 15 · p. 49, Table 16 · p. 50
  • +3.42 points on the eight-worker complete graph and +2.53 points on the ring: index-free edge-local updates outperform global support in QNLI accuracy.The corresponding label-NLL reductions are 0.0366 and 0.0291; the index-charged edge-local control is also reported.Source: §D.3 · p. 51, Figure 19 · p. 51
  • At 1540 rounds, fixed-matching G, shared-support independent-sign S, and independent-support I reach 74.07%, 77.82%, and 75.97% QNLI accuracy, respectively.A shared tenfold step reduction improves their terminal accuracy by 23.95, 28.10, and 25.96 points over archived constant-step runs; S exceeds G by 3.75 points with support and schedule fixed, while moving from S to I reduces disagreement without an established accuracy gain.Source: §D.3 · pp. 52–53, Figure 20 · p. 52

D.5 IMPLEMENTATION DETAILS

  • In a single-worker full-model sparse two-query run, adding coordinate identifiers to the same updates gives 532.5K bits per step, 2.03× the value-only payload.Momentum is stored only on visited coordinates, while the model is loaded in bfloat16 and the sparse momentum map can remain on CPU.Source: §D.3 · p. 53

D.4 REPRODUCIBILITY ARTIFACTS

  • The reproducibility artifacts include experiment configurations, raw logs, figures, transfer and serialization records, with aggregation checks for hashes, checkpoints, and payload formulas.The same-update indexed control isolates representation cost, while momentum, independent-support, and periodic-refresh controls test distinct mechanisms or budget limits.Source: §D.4 · p. 54, Table 18 · p. 54, appendix communication diagnostics · p. 55

appendix communication diagnostics

  • Seed-aware encoding reconstructs independent supports from public node-specific seeds without changing their trajectories; global and edge-local supports use round- and edge-keyed generators.Communication accounting charges sparse payload per directed link, except the edge-local topology study, which fixes payload per node and also records network totals.Source: appendix communication diagnostics · p. 55, §D.5 · p. 55

D.6 ABLATION DESIGN

  • The ablations separate index-free representation from optimization and compressor effects, and separately test momentum scaling, support alignment, and the over-budget first refresh.Com-DSZO adds data-adaptive, error-compensated Top-k innovations but communicates indices and maintains two dense auxiliary arrays.Source: §D.6 · pp. 55–56

E BROADER IMPACT AND ETHICS

  • Forward-only fine-tuning reduces backward-activation storage, but local data and exchanged model states still require access controls; hardware and execution details appear in Appendix D.The experiments use logical workers to evaluate optimization and payload use.Source: E BROADER IMPACT AND ETHICS · p. 56

Related papers

Loading 2609.27199v1…