📊 statistics

DIGing--SGLD: Decentralized and Scalable Langevin Sampling over Time--Varying Networks

This paper introduces DIGing-SGLD, a decentralized sampling algorithm that integrates gradient tracking with Stochastic Gradient Langevin Dynamics to achieve bias-free, geometric convergence over time-varying networks, providing the first finite-time non-asymptotic convergence guarantees for such settings.

Original authors: Waheed U. Bajwa, Mert Gurbuzbalaban, Mustafa Ali Kutbay, Lingjiong Zhu, Muhammad Zulqarnain

Published 2026-08-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Waheed U. Bajwa, Mert Gurbuzbalaban, Mustafa Ali Kutbay, Lingjiong Zhu, Muhammad Zulqarnain

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.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

In the world of modern artificial intelligence, machines often learn by looking at vast amounts of data to find patterns and make predictions. A powerful way to do this is through a method called Bayesian learning, which allows a computer to not only make a guess but also to understand how uncertain that guess might be. Imagine trying to find the most likely location of a hidden object; instead of settling on a single spot, this approach keeps a mental map of all the possible places the object could be, weighted by how likely each spot is. To build this map, computers need to generate thousands of random samples from a complex mathematical landscape. For decades, researchers have used a tool called Stochastic Gradient Langevin Dynamics to do this, a technique that is like a hiker wandering through a foggy valley, taking small, random steps guided by the slope of the ground to eventually explore the entire terrain.

However, a major challenge arises when the data needed to build this map is not stored in one central place but is scattered across many different devices, such as sensors on a fleet of drones or computers in a network of hospitals. In these situations, the devices cannot simply send all their raw data to a central server to be processed, often because of privacy rules or limited bandwidth. Instead, they must talk to each other, sharing only small pieces of information with their immediate neighbors. The problem is that the networks these devices use to talk are rarely static; connections can drop, devices can move, and the web of communication changes constantly. Existing methods for sampling in these distributed settings were designed for fixed, unchanging networks and often fail or produce inaccurate results when the connections shift, leaving the devices with a distorted view of the true answer.

To solve this, researchers Waheed U. Bajwa, Mert Gürbüzbalaban, Mustafa Ali Kutbay, Lingjiong Zhu, and Muhammad Zulqarnain have developed a new algorithm called DIGing-SGLD. This method is designed specifically for networks that change over time, allowing a group of agents to collaboratively sample from a target distribution without ever needing a central leader to coordinate them. The core innovation lies in how the algorithm handles the flow of information. While older methods simply averaged the data from neighbors, which can lead to errors when the network topology shifts, this new approach uses a mechanism called gradient tracking. This allows each device to keep a running estimate of the average gradient across the entire network, effectively correcting for the discrepancies caused by moving connections and noisy data. By combining this tracking ability with the random-walk sampling technique, the algorithm ensures that even as the network reconfigures itself, the devices stay aligned and converge toward the correct statistical picture.

The researchers proved mathematically that this new method works reliably under strict conditions, showing that the error between the devices' samples and the true target distribution shrinks at a predictable rate. They demonstrated that the algorithm reaches a state of high accuracy in a number of steps that is comparable to the best methods used in centralized settings, despite the added complexity of a changing network. Crucially, they showed that the devices do not need to slow down their learning or use diminishing step sizes to compensate for the network changes; they can maintain a steady pace while the algorithm automatically corrects for the instability of the connections. This theoretical guarantee is significant because previous approaches for time-varying networks often resulted in slow convergence or required assumptions that did not hold in real-world scenarios.

To verify these mathematical claims, the team tested the algorithm on two common types of problems: predicting continuous values, such as in linear regression, and classifying categories, such as in logistic regression. They simulated these tasks using both synthetic data and a real-world medical dataset involving breast cancer diagnosis. In these experiments, the network topology was made to change dynamically, mimicking the unpredictable nature of wireless communication. The results showed that the new algorithm consistently outperformed the standard decentralized methods. In the classification tasks, the new method achieved higher accuracy and maintained stable performance, whereas the older methods struggled with the shifting connections, leading to slower convergence and less reliable results. The experiments confirmed that the gradient-tracking mechanism successfully neutralized the drift caused by the changing network, allowing the agents to agree on a high-quality approximation of the target distribution.

The work establishes a new standard for decentralized learning in dynamic environments, proving that it is possible to perform complex statistical sampling without a central coordinator, even when the communication links between devices are constantly breaking and reforming. By providing explicit mathematical bounds on the error and demonstrating robust performance in simulations, the researchers have shown that their approach is not just a theoretical possibility but a practical solution for the next generation of distributed artificial intelligence systems. This advancement opens the door for more resilient and privacy-preserving machine learning applications, where networks of devices can learn together effectively despite the inherent instability of their connections.

Problem Statement
The paper addresses the challenge of decentralized Bayesian learning in multi-agent systems where data is distributed across a network of agents, and the communication topology is time-varying. The goal is to sample from a target posterior distribution $\pi(x) \propto e^{-f(x)}$ , where the global objective function $f(x)$ is a sum of local functions $f_i(x)$ held by individual agents. While Stochastic Gradient Langevin Dynamics (SGLD) is a standard tool for scalable posterior sampling in centralized settings, existing decentralized variants (DE-SGLD) are typically restricted to static network topologies. Furthermore, many existing decentralized methods suffer from steady-state sampling bias caused by network-induced discrepancies among agents' local gradients, even when full batches are used. The specific gap this work targets is the lack of decentralized sampling algorithms that can operate reliably over time-varying networks while providing rigorous finite-time convergence guarantees with constant step sizes.

Methodology
The authors propose DIGing-SGLD (Decentralized Inexact Gradient-tracking Stochastic Gradient Langevin Dynamics). This algorithm integrates two core components:

Stochastic Gradient Langevin Dynamics (SGLD): To handle large datasets via mini-batch stochastic gradients and to perform sampling via the addition of Gaussian noise.
DIGing (Distributed Inexact Gradient-tracking): A mechanism originally developed for decentralized optimization over time-varying graphs.

In DIGing-SGLD, each agent $i$ maintains a local iterate $x_i^{(k)}$ and an auxiliary variable $y_i^{(k)}$ . The auxiliary variable tracks the evolving network-wide average of the local stochastic gradients. The update rules are:

Primal Update: $x_i^{(k+1)} = \sum_{j \in \Omega_i(k)} W_{ij}^{(k)} x_j^{(k)} - \eta y_i^{(k)} + \sqrt{2\eta} w_i^{(k+1)}$
Gradient Tracking Update: $y_i^{(k+1)} = \sum_{j \in \Omega_i(k)} W_{ij}^{(k)} y_j^{(k)} + g_i^{(k+1)} - g_i^{(k)}$

Here, $g_i^{(k)}$ represents the stochastic gradient estimate at agent $i$ , $W^{(k)}$ is a doubly stochastic mixing matrix reflecting the time-varying connectivity, and $w_i^{(k)}$ is Gaussian noise. The gradient tracking mechanism allows agents to collaboratively approximate the global gradient without a central coordinator, thereby correcting the bias introduced by time-varying network mixing and stochastic gradient noise.

Key Contributions

Algorithmic Development: The introduction of DIGing-SGLD, the first decentralized SGLD algorithm designed specifically for undirected time-varying networks that relies solely on local stochastic gradients and neighbor-to-neighbor communication.
Theoretical Guarantees: The paper provides the first finite-time, non-asymptotic Wasserstein convergence guarantees with explicit constants for decentralized SGLD with a constant stepsize over time-varying networks.
- Under standard assumptions (local functions are $\mu$ -strongly convex and $L$ -smooth; mixing matrices satisfy a joint spectral condition), the authors prove that the marginal distribution of each agent's iterate converges geometrically in the 2-Wasserstein distance to an $O(\sqrt{\eta})$ neighborhood of the target distribution.
- The analysis explicitly bounds the dependence on stepsize $\eta$ , network connectivity (via spectral gap parameters), gradient noise variance, problem dimension, and the number of agents.
Iteration Complexity: The authors establish that to achieve a target accuracy $\epsilon$ in the 2-Wasserstein distance, the algorithm requires $K = O\left(\frac{\log(1/\epsilon)}{\epsilon^2}\right)$ iterations. This rate matches the best-known results for centralized and static-network SGLD algorithms with constant stepsize, despite the added complexity of dynamic topologies.
Uniform Bounds: The results include a uniform bound over the agents' marginal distributions, ensuring that every agent's distribution is close to the target, not just the network average.

Results

Theoretical: The convergence bounds decompose the error into three components: the error of a centralized Unadjusted Langevin Algorithm (ULA), the error induced by stochastic gradients and decentralized averaging, and the consensus error among agents. The analysis shows that the consensus error decays geometrically, and the residual error scales with $\sqrt{\eta}$ .
Empirical: Numerical experiments were conducted on Bayesian linear and logistic regression using both synthetic and real-world datasets (UCI Breast Cancer dataset).
- Linear Regression: Measured via the 2-Wasserstein distance between the empirical posterior and the true Gaussian posterior.
- Logistic Regression: Measured via classification accuracy on a held-out test set.
- Findings: In time-varying barbell and lollipop network topologies, DIGing-SGLD consistently outperformed DE-SGLD. Specifically, DE-SGLD exhibited larger variability and reduced accuracy, while DIGing-SGLD maintained stable performance and converged to higher accuracy. The performance gap was more pronounced in topologies with smaller spectral gaps (e.g., barbell graphs), highlighting the effectiveness of the gradient-tracking mechanism in mitigating network-induced drift.

Significance
The paper claims that DIGing-SGLD addresses a critical theoretical gap in scalable decentralized Bayesian inference. By enabling efficient sampling without a central coordinator over dynamically changing networks, the method extends the applicability of Bayesian learning to realistic multi-agent systems (such as IoT platforms and autonomous fleets) where network connectivity is inherently time-varying due to mobility, interference, or reconfiguration. The work demonstrates that it is possible to achieve convergence rates comparable to static and centralized settings even under dynamic conditions, provided that gradient tracking is utilized to control network-induced disagreement. The authors note that while their current analysis assumes strong convexity and smoothness, the framework unifies decentralized stochastic sampling with gradient-tracking-based optimization, paving the way for future extensions to non-convex objectives or directed network settings.

More like this