⚡ electrical engineering

Convergence Analysis of Continuous-Time Distributed Stochastic Gradient Algorithms

This paper proposes a continuous-time distributed stochastic gradient algorithm for multi-agent systems to cooperatively minimize the sum of convex functions using local stochastic gradients and time-varying directed communication, proving through Lyapunov theory and Ito calculus that agents asymptotically reach a common minimizer in expectation.

Original authors: Jianhua Sun, Kaihong Lu, Xin Yu

Published 2026-02-10

📖 3 min read☕ Coffee break read

CC0 1.0

Original authors: Jianhua Sun, Kaihong Lu, Xin Yu

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are part of a massive, global scavenger hunt. There is one single "Grand Prize" hidden somewhere in a vast field, but there’s a catch: no one knows where it is, and no one can see the whole field.

Instead, the field is divided into small patches. You are standing in one patch, and your friends are standing in others. Each person can only see the ground right beneath their feet. To find the Grand Prize, everyone has to work together, sharing what they know with their immediate neighbors to eventually converge on the exact center of the field.

This paper describes a mathematical way to make this "scavenger hunt" work even when things get messy. Here is the breakdown:

1. The Problem: The "Foggy" Scavenger Hunt

In a perfect world, you would look at your patch of ground, see exactly which way the prize is, and walk toward it. This is called "Gradient Descent."

But in the real world (and in this paper), two things go wrong:

The "Bad Eyesight" Problem (Stochastic Gradients): When you look at your patch, you don't see the true slope of the ground. Instead, you see a blurry, shaky version of it. It’s like trying to walk downhill while wearing thick, vibrating glasses.
The "Moving Map" Problem (Time-Varying Graphs): You can’t always talk to all your friends. Sometimes the person to your left is busy, or the radio signal drops. You can only exchange information with whoever is currently "in range."

2. The Solution: The "Continuous Flow" Strategy

Most math models treat time like a series of snapshots (Step 1, Step 2, Step 3). This paper does something different: it treats time like a smooth, flowing river (Continuous-Time).

The researchers proposed a specific "recipe" (an algorithm) for the agents:

Listen to your neighbors: Constantly adjust your position based on where your neighbors are moving (this is called Consensus).
Follow the blurry slope: Move in the direction your "shaky glasses" tell you is downhill (this is the Stochastic Gradient).
Slow down as you get closer: As time goes on, you don't make huge leaps; you take smaller and smaller steps to avoid overshooting the prize because of the "shaky glasses."

3. The Math Magic: The "Itô" Tool

Because the "shaky glasses" (the noise) are modeled using something called Brownian Motion—which is essentially mathematical "jitter"—the path isn't a smooth line; it's a jagged, vibrating scribble.

Standard calculus breaks when things are that jagged. To fix this, the authors used a specialized tool called the Itô Formula. Think of this as a "super-powered calculator" designed specifically to handle math that is constantly vibrating and jumping.

4. The Result: Finding the Prize

The authors proved mathematically that even with the blurry vision and the changing communication links, the group will eventually find the prize.

They even calculated exactly how fast they would get there. They found that if you tune your "step size" (how much you move each second) just right, you can reach the goal with a specific level of efficiency. They proved this with equations and then showed it works in a computer simulation where six "agents" successfully found the center of a mathematical valley despite constant noise.

Summary in a Nutshell

The Paper's Goal: How can a group of robots find the bottom of a valley if they have bad sensors, shaky movements, and unreliable radios?
The Answer: By using a continuous-flow mathematical model and a special "vibration-proof" calculus, we can guarantee they will all eventually meet at the exact same bottom point.

Technical Summary: Convergence Analysis of Continuous-Time Distributed Stochastic Gradient Algorithms

This paper presents a pioneering study on continuous-time distributed stochastic optimization within multi-agent systems. While existing literature extensively covers discrete-time stochastic gradient descent (SGD) and deterministic continuous-time distributed optimization, this work bridges the gap by addressing the complexities introduced by continuous-time dynamics coupled with stochasticity modeled via Brownian motion.

1. Problem Formulation

The authors consider a multi-agent system (MAS) where $n$ agents aim to cooperatively minimize a global objective function $f(x)$ , defined as the sum of local convex functions:
$\min_{x \in \mathbb{R}^m} f(x) = \sum_{i=1}^{n} f_i(x)$
The problem is characterized by several realistic constraints:

Stochasticity: Agents do not have access to the true gradient $\nabla f_i(x_i)$ ; instead, they observe a noisy version $\tilde{\nabla} f_i(x_i)$ modeled by an Itô process involving Brownian motion.
Communication: Agents can only exchange local state information with immediate neighbors through a time-varying directed graph $G(t)$ .
Dynamics: The system operates in continuous time, making the stochastic gradients non-differentiable and requiring advanced stochastic calculus for analysis.

2. Methodology

The authors propose a new continuous-time distributed stochastic gradient algorithm based on the integration of consensus algorithms and gradient descent strategies. The dynamics of agent $i$ are governed by the following Stochastic Differential Equation (SDE):
$dx_i(t) = \sum_{j=1}^{n} a_{ij}(t)(x_j(t) - x_i(t))dt - \eta_t \left( \nabla f_i(x_i(t))dt + g_i(t)dB_i(t) \right)$
Where:

$a_{ij}(t)$ are adjacency weights from the time-varying graph.
$\eta_t$ is a non-increasing step size.
$g_i(t)$ is the noise intensity.
$B_i(t)$ is a standard Brownian motion.

Analytical Framework:
To handle the non-differentiability caused by Brownian motion, the authors employ:

Itô’s Formula: To derive the differential of the Lyapunov function.
Lyapunov Stability Theory: Using a composite Lyapunov function $V(\bar{x}(t), t)$ that accounts for both the optimality gap of the average state and the distance of individual states from the average.
Convex Analysis and Graph Theory: To bound the consensus error and the gradient deviations under the assumption of a $(\delta, T_c)$ -strongly connected and balanced digraph.

3. Key Contributions

First-of-its-kind Framework: It is the first work to study distributed stochastic optimization in continuous time where stochasticity is captured by Brownian motion rather than discrete Gaussian noise.
Rigorous Convergence Proofs: The paper provides a complete theoretical derivation of the convergence of agent states to a common minimizer in expectation.
Convergence Rate Characterization: The study explicitly links the decay rate of the objective function to the choice of the step-size exponent $a$ in $\eta_t = \frac{\beta}{(t+1)^a}$ .

4. Main Results

The primary theoretical result (Theorem 1) establishes that the agents' states asymptotically reach a common minimizer in expectation. The convergence rate is highly dependent on the step-size parameter $a$ :

If $\frac{1}{2} < a < \frac{3}{4}$ , the rate is $O(t^{-(a-1/2)})$ .
Optimal Rate: The fastest polynomial convergence rate is achieved when $a = 3/4$ , yielding $O\left(\frac{\sqrt{\ln t}}{t^{1/4}}\right)$ .
If $\frac{3}{4} < a < 1$ , the rate is $O(t^{-(1-a)})$ .
If $a = 1$ , the rate is $O((\ln t)^{-1})$ .

5. Significance

This research is significant for engineering applications where systems are inherently continuous-time and subject to environmental uncertainties, such as:

Unmanned Ground Vehicles (UGVs): Cooperative delivery and path planning where dynamics are continuous and sensor noise is stochastic.
Sensor Networks: Distributed tracking where measurements are continuously updated and influenced by Brownian-like noise.
Control Theory: It provides a mathematical foundation for applying stochastic optimization to multi-agent control systems, moving beyond the limitations of discrete-time approximations.