CS Paper Radar

Distributed Stochastic Approximation Algorithms and Heavy-Tailed Age of Information

Adrian Redder, Arunselvan Ramaswamy, Holger Karl

cs.DC math.OCcs.MAcs.NImath.PR ·submitted 2026-09-23 08:01 UTC · v1

Abstract

Algorithms in multi-agent systems such as federated learning, mobile robotic swarming, and consensus control can be designed and analyzed as distributed stochastic approximation algorithms. Such algorithms involve information exchanges between agents for various computations. The freshness of the information can be quantified using the Age of Information (AoI) metric. Consider robotic teams operating in highly obstructed geographical settings, such as subterranean or dense urban environments. Because of spatial disconnections, AoI has empirically been observed to be heavy-tailed with unbounded moments. However, most analyses assume AoI with bounded moments, creating a gap between theory and practice. To the best of our knowledge, ours is the first analysis under general heavy-tailed AoI with potentially infinite mean. We study the stability (almost sure boundedness of the distributed iterates) and convergence of multi-agent systems that are strictly dissipative in the scaling limit (system at ``infinity''). Examples include most gradient-based and consensus algorithms under the Robbins-Monro step-size regime.

Closest papers

Nearest neighbours by meaning across the whole index.

Exact Average Consensus under Noisy Communication Links: A Decentralized Gradient Perspective

eess.SY cs.ITmath.OC ·2026-09-23 ·Yuhang Deng, Zheng Chen, Erik G. Larsson
publishedtheory similarity 0.64
Abstract · 8 pages, 2 figures. Accepted to the 2026 IEEE 65th Conference on Decision and Control (CDC 2026)

We study the distributed average consensus problem under persistent link-level disturbances modeled as a martingale difference sequence with uniformly bounded conditional second moments. Under such disturbances, the standard stochastic-approximation-based linear iteration with diminishing stepsizes drives the network to consensus on an unbiased random variable with non-vanishing variance instead of the exact initial average. To understand and resolve this limitation, we develop an anchoring-based mechanism derived from a decentralized gradient descent formulation and study the effect of incorporating a decaying anchoring term that continuously pulls each agent state toward its initial value. This perspective provides an intuitive interpretation of how state anchoring counteracts disturbance accumulation. Under standard summability conditions, we prove that the resulting algorithm achieves exact average consensus almost surely. Furthermore, this decentralized gradient perspective offers a unifying framework for several related methods and an interpretable design principle for exact average consensus under persistent disturbances.

0.53

Optimistic Distributed Submodular Coordination with Applications to Multi-Target Tracking with Multiple Robots

eess.SY ·2026-10-14 ·Pranjal Sharma, Atharva Navsalkar, Zirui Xu, Vasileios Tzoumas
hot direction similarity 0.63
Abstract · 8 pages, 1 figure, under review for the American Control Conference (ACC 2027)

We provide a distributed online algorithm for multi-agent submodular coordination in bandit environments, i.e., environments whose evolution is unknown a priori and may even adapt to the agents' actions. We are motivated by multi-robot tasks such as target tracking, where the optimal actions change over time and the agents must track them rather than a single fixed optimum. To address such problems, we provide the Optimistic Distributed Online Greedy (O-DOG) algorithm, that leverages predictions about the environment's behavior and improves regret guarantees. The agents select actions simultaneously over arbitrary, possibly time-varying, network topologies, and each agent acts optimistically, i.e., leveraging predictions of its upcoming rewards, e.g., from forecasts of the targets' motion and of its neighbors' actions. We bound O-DOG's tracking regret in terms of the agents' prediction error and the bound never exceeds its prediction-free counterpart. Particularly, it is sublinear even when the optimal action changes at every time step, provided the predictions are accurate enough. We further quantify the suboptimality due to decentralization as a function of the network structure, and show that accurate predictions accelerate convergence. We validate O-DOG in simulated multi-robot target tracking.

0.31

Toward a decentralized design framework for discrete-time distributed algorithms via their emergent dynamics

eess.SY ·2026-10-21 ·Jinwook Heo, Hyungbo Shim, Jin Gyu Lee
similarity 0.63
Abstract

This paper develops a procedure for designing discrete-time distributed algorithms to achieve a desired collective behavior. Each agent combines its node and coupling updates at every iteration, in either explicit or implicit form. For this structure, we derive necessary and sufficient conditions on the local parameters for realizing a desired continuous-time blended dynamics. These conditions yield a decentralized procedure for computing the parameters. A Tikhonov-type approximation result relates the resulting agent trajectories to the blended dynamics on a rescaled time axis. Under a stability condition imposed only on the blended dynamics, we further establish uniform-in-time approximation bounds. We also characterize the trade-off between approximation accuracy and the iteration count guaranteed by these bounds. The framework is illustrated through four applications in distributed computation and estimation.

0.20

AC-DC: Adaptive Communication for Scalable Dynamic Average Consensus in Multi-Robot Ergodic Search

cs.RO ·2026-09-21 ·Robin Inho Kee, Begum Cannataro, Vasileios Tzoumas
similarity 0.62
Abstract · 9 pages, 3 figures

We study scalable peer-to-peer dynamic average consensus (DC) for multi-robot systems under finite-range, finite-rate, and interference-constrained communication. We introduce Adaptive Communication for Dynamic Average Consensus (AC-DC), which jointly adapts Who communicates with whom, When, and over What parts of the consensus state, using local inputs and successfully received neighbor information. Each robot's consensus state estimates the current average of the robots' local inputs. AC-DC updates these estimates as local inputs change and averages the values exchanged between robot pairs. In AC-DC, robot pairs update without waiting for every robot to complete a communication round, and the selected-state messages carry consensus state coordinates independent of team size for a fixed state representation. We apply AC-DC to dynamic-priority multi-robot ergodic search: one consensus stream estimates team visitation for motion coordination, while the other fuses regional measurement information to update uncertainty maps and search targets. Across twelve settings with up to 80 robots and 20 paired trials per setting, AC-DC has the lowest mean (i) normalized covariance-trace area under the curve (AUC) and (ii) attempted modeled communication payload among the compared decentralized methods. Averaged across settings, AC-DC achieves paired AUC reductions of 27.5% relative to state-of-the-art baselines, with 8.7x less communication traffic. As the number of robots increases, we observe that AC-DC's communication payload approaches that of the ideal centralized baseline (one ground compute-station communicating directly with all robots): with 120 robots in a fixed 600 x 600 m scaling test, AC-DC uses 19.3 MB versus 19.2 MB for the ideal centralized baseline, while remaining peer-to-peer.

0.24

Cooperative Learning of Shared Latent Dynamics for Distributed Online Optimization

eess.SY ·2026-11-11 ·Shivanshu Tripathi, Maziar Raissi
similarity 0.61
Abstract

We study networked agents that must agree on a decision minimizing the sum of their local costs, where each cost contains unmeasurable stochastic parameters that evolve with linear but unknown dynamics shared by all agents. Each agent receives only finitely many noisy gradient measurements and must then keep tracking the moving minimizer. Our scheme reconstructs the parameters from windows of gradients, learns the shared dynamics cooperatively by averaging instrumental-variable moment matrices over the network, and tracks the minimizer by gradient tracking on forecast gradients. We bound the error of every agent in learning the dynamics and in tracking the minimizer, and show that the learning error, and through it the tracking error, decreases with the number of agents. We demonstrate the approach on two case studies.

0.14

Stochastic Gradient Tracking over Time-Varying Networks: One-Step Lyapunov Analysis

cs.DC math.OCeess.SY ·2026-08-17 ·Sulaiman A. Alghunaim
similarity 0.61
Abstract

We study decentralized stochastic gradient tracking over a time-varying network of $N$ agents under a uniform window-mixing condition. Products of $τ$ consecutive doubly stochastic mixing matrices contract disagreement by a factor $λ<1$, although individual matrices need not contract disagreement strictly and individual communication graphs may be disconnected. We construct a time-varying quadratic norm that turns this window contraction into an exact one-step Lyapunov identity. This leads to coupled one-step recursions for the centroid and disagreement errors, without unrolling the dynamics over communication windows. For smooth strongly convex objectives, the leading stochastic term is $\widetilde{\mathcal O}(1/(NK))$; for smooth convex objectives, it is $\mathcal O(1/\sqrt{NK})$. Both match their centralized mini-batch counterparts and yield linear speedup after a network-dependent transient.

0.39

DGF-Asym: Adaptive Peer Weighting for Collective Estimation under Noisy and Faulty Sensing

cs.RO cs.AI ·2026-11-17 ·Mohammad Nomaan Husain, Tanja Katharina Kaiser
similarity 0.60
Abstract

Collective estimation under unreliable sensing requires robots to adaptively balance personal observations and social information from peers. We propose DGF-Asym, a decentralized collective estimation method extending the DeGroot-Friedkin model with asymmetric peer weighting based on retrospective predictive performance. The method supports consensus formation without prior sensor-noise statistics or explicit fault models while keeping inter-robot communication asynchronous. We evaluate DGF-Asym in simulated collective navigation under noisy observations and time-varying sensor faults. Compared with three baselines, it produces more stable estimates and more reliably sustains the decision criterion, at the cost of longer decision times. However, overall performance depends on fault ratio, group size, and influence-threshold selection. Our results demonstrate the potential of adaptive peer weighting for stable model-free collective estimation under unreliable sensing.

0.25

Distributed Consensus, Optimization, and Learning under Communication Constraints

cs.IT cs.DCeess.SP ·2026-11-04 ·Zheng Chen, Nicolò Michelusi, Themistoklis Charalambous, Kaibin Huang
published similarity 0.60
Abstract · 20 pages, 3 figures, to appear in IEEE JSAC

Many modern engineering applications require distributed problem-solving in which multiple nodes in a network cooperate to achieve a common optimization objective. Numerous distributed optimization and learning algorithms rely on consensus-based distributed coordination to ensure network-wide agreement via iterative local interactions. In these algorithms, the accuracy, frequency, and reliability of information exchange among network nodes directly influence system performance, including convergence behavior, training delay, and model accuracy. This tutorial article adopts a bottom-up approach to present the fundamentals of consensus averaging and distributed optimization methods, and highlights the impact of network connectivity, information flow, and communication uncertainty on network cooperation and optimization performance. Building on these theoretical insights, we discuss key design principles for communication-constrained distributed learning across diverse network topologies and review common approaches to communication-efficient learning, particularly in wireless networks. Despite substantial progress, further efforts are needed to bridge the gap between theory and practice and fully realize the potential of cooperative and networked intelligence.

0.32