Scalar Communication via Random Direction Refreshing for Distributed Optimization

Mohammadreza Rostami; Solmaz S. Kia

cs.MAOct 5, 2026

Scalar Communication via Random Direction Refreshing for Distributed Optimization

Authors: Mohammadreza Rostami, Solmaz S. Kia

Organizations: Department of Mechanical and Aerospace Engineering, University of California Irvine, Irvine, CA 92697

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.

Figures & tables

Fig. 1: Relative RMS error at

d\tau=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.

Fig. 2: Effect of refreshing in the concentrated case: (a) error versus time; (b) RMS error at

t=40

versus

d\tau

. Error bars show pointwise 95% bootstrap confidence intervals.

Explore similar work

Sep 16, 2026cs.LG

Revisiting Distributed Sign-Based Variance Reduction

Sign-based methods reduce communication costs in distributed environments, but aggregating local signs can introduce bias when data are heterogeneous. As a result, existing sign-based variance reduction methods fail to obtain the optimal convergence rates. In this paper, we solve this problem and obtain optimal rates for both nonconvex stochastic and finite-sum optimization. We first give a counterexample showing that majority voting can fail to approach stationary points even with exact local gradients. Motivated by this limitation, we propose tracking the global gradient at the server through unbiased compression of recursive gradient increments. As a result, we can obtain the convergence rates of

O(\sqrt{d/K}+\sqrt d (a/(nK))^{1/3})

for the

\ell_1

-norm and

O(\sqrt{a/K}+\sqrt a/(nK)^{1/3})

for the

\ell_2

-norm. Here,

K

is the iteration number,

n

is the number of workers,

d

is the dimension, and

a=1+ω

, with

ω

denoting the compressor's relative variance. For finite-sum problems with

M

components, we combine periodic exact gradient refreshes with compressed component-gradient differences. The resulting total sample complexities are

O(M+d\sqrt{aM}ε^{-2})

and

O(M+a\sqrt M\ epsilon^{-2})

for

\ell_1

and

\ell_2

gradient norms at most

ε

, matching the corresponding bounds in centralized settings.

Wei Jiang, Zechao Li, Lijun Zhang

School of Computer Science and Engineering, Nanjing University of Science and Technology, China · National Key Laboratory for Novel Software Technology,Nanjing University, China · School of Artificial Intelligence, Nanjing University, China

Sign-Based Optimization Communication-Efficient Distributed Training Distributed Optimization Nonconvex Stochastic Optimization Variance Reduction

Ask PDF

Jun 5, 2026cs.LG

Accelerated Decentralized Stochastic Gradient Descent for Strongly Convex Optimization

Decentralized stochastic optimization is a fundamental paradigm for large-scale learning over networks, where agents communicate only with their neighbors and no central coordinator is required. For strongly convex problems, communication efficiency is mainly determined by the condition number

κ=L/μ

and the network spectral gap

1-β

. Although deterministic decentralized methods can simultaneously achieve accelerated

\sqrtκ

and

1/\sqrt{1-β}

dependences, no existing stochastic method attains both improvements at once. In this paper, we propose \emph{Multi-Gossip Accelerated DSGD} (MG-ADSGD), a decentralized stochastic algorithm that combines Nesterov-type primal--dual extrapolation with multi-round fast gossip averaging. The key idea is to couple the gossip depth with the mini-batch size so that additional communication rounds simultaneously improve consensus accuracy and reduce gradient variance. We show that MG-ADSGD achieves the communication complexity

\widetilde{\mathcal O}\!\left( \frac{σ^2}{μnε}\log\frac{1}ε + \sqrt{\fracκ{1-β}}\log\frac{1}ε \right),

where

ε

denotes the target accuracy,

n

is the number of nodes, and

σ^2

is the gradient variance. To the best of our knowledge, this bound yields the best currently available communication complexity for decentralized stochastic strongly convex optimization, up to logarithmic factors that are independent of

ε

Ming Sun, Kun Yuan

Center for Machine Learning Research Peking University

Gradient Descent Accelerated Gradient Methods Decentralized Optimization Stochastic Gradient Descent

Ask PDF

Jul 2, 2026cs.LG

Revisiting Decentralized Online Convex Optimization with Compressed Communication

Decentralized online convex optimization (D-OCO) is a popular framework for distributed applications with streaming data. To tackle the communication bottleneck, previous studies have investigated D-OCO with compressed communication and proposed several algorithms that are variants of online gradient descent (OGD). However, for D-OCO with exact communication, the best existing algorithms are variants of follow-the-regularized-leader (FTRL). In this paper, for the first time, we propose two FTRL-type algorithms for D-OCO with compressed communication. Compared with OGD-type algorithms, our algorithms are more elegant in both algorithmic design and theoretical analysis. The key insight is that the dual update mechanism of FTRL allows us to make a simple application of the technique for average consensus with communication compression. More specifically, our first algorithm considers the full-information setting, and can match the existing regret bounds. Our second algorithm is designed for the bandit setting, and can significantly improve both the regret bounds and communication costs of existing algorithms.

Hao Zhou, Xiaoyu Wang, Chang Yao +2

School of Software Technology, Zhejiang University, Ningbo, China · State Key Laboratory of Blockchain and Data Security, Zhejiang University, Hangzhou, China

Online Convex Optimization Follow-the-Regularized-Leader Decentralized Optimization

Ask PDF