Paper deep dive
Scalar Communication via Random Direction Refreshing for Distributed Optimization
Mohammadreza Rostami, Solmaz S. Kia
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 95%
Last extracted: 10/6/2026, 9:57:36 AM
Summary
This paper proposes a scalar-communication mechanism for distributed optimization over networks to address bandwidth constraints in high-dimensional settings. Unlike existing methods that quantize or sparsify vectors (still scaling with dimension d), this approach allows agents to exchange only a single real number per message. Agents regenerate a common random direction from a shared seed, transmit the inner product of their state with this direction, and reconstruct a rank-one surrogate for neighbor states. The authors analyze this mechanism applied to a continuous-time distributed optimization algorithm, proving that refreshing the random direction at a sufficient rate ensures exponential mean-square and almost-sure convergence to the unique optimizer, avoiding spurious equilibria associated with fixed directions. Various direction distributions (Rademacher, scaled-coordinate, sphere-normalized Gaussian) are evaluated for their encoding variance.
Entities (10)
Relation Signals (7)
Mohammadreza Rostami → affiliatedwith → University of California, Irvine
confidence 99% · The authors are with the Department of Mechanical and Aerospace Engineering, University of California Irvine
Solmaz S. Kia → affiliatedwith → University of California, Irvine
confidence 99% · The authors are with the Department of Mechanical and Aerospace Engineering, University of California Irvine
Scalar Communication Mechanism → reduces → Communication Cost
confidence 98% · reducing the per-message cost from O(d) to O(1)
Scalar Communication Mechanism → uses → Random Direction Refreshing
confidence 96% · Agents regenerate a common random direction from a shared seed... refreshing the direction at a sufficiently high rate yields exponential mean-square and almost-sure convergence
Rademacher Directions → istypeof → Isotropic Fixed-Norm Direction
confidence 95% · Rademacher, scaled-coordinate, and sphere-normalized Gaussian directions satisfy both isotropy and the fixed-norm condition
Scalar Communication Mechanism → solves → Distributed Optimization
confidence 95% · This paper addresses the bandwidth constraint by developing a distributed optimization algorithm whose per-message cost is independent of d.
Scalar Communication Mechanism → appliedto → Kia et al. Algorithm
confidence 90% · We develop and analyze the mechanism for an existing continuous-time distributed optimization algorithm... for the algorithm of Kia et al. [8]
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Distributed optimization over networks requires agents to repeatedly exchange decision variables with their neighbors. When the decision dimension $d$ is large, these exchanges dominate the communication cost, which is critical for bandwidth-constrained agents. Existing remedies quantize or sparsify the exchanged vectors, yet each message still scales with $d$ and the compression error must be compensated by additional states. To address this limitation, we propose a scalar-communication mechanism in which every neighbor message carries a single real number regardless of $d$. Agents regenerate a common random direction from a shared seed, transmit only the inner product of their state with that direction, and act on the resulting rank-one surrogate of their neighbors' states while retaining full local gradients. We develop and analyze the mechanism for an existing continuous-time distributed optimization algorithm. For strongly convex local costs with Lipschitz gradients, we show that the optimizer remains the unique consensus equilibrium, that a fixed direction admits spurious equilibria, and that refreshing the direction at a sufficiently high rate yields exponential mean-square and almost-sure convergence with constant gains and no residual error. The framework admits any isotropic fixed-norm direction distribution, including Rademacher, scaled-coordinate, and sphere-normalized Gaussian directions; all three attain lower fresh-encoding variance than unnormalized Gaussian directions. The effects of the direction distribution and the refresh interval are illustrated in~simulations.
Tags
Links
- Source: https://arxiv.org/abs/2610.05666v1
- Canonical: https://arxiv.org/abs/2610.05666v1
Trouble viewing inline? Open PDF directly →
Full Text
61,599 characters extracted from source content.
Expand or collapse full text
Scalar Communication via Random Direction Refreshing for Distributed Optimization Mohammadreza Rostami Solmaz S. Kia Senior member, IEEE †thanks: This work is supported by the 2026 UCLA–UCI grant awarded by the Samueli Foundation. The authors are with the Department of Mechanical and Aerospace Engineering, University of California Irvine, Irvine, CA 92697, mrostam2,solmaz@uci.edu. Abstract Distributed optimization over networks requires agents to repeatedly exchange decision variables with their neighbors. When the decision dimension d is large, these exchanges dominate the communication cost, which is critical for bandwidth-constrained agents. Existing remedies quantize or sparsify the exchanged vectors, yet each message still scales with d and the compression error must be compensated by additional states. To address this limitation, we propose a scalar-communication mechanism in which every neighbor message carries a single real number regardless of d. Agents regenerate a common random direction from a shared seed, transmit only the inner product of their state with that direction, and act on the resulting rank-one surrogate of their neighbors’ states while retaining full local gradients. We develop and analyze the mechanism for an existing continuous-time distributed optimization algorithm. For strongly convex local costs with Lipschitz gradients, we show that the optimizer remains the unique consensus equilibrium, that a fixed direction admits spurious equilibria, and that refreshing the direction at a sufficiently high rate yields exponential mean-square and almost-sure convergence with constant gains and no residual error. The framework admits any isotropic fixed-norm direction distribution, including Rademacher, scaled-coordinate, and sphere-normalized Gaussian directions; all three attain lower fresh-encoding variance than unnormalized Gaussian directions. The effects of the direction distribution and the refresh interval are illustrated in simulations. Keywords: Distributed optimization, bandwidth-limited communication, scalar communication, random projections, multi-agent systems. I Introduction Distributed optimization enables a network of N agents to cooperatively solve minz∈ℝdF(z)=∑i=1Nfi(z), _z ^dF(z)=Σ _i=1^Nf^i(z), (1) where each local objective fif^i is private to agent i, using only local computation and communication with neighbors. Problems of this form arise in cooperative control, distributed estimation, resource allocation, and networked learning, and a mature set of discrete- and continuous-time algorithms with strong convergence guarantees is now available; see, e.g., [1, 2, 3, 4]. Despite these advances, communication remains a key impediment to deploying distributed optimization on resource-constrained networks [5]. Communication cost has two distinct sources. The first is energy: in battery-powered systems, every transmission depletes a limited budget, so agents should communicate only when needed. The second is bandwidth: the channel limits how much information a single message can carry. This is a hard constraint that holds regardless of battery status and can only be met by reducing the size of each message. Event- and self-triggered mechanisms [6, 7, 8] address the energy side by reducing how often agents communicate, but each message still contains a full d-dimensional state or gradient. Quantization and sparsification reduce the number of bits or entries sent, but the exchanged objects remain d-dimensional and require auxiliary error-compensation or tracking states. These limitations become severe when the decision variable is high dimensional, d≫1d 1. This paper addresses the bandwidth constraint by developing a distributed optimization algorithm whose per-message cost is independent of d. Our approach builds on a scalar encoding principle from our recent federated learning work [9, 10, 11]. For any random direction u∈ℝdu ^d with [uu⊤]=IdE[u ]=I_d, a vector g∈ℝdg ^d satisfies g=[u⏟vectoru⊤g⏟scalar],g=E [\, u_vector\, u g_scalar\, ], (2) so a sender that shares a random seed with the receiver need only transmit the scalar u⊤gu g, from which the receiver forms the unbiased estimate (u⊤g)u(u g)\,u. We apply this principle to the states exchanged between neighbors in consensus-based distributed optimization. All agents regenerate a common direction from a shared seed, each agent transmits the projection of its state onto that direction, and every agent keeps using its full local gradient. No direction vector is transmitted, and no compression-error memory is required. Related Work: In bandwidth-limited settings, the central concern is the size of each transmitted message, and two major approaches have been developed to address it. The first reduces the number of bits used to represent each entry of the exchanged vector. Building on quantized consensus [12, 13, 14], the effect of quantization on distributed subgradient methods was first characterized in [15]. Subsequent work established data-rate requirements for convergence [16], designed quantizers tailored to optimization dynamics [17], and analyzed convergence under limited communication [18]. With a fixed quantizer, these methods generally converge to a neighborhood of the optimizer, whereas adaptive quantization that progressively shrinks the quantization range can recover exact convergence [19, 20], achieving linear rates for smooth strongly convex objectives [21]. However, the communicated object remains a d-dimensional vector, so the message length still scales with the problem dimension. The second approach reduces the number of transmitted entries. In distributed learning, QSGD showed that aggressive quantization trades communication against estimator variance [22], which motivated sparsification methods that retain only a subset of entries and use error memory to preserve discarded information [23, 24]. Koloskova et al. [25] extend this idea to decentralized networks, where agents maintain auxiliary estimates of their neighbors’ states to accommodate biased and unbiased compressors. Compressed gradient-tracking and push–pull methods add tracking variables to achieve linear convergence on directed networks and nonconvex objectives [26, 27]. The closest schemes to our approach are random sparsification operators that retain k of the d entries [23, 25]. With k=1k=1, the rescaled operator d⋅rand1d·rand_1 is equivalent to the scaled coordinate-direction encoder considered in this paper. In these methods, however, the selected indices are transmitted together with the retained values [23], and the resulting compression error is compensated using either error memory [23] or auxiliary neighbor estimates [25]. In summary, existing communication-efficient methods either exchange messages whose length scales with the problem dimension or rely on memory, tracking, or auxiliary states to compensate for compression error. In contrast, our scheme regenerates the communication direction, and hence any selected index, from a shared seed, so each message consists of a single real number and no compensating state is required. Contributions: This paper introduces a scalar-communication mechanism for distributed optimization in which neighboring agents exchange a single real number per message, regardless of the decision dimension. The mechanism is developed for the continuous-time coordination algorithm of [8], although it is applicable to any distributed optimization scheme whose inter-agent coupling depends only on relative states. By generating common random directions from a shared seed, agents communicate only scalar projections of their states, eliminating the need to transmit direction vectors or maintain compression-error memory. We show that the optimal consensus equilibrium of the original algorithm is preserved under scalar communication and remains the unique equilibrium on the zero-sum integral-state subspace. For strongly convex local objectives with globally Lipschitz gradients, we establish exponential mean-square and almost-sure convergence to the optimizer using constant gains, provided the direction-refresh interval is sufficiently small. The resulting refresh condition explicitly reveals how graph connectivity, objective regularity, and direction statistics influence convergence. A key challenge is that the communication direction is held fixed between refreshes. Although the resulting encoder is unbiased at each refresh instant, the held direction becomes coupled with the evolving network state over time. We address this challenge through a Lyapunov analysis that combines conditional drift at refresh times with bounds on the evolution between refreshes. Finally, we characterize the fresh-encoding variance of unnormalized Gaussian, Rademacher, scaled-coordinate, and spherical directions. The convergence theorem applies to the latter three fixed-norm distributions; scaled-coordinate directions recover random-coordinate communication as a special case. Compared to our prior work on scalar communication for federated learning [9, 10], this paper extends the framework from client-server aggregation to distributed neighbor-to-neighbor interactions, where the communicated quantities are dynamically coupled through the network. I Problem Formulation and Baseline Algorithm We consider problem (1) over a network of N agents that communicate over a connected, undirected graph =(,ℰ)G=(V,E) with symmetric adjacency matrix A=[aij]A=[a_ij], where aij=aji>0a_ij=a_ji>0 if (i,j)∈ℰ(i,j) and aij=0a_ij=0 otherwise, and Laplacian L. Assumption 1 Each local cost fi:ℝd→ℝf^i:R^d is private to agent i, continuously differentiable, and strongly convex, with a globally Lipschitz continuous gradient. Let mf>0m_f>0 and ℓf _f denote a common lower bound on the strong convexity parameters and a common upper bound on the gradient Lipschitz constants, respectively. Under Assumption 1, F has a unique minimizer z⋆z . Several continuous-time algorithms solve problem (1) over connected graphs, including the control-theoretic dynamics of Wang and Elia [28, 29] and their variants [30, 8]. These algorithms couple agents only through relative states xi−xjx^i-x^j, which is precisely the quantity our scalar encoding targets. The encoding therefore applies to any of them, although convergence must be established for each. For concreteness, we develop and analyze it for the algorithm of Kia et al. [8]: v˙i v^i =αβ∑j=1Naij(xi−xj), =αβΣ _j=1^Na_ij\,(x^i-x^j), (3a) x˙i x^i =−α∇fi(xi)−β∑j=1Naij(xi−xj)−vi, =-α∇ f^i(x^i)-βΣ _j=1^Na_ij\,(x^i-x^j)-v^i, (3b) where α,β>0α,β>0 are design gains, xi∈ℝdx^i ^d is agent i’s estimate of z⋆z , and vi∈ℝdv^i ^d is an integral correction variable initialized so that ∑i=1Nvi(0)=0 _i=1^Nv^i(0)=0. The following result establishes convergence of this baseline. Theorem I.1 (See Theorem 6 of [8]) Let Assumption 1 hold and let G be connected and undirected. Then, for any α,β>0α,β>0 and any initial condition satisfying ∑i=1Nvi(0)=0 _i=1^Nv^i(0)=0, the trajectories of (3) converge exponentially fast to xi=z⋆x^i=z and vi=−α∇fi(z⋆)v^i=-α∇ f^i(z ) for all i∈i . Implementing (3) requires each agent to receive the full d-dimensional state xjx^j from every neighbor. Section I replaces this exchange with a single scalar per neighbor, reducing the per-message cost from (d)O(d) to (1)O(1). I Scalar Communication via Random Encoding and Decoding The idea is to enforce consensus by letting neighbors act on a rank-one surrogate of each other’s state rather than on the state itself. Given a random direction u∈ℝdu ^d with [uu⊤]=IdE[u ]=I_d, the surrogate yi=(u⊤xi)uy^i=(u x^i)\,u (4) is an unbiased estimate of xix^i, since [yi]=[uu⊤]xi=xiE[y^i]=E[u ]x^i=x^i. Its usefulness for communication lies in how it factors: if the receiver already knows u, then yiy^i is fully determined by the scalar u⊤xiu x^i. In the coupling terms of (3), we therefore replace xi−xjx^i-x^j by yi−yj=uu⊤(xi−xj)y^i-y^j=u (x^i-x^j), which requires each agent to send one real number per message instead of d. For this to work, all agents must hold the same direction at the same time without exchanging it. We let uk∈ℝdu_k ^d be drawn independently of the past at the refresh times tk=kτt_k=kτ, τ>0τ>0, and held constant on [tk,tk+1)[t_k,t_k+1). A common seed, the same pseudorandom generator, and a synchronized index k allow every agent to regenerate uku_k locally, so the direction is never transmitted. During [tk,tk+1)[t_k,t_k+1), agent i transmits the scalar encoding ci(t)=uk⊤xi(t)∈ℝ,c^i(t)=u_k x^i(t) , (5) and each neighbor decodes yi(t)=ci(t)uky^i(t)=c^i(t)\,u_k. We stress that yiy^i is not a reconstruction of xix^i from a single scalar; it is the component of xix^i visible along uku_k, and it is the refreshing of uku_k that exposes all components over time. The resulting algorithm is v˙i v^i =αβ∑j=1Naij(yi−yj), =αβΣ _j=1^Na_ij(y^i-y^j), (6a) x˙i x^i =−α∇fi(xi)−β∑j=1Naij(yi−yj)−vi. =-α∇ f^i(x^i)-βΣ _j=1^Na_ij(y^i-y^j)-v^i. (6b) The local gradient is evaluated at the actual state xix^i; only the neighbor coupling is encoded and decoded. Each message thus carries (1)O(1) rather than (d)O(d) entries. In this continuous-time model, ci(t)c^i(t) varies continuously within each holding interval; the finite-bit cost of an implementation also depends on sampling and quantization, which we do not address here. Any distribution with [ukuk⊤]=IdE[u_ku_k ]=I_d can be used in the unbiased encoding identity (4); no normalization is required for that identity. The convergence analysis in Section I-C additionally requires ‖uk‖2=d\|u_k\|^2=d almost surely. We consider three representative choices: (G) Gaussian: gk∼(0,Id)g_k (0,I_d), used either directly, uk=gku_k=g_k, or normalized to the sphere, uk=dgk/‖gk‖u_k= d\,g_k/\|g_k\|; (R) Rademacher: uk∈−1,+1du_k∈\-1,+1\^d with independent, equiprobable entries; (C) scaled coordinate: uk=deJku_k= d\,e_J_k with JkJ_k uniform on 1,…,d\1,…,d\, so that agents exchange one randomly selected coordinate at a time. Rademacher, scaled-coordinate, and sphere-normalized Gaussian directions satisfy both isotropy and the fixed-norm condition required by Theorem I.1. Unnormalized Gaussian directions satisfy isotropy but are not covered by Theorem I.1; they are included below only for the fresh-encoding variance comparison. Among the covered choices, Rademacher directions mix all d coordinates into every transmitted scalar, whereas scaled-coordinate directions expose one coordinate per transmission; Section IV shows that either can be preferable depending on where the disagreement between agents lies. I-A Equilibrium Analysis We first verify that the optimizer z⋆z of (1) remains an equilibrium of (6). Let (x¯,v¯)( x, v) denote a constant equilibrium of the state and integral variables; the decoded variables y¯i=ukuk⊤x¯i y^i=u_ku_k x^i may still change when the direction changes. For any fixed direction, setting v˙i=0 v^i=0 at equilibrium in (6a) yields ∑j=1Naij(y¯i−y¯j)=0⟺(L⊗Id)y¯=0.Σ _j=1^Na_ij( y^i- y^j)=0\ \ (L I_d) y=0. (7) Since G is connected, the null space of L is spanned by N1_N, so the decoded variables reach consensus. This alone does not imply x¯i=z⋆ x^i=z , so we verify the desired equilibrium directly. Set x¯i=z⋆,v¯i=−α∇fi(z⋆). x^i=z , v^i=-α∇ f^i(z ). (8) For every shared direction uku_k, the decoded states satisfy y¯1=⋯=y¯N=ukuk⊤z⋆ y^1=·s= y^N=u_ku_k z , so all neighbor differences vanish and v˙i=0,x˙i=−α∇fi(z⋆)−v¯i=0. v^i=0, x^i=-α∇ f^i(z )- v^i=0. (9) Because the graph is undirected, the sum of the integral variables is conserved, ∑i=1Nvi(t)=∑i=1Nvi(0)=0,Σ _i=1^Nv^i(t)=Σ _i=1^Nv^i(0)=0, (10) and the proposed equilibrium respects this condition since ∑iv¯i=−α∑i∇fi(z⋆)=0 _i v^i=-α _i∇ f^i(z )=0, which is precisely the first-order optimality condition for F. Thus the optimal consensus state is an exact equilibrium for every shared direction. Conversely, if [ukuk⊤]=IdE[u_ku_k ]=I_d, any constant equilibrium common to almost every direction satisfies (L⊗ukuk⊤)x¯=0(L u_ku_k ) x=0 for almost every uku_k; averaging gives (L⊗Id)x¯=0(L I_d) x=0, so x¯i x^i is common to all agents. Summing the equilibrium equations for x˙i x^i then gives ∑i∇fi(x¯i)=0 _i∇ f^i( x^i)=0. Hence, on the zero-sum subspace (10), the common equilibrium (8) is unique. I-B Why a Fixed Direction Can Fail Although z⋆z is an equilibrium for every direction, holding a single direction u fixed for all time need not yield convergence when d>1d>1. Let P=uu⊤P=u denote the rank-one encoding–decoding operator (an orthogonal projection only when ‖u‖=1\|u\|=1). The coupling depends on the states only through yi−yj=P(xi−xj),y^i-y^j=P(x^i-x^j), (11) so if xi−xj∈span(u)⟂x^i-x^j (u) for adjacent agents, then yi−yj=0y^i-y^j=0 and the coupling is blind to disagreement in the remaining d−1d-1 dimensions. A state profile is therefore a spurious equilibrium whenever xi−xj x^i-x^j ∈span(u)⟂, (u) , ∀(i,j)∈ℰ, ∀(i,j) , (12) vi v^i =−α∇fi(xi), =-α∇ f^i(x^i), ∑i=1N∇fi(xi) Σ _i=1^N∇ f^i(x^i) =0. =0. (13) For example, take two agents with f1(z)=12‖z−a‖2f^1(z)= 12\|z-a\|^2 and f2(z)=12‖z+a‖2f^2(z)= 12\|z+a\|^2, where a≠0a≠ 0 and u⊤a=0u a=0. The optimizer is z⋆=0z =0, yet x1=ax^1=a, x2=−ax^2=-a, v1=v2=0v^1=v^2=0 is a nonconsensus equilibrium. A fixed direction thus offers no general convergence guarantee, which motivates refreshing the direction. I-C Convergence under Direction Refreshing Let uku_k be redrawn independently from a fixed distribution at the refresh times tk=kτt_k=kτ. Unbiasedness alone does not guarantee convergence for arbitrary holding intervals, so we derive a positive constant τ¯d τ_d, determined by the problem data alone, such that convergence is preserved for every holding interval τ∈(0,τ¯d]τ∈(0, τ_d]. Any refresh period in this range is admissible, so τ can be chosen as large as τ¯d τ_d to refresh directions as infrequently as the guarantee allows. Since the refresh times are periodic rather than state-triggered, no Zeno-type issue arises. Let ℱkF_k denote the history immediately before drawing uku_k, and assume [ukuk⊤∣ℱk]=Id,‖uk‖2=d.E[u_ku_k _k]=I_d, \|u_k\|^2=d. (14) The first condition holds for (G), (R), and (C). The second holds for (R), (C), and normalized Gaussian directions, which remain isotropic (Remark I.3); it fails for unnormalized Gaussian directions, whose squared norm ‖gk‖2\|g_k\|^2 is random. At a refresh time the states are ℱkF_k-measurable, so [yi(tk+)−yj(tk+)∣ℱk] [y^i(t_k^+)-y^j(t_k^+) _k] =[ukuk⊤∣ℱk](xi(tk)−xj(tk)) =E[u_ku_k _k]\,(x^i(t_k)-x^j(t_k)) =xi(tk)−xj(tk). =x^i(t_k)-x^j(t_k). (15) Within a holding interval, however, the states depend on the sampled direction, so this factorization is available only at refresh times. The analysis below controls this dependence through the component of the state along uku_k. Error coordinates. Let x=col(x1,…,xN)x=col(x^1,…,x^N) and define the stacked cost G(x)=∑i=1Nfi(xi)G(x)= _i=1^Nf^i(x^i), whose gradient stacks the local gradients (in contrast to the common-argument cost F in (1)). Let x⋆=N⊗z⋆,v⋆=−α∇G(x⋆),x =1_N z , v =-α∇ G(x ), (16) and define the errors x~=x−x⋆ x=x-x , v~=v−v⋆ v=v-v and h=∇G(x)−∇G(x⋆)h=∇ G(x)-∇ G(x ). Following [8], let r=N/Nr=1_N/ N and let R∈ℝN×(N−1)R ^N×(N-1) satisfy r⊤R=0r R=0, R⊤R=IN−1R R=I_N-1, and RR⊤=IN−1NNN⊤R =I_N- 1N1_N1_N , and apply the orthogonal change of variables z=([rR]⊤⊗Id)x~,w=([rR]⊤⊗Id)v~,z= ([r\ R] \! I_d ) x, w= ([r\ R] \! I_d ) v, (17) partitioned as z=(z1,z2)z=(z_1,z_2) and w=(w1,w2)w=(w_1,w_2) with z1,w1∈ℝdz_1,w_1 ^d. Here z1z_1 is the (scaled) average error and z2z_2 the disagreement. Let L^=R⊤LR∈ℝ(N−1)×(N−1) L=R LR ^(N-1)×(N-1), which is symmetric positive definite with eigenvalues λ2≤⋯≤λN _2≤·s≤ _N (the positive eigenvalues of L), and satisfies LR=RL^LR=R L. Write h¯=([rR]⊤⊗Id)h=(h1,h2) h=([r\ R] I_d)h=(h_1,h_2), so that z⊤h¯=x~⊤hz h= x h and ‖h¯‖=‖h‖\| h\|=\|h\|. Because r⊤L=0r L=0, along (6a)–(6b) we have w˙1=0 w_1=0, and the initialization ∑ivi(0)=0 _iv^i(0)=0 gives w1(t)≡0w_1(t)≡ 0: this is the constant of motion identified in [8]. The remaining error dynamics, with P=ukuk⊤P=u_ku_k on [tk,tk+1)[t_k,t_k+1), are z˙1 z_1 =−αh1, =-α h_1, (18a) z˙2 z_2 =−αh2−β(L^⊗P)z2−w2, =-α h_2-β( L P)z_2-w_2, (18b) w˙2 w_2 =αβ(L^⊗P)z2. =αβ( L P)z_2. (18c) The reduced state ζ=col(z1,z2,w2)ζ=col(z_1,z_2,w_2) has the origin as its unique equilibrium common to almost every direction realization on the zero-sum integral-state subspace; for an individual fixed direction, additional spurious equilibria may exist, as shown in Section I-B. Since (17) is an isometry, ‖ζ‖2=‖x~‖2+‖v~‖2\|ζ\|^2=\| x\|^2+\| v\|^2, and convergence of ζ is equivalent to convergence of (x,v)(x,v) to (x⋆,v⋆)(x ,v ). The zero eigenvalue of L has been removed: no invariant subspace needs to be tracked, and all Lyapunov functions below are positive definite on the whole reduced state space. Projected states. On [tk,tk+1)[t_k,t_k+1) let u^=uk/d u=u_k/ d, so P=du^u^⊤P=d\, u u , and for y∈ℝ(N−1)dy ^(N-1)d let y∥=(IN−1⊗u^⊤)y∈ℝN−1y =(I_N-1 u )y ^N-1 collect the components along uku_k. Write a=z2∥a=z_2 , b=w2∥b=w_2 , and h∥=h2∥h =h_2 . Then (L^⊗P)y=d(L^y∥)⊗u^( L P)y=d\,( Ly ) u and, for ℱkF_k-measurable y, ‖y∥‖≤‖y‖,[‖y∥‖2∣ℱk]=‖y‖2/d.\|y \|≤\|y\|, [\|y \|^2 _k ]=\|y\|^2/d. (19) The projected dynamics of (18b)–(18c) are a˙=−αh∥−βdL^a−b,b˙=αβdL^a. a=-α h -β d\, La-b, b=αβ d\, La. (20) The only O(d)O(d) term in (18), −βd(L^a)⊗u^-β d( La) u, is dissipative. It acts only on a, whose mean square at a refresh is ‖z2‖2/d\|z_2\|^2/d by (19). The average error z1z_1 is not affected by the direction at all. Lyapunov function. Define b− b_- =min1,1/(αβλN),b+=max1,1/(αβλ2), = \1,1/(αβ _N)\, b_+= \1,1/(αβ _2)\, B B =αℓf+βλN, =α _f+β _N, (21) choose 0<ε≤minb−2,αmfB2,12α,0< ≤ \ b_-2,\ α m_fB^2,\ 12α \, (22) and set c−=b−εc_-=b_-- , c+=b++εc_+=b_++ , c0=12minαmf,εc_0= 12 \α m_f, \, and κ=1+εβλNκ=1+ β _N. Consider Vε=12z⊤z+12αβw2⊤(L^−1⊗Id)w2+εz2⊤w2.V_ = 12z z+ 12αβw_2 ( L^-1 I_d)w_2+ z_2 w_2. (23) Since λN−1I⪯L^−1⪯λ2−1I _N^-1I L^-1 _2^-1I and |εz2⊤w2|≤ε2‖ζ‖2| z_2 w_2|≤ 2\|ζ\|^2, c−2‖ζ‖2≤Vε(ζ)≤c+2‖ζ‖2, c_-2\|ζ\|^2≤ V_ (ζ)≤ c_+2\|ζ\|^2, (24) so VεV_ is positive definite and radially unbounded on the reduced state space. Using this Lyapunov function, we establish in Appendix three auxiliary results that lead to our main theorem. Lemma A.1 bounds the growth of the state over one holding interval by a constant independent of d; Lemma A.2 decomposes V˙ε V_ along (18) into a strictly dissipative part, a term absorbed by the O(d)O(d) dissipation in (20), and a term that has zero conditional mean at refresh times; and Lemma A.3 shows that the projected quantities a, b, h∥h , and the deviation ζ(t)−ζ(tk)ζ(t)-ζ(t_k), have conditional mean square O(1/d)O(1/d) over the holding interval. Together these control the dependence of the held direction on the evolving state and yield the following result. Theorem I.1 Let Assumption 1 hold, let G be connected and undirected, let ∑ivi(0)=0 _iv^i(0)=0, and let the directions uku_k be drawn independently across refreshes so that (14) holds. Let γ¯=γ(1/C¯) γ=γ(1/ C) and θ¯=1+α2ℓf2(1+Ch2γ¯2/4) θ=1+α^2 _f^2(1+C_h^2 γ^2/4), and define the d-independent constants ρ0 _0 =min14α,142αβλN, = \ 14α, 14 2\,αβ _N, 1κc0128βλN,132βλN2+α2, 1κ c_0128β _N, 132β _N 2+α^2 \, σ0 _0 =min1,1αβλN(1+ℓf),164Ch2γ¯2, = \1, 1αβ _N(1+ _f), 164C_h^2 γ^2 \, τ0 _0 =min1,1C¯,1θ¯,c016K0, = \1, 1 C, 1 θ, c_016K_0 \, where K0=23ακℓf+82βκλN+4εβλN+32εαβ2λN2+c7γ¯2K_0=2 3\,ακ _f+8 2\,βκ _N+4 β _N+32 αβ^2 _N^2+c_7 γ^2, and let τ¯d=minτ0,ρ0d,σ0d>0. τ_d= \ _0,\ _0d,\ _0d \>0. (25) If τ∈(0,τ¯d]τ∈(0, τ_d], then the trajectories of (6a)–(6b) converge to (x⋆,v⋆)(x ,v ) exponentially fast in mean square and almost surely. In particular, with r=1−c0τ/(2c+)r=1-c_0τ/(2c_+), ‖ζ(tk)‖2≤c+c−rk‖ζ(0)‖2.E\|ζ(t_k)\|^2≤ c_+c_-\,r^k\,\|ζ(0)\|^2. (26) Proof: The condition τ≤τ¯dτ≤ τ_d is equivalent to τ≤τ0,dτ≤ρ0,dτ2≤σ0,τ≤ _0, d\,τ≤ _0, d\,τ^2≤ _0, (27) and τ¯d τ_d depends only on the problem data, so refresh times are separated by the fixed interval τ>0τ>0 and every interval [0,T][0,T] contains finitely many of them; on each holding interval the right-hand side of (18) is globally Lipschitz, so the solution exists, is unique, and by Lemma A.1 stays bounded. Integrate (A.1) over the holding interval and write ∫0τSus=τSu(ζk)+∫0τ(τ−s)S˙us _0^τS_u\,ds=τ S_u( _k)+ _0^τ(τ-s) S_u\,ds. This gives Vε(tk+1)−Vε(tk)≤−c0∫0τ∥ζ∥2ds V_ (t_k+1)-V_ (t_k)≤-c_0\! _0^τ\!\|ζ\|^2ds −βd(1−εα)∫0τa⊤L^ads+τSu(ζk)+τ∫0τ[S˙u]+ds. -β d(1- α)\! _0^τ\!a La\,ds+τ S_u( _k)+τ\! _0^τ\![ S_u]_+\,ds. Bound [S˙u]+[ S_u]_+ using (A.2). Since 1−εα≥121- α≥ 12 and αρ≤14αρ≤ 14, the first term of (A.2), multiplied by τ, is at most 12βd(1−εα)a⊤L^a 12β d(1- α)a La. By Young’s inequality, τ times the second term is at most 14βd(1−εα)a⊤L^a+2βκ2λNd3τ2‖b‖2 14β d(1- α)a La+2βκ^2 _Nd^3τ^2\|b\|^2. The dissipative integral absorbs both a⊤L^a La parts along every trajectory. Next, take conditional expectations. The term τSu(ζk)τ S_u( _k) vanishes by Lemma A.2. Condition (27) ensures κa≤32 _a≤ 32, κb≤4 _b≤ 4, κh≤3ℓf2 _h≤ 3 _f^2, and κδ≤18 _δ≤ 18. Lemma A.3 and the Cauchy–Schwarz inequality then give: • the ‖b‖2\|b\|^2 remainder is at most 2βκ2λNκbρ2τ‖ζk‖2≤c016τ‖ζk‖22βκ^2 _N _bρ^2τ\| _k\|^2≤ c_016τ\| _k\|^2; • the remaining terms of (A.2) contribute at most τ2K0‖ζk‖2≤c016τ‖ζk‖2τ^2K_0\| _k\|^2≤ c_016τ\| _k\|^2; • since ‖ζ(s)‖2≥12‖ζk‖2−‖ζ(s)−ζk‖2\|ζ(s)\|^2≥ 12\| _k\|^2-\|ζ(s)- _k\|^2, the first integral contributes at most −38c0τ‖ζk‖2- 38c_0τ\| _k\|^2 by (A.4). Hence [Vε(tk+1)∣ℱk]−Vε(tk)≤−c0τ4‖ζk‖2≤−c0τ2c+Vε(tk),E[V_ (t_k+1) _k]-V_ (t_k)≤- c_0τ4\| _k\|^2≤- c_0τ2c_+V_ (t_k), and iterating with (24) gives (26). Between refreshes, Lemma A.1 gives [suptk≤t≤tk+1‖ζ(t)‖2]≤γ¯2‖ζ(tk)‖2E[ _t_k≤ t≤ t_k+1\|ζ(t)\|^2]≤ γ^2E\|ζ(t_k)\|^2. For any r¯∈(r,1) r∈(r,1), Markov’s inequality shows that ∑kℙ(sup[tk,tk+1]‖ζ‖2>r¯k)<∞ _kP( _[t_k,t_k+1]\|ζ\|^2> r^k)<∞, and the Borel–Cantelli lemma yields almost sure exponential convergence. Since (17) is an isometry, the same statements hold for (x~,v~)( x, v). ∎ Remark I.1 (Dimension dependence) For d≥ρ02/σ0d≥ _0^2/ _0, (25) reduces to τ¯d=minτ0,ρ0/d τ_d= \ _0, _0/d\, so the admissible holding interval scales as 1/d1/d, while the decay rate per unit time, c0/(2c+)c_0/(2c_+), does not depend on d and matches, up to constants, the rate the same Lyapunov argument gives for full-vector exchange. A bound based only on the worst-case norm ‖L^⊗ukuk⊤‖=λNd\| L u_ku_k \|= _Nd would give τ=O(1/d2)τ=O(1/d^2); the improvement comes from the two facts noted after (20). In the continuous-time model, refreshing costs no communication, since uku_k is regenerated locally, and each link carries one real-valued signal instead of d for every admissible τ. In a sampled implementation that transmits one scalar per refresh, however, the condition τ≤τ¯d=O(1/d)τ≤ τ_d=O(1/d) implies O(d)O(d) scalar transmissions per unit time per link, the same order as one full-vector message per unit time. The guarantee therefore establishes a reduction in message size, which is what a per-message bandwidth limit constrains, and not a reduction in total scalar throughput. The example in Section IV converges at refresh intervals well above τ¯d τ_d, which suggests the bound is conservative; whether the throughput also decreases is an open question that requires the sampled-data analysis left to future work. Remark I.2 (Conservativeness) The constants in (25) are sufficient, not necessary. In the example of Section IV, convergence is observed for holding intervals well beyond τ¯d τ_d, and the error at a fixed time grows with dτdτ (Fig. 2b), so some bound is needed even though (25) is not tight. The threshold is governed by the term 1/(αβλN)1/(αβ _N) in ρ0 _0, which bounds the integral action αβdL^αβ d L accumulated over one holding interval. Remark I.3 (Gaussian directions) Lemmas A.2 and A.3 use ‖uk‖2=d\|u_k\|^2=d through P=du^u^⊤P=d\, u u ; for uk=gku_k=g_k the factor d is replaced by ‖gk‖2\|g_k\|^2, which is unbounded, which is why no refresh bound of the form (25) follows. Normalizing to the sphere of radius d d restores (14) and gives encoding variance (d−1)‖a‖2(d-1)\|a\|^2, the same as (R) and (C). I-D Encoding Variance and Exactness of Convergence Theorem I.1 guarantees convergence to z⋆z under the refresh condition. Random encoding nevertheless introduces transient fluctuations, which we now quantify at the refresh times. Let P(t)=IN⊗(ukuk⊤)P(t)=I_N (u_ku_k ) on [tk,tk+1)[t_k,t_k+1) and decompose P(t)=INd+k,[k∣ℱk]=0.P(t)=I_Nd+ _k, [ _k _k]=0. (28) With the coupling perturbation ξ(t)=(L⊗Id)kx~(t)ξ(t)=(L I_d) _k x(t), the error dynamics read x~˙ x =−αh−β(L⊗Id)x~−v~−βξ(t), =-α h-β(L I_d) x- v-βξ(t), (29) v~˙ v =αβ(L⊗Id)x~+αβξ(t). =αβ(L I_d) x+αβξ(t). This is a random differential equation with piecewise-constant directions, not an Itô stochastic differential equation; a diffusion approximation would require a separate limiting argument. The perturbation enters both the state and the integral equations, is multiplicative in the disagreement, and vanishes at consensus. Encoding variance For a fixed a∈ℝda ^d, unnormalized Gaussian fourth moments give [(uu⊤)2]=(d+2)IdE[(u )^2]=(d+2)I_d, hence ‖(uu⊤−Id)a‖2=(d+1)‖a‖2.E\|(u -I_d)a\|^2=(d+1)\|a\|^2. (30) For any fixed-norm direction, including (R), (C), and sphere-normalized Gaussian, ‖u‖2=d\|u\|^2=d and [(uu⊤)2]=dIdE[(u )^2]=dI_d, so ‖(uu⊤−Id)a‖2=(d−1)‖a‖2.E\|(u -I_d)a\|^2=(d-1)\|a\|^2. (31) Consequently, at each refresh time, [ξ(tk+)∣ℱk] [ξ(t_k^+) _k] =0, =0, (32) [‖ξ(tk+)‖2∣ℱk] [\|ξ(t_k^+)\|^2 _k] =ω‖(L⊗Id)x~k‖2≤ωλN2‖x~k‖2, =ω\|(L I_d) x_k\|^2≤ω _N^2\| x_k\|^2, (33) with ω=d+1ω=d+1 for unnormalized Gaussian and ω=d−1ω=d-1 for fixed-norm directions. Fixed-norm directions thus reduce the encoding variance by 2‖(L⊗Id)x~k‖22\|(L I_d) x_k\|^2 relative to the unnormalized Gaussian choice, the direct analogue of the variance reduction established for federated aggregation in [9]. The fixed-norm choices differ in how this variance is distributed: coordinate directions concentrate it on the sampled coordinate, whereas Rademacher directions spread it over all coordinates and yield a transmitted scalar that is sub-Gaussian with parameter ‖xi‖\|x^i\| rather than of magnitude up to d‖xi‖ d\,\|x^i\|. For all of these unbiased encoders the variance grows linearly with d; it is the refresh condition, not the choice of encoder, that controls the error. These identities concern a freshly drawn direction; no independence is assumed within a holding interval. Exact convergence Let X(t)=[x~(t)x~(t)⊤]X(t)=E[ x(t) x(t) ]. By Theorem I.1, limt→∞trX(t)=limt→∞‖x~(t)‖2=0 _t→∞trX(t)= _t→∞E\| x(t)\|^2=0. Hence, with constant positive gains and sufficiently frequent refreshes, scalar communication yields exact convergence: random encoding does not leave a residual error ball. This is consistent with (29), since ξ vanishes when all agents agree. In particular, no diminishing coupling gain is required. The result concerns the held-direction continuous-time model; a sampled-message or discrete-time implementation requires its own step-size and sampling analysis. IV Numerical Example We consider distributed ℓ2 _2-regularized logistic regression over N=20N=20 agents with decision dimension d=64d=64. Agent i minimizes the local cost fi(x)=1m∑s=1mlog(1+e−yi,sai,s⊤x)+0.32‖x‖2,f^i(x)= 1mΣ _s=1^m \! (1+e^-y_i,sa_i,s x )+ 0.32\|x\|^2, (34) where ai,s∈ℝ64a_i,s ^64 and yi,s∈−1,+1y_i,s∈\-1,+1\. Each agent communicates with the agents one and three positions away in either direction around a cycle, with edge weights 1/81/8. We set α=β=1α=β=1 and initialize xi(0)=vi(0)=0x^i(0)=v^i(0)=0. Fig. 1: Relative RMS error at dτ=2dτ=2 for concentrated (left) and spread (right) gradient differences. Results use 4096 runs; shaded bands show pointwise 95% bootstrap confidence intervals for the RMS estimate. We construct synthetic data to control which coordinates cause disagreement between agents. Each agent receives 128 samples with feature vector γjej _je_j for each coordinate j, giving m=8192m=8192 samples in total. Here, eje_j is the jjth coordinate vector, γj=16 _j=16 for j≤49j≤ 49, and γj=2 _j=2 otherwise. Thus, each sample involves a single coordinate, and the feature magnitudes create different curvatures across coordinates. The local costs are strongly convex and have globally Lipschitz gradients, with mf=0.3m_f=0.3 and ℓf≤1.3 _f≤ 1.3. Agents are divided into two groups that alternate around the cycle. The groups have identical feature vectors but different labels. For coordinate 1, every agent has 96 positive and 32 negative labels. We then consider two cases. In the concentrated case, the two groups have 16 and 112 positive labels, respectively, among the 128 samples for coordinate 50; every other coordinate except coordinate 1 has equally many positive and negative labels. In the spread case, the groups instead have 63 and 65 positive labels for each coordinate from 2 through 37; all coordinates other than these and coordinate 1 are balanced. The differences between agents therefore occur in one weak-curvature coordinate in the first case and in 36 stronger-curvature coordinates in the second. Both cases have the same aggregate objective and optimizer z⋆z . They also have the same magnitude of local gradient differences: ‖∇fi(x)−N−1∑j∇fj(x)‖=3/256\|∇ f^i(x)-N^-1 _j∇ f^j(x)\|=3/256. This construction lets us compare the effect of where those differences occur while keeping their overall magnitude fixed. We compare scalar communication with shared Rademacher directions uk∈−1,+164u_k∈\-1,+1\^64, scalar communication with shared coordinate directions uk=64eJku_k= 64\,e_J_k for uniformly sampled JkJ_k, and full-vector exchange. Directions are drawn independently at intervals of length τ and held constant between refreshes. We simulate the continuous-time dynamics using fourth-order Runge–Kutta integration, with steps ending at each refresh. The integration step is at most minτ/4, 0.4/(d+1.3) \τ/4,\,0.4/(d+1.3)\ for all methods. For M independent runs, the relative RMS error is ERMS(t)=1‖z⋆‖(1MN∑r=1M∑i=1N‖xri(t)−z⋆‖2)1/2.E_RMS(t)= 1\|z \| ( 1MN _r=1^M _i=1^N\|x_r^i(t)-z \|^2 )^1/2. (35) This measures the distance to the optimizer, averaged over agents and runs, relative to its initial value. Since all agents start at zero, ERMS(0)=1E_RMS(0)=1. Figure 1 compares the two data sets at τ=2/64τ=2/64, using M=4096M=4096 runs per stochastic method. In the concentrated case, Rademacher encoding gives a substantially smaller RMS error: at t=20t=20, its error is 0.005040.00504, compared with 0.07600.0760 for coordinate encoding. The ordering reverses in the spread case, where coordinate encoding reaches 0.002450.00245, compared with 0.004140.00414 for Rademacher encoding. In this separable problem, coordinate feedback acts on individual coordinates, whereas Rademacher feedback couples coordinates with different curvatures. The comparison shows that this mixing can help or hurt depending on where the differences between agents occur. These are RMS comparisons: coordinate encoding can have a smaller median error but a larger RMS error because some runs converge much more slowly. Thus, neither direction distribution is uniformly better, consistent with the theorem providing convergence guarantees for both. Fig. 2: Effect of refreshing in the concentrated case: (a) error versus time; (b) RMS error at t=40t=40 versus dτdτ. Error bars show pointwise 95% bootstrap confidence intervals. Figure 2 shows the effect of the holding interval in the concentrated case. Panel (a) shows that frequent refreshing leads to faster error decay, whereas a fixed direction leaves a persistent error. Panel (b) reports the RMS error at t=40t=40 for different values of dτdτ. Smaller holding intervals give lower errors for both encoders, while Rademacher encoding performs better at larger holding intervals in this example. These results illustrate how scalar communication can support convergence to the optimizer while reducing the size of the exchanged information. Each agent transmits only the scalar uk⊤xiu_k x^i, and its neighbors reconstruct the shared direction locally. The communicated state therefore has one component instead of d, reducing the per-message payload from (d)O(d) to (1)O(1) in a sampled implementation. This makes the mechanism attractive for channels that can accommodate a scalar message but cannot carry a full state vector within the available transmission budget. The continuous-time results demonstrate convergence with scalar-valued exchange, providing the basis for such bandwidth-constrained implementations. V Conclusions We introduced a scalar-communication mechanism for consensus-based distributed optimization in which each neighbor message carries a single real number regardless of the decision dimension. Agents regenerate a common random direction from a shared seed, transmit the projection of their state onto that direction, and act on a rank-one surrogate of their neighbors’ states. We showed that the optimal consensus equilibrium is preserved, that fixed directions can introduce spurious equilibria, and that sufficiently frequent direction refreshes yield exponential mean-square and almost-sure convergence with constant gains and no residual error for strongly convex objectives with Lipschitz gradients. Simulations illustrated the effects of the direction distribution and refresh interval. Future work includes a discrete-time formulation with sampled and quantized scalar messages, tighter refresh-interval bounds, extensions to directed and time-varying networks, robustness to unreliable communication channels through redundant scalar transmissions, and the combination of scalar communication with event-triggered scheduling to reduce both message size and communication frequency. References [1] A. Nedić and A. Ozdaglar, “Distributed subgradient methods for multi-agent optimization,” IEEE Transactions on Automatic Control, vol. 54, no. 1, p. 48–61, 2009. [2] G. Qu and N. Li, “Harnessing smoothness to accelerate distributed optimization,” IEEE Transactions on Control of Network Systems, vol. 5, no. 3, p. 1245–1260, 2018. [3] A. Nedić and J. Liu, “Distributed optimization for control,” Annual Review of Control, Robotics, and Autonomous Systems, vol. 1, p. 77–103, 2018. [4] T. Yang, X. Yi, J. Wu, Y. Yuan, D. Wu, Z. Meng, Y. Hong, H. Wang, Z. Lin, and K. H. Johansson, “A survey of distributed optimization,” Annual Reviews in Control, vol. 47, p. 278–305, 2019. [5] M. Rostami and S. S. Kia, “Adaptive threshold-driven continuous greedy method for scalable submodular optimization,” IEEE Control Systems Letters, 2026. [6] D. V. Dimarogonas, E. Frazzoli, and K. H. Johansson, “Distributed event-triggered control for multi-agent systems,” IEEE Transactions on Automatic Control, vol. 57, no. 5, p. 1291–1297, 2012. [7] G. S. Seyboth, D. V. Dimarogonas, and K. H. Johansson, “Event-based broadcasting for multi-agent average consensus,” Automatica, vol. 49, no. 1, p. 245–252, 2013. [8] S. S. Kia, J. Cortés, and S. Martínez, “Distributed convex optimization via continuous-time coordination algorithms with discrete-time communication,” Automatica, vol. 55, p. 254–264, 2015. [9] M. Rostami and S. Kia, “Fedscalar: Federated learning with scalar communication for bandwidth-constrained networks,” arXiv preprint arXiv:2410.02260, 2024. [10] M. Rostami, S. Talebi, and S. S. Kia, “Scalar federated learning for linear quadratic regulator,” arXiv preprint arXiv:2604.05088, 2026. [11] M. Rostami and S. S. Kia, “Fedmpdd: Communication-efficient federated learning with privacy preservation attributes via projected directional derivative,” arXiv preprint arXiv:2512.20814, 2025. [12] A. Kashyap, T. Başar, and R. Srikant, “Quantized consensus,” Automatica, vol. 43, no. 7, p. 1192–1203, 2007. [13] R. Carli, F. Fagnani, P. Frasca, and S. Zampieri, “Gossip consensus algorithms via quantized communication,” Automatica, vol. 46, no. 1, p. 70–80, 2010. [14] T. Li, M. Fu, L. Xie, and J.-F. Zhang, “Distributed consensus with limited communication data rate,” IEEE Transactions on Automatic Control, vol. 56, no. 2, p. 279–292, 2011. [15] A. Nedić, A. Olshevsky, A. Ozdaglar, and J. N. Tsitsiklis, “Distributed subgradient methods and quantization effects,” in Proc. 47th IEEE Conference on Decision and Control, (Cancun, Mexico), p. 4177–4184, 2008. [16] P. Yi and Y. Hong, “Quantized subgradient algorithm and data-rate analysis for distributed optimization,” IEEE Transactions on Control of Network Systems, vol. 1, no. 4, p. 380–392, 2014. [17] Y. Pu, M. N. Zeilinger, and C. N. Jones, “Quantization design for distributed optimization,” IEEE Transactions on Automatic Control, vol. 62, no. 5, p. 2107–2120, 2017. [18] S. Magnússon, C. Enyioha, N. Li, C. Fischione, and V. Tarokh, “Convergence of limited communication gradient methods,” IEEE Transactions on Automatic Control, vol. 63, no. 5, p. 1356–1371, 2018. [19] T. T. Doan, S. T. Maguluri, and J. Romberg, “Fast convergence rates of distributed subgradient methods with adaptive quantization,” IEEE Transactions on Automatic Control, vol. 66, no. 5, p. 2191–2205, 2021. [20] A. Reisizadeh, A. Mokhtari, H. Hassani, and R. Pedarsani, “An exact quantized decentralized gradient descent algorithm,” IEEE Transactions on Signal Processing, vol. 67, no. 19, p. 4934–4947, 2019. [21] Y. Kajiyama, N. Hayashi, and S. Takai, “Linear convergence of consensus-based quantized optimization for smooth and strongly convex cost functions,” IEEE Transactions on Automatic Control, vol. 66, no. 3, p. 1254–1261, 2021. [22] D. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnovic, “QSGD: Communication-efficient SGD via gradient quantization and encoding,” in Advances in Neural Information Processing Systems, vol. 30, 2017. [23] S. U. Stich, J.-B. Cordonnier, and M. Jaggi, “Sparsified SGD with memory,” in Advances in Neural Information Processing Systems, vol. 31, 2018. [24] S. P. Karimireddy, Q. Rebjock, S. Stich, and M. Jaggi, “Error feedback fixes SignSGD and other gradient compression schemes,” in Proceedings of the 36th International Conference on Machine Learning, vol. 97 of Proceedings of Machine Learning Research, p. 3252–3261, 2019. [25] A. Koloskova, S. Stich, and M. Jaggi, “Decentralized stochastic optimization and gossip algorithms with compressed communication,” in Proceedings of the 36th International Conference on Machine Learning, vol. 97 of Proceedings of Machine Learning Research, p. 3478–3487, 2019. [26] Y. Liao, Z. Li, K. Huang, and S. Pu, “A compressed gradient tracking method for decentralized optimization with linear convergence,” IEEE Transactions on Automatic Control, vol. 67, no. 10, p. 5622–5629, 2022. [27] Y. Liao, Z. Li, S. Pu, and T.-H. Chang, “A robust compressed push-pull method for decentralized nonconvex optimization.” arXiv preprint arXiv:2408.01727, 2024. [28] J. Wang and N. Elia, “Control approach to distributed optimization,” in Proc. 48th Annual Allerton Conference on Communication, Control, and Computing, (Monticello, IL, USA), p. 557–561, 2010. [29] J. Wang and N. Elia, “A control perspective for centralized and distributed convex optimization,” in Proc. 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC), (Orlando, FL, USA), p. 3800–3805, 2011. [30] B. Gharesifard and J. Cortés, “Distributed continuous-time convex optimization on weight-balanced digraphs,” IEEE Transactions on Automatic Control, vol. 59, no. 3, p. 781–786, 2014. [Auxiliary Results] Lemma A.1 (Dimension-free growth) For any direction and 0≤s≤τ0≤ s≤τ, ‖ζ(tk+s)‖≤γ(s)‖ζ(tk)‖\|ζ(t_k+s)\|≤γ(s)\|ζ(t_k)\|, where γ(s)=(1+α)1+(1+α)2eC¯sγ(s)=(1+α) 1+(1+α)^2\,e Cs and C¯=max1+α,α+α2(1+ℓf) C= \1+α,\ α+α^2(1+ _f)\. Proof: Let q=w2+αz2q=w_2+α z_2. By (18b)–(18c), q˙=−α(αh2+w2) q=-α(α h_2+w_2), so the direction-dependent terms cancel. Also, by (18) and z⊤h¯≥0z h≥ 0, dt12‖z‖2=−αz⊤h¯−βda⊤L^a−z2⊤w2≤‖z‖‖w2‖ ddt 12\|z\|^2=-α z h-β d\,a La-z_2 w_2≤\|z\|\|w_2\|. Using ‖w2‖≤‖q‖+α‖z‖\|w_2\|≤\|q\|+α\|z\| and ‖h¯‖≤ℓf‖z‖\| h\|≤ _f\|z\|, m=‖z‖+‖q‖m=\|z\|+\|q\| satisfies m˙≤C¯m m≤ Cm. Since m(0)≤1+(1+α)2‖ζ(tk)‖m(0)≤ 1+(1+α)^2\,\|ζ(t_k)\| and ‖ζ‖≤(1+α)m\|ζ\|≤(1+α)m, the claim follows. ∎ Lemma A.2 (Decomposition of V˙ε V_ ) For a fixed direction, along (18), V˙ε=g¯(ζ)−βd(1−εα)a⊤L^a+Su(ζ), V_ = g(ζ)-β d(1- α)\,a La+S_u(ζ), (A.1) where g¯ g =−αz⊤h¯−εw2⊤(αh2+β(L^⊗Id)z2)−ε‖w2‖2 =-α z h- w_2 (α h_2+β( L I_d)z_2 )- \|w_2\|^2 ≤−c0‖ζ‖2, ≤-c_0\|ζ\|^2, Su S_u =db⊤a−w2⊤z2−εβ(db⊤L^a−w2⊤(L^⊗Id)z2), =d\,b a-w_2 z_2- β (d\,b La-w_2 ( L I_d)z_2 ), and [Suk(ζ(tk))∣ℱk]=0E[S_u_k(ζ(t_k)) _k]=0. Proof: With ∇z1Vε=z1 _z_1V_ =z_1, ∇z2Vε=z2+εw2 _z_2V_ =z_2+ w_2, and ∇w2Vε=1αβ(L^−1⊗Id)w2+εz2 _w_2V_ = 1αβ( L^-1 I_d)w_2+ z_2, a direct expansion along (18) using (L^⊗P)z2=d(L^a)⊗u^( L P)z_2=d( La) u and w2⊤(L^−1L^⊗u^u^⊤)z2=b⊤aw_2 ( L^-1 L u u )z_2=b a gives (A.1). The bound on g¯ g follows from z⊤h¯=x~⊤h≥mf‖z‖2z h= x h≥ m_f\|z\|^2, ‖αh2+β(L^⊗Id)z2‖≤B‖z‖\|α h_2+β( L I_d)z_2\|≤ B\|z\|, Young’s inequality, and (22). The zero mean follows from (19), since [db⊤a]=w2⊤z2E[d\,b a]=w_2 z_2 and [db⊤L^a]=w2⊤(L^⊗Id)z2E[d\,b La]=w_2 ( L I_d)z_2. ∎ The bound g¯≤−c0‖ζ‖2 g≤-c_0\|ζ\|^2 holds along every trajectory, not only in expectation, and the second term of (A.1) is dissipative. Only SuS_u has an indefinite sign. Because it is quadratic, differentiating along (18)–(20) and dropping nonpositive terms gives S˙u≤ S_u≤ αβd2a⊤L^a+βκλNd2‖b‖a⊤L^a αβ d^2a La+βκ _N\,d^2\|b\| a La +d(ακ‖b‖‖h∥‖+βκλN‖b‖‖a‖+εβλN‖b‖2CLOSE +d (ακ\|b\|\|h \|+βκ _N\|b\|\|a\|+ β _N\|b\|^2 OPEN+εαβ2λN2‖a‖2)+c7‖ζ‖2, + αβ^2 _N^2\|a\|^2 )+c_7\|ζ\|^2, (A.2) with c7=1+ακℓf/2c_7=1+ακ _f/2. The two O(d2)O(d^2) terms are paired with a⊤L^a La and can be absorbed by the dissipative term in (A.1). Every other factor d multiplies a product of two projected quantities, and the next lemma shows that each has mean square O(1/d)O(1/d). Lemma A.3 (Projected moments) Let ρ=dτρ=dτ and suppose dτ2≤min1,1/(αβλN(1+ℓf))dτ^2≤ \1,1/(αβ _N(1+ _f))\. Then [suptk≤t≤tk+1‖y(t)‖2|ℱk]≤κyd‖ζ(tk)‖2E [ _t_k≤ t≤ t_k+1\|y(t)\|^2\, |\,F_k ]≤ _yd\,\|ζ(t_k)\|^2 (A.3) for y∈a,b,h∥y∈\a,b,h \ (writing κh _h for κh∥ _h ), and [suptk≤t≤tk+1‖ζ(t)−ζ(tk)‖2|ℱk]≤κδd‖ζ(tk)‖2,E [ _t_k≤ t≤ t_k+1\|ζ(t)-ζ(t_k)\|^2\, |\,F_k ]≤ _δd\,\|ζ(t_k)\|^2, (A.4) where, with Ch=1+α2ℓf2C_h= 1+α^2 _f^2, γ=γ(τ)γ=γ(τ) from Lemma A.1, and θ=1+α2ℓf2(1+Ch2γ2/4)θ=1+α^2 _f^2 (1+C_h^2γ^2/4 ), κa _a =16(1+θτ2),κb=2(1+α2β2λN2ρ2κa), =16(1+θτ^2), _b=2 (1+α^2β^2 _N^2ρ^2 _a ), κz _z =2(ρτCh2γ2+β2λN2ρ2κa),κh=2ℓf2(1+κz), =2 (ρτ C_h^2γ^2+β^2 _N^2ρ^2 _a ), _h=2 _f^2(1+ _z), κδ _δ =κz+α2β2λN2ρ2κa. = _z+α^2β^2 _N^2ρ^2 _a. (A.5) These constants depend on (α,β,λN,ℓf,ρ,τ)(α,β, _N, _f,ρ,τ) but not on d. Proof: Fix a realization of uku_k and write s=t−tk∈[0,τ]s=t-t_k∈[0,τ], ζk=ζ(tk) _k=ζ(t_k), and likewise zk,ak,bk,hk∥z_k,a_k,b_k,h_k . Let A=sups∈[0,τ]‖a(s)‖A= _s∈[0,τ]\|a(s)\|; all suprema below are over s∈[0,τ]s∈[0,τ]. Step 1: pathwise bounds in terms of A. From (18), ‖L^a‖≤λN‖a‖\| La\|≤ _N\|a\|, and ‖(L^a)⊗u^‖=‖L^a‖\|( La) u\|=\| La\|, ‖w2(s)−w2,k‖ \|w_2(s)-w_2,k\| ≤αβλNdsA, ≤αβ _Nd\,sA, (A.6) ‖z(s)−zk‖ \|z(s)-z_k\| ≤∫0s(α‖h¯‖+‖w2‖)+βλNsA ≤ _0^s\! (α\| h\|+\|w_2\| )+β _Nd\,sA ≤sChγ‖ζk‖+βλNdsA, ≤ sC_hγ\| _k\|+β _Nd\,sA, (A.7) where we used α‖h¯‖+‖w2‖≤αℓf‖z‖+‖w2‖≤Ch|ζ|≤Chγ‖ζk‖α\| h\|+\|w_2\|≤α _f\|z\|+\|w_2\|≤ C_h\|ζ\|≤ C_hγ\| _k\| by Lemma A.1. Since ‖y∥‖≤‖y‖\|y \|≤\|y\| and ‖h2(s)−h2,k‖≤‖h¯(s)−h¯k‖≤ℓf‖z(s)−zk‖\|h_2(s)-h_2,k\|≤\| h(s)- h_k\|≤ _f\|z(s)-z_k\|, ‖b(s)‖ \|b(s)\| ≤‖bk‖+αβλNdsA, ≤\|b_k\|+αβ _Nd\,sA, (A.8) ‖h∥(s)‖ \|h (s)\| ≤‖hk∥‖+ℓf‖z(s)−zk‖ ≤\|h_k \|+ _f\|z(s)-z_k\| ≤‖hk∥‖+ℓfsChγ‖ζk‖+βℓfλNdsA. ≤\|h_k \|+ _fsC_hγ\| _k\|+β _f _Nd\,sA. (A.9) Step 2: closing the bound on A. From (20) and a⊤L^a≥0a La≥ 0, ds‖a‖≤α‖h∥‖+‖b‖ dds\|a\|≤α\|h \|+\|b\| wherever a≠0a≠ 0. Integrating and inserting (A.8) and (A.9), A≤ A≤ ‖ak‖+τ(α‖hk∥‖+‖bk‖)+τ22αℓfChγ‖ζk‖ \|a_k\|+τ (α\|h_k \|+\|b_k\| )+ τ^22α _fC_hγ\| _k\| +τ22αβλN(1+ℓf)dA. + τ^22αβ _N(1+ _f)\,d\,A. By hypothesis τ22αβλN(1+ℓf)d≤12 τ^22αβ _N(1+ _f)d≤ 12, so A≤2[‖ak‖+τα‖hk∥‖+τ‖bk‖+τ22αℓfChγ‖ζk‖].A≤ 2 [\|a_k\|+τα\|h_k \|+τ\|b_k\|+ τ^22α _fC_hγ\| _k\| ]. (A.10) Step 3: expectations. Write k=[⋅∣ℱk]E_k=E[\,· _k]. The quantities ak,bk,hk∥a_k,b_k,h_k are projections of the ℱkF_k-measurable vectors z2,k,w2,k,h2,kz_2,k,w_2,k,h_2,k onto the fresh direction, so by (19) and ‖h2,k‖≤ℓf‖zk‖\|h_2,k\|≤ _f\|z_k\|, k‖ak‖2=‖z2,k‖2d,k‖bk‖2=‖w2,k‖2d, _k\|a_k\|^2= \|z_2,k\|^2d, _k\|b_k\|^2= \|w_2,k\|^2d, k‖hk∥‖2≤ℓf2‖zk‖2d. _k\|h_k \|^2≤ _f^2\|z_k\|^2d. Squaring (A.10) with (∑i=14yi)2≤4∑iyi2( _i=1^4y_i)^2≤ 4 _iy_i^2 and taking kE_k, kA2≤16d[ _kA^2≤ 16d [ ‖z2,k‖2+τ2α2ℓf2‖zk‖2+τ2‖w2,k‖2 \|z_2,k\|^2+τ^2α^2 _f^2\|z_k\|^2+τ^2\|w_2,k\|^2 +dτ44α2ℓf2Ch2γ2∥ζk∥2]. + dτ^44α^2 _f^2C_h^2γ^2\| _k\|^2 ]. Using dτ4≤τ2dτ^4≤τ^2 (from dτ2≤1dτ^2≤ 1) and ‖z2,k‖,‖zk‖,‖w2,k‖≤‖ζk‖\|z_2,k\|,\|z_k\|,\|w_2,k\|≤\| _k\|, kA2≤16d[1+τ2(1+α2ℓf2+α2ℓf2Ch2γ24)]‖ζk‖2=κad‖ζk‖2,E_kA^2≤ 16d [1+τ^2 (1+α^2 _f^2+ α^2 _f^2C_h^2γ^24 ) ]\| _k\|^2= _ad\| _k\|^2, which is (A.3) for y=ay=a. For y=by=b, square (A.8) with s≤τs≤τ using (y1+y2)2≤2y12+2y22(y_1+y_2)^2≤ 2y_1^2+2y_2^2: ksup‖b‖2 _k \|b\|^2 ≤2‖w2,k‖2d+2α2β2λN2d2τ2kA2 ≤ 2\|w_2,k\|^2d+2α^2β^2 _N^2d^2τ^2\,E_kA^2 ≤2(1+α2β2λN2ρ2κa)d‖ζk‖2=κbd‖ζk‖2. ≤ 2(1+α^2β^2 _N^2ρ^2 _a)d\| _k\|^2= _bd\| _k\|^2. For the state deviation, square (A.7): ksup‖z(s)−zk‖2 _k \|z(s)-z_k\|^2 ≤2τ2Ch2γ2‖ζk‖2+2β2λN2d2τ2kA2 ≤ 2τ^2C_h^2γ^2\| _k\|^2+2β^2 _N^2d^2τ^2\,E_kA^2 ≤κzd‖ζk‖2, ≤ _zd\| _k\|^2, where we wrote 2τ2Ch2γ2=2ρτCh2γ2/d2τ^2C_h^2γ^2=2ρτ C_h^2γ^2/d. For y=h∥y=h , square the first inequality in (A.9): ksup‖h∥‖2 _k \|h \|^2 ≤2ℓf2‖zk‖2d+2ℓf2ksup‖z(s)−zk‖2 ≤ 2 _f^2\|z_k\|^2d+2 _f^2\,E_k \|z(s)-z_k\|^2 ≤2ℓf2(1+κz)d‖ζk‖2=κhd‖ζk‖2. ≤ 2 _f^2(1+ _z)d\| _k\|^2= _hd\| _k\|^2. Finally, ‖ζ(s)−ζk‖2=‖z(s)−zk‖2+‖w2(s)−w2,k‖2\|ζ(s)- _k\|^2=\|z(s)-z_k\|^2+\|w_2(s)-w_2,k\|^2 exactly, so by (A.6), ksup‖ζ(s)−ζk‖2 _k \|ζ(s)- _k\|^2 ≤κzd‖ζk‖2+α2β2λN2d2τ2kA2 ≤ _zd\| _k\|^2+α^2β^2 _N^2d^2τ^2\,E_kA^2 ≤κz+α2β2λN2ρ2κad‖ζk‖2, ≤ _z+α^2β^2 _N^2ρ^2 _ad\| _k\|^2, which is (A.4) with κδ _δ as in (A.5). ∎