Client-only Distributed Markov Chain Monte Carlo Sampling over a Network
Authors: Bo Yuan
Jiaojiao Fan
Jiaming Liang
Yongxin Chen
Venue: Accepted by TMLR ()

Abstract: We aim to sample from a target
$\exp\left(-\sum_{i=1}^n f_i(x|\mathcal{D}_i\right))$ where each client $f_i$ only has access to local data $\mathcal{D}_i$. We present a fully distributed Markov Chain Monte Carlo (MCMC) sampler that operates through client-to-client communication, eliminating the need for additional centralized servers. Unlike MCMC algorithms that rely on server-client structures, our proposed sampler is entirely distributed, enhancing security and robustness through decentralized communication. 
In contrast to limited decentralized algorithms arising from Langevin dynamics, our sampler utilizes blocked Gibbs sampling on an augmented distribution. Furthermore, we establish a non-asymptotic analysis of our sampler, employing innovative techniques. This study contributes to one of the initial analyses of the non-asymptotic behavior of a fully distributed sampler arising from Gibbs sampling.

Published in Transactions on Machine Learning Research (08/2025)
Client-only Distributed Markov Chain Monte Carlo Sampling over a Network
Bo Yuan
@yuan48@gatech. edu
School of Aerospace Engineering Georyia Institute of Technology
Jiaojiao Fan Neidia
jiaojia/Brvvidiaccmmm com
Jiaming Liang
Jiaming. Jiaming.Liong edu
Department of Computer Science University of Rochester
Yongxin Chen
yongchen Sagrechee@ggtchh..ce
School of Aerospace Engineering Georgia Institute of Technology
Reviewed OpenReview: https: https:///penreeveeu openreview. net/ forum? id= f222rL
Abstract
We aim to sample from a target i fi(x(D:)) where each client fi only has access to local data D,. We present a fully distributed Markov Chain Monte Carlo (MCMC) sampler that operates through client-to-client communication, eliminating the need for additional centralized servers. Unlike MCMC algorithms that rely on server-client structures, our proposed sampler is entirely distributed, enhancing securily and robustness through decentralized communication. In contrast to limited decentralized algorithms arising from Langevin dynamics, our sampler utilizes blocked Gibbs sampling on an augmented distribution. Furthermore, we establish a non-asymplotic analysis of our sampler, employing innovative techniques. This study contributes to one of the initial analyses of the non-asymptotic behavior of a fully distributed sampler arising from Gibbs sampling.
1 Introduction
recent years, inspired by the rapid development in optimization, a lot of sampling algorithms have been proposed and then analyzed to obtain their non-asymptotic behaviors (Dalalyan) [017b] Dalalyan &
Riou-Durand] 2020 Zhang al.) 2023 Fan et al. 2023: Altschuler Chewi 2023). In this work, we
interested in sampling from target distribution of R2 defined as
(xx) exp
Σ M(TD))
in distributed manner. With this formulation, implicitly have that each potential (negative log density) fa only possesses access to its local data D,. Fully distributed systems, c.g,, distributed sensor networks (Qi et al. 2001) and edge computation (Mach & Becvar, 2017), provide advantages over centralized ones by enabling computing agents to share limited information, reducing communication costs, and improving security and robustness. These factors make them potentially superior terms of computational performance and data protection. These raise the need to develop and analyze a distributed sampling algorithm without centralizod servers. Our target distribution is the straight.frward generalization of the objective function Ei= f((x(D,) in

---

Published in Transactions on Machine Learning Research (08/2025)
distributed optimization, and this problem naturally arises in various applications of distributed optimization, e-g.; power systems, sensor networks, and smart manufacturing (Yang et al. 2019).
In the machine learning community, our sampling problem is heavily related to Bayesian learning (Cao et al. 2023), an area carrying on Bayesian inference and uncertain quantification on learned models. Consider a learning setting where the goal to train models with minimizing Σi=1 (a))) As mentioned in Sun et al. (2022), one can view each fi as a loss function on data collection D.. Compared with only searching for the minimizer of > ft. Bayesian inference the distribution can give more detailed information on the loss landscape. Moreover, Bayesian inference is preferred when only limited data is available; applying prior distributions on model parameters can significantly enhance the performance of models trained on limited data (Sun et al. 2019 In what follows, we omit the dependency on D; for brevity.
Many existing distributed Markov Chain Monte Carlo (MCMC) algorithms are deployed with server-client architoctures: at each step, the server aggregates information from clients as shown in Figure [ Distributod sampling via moment-sharing proposed in Xu et al. (2014). More parallel MCMC algorithms are presented
in Wang & Dunson (2013); ; Neiswanger et al (2013) Wang et al. (2015); Chowdhury & Jermaine (2018)
De Souza et al. (2022). Recently, several distributed MCMC algorithms (Vono et al. 2022b Plassier et al.
2021 Kotelevski et al. 2022 are proposed to address practical issues like safety, communication cost, and heterogeneity. These parallel and distributed MCMC algorithms either rely on client-server architectures or lack non-asymptotic convergence rates. To the best of our knowledge, only a handful of sampling literature (Kungurtsev) 2020: Parayil et al. 2020: Gürbizbalaban et al., 2021 Kolesov Kungurtsev 2021
Kungurtsev et al., (2233) proposes fully distributed samplers and establishes the non-asymptotic results. These samplers arise from Langevin Monte Carlo Hamiltonian Monte Carlo, leveraging the concept of gradient tracking in distributed optimization (Pu & Nedić 2021). However, unsuitable hyperparameters of these methods may result in failure to sample from the target. As demonstrated in our experiments, samplers based on Langevin Monte Carlo diverge with unreasonably large step sizes, while our proposed sampler ensures convergence with the same stop sizes.
Another well-known sampler is the Gibbs sampler, commonly used in asynchronous settings where multiple nodes can update their samples without waiting for each other (Terenin et al. 2020). However, the exploration of the non-asymptotic behaviors of a fully distributed sampler based on Gibbs sampling remains uncharted territory. Even though the parallel Gibbs sampler was already proposed in the distributed setting in Gonzalez et al. (2011), we give non-asymptotic results for the first time, Given the intricate nature of Gibbs sampling, which differs from Langevin dynamics, our main challenge is to develop innovative proof ideas to analyze non-asymptotic behaviors.
Figure 1: Comparison of server-client architectures with centralized servers (Left) and Trees that enable distributed sampling (Right). In the server-client. structure, each client (small node) must communicate with a centralized server (big node).
We fill in the gap with a novel and fully distributed sampling framework. Our work represents one of the first endeavors to address the non-asymptotic convergence results of a fully distributed sampling algorithm on a Gibbs sampler. Our experiments further show that, compared with Langevin Monte Carlo baselines, our Gibbs sampler is noticeably more robust to the choice of step size. To utilize specific Gibbs sampler, we
2

---

Published in Transactions on Machine Learning Research (08/2025)
assume all the clients are distributed bipartite graph. Note that every connected graph has spanning tree. For a comparison of the server-client. structures and trees, see Figure 1
To sample from the target (x) & exp(->2. f(()) where I E Idd we instead consider sampling from an augmented distribution of { E Rnd #(21, F2,...,, In) x exp(-Ei== fi(x;) - E.EA EsEB /w//2n| - 2xll²) where A and B stand for two disjoint node groups of bipartite graph. Here, each I; E H stands for one node. We assume aab E (0, 1] if there is an edge between Za and Ib, otherwise, oab = O. Furthermore, Ea Jah S 1, E, aah S for any a, b. The nature of Gibbs sampling, iteratively sampling from conditional distributions, makes it candidate for distributed sampling. With the specific design of â, it can be observed that if v is small enough, the marginals of âे and the distribution of the averaged samples can be arbitrarily close to π.
A closely related line of research is data-augmennation methods (Vono et al. 2020 2022a Plassier et al. 2021
which proposes the joint density exp (-E-- 11-ii=((le (f((z;) + 1/2n ||a - =)(²) with a new auxiliary variable y, and sample from it with a Gibbs scheme. Note that in our augmented distribution, there are no additional nodes involved in the original network, while other data-augmentatton algorithms are inherently centralized. In contrast, our method is fully distributed, offering improved security and robustness compared to centralized samplers.
In terms of the theoretical contributions, Theorems 4.3 and 5.4 deliver new non-asymptotic bias bounds. Our analysis generalizes Corollary 3 in Vono et al. (2020): that corollary a special case of Theorem 4.3 by setting either f or 9 to a constant. We extend the result to the two-node setting (Theorem 4.3) and further to bipartite graphs (Theorem 5.40, with new proof ideas.
Our main theoretical contribution is the non-asymptotic bounds of the distance between the average of samples and the target in Theorem 5.4 Combining with improved convergence results of sampling from
# in Yuan et al. (202)), we eventually give the overall iteration complexity in Proposition 5.5 Yuan et al. (2023) only considers the convergence of the Gibbs sampler without quantifying the non-asymplolic error between the original distribution and the marginals. We emphasize that the target distribution in (Yuan ct al. 2023) not the composite target distribution considered in our work. Hence, the nonasympttoie guantee toward to Sep(-Ei-) fi(x;)) ((()))(()) does not exist without our contributions in Theorem 4.3 and 5.4 Moreover, we revise the proof of Theorem 10 in (Yuan et al. 2023) and improved the convergence rate detailed after Theorem 5.3 We also demonstrate our sampler's superior performance under various settings. Please refer to Appendix A.7 for more detailed discussion on our novelty compared to Yuan et al. 2023).
In summary, our contributions are listed below.
We propose a new distributed sampling algorithm (Algorithm 2 that does not require a server node and can be deployed on any bipartite graphs. Our sampler is applicable to any target distributions, provided that mild regularity conditions are met (Remark 5.6 Unlike previous works relying on Langevin Monte Carlo or Hamiltomian Monte Carlo, our sampler builds upon Gibbs sampling.
We analyze its non-asymptotic results (Proposition 5.5 with the bound improved from Yuan et al., 2023) and the non-trivial upper bound between marginals of ø and π (Theorem 5.4 established in this work with novel techniques.
We conduct both qualitative and quantitative experiments in Section t and Appendix A.5 demon- strating the efficiency of our sampler for large-scale distributed systems and the superior performance over the basclines. Specifically, we show that our sampler is markedly more robust than existing Langevin Monte Carlo.
2
Related works
Fully distributed (Decentralized) MCMC with thcoretical guarantees In the following related literature, our fully distributed architecture typically described as "docentralized". Throughout this paper, we use the term "fully distributed" for our sampler to underscore its distinction from server-dependent distributed
3

---

Published in Transactions on Machine Learning Research (08/2025)
convergence and consensus guarantee provided for decentralized Langevin dynamics, with the necessity of diminishing stepsize for ensuring asymptotic consensus. Gürbizzallban et al. (2021) independently investigates decentralized stochastic gradient Langevin dynamics and decentralized stochastic gradient Hamiltonian dynamics under the strong convexity assumption. Parayil et al. (0220) consider unadjusted Langevin algorithu with non-log-concave potentials, replacing convexity assumption with bounded conditions of disagreement on the gradient among the distributed agents. Kolesov & Kungurtsev (2021) considers directed graphs in their analysis. Kungurtsev et al. (2023) shows theoretical guarantees for decentralized Metropolis-adhuseed Hamiltonian Monte Carlo, enabling constant step size. It is worth pointing out that except for Parayll et al. (2020), the convergence rates are quantified with Wasserstein distance, while ours is Total Variation distance, which is due to innovative proof techniques used in this work. [har et al. (2023a b) analyzed recentralized Langevin algorithms under asynchronous and event-lriggered conditions, but requires a diminishing step size, while we focus on synchronous settings and utilize a constant step size. Tzikas al. (2024) is, to the best of our knowledge, the most recent work on decentralizod MCMC. Its theoretical guarantees, however, are weaker than ours. Assumption is uncommon, and Theorem 2 predicts counter-intuitivn outcome: the sampler converges more slowly the network becomes denser. In contrast, analysis relies standard assumptions, and Proposition 5.5 shows that convergence speeds up with increased connectivity. Our experiments further show the superior performance of our sampler.
samplers. In Kungurtsey (2020),
See Appendix A.1 for more related works.
3 Preliminaries
3.1
Problem setting
Throughout this paper, we aim to perform Bayesian inference on distributed models by sampling from a target distribution
x
x(x) x exp
Σ
f((z)
(1)
where x Rd. In these models, data is stored locally at each client. To uphold privacy, only estimated parameters are permitted to traverse across the clients.
Without loss of generality, we assume that all the clients located undirected tree structure. This assumption can be satisfied long all the clients non-asymptotic convergence bounds, we utilize the standard assumptions on each potential: we assume each fo is oo-strongly-convex and 3.ssmooth. This condition implies that for any x and
undirected connected graph. To obtain the
V(il)) v) + ///2/l= - vll2 s f1(x) fi(v),
Vfllv) 4/2||= vll 2 fi(x) f.(v).
3.2 Notation
For joint distribution XY defined on (X,Y), the X-marginal distribution is represented by xx, and the X-conditional distribution given y is X|Y==, The iteration complexity is the required number of iterations of Gibbs samplers to achieve a given accuracy.
3.3 Sampling background
Here we list several useful tools and lemmas utilize. The Total Variation (TV) distance and the Kullback- Leibler (KT.) divergence are widely used to quantify the distance between two distributions. For two measures and with density function representations, we have TV,,, = _ =1pp =ll.. The KL divergence of μ and v is defined as KL(A||p) = log tu. Pinsker's inequality states that TV v) < / [KL())))). We also quantify the convergence with We distance in experiments. is defined W2 v) (E, 2/13) where is the coupling of μ and v.
4

---

Published in Transactions on Machine Learning Research (08/2025)
Recall that probability measure satisfies Logarithmic Sobolev Inequality (LSI) with constant 0 (in short, IST(()), if for any distribution such than < v, the KT, divergence KT,(ulpv) and Fisher information [(u]le) = f IIV log p satisfy KL(A|pp) S (1(ll))) It is well-known that a strongly log- concave distribution y with a constant a, equivalently its potential is a-strongly-convex, satisfics LSI with the same constant. Moreover, we utilize the following lemma in our proof.
Lemma 3.1 (Theorem in Durmus & Moulines (2019)). For a strongly log- distribution x with a defined on R one has E Ez>x m mI
where m is the minimizer of the potential.
4 Analysis of Composite Sampling
In this section, we aim to provide the analysis for composite sampling, i.c., sampling from special case of equation !
π(z) & exp(-f(x)) - 9(x)).
(2)
We emphasize that in this distributed setting, each client symmetrically generates samples from conditional distributions, without the need for additional server to aggregate parameters from the two clients. This (wo-node composite sampling is special case of equation [ and our main analysis of distributed sampling is
essentially a generalization of ideas in this section. To proceed, we have the following assumption.
Assumption 4.1. Let (xx) be ay-strongly-conve and B--smothh. Similarly, let g(x) be an og-strongly- convex and 8y-smooth function. It is also necessary to assume f and share the same minimizer m.
Inspired by the success of proximal samplers, this sampling task can be performed by sampling from an augmented distribution
1 || y1² 27
(z. n (x, x exp (f(x) ((v)
and then control the TV distance between т and x with a sufficiently small vy. The procedure summarized in Algorithm 1 We emphasize that Steps 2-4 follow the standard Gibbs sampling procedure, as also adapted in Yuan et al. 2023). Compared to Yuan et al. (2023), one of our main contributions is apply the standard different target distribution and obtain the non-asymptomatic convergence
Gibbs sampling procodure rale to the new larget.
The strong convexity and smoothness assumptions are standard and have been used in a series of sampling
works (Dalalyan 2017a Dalalyan & Karagulyan 2019 Fan et al.) 2023 Altschuler & Chewi 2023). ) Note
that the other assumption that f and g have the same minimizer required to establish the non- aammasymptoicc bounds of TV(n, x )). The same assumption has been discussed Loe et al. (2021) and Yuan et al. (2023).
In Lee et al. (2021), this assumption necessary to analyze the non-asymptotic results of samplers for the same target equation
As mentioned in Lee et al. (2021), ), for two functions f and 9 that have different. minimizers, one can casily find m such that ff(m) + Vg(m)= = 0 since both f and g are strongly convex. Then define f(z) = f(z) - (Vf(m), z) and g(x) := ((z) - x)) It is easy to verify that sampling from cxp(-f(x) - 9(x)) is equivalent to the original target, and f and share the same minimizer m. Furthermore, the necessity of this assumption has been illustrated in Example 3 in Yuan et al. (0023). It is worth emphasizing that Example shows that, without the same minimizer assumption, the non-asymptotic bound also depends on other parameters: when ff and g are quadratic, it also relies on the distance between the centers of the two functions.
The convergence result of the Gibbs sampler in Algorithm 1 has been established in Theorem 5 in Yuan et al. 2023). For the sake of completeness, we restate it here.
Theorem 4.2 (Theorem 5 in Yuan et al. 2023)). Assume Step 3 and Step 4 are eract without any bias, i.e., y and x follow the conditional distributions eractly. Denote the distribution of the k-th samples (x* ) by uXY For the target distribution XY under Assumplion
4.1 we have
KL XL(xXall S KL (1 (1+noy)) + n,,g)
where vx is the X -mmarginal of us XY
5

---

Published in Transactions on Machine Learning Research (08/2025)
Algorithm A Sampler for Composite Potentials
Input: exp(-f(x)) 9(x)): target distribution
Output: zK: Samplers within TV distance of π
Step 1: Construct a distribution x>x;; exp((f((x) g(v) 2n || - =1l²)
# The following the Gibbs sampler for x-
Step Generate an initial sample 2 from vnd
for k + 0,... K do
Step Sample y² π X (y) x exp(-g(V) (g()) 2n 1| y1(
Step Sample x441 x (x) x end for
2nj || y 122)
obtain the overall iteration complexity of Algorithm/ remains select a suitable v based on TV(T,, π )
which can be seen from Theorem 4.3 Even though similar intuition has been discussed in Yuan et al. (023) our work rigorously proves the non-asymptotic bound of TV(x, for the first time.
Theorem 4.3. Under Assumplion
we have
3dd
1
! n0g +1
TV( n S V 2(
(3)
+
0g
O
0g
Proof. As both f and g are strongly convex, by Theorem 3.8. in Saumard & Wellner (014)) the X-marginal distribution x is strongly-log-come concceee with a parameter af + na,t1" Hence, x satisfies LST((y + na,+1 This implies that
ag
KL(T|| S 2(0 g0,+1
[TT|T>*
(4)
By definition, the relative Fisher information I[T||= satisfies
t (x)
[(T|[=*) =
E
V log
(5)
(g) V log (z))
where G,(z)) = fexpeeeppppppe-pp eex((-(()) - 1
27 || - -113))dy
To proceed, notice that
V log G2 E. yywexp( ((pppp(((()-----e - - 11 -1
(6)
where we use the identity I y (Vyeexp(- yields that
211 ulf²) O. Combining equation and equation
[[T||Tx*)
= E E
E - (v(()) - vo(ii)
Ex Eywexpp 9(v) || Vg(ax) V
< -yB - || y/l²
where we adopt Jensen's inequality and the smoothness of g. Then estimate the upper bounds of two expectations ions separately. Denote the minimizer of g(v) 1 | vll as y². For the inner expectation over y in equation 7 we have
E Bysexp( 1000-ggly g(v) ,, || -511=~113>]11 ,|1 - 2
2/ y² 2E
yexp 3. - -11;-=1 v11
(8)
2d
< 2 - y 1/2
ag + 1/7

---

Published in Transactions on Machine Learning Research (08/2025)
Here, the last line is due to Lemma 3.1 Since Vg(u²) (v' x) = 0, for the outer expectation in equation 7
E | 10 v²112 1 En-a V/('")|1
(9)
1)² Bg Euen 111 ml1
d
1) Bg E || |x- mll
S 1 n
3 aj + 0gg
(10)
The second inequality is due to the smoothness of 9 and the assumption that Vy(m) 0, and the third inequality is from the contraction property of the proximal method in optimization. For the last line, we use Lemma 3.1 and the assumption that f and have the same minimizer. With equation equation 7
equation and equation g one has
3d
1/232 a + Og
KL(T||
+
(11)
Of
By n
na +
By Pinsker's incquality, we obtaín equation
Combining Theorem 4.2 and Theorem we are ready to show the overall iteration complexity in Proposi- tion
Proposition 4.4. For simplicity, assume is small enough that the second order term of / ((y-a))))))))))) in
Theorem 4.3 is upped bounded by the first order term n0 and nag < 1. Under Assumption 4.1 to achieve
n
TV distance to n, with Algorithm where 17 = 0
one needs iterations
(0r+3,))d
+ Bg) log
(I 11xx)) ))
K K= 0
(12)
(ay + 2e2
22
2
Proof. Notice that the overall biased term comes from two components: the Gibbs sampler for XX and the distance between and x
By Theorem 4.2 the number of iterations to achieve TV xx)
e/2 is
K 0 <=0(10g) log
KT.(u [
(13)
22
1)(cy + ag))
To ensure TV(T, xx)= S c/2, combining the assumption that 82
is is bounded by the first order term and
asta,
Theorem 4.3 one needs
o
(as + ag)e²
(14)
83d
Therefore, to have TV π) < e, with equation and K 0 (Brt log KL 11**
13 and equation
14 n and K can be =0 (ayta,
0
(3) +8,
[ayta,]22
Remark 4.5 (Weaker Assumptions). The result of Proposition 4.4 can be generalized to the case that g is still strongly convex and smooth, but f is convex and smooth. Then, with the same procedure, one can show the iteration complexity is K = O (0)+ log KL(g""[a>>>
5 Analysis of Distributed Sampling over bipartite graphs
In this section, we present our main result: distributed sampler and its non-asymplolic analysis. Recall that we are interested in sampling from
x(x) x exp -- f((z) (E(()))
(15)

---

Published in Transactions on Machine Learning Research (08/2025)
with the following Assumption 5.1
Assumption 5.1. Without loss of generality, assume that each f1(2) is a-strongly convex and f-smooth. We also assume that each ft shares the same minimizer m. As explained in Section X this assumption is necessary to have non-asymptotic results, and our sampler still converges asymptotically even without this assumplion, as discussed in Remark 5.6
Note the assumption on the same minimizers is computationally feasible to satisfy under the strong convex and smoothness assumption. As discussed above Algorithm 1, potentials with different minimizers can be transformed to satisly the same minimizer assumption without altering the larget. This transformation mainly involves computing minimizer of ft The computation cost of this step is negligible comparing with the sampling iterations when the potentials are strongly convex and smooth. For example, efficient. methods such as fast incremental gradient methods and randomized algorithms (Shalev-Shwartz & Zhang 2014 Nitanda 2014 Lin et al., 2015 Lan& & Zhou 2018) have been developed to solve strongly convex and smooth finite-sum problems in a distributed manner. These methods exhibit complexity that depends on the square root of the condition number, independent of the dimension.
Tt is worth noting that the bipartite graph assumption can be fulfilled on any connected graph. For example. every connected graph has a spanning tree (Serre 2002), and a tree is always bipartite graph (Bondy et al. 1976.. In this setting, the sampler and its iteration complexity are established with steps similar to Section To begin with, denote
ABB T2..... .n) ) x exp
Σ S((x)) ΣΣ aEA DEB
Gas/2nl|zz - m//13) )
(16)
With a slight abuse of notation, we will interchangeably use म AB and म. We have the following assumption for the weights ab..
Assumption 5.2. Let oab > 0 stand for there is an edge between nodes and b. Otherwise, aab 0. Morcover, we assume >. aas I 1 and E, as S 1. Furthermore, we assume the graph is a fully connected bipartite graph. Define the n by n doubly stochastic matrix Σ whose element at the s-th row and t-th column stt This matrix satisfies ats = ast = aab 2 0 if s= a and t = b, and ass = 1 - Ea ss 2 Let (A1,...,An) An) E 1 be the eigenvalues of Σ organizing in the descending order, i.e., A Ai+1,
A bipartite graph divides all nodes into two independent sets: A and B. One can view ft as a local distribution on each node, and the quadratic terms ||.r - 2b correspond to Gaussian distributions on edges. With the same idea in Section | one can sample from â with Gibbs sampling and then reduce the distance between the target and the distribution of Ei= 2//n with a small n, To sample from f, it is natural to use block Gibbs sampler where, at each iteration, each set of parameters is updated simultaneously as shown in Algorithm 2 Namely, in Step 3-4, one can generate the k-th samples, {al beB and {Ma)aEs, in parallel. We emphasize that, thanks to the bipartite graph structure, our sampler is fully distributed without the need for server nodes. In practice, each node only receives information from its neighbors. As explained in 4 While Yuan et al. 2023) also employs Gibbs updates, our analysis concerns different target distribution and, crucially, establishes a non-asymptotic rate for this new target.
To obtain the overall iteration complexity of the sampler in Algorithm 2 we start with the non non-asymptotic bounds associated with the block Gibbs sampler. Theorem 10 in Yuan et al. (2023) establishes the convergence rate of the block Gibbs sampler over bipartite graphs. We improve the original convergence rates after reviewing its proof. The improvement. comes from both the definition of ABB and a tighter upper bound of e, in Equation (12) in Yuan et al. (2023). Notice that in Yuan et al. (2023) Tab E [0, 1] without the additional constrain that E, Jab S 1, Σ, Oab S 1 we add in this work. Honce, the lower bound of пj used in the proof of Theorem 10 in Yuan et al. (002)), which is defined as '/ aus with our notation, can be improved to n)-
This leads to Lemma A.1 Directly applying our improved results yields the following convergence rate. The proof of Theorem 5.3 is in Appendix A.2
Theorem 5.3 (Improved from Theorem 10 Yuan et al. (023 ) Assume Steps 3 and 4 in Algorithm 2 are evact without biased terms. Denote the distribution of the samples generated in the k-th iteration by u AB
8

---

Published in Transactions on Machine Learning Research (08/2025)
Algorithm Distributed Sampling over bipartite graph
Input: и as in equation 1 the target distribution
Output: {zr AaEA and { HOB
Step 1: Construct a distribution AAB as in equation 16
# The following the block Gibbs sampler for #AB Step Generate the initial samples {a Joed from 1/)
for +- 0,... K do
Step 3: Sample {- hen ~ Flaotleethaa
which is proportional to exp(- ElEB fol2s) EnEa EsEB 2et 1 rbll?))
Step Sample (a=+))&Ea # @(xa)(ee/een
which is proportional exp(- -1- fa(x)) EnEA EbEn 2n 1 11)) end for
For the target distribution AAB equation 16 under Assumption 5.1 we have
KL AB) s (=
(17)
where C is
C = 11 1."' 17t(1 - t) -t)
t2 + (1 11-t) B
min, Eo Jab
nt(1 - t)
(1-t)
dt.
(18)
min, EE Jab
Here |A] and [B] are the number of nodes in the two disjoint groups, respectively.
As a comparison, in Yuan et al. 2023 the constant C is
f.
nnt(1 - t)
+ (1 1)2 B
1
[
mins Σa Oah
a
17t(1 t) (1-t) 1) B
t2
7
dt.
B
min, En aab
This implies that, for the Gibbs sampler analyzed in Theorem improvement, where the number of nodes.
5.3 our new bound can enjoy an O(n²)
Now we show the proof on bounding TV(#, T) where स is the distribution of Σ, x:/n with joint distribution being Ā. The following Theorem 5.4 holds for any graph, for the sake of presentation, rewrite
* (01, T2, F2.,,,, & exp
Σ M(xa)) - ΣΣ 0.//2n xt.1? 1=1
(19)
s
Theorem 5.4. Under Assumplion 5.1 on the polentials and Assumplion 5.2 on the weights, we have
nf2dd
(n-1) +
12
TV
(20)
a ( -1 (1
2a
where the distribution of E.2/// given the joint distribution in equation largest eigenvrauue of the doubly stochastic matria E defined in Assumption 5.2
19 and X is the second
Proof. First, notice that En Ei 01//20|/ xel1= 24 X (Ind E6 1a) where XT =xff .....
.......,
9

---

Published in Transactions on Machine Learning Research (08/2025)
It is well-known that the cigenvalues of Σ, denoted as (A1...., An) in Assumption 5.2 are from -1 to 1, and (I..... 1) is one eigenvector corresponding to eigenvalue 1. Define the eigendecompasition of Ind - Σ 69 I UAU*, Note that the eigenvalues of Lnd - 2 @ Ia are 1 - A for each X in the set of eigenvalues of L. Since we assume the graph is fully connected, there is only one solution to 1/2,,T((Tnn Σ & Ia)X 0, which is
#1 = 22 ... -n- This implies that - 21 and X > 0 for 2...., n.
With the eigendecompooition, the potential of is F(VRUX) +
2 A..A Here, F(X) : Di= fx();) and X J X. As the first columns of VnU are (1, (1,..., 1) @ I have &f -i=1 Jq. Then, the distribution over the average E It is
2n
# *x1 (81) (x1)
(xp(--((/UX))~////)
II da.
(21)
Intuitively, when 1) is small enough, XTA should be approximately zero. Since 1 - X; 0 if and only if A Xi should converge exp(-F xxp(-F(vnUX)) ==f (f.........) as 17 goes O. With this intuition, we have the following rigorous proof.
When X (of 0, ......0). 0), one has
F(VnUX) = Σ M(t1),
(22)
which is exactly the potential of the target n. Hence, is sufficient to bound the TV distance between distributions in equation 21 and equation 22 This is achieved following similar proof ideas used in the proof
of Theorem
1.3
by Theorem 3.8. in Saumard & Wellner 2014 the &n X1-marginal distribution of #(X) is strongly-log-conent concave with parameter na. Hence, x satisfies LSI(na). This implies that
Under Assumption 5.1
1. [TT|I* KL(T||AA1)> S 2na
(23)
By definition and Jensen's inequality;
*x,
T( [ X1) = Ex V log
π
ET V
log
# #x1
E. B2 F VU 8) -01.0 (A..0......) ........
- - Ve, F(VnUX) X) & (f t
113
< E, =,, 2V,, (VFUU X
VV,F((( 8= (fa
Here &i=m is the conditional distribution of â given &t, i.c.,
n > A.) 1
exp -
2n
Then with the definition of F(X), the assumption that Se(x)) is 3-smooth and Cauchy inequality, we have
()] s 333 x ". 12
10

---

Published in Transactions on Machine Learning Research (08/2025)
Here U2 E [nd consisting of the last (n 1)d columns of U. It follows that
I 2n 3² E E x
11 82
27 2 U2 1?
+ 2n E
ax - (1
U,2 12
(24)
(n l)d
2 32
E 11 ,....,,......................, )
a m - X2)
where { is the minimizer of the potential of x that satisfies
V2, V2,F(Vnl (X + (1 A,)ā;= 0,
(25)
and the last line follows from Lemma
3.1 and the fact that the strong convexity constant of a xi a + [1 - 22)- Then, by equation 25 the smoothness of Jú and each fi has the minimizer m,
is
E, (
1 DUTII
n²
E, |1221 VF & (8
n(1
22)
(26)
1282
B2d
Ex
10 ml1² - (1 X2
)2)
where =
- (V (z1). (xx)) and (.T.....,..,,) ",....,,,T))=----- ~ ( 5 The first line is given
by equation 25 The last line is obtained by the assumption that each J; has the minimizer and the contraction property of the proximal method. With equation 23 equation 24 equation 26 and Pinsker's
inequality, we complete the proof.
Finally, present the overall iteration complexity, assuming n is sufficiently small. In Proposition 5.5 the iteration complexity is affected by the structure of the bipartite graph from two aspects: the mumber of nodes n and the sparsity measured by the spectral gap 1- In Appendix A.5.2) we demonstrate that our sampler presents faster convergence than quadratic dependence on n for perfect binary trees and circular graphs. In Appendix A.4 we show that the same non-asymptotic complexity can be obtained under Wasserstein distance.
Proposition 5.5. For simplicily, we assume is small enough so that the quadralãc term aa in Theorem 5.4 is upped bounded by the first order term a+ Under Assumption 5.1 and 5.2 achieve
n=1
TV distance to n, with an exact sampler for Algorithm and = o (0a221 (1-21-22) one needs iterations d
K- = Ó n ---=(1-xa)) Here x2 is the second largest eigenvalue of the doubly stochastic matria defined in
Assumption 5.2
Proof. Please see the proof in Appendix A.3 which follows the same idea in the proof of Proposition 4.4
Remark 5.6 (Asymptotically convergence). We emphasize that our sampler still converges asymptotically after replacing Assumption 5.1 with mild regularity conditions. As shown in Proposition 5.5 to establish the convergence of the overall sampler, we only need to ensure the convergence of the Gibbs sampler and the convergence of ग lowards π with a sufficiently small Roberts & Smith (1994) gave the simple conditions under which Gibbs samplers converge asymptotically. The second convergence can be proved by Scheffè's s lemma (Scheffé) 1947). as shown in proposition 5.1 in Yuan et al. (2023) and equation in Vono al. (2022a). Both asymptotic convergenees require only mild regularity conditions. Moreover, we demonstrate the convergence in Figure 2b and 2c
11

---

Published in Transactions on Machine Learning Research (08/2025)
6 Experiments
We mainly compare our sampler with two baselines developed from Langevin dynamics. D-SGLD (Gürbüzbal
aban et al. 24
2021 is the decentralized version of stochastic gradient Langevin dynamics, which proceeds
- Jzjj +nVf((=f)) + V k+1 w k+1 (O, where z is the k-th sample on node i. Note that here 1) is fixed, while another baseline, D-SGLD with diminishing step sizes (Parayil et al. 2020 utilizes diminishing step sizes and has been proved to operate under weaker assumptions.
We compare our sampler against D-SGLD using Gaussian targets on perfect binary trees of depth 3. In this case, 0y = 1/3 if there is one edge connecting and j, 0g 11 oij and we replace the unbiasod estimation of gradients (x.") by the exact value. The dimension is 5, and the initial distribution each node is (0, The performance is measured by the estimated 2- 2-Wasserstein distance. We also conduct experiments a more challenging target defined by Exp(-E== fi(x)) xx exp(-|<z]]1-5 -||-- 0.5|| - | 1 || 1.5 where each minimizer is an all-one vector multiplied by scale. It is important to note that this target distribution does not satisfy any condition outlined in Assumptions [.1 and 5.1 Each potential function has distinct minimizers and does not have propertics such as strong convexity or smoothness. Due to potential bias when estimating the W2 distance for this non-Gaussian targel, we measure performance using the L,2 distance between the estimated mean and the ground truth. We repeat each experiment three times and report the mean and 2-sigma error of measurements. Our sampler demonstrates robust performance even for distributions that do not satisfy the assumptions, and it shows greater stability in terms of initial step size compared to the two Langevin-basee samplers.
We highlight the detailed observations. results in Section A..51 larger step size yields faster convergence but also leads more bias. Furthermore, advantage of our Gibbs sampler is that it converges with any step size, while D-SGLD is highly sensitive to the initial step size: large step size result in non-convergence (Figure 2c even divergence (Figure 2ah. Also, D-SGLD with diminishing step sizes exhibits slow convergence when the initial step size is small or when a large number of iterations is required (Figure 2b
First, the performance of our Gibbs sampler aligns with our qualitative
3.0
Di SOU. mestint
055
Goss.
2e00 41-11
0.4
0.2
Ierettone
Tanatoma
(a) Gaussian target with varying
(b) non- -an-Gaasiian target, 1) = 0.2
(c) non-Gaussian target, =
Figure 2: Comparison against D-SGLD with fixed step sizes and diminishing step sizes
Please see Appendix A.6 for more experiments.
7 Conclusions
In conclusion, our study introduces a fully distributed sampler using blocked Gibbs sampling, adaptable to various bipartite graph structures without centralized servers. The non-asymplotic analysis provides a theoretical understanding of its behavior, contributing to the theoretical exploration of fully distributed samplers. Exploring the design and analysis of a more efficient augmented distribution represents a promising direction for future research. It is also interesting to explore how to modify our sampler to mitigate practical issues, e.g., communication cost and statistical heterogeneity.
12

---

Published in Transactions on Machine Learning Research (08/2025)
References
Jason M Altschuler and Sinho Chewi. Faster high-accuracy log-concave sampling via algorithmic warm starts. arXiv preprinl 00c:2322.12243 2023.
Krishna Balasubramanian, Sinho Chewi, Murat A Erdogdu, Adil Salim, and Shunshi Zhang. Towards a theory of con-log-concavs sampling: first-order stationarity guarantees for Langevin Monte Carlo. In Conference on Learning Theory, pp. 2896-2923. PMLR, 2022.
Rémi Bardenet, Arnaud Doucet, and Chris Holmes. On Markov chain Monte Carlo methods for tall data. Journal of Machine Learning Research, 18(47), 2017.
Kinjal Bhar, He Bai, Jemin George, and Carl Busart. Asynchronous Local Computations in Distributed Bayesian Learning. Xixi preprint arXiv:2311 1.00999,, 2023a.
Kinjal Bhar, He Bai, Jemin George, and Carl Busart. Distributed event-triggered unadjusted Langevin algorithm for Bayesian learning. Automatica, 156: 156:111221, 2023b.
John Adrian Bondy, Uppaluri Siva Ramachandra Murty, et al. Graph theory with applications, volume 290. Macmillan London, 1976.
Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, Jonathan Eckstein, et al. Distributed oplimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends& in Machine learning, (()):1 122, 2011.
Longbing Cao, Hui Chen, Xuhui Fan, Joao Gama, Yew-Soon Ong, and Vipin Kumar. Bayesian Federated Learning: A Survey. arXiv preprint arXiv:2304. 13267, 2023.
Yongxin Chen, Sinho Chewi, Adil Salim, and Andre Wibisono. Improved analysis for a proximal algorithm PMLR, 2022.
for sampling. In Conference on Learning Theory, pp.
Arkabandhu Chowdhury and Christopher Jermaine. Parallel and distributed MCMC via shepherding distributions. In International Conference on Artificial Intelligence and Statistics, pp. 1819-1827. PMLR, 2018.
Arnak Dalalyan. Further and stronger analogy between sampling and optimization: Langevin Monte Carlo and gradient descent. In Conference on Learning Theory, pp. 678-689 PMLR, 2017a.
Arnak Dalalyan. Theoretical guarantees for approximate sampling from smooth and log-concave densities. Journal of the Royal Statistical Society Series B: Statistical Methodology, 79(3):651 676, 2017b.
Arnak S Dalalyan and Avetik Karagulyan. User-friendly guarantees for the Langevin Monte Carlo with inacourate gradient. Stochastic Processes and their Ayplications, 129(12):5278 5311, 2019.
Arnak S Dalalyan and Lionel Riou-Durand. On sampling from log-concave density using kinetic Langevin diffusions. 2020.
Daniel A De Souza, Diego Mesquita, Samuel Kaski, and Luigi Acerbi. Parallel MCMC without embarrassing failures. In International Conference on Artificial Intelligence and Statistics, pp. 1786-1804. PMLR, 2022.
Kumar Avinava Dubey, Sashank Reddi, Sinead A Williamson, Barnabas Poczos, Alexander J Smola, and Eric P Xing. Variance reduction in stochastic gradient Langevin dynamics. Advances in neural information processing systems, 29, 2016.
Alain Durmus and Eric Moulines. High-dimensional Bayesian inference via the unadjusted Langevin algorithm. 2019.
Jiaojiao Fan, Bo Yuan, and Yongxin Chen. Improved dimension dependence of proximal algorithm for sampling. In Conference Learning Theory, pp. PMLR, 2023.
13

---

Published in Transactions on Machine Learning Research (08/2025)
Joseph Gonzalez, Yucheng Low, Arthur Gretton, and Carlos Guestrin. Parallel gibbs sampling: From colored fields to thin junction trees. In Proceediiggs of the Fourleenth International Conference on Arlificial Intelligence and Statistics, pp. 324 332. JMLR Workshop and Conference Proceedings, 2011.
Mert Gürbüzzalabaa, Xuefeng Gao, Yuanhan Hu, and Lingjiong Zhu. Decentralized stochastic gradient Langevin dynamics and Hamiltonian Monte Carlo. The Journal of Machine Learning Research, 22(1): 10804-10872, 2021.
Trevor Halsted, Ola Shorinwa, Javier Yu, and Mac Schwager. A survey of distributed optimization methods for multi-robot systems. arXivv preprint arXiv:2103. 12840, 2021.
Dušan Jakovetić, Joao Xavier, and José MF Moura. Fast distributed gradient methods. 1EEE Transactions on Automatic Control, 59(5):1131-1146, 2014.
Yuri Kinoshita and Taiji Suzuki. Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization. arXiv preprint arXiv:2203.16117 2022.
Alexander Kolesov and Vyacheslav Kungurtsev. Decentralized langevin dynamics over a directed graph.
arXiv preprint arXiv:2103.00 05444, 2021.
Nikita Kotelevskii, Maxime Vono, Alain Durmus, and Eric Moulines. Fedpop: A bayesian approach for personalised federated learning. Advances in Neural Information Processing Systems, 35:8687 8701, 2022.
Vyacheslav Kungurtsev. Stochastic gradient Langevin dynamics a distributed network. arXiv preprinl arXi::2001.00665, 2020.
Vyacheslav Kungurtsev, Adam Cobb, Tara Javidi, and Brian Jalaian. Decentralized Bayesian learning with Metropolli-adjustod Hamiltonian Monte Carlo. Machine Learning, pp. 1-29, 2023.
Guanghui Lan and Yi Zhou. An optimal randomizod incremental gradient method. Mathematical programming, 171:167 215, 2018.
Yin Tat Lee, Ruoqi Shen, and Kevin Tian. Structured logconcave sampling with a restricted Gaussian oracle. In Conference on Learning Theory, pp.
PMLR, 2021.
Chunyuan Li, Changyou Chen, David Carlson, and Lawrence Carin. Preconditioned stochastic gradient Langevin dynamics for deep neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 30, 2016a.
Mufan Bill Li and Murat A Erdogdu. Riemannian Langevin algorithm for solving semidefinite programs. arXiv preprint 2rX1::2010.11176, 2020.
Wenzhe Li, Sungjin Ahn, and Max Welling. Scalable MCMC for mixed membership stochastic blockmodels. In Artificial Intelligence and Statistics, pp. 723-731 PMLR, 2016b.
Hongzhou Lin, Julien Mairal, and Zaid Harchaoui. A universal catalyst for first-order optimization. Advances in neural information processing systems, 28, 2015.
Pavel Mach and Zdenek Becvar. Mobile edge computing: A survey on architecture and computation oflooding. IEFE communications surveys butorials, 19(3):1628-166) -111666886666,, 2017.
Gonzalo Mateos, Juan Andrés Bazerque, and Georgios B Giannakis. Distributed sparse linear regression. IEEE Transactions on Signal Processing, 58(10):5262 5276, 2010.
Angelia Nedic, Alex Olshevsky, and Wei Shi. Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optimization, 27(4): -6333, 2017.
Willie Neiswanger, Chong Wang, and Eric Xing. Asymptotically exact, embarrassingly parallel MCMC. orXiv preprint ar xrx:: 1314778,,, 2013.
14

---

Published in Transactions on Machine Learning Research (08/2025)
Atsushi Nitanda. Stochastic proximal gradient descent with acceleration techniques. Advonces in neural informalion processing systems, 27, 2014.
Felix Otto and Cédric Villani. Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality. Journal of Functional Analysis, 173(2):361-400) 2000.
Anjaly Parayil, He Bai, Jemin George, and Prudhvi Gurram. Decentralized Langevin dynamics for Bayesian learning. Advances in Neural Information Processing Systems, 33:15978-15089, 2020.
Sam Patterson and Yee Whye Teh. Stochastic gradient Riemannian Langevin dynamics on the probability simplex. Advances in neural information processing systems, 26, 2013.
Vincent Plassier, Maxime Vono, Alain Durmus, and Eric Moulines. DG-LMC: turn-key and scalable synchronous distributed MCMC algorithm via Langevin Monte Carlo within Gibbs. In International Conference on Machine Learning, pp. 8577 8587. PMLR, 2021.
Shi Pu and Angelia Nedié. Distributed stochastic gradient tracking methods. Mathematical Programming, 187:409-4555 2021.
Hairong Qi, Sitharama Iyengar, and Krishnendu Chakrabarty. Distributed sensor networks- a review of recent research. Journal of the Franklin Institute, 338(6):655-666)) 668, 2001.
Gareth O Roberts and Adrian FM Smith. Simple conditions for the convergence of the gibbs sampler and metropolis-hastings algorithms. Stochastic processes and their applications, 49(2):207-216, 1994.
Adrien Saumard and Jon A Wellner. Log-concavity and strong log-concavity: a review. Statistics surveys, 8: 45, 2014.
Henry Scheffé. A useful convergence theorem for probability distributions. The Annals of Mathematical Statistics, 18(3):434-433, 1947.
Jean-Pierre Serre. Thees. Springer Science Business Media, 2002.
Shai Shalev-Shwartz and Tong Zhang. Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization. In International conference on machine learning, pp. 64 72. PMLR, 2014.
Lukang Sun, Adil Salim, and Peter Richtárík. Federated Learning with Sampling Algorithm under Isoperimetry. arXiv preprint arXiv:2206.0099 00920, 2022.
Shengyang Sun, Guodong Zhang, Jiaxin Shi, and Roger Grosse. Functional variational Bayesian neural networks. arxiv preprint arXic:1903. 05779, 2019.
Alexander Terenin, Danicl Simpson, and David Draper. Asynchronous gibbs sampling. In International Conference on Artificial Intellgencee and Slotistics, pp. 144 154. PMLR, 2020.
Alexandros E Tzikas, Licio Romao, Mert Pilanci, Alessandro Abate, and Mykel Kochenderfer. Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers. arXiv preprint 2rx::22401. 15838, 2024.
properties, and algorithms. Journal of Computational and Graphical Statistics, 30(2):335-23 348, 2020. Maxime Vono, Nicolas Dobigeon, and Pierre Chainais. Asymptotically exact data augmentation: Models,
Maxime Vono, Daniel Paulin, and Arnand Doucet. Efficient MCMC sampling with dimension- free convergence rate using ADMM-type splitting. The Journal of Machine Learning Research, 23(1):1100-1168, 2022a.
Maxime Vono, Vincent Plassier, Alain Durmus, Aymeric Dieuleveut, and Eric Moulines. QL.DD: Quantised Langevin stochastic dynamics for Bayesian foderated learning. In International Conference Artificial Intelligence and Slulislics, pp. 6459 6500. PMLR, 2022b.
Xiangyu Wang and David Dunson. Parallelizing MCMC via Weierstrass sampler. arXiv preprint ar 13Xiv:1312.44000 2013.
15

---

Published in Transactions on Machine Learning Research (08/2025)
Xiangyu Wang, Fangjian Guo, Katherine A Heller, and David B Dunson. Parallelizing MCMC with random partition trees. Advances in neural information processing syslems, 28, 2015.
Chenguang Xi, Van Sy Mai, Ran Xin, Eyad H Abed, and Usman A Khan. Linear convergence in optimization over directed graphs with row-stochastic matrices. IEFE Transactions Automatic Control, 63(10): 3558 3565, 2018.
Minjie Xu, Balaji Lakshminarayanan, Yee Whye Tch, Jun Zhu, and Bo Zhang. Distributed Bayesian posterior sampling via moment sharing. Advonces in neural information processing systems, 27, 2014.
Tao Yang, Xinlei Yi, Junfeng Wu, Ye Yuan, Di Wu, Ziyang Meng, Yiguang Hong, Hong Wang, Zongli Lin, and Karl Johansson. A survey of distributed optimization. Annual Reviews in Control, 47:278-300 305, 2019.
Bo Yuan, Jisojiao Fan, Jiaming Liang, Andre Wibisono, and Yongxin Chen. On class of gibbs sampling over networks. In Gergely Neu and Lorenzo Rosasco (eds.), Proceedings of Thirty Sirth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pp- 5754-5780 PMLR, 12-15 Jul 2023. URL httpps://proceeeiiii
mlr. press/v196/yuan233. hhtml
Kun Yuan, Qing Ling, and Wotao Yin. On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 26(3):1835-1854, 2016.
Shunshi Zhang, Sinho Chewi, Mufan Li, Krishna Balasubramanian, and Murat A Erdogdu. Improved discretization analysis for underdamped Langevin Monte Carlo. In The Thirty Sirth Annuol Conference Learning Theory, pp. 36-71. PMTR, 2023.
Yanling Zheng and Qingshan Liu. review of distributed optimization: Problems, models and algorithms. Neurocomputing, 483:446 459, 2022.
Difan Zon, Pan Xu, and Quanquan Gu. Stochastic gradient Hamiltonian Monte Carlo methods with recursive variance reduction. Advances in Neural Information Processing Systems, 32, 2019.
Difan Zou, Pan Xu, and Quanquan Gu. Faster convergence of stochastic gradient Langevin dynamics for non-log-concave sampling. In Uncertainty in Artificial Intelligence, pp. 1152 1162. PMLR, 2021.
A Appendix
A.1 Other related works
Proximal Samplers: Recently, the proximal sampler (Lee et al. 2021 Chen et al. 2022) achieved the stale-of-the-art probable dimension dependency under different assumplions. Its idea as follows. To sample from ex)(-f(x)), one can sample from exp(-f(x)- 2ny || - y)(²) alternatively between x and y with a Gibbs sampler. Our proposed algorithm can be scen a generalization of proximal samplers into distributed setting. Vono et al. 2022a presents MCMC algorithm using ADMM-type splitting. It considers sampling (a:a) 27 -1 fo:=0ll 0112) with Gibbs sampler and then control the distance between marginals
from exp(- > 1= and the target with a small n) Despite having similar concepts to ours, this sampler requires a centralized
server for the parameter f. Combining with the proximal sampler framework, Lee et al. (2021) has proposed
a high-accuracy approximate sampling algorithm for the same target exp( Ei f(())) This approximate Eatropolis-Hastiing algorithm again requires a server node to gather information from every client.
Distributed MCMC with server-client structures: Embarrassingly parallel MCMC (Neiswanger et al. 2013) employs a two-step process where MCMC runs in parallel on data partitions, followed by a server combining the local results, but suffers from misroprescntation of low-density regions. To mitigate embarrassing failures, De Souza et al. (2022) proposes a new combination strategy, leveraging Gaussian Process surrogate modeling and active learning. To reach high-density regions faster,/Chowar [Chowdhury & Jermaine (2018) utilizes an auxiliary shepherding distribution (SD) to control parallel MCMC chains. Recently several works have focused on Bayesian federated learning. Vono et al. (2022b) extends SGLD to the foderated learning setting, handling the communication bottleneck using gradient compression. Plassier et al. 2021
16

---

Published in Transactions on Machine Learning Research (08/2025)
introduces "DG-LMC", novel, scalable, synchronous distributed MCMC algorithm that integrates Langevin Monte Carlo and Gibbs sampling for efficient Bayesian inference in large-scale data analysis. [otelevskii et al. (002)) addresses uncertainty quantification of personalized federated learning with federated stochastic optimization algorithms.
Distributed Optimization: The typical problem distributed optimization to minimize the target function, >i=1 fi(z) under certain assumptions on each fa and the underlying communication graphs. A class of classical gradient descent based algorithms (Yuan et all 2016) on undirected connected graphs can be represented as x Ei= a.jzz Th ff(z)) where 24g is the local estimated variable client i, A (asz) is the connection matrix, and is the step size at the k-th itcration. There exists great number of distributed optimization algorithms that address unconstrained problems, e.g., the alternating direction method of multipliers (Boyd et al. 2011), the fast gradient method (Jakovetić et al.] 2014), the push-sum algorithm (Nedic et al. 2017 7 Xi et al.
2018), and others. We recommend several surveys (Yang et al,, 2019: Halsted et al. 2021 Zheng & Liu 2022) for readers interested in more comprehensive discussions. We
emphasize that a majority of distributed optimization algorithms do not rely on centralized servers.
Stochastic Gradient Langevin Dynamics: The centralized Stochastic Gradient Langevin Dynamics (SGLD) can be used to sample from exp(- 1 f((x)) on the server-client architecture, It requires evaluating unbiased estimators of gradients by mini-batches. This method has sparked huge number of associated works
in sampling and other machine learning areas (Patterson & Teh 2013 Li et al. 2016a Dubey et al. 2016
et al. 2016b [aardenet et al., 2017 Li & Erdogdul 2020). Non-asymptotic bounds in terms of Wasserstein distance for strongly convex and smooth potentials have been established in Dalalyan (2017a): Dalalyan &
Karagulyan (011)). It is then suggested to combine SGLD with variance reduction to reduce the variance of
stochastic gradients Zoo et al. 2019 2021p. Recently, Kinoshita & Suzuki (0022] Balasubramanian et al.
(2022) have established non-asymptotic bounds under weaker assumptions on potentials.
A.2 Proof of improved convergence rates in Theorem
5.3
To begin with, we rewrite the key results from Yuan et al. 2023 The following corresponds to the proof of Theorem 10 and Proposition 16 in it. As discussed, the following lemma directly comes from utilizing the additional condition E. Jab S 1, E. Jab S we add in this work.
Lemma A.1. Assume Steps 3 and 4 in Algorithm are eract without biased terms. Denote the distribution of the kith samples by v.B. For the larget distribution AAB equation 10 under Assumption 5.1 we have
KL S sexp(() (-m/// cidl KL(U
(27)
where
1)t(1 n -) t)
2
(1 (1-t)² t)2
C ming E. Jab
Here is the upper bound of eigenwalues of HT where the entry of H at the a-th row and b-th column is ow/E.. our- In the proof of Proposilion 16 in Yuan el al. (2023), this H molric is denoted A. We rewrile it to avoid confticts between notations.
Based on Lemma A.1 we have the proof of Theorem 5.3
Proof. We consider the estimation of h in Lemma A.1 As a comparison, Yuan et al. (2023) bounds h by the squared operator norm of H1 which follows that
| op <
BA|
S [|
max
In contrast, we notice
| < | = -ΣΣ
22
- ΣΣ
EE Fab) $ ||B).
Oab
oat)2
a
17

---

Published in Transactions on Machine Learning Research (08/2025)
|A| and [B] are the number of nodes in the group A and B, respectively.
This modification leads to the new lower bound for and hence the improved convergence rate shown in Theorem 5.3 The contraction from (L |*aA) to KL can be analyzed in the same way.
A.3 Proof of Proposition 5.5
Proof. The proof is gencralized from the proof of Proposition
With Theorem 5.3
the roquired iteration
Apply our assumption that the quadratic term is bounded by the first order term to Theorem 5.4. then we have TV(T, π) 0
ensure the convergence of Algorithm 2 is =
0
7pce
This implies that Combining all the requirements, we conclude the proof.
mf
o(1
to have TV(T, x) S e/2, O (1-A)))))) d
A.4 Iteration complexity of Algorithm 2 under Wasserstein distance
In proposition 5.5 we established the interaction complexity when the distance is measured by TV distance. The same complexity can be obtained under Wasserstein distance. Our complexity measured by TV distance is based on Theorem 5.3 and Theorem 5.4 Both thcorems can be reformulated with KL divergence: Theorem 5.4, this can be done by omitting Pinsker's inequality used in the last step. Since we assume each potential is strongly convex, we can apply Talagrand inequality (Otto & Villani 2000) on and f. This inequality claims that the Wasserstein distance is upper bounded by the KL divergence. Hence, the same iteration complexity is followed by the triangle inequality of Wasserstein distance.
A.5 Experiments
A.5.1
Qualitative analysis on general Tree
To illustrate how our algorithm works for general trees, we conduct experiments a tree with five nodes shown in Figure 3 Each fs represents 5-dimensional Gaussian distribution with randomly generated mean and covariance matrix. We denote each one as N E,), and our target is exp(- E
& N(ū, Σ) where ji = - -E ET ET'm, 14) and Σ- = =i= Σ All the Gaussian distributions have condition numbers (the ratio of smoothness and strong convexity) ranging from 2 to 5. The initial samples of X1, X2, and X5 are drawn from a standard Gaussian N I), independently. As explained in Algorithm 2 at each step, our sampler enables fully distributed sampling. For instance, clients and can sample from conditionals independently once 21, Tz, and Ø3 are given. Each sampler runs for 400,000 steps, with the first 100,000 steps being the burn-in stage. In Figure 4 we compare the histogram of generated samples and the truc density along the first coordinate. In this experiment, can demonstrate the following points.
Our sampler can operate on general trees, accommodating scenarios where each node may possess unique strong convexity and smoothness parameters. We point out that a reasonable choice in this case is 17 0.001 and K 400, 000 (See the second column in Figure 4
All marginals converge to the same distribution. This observation holds even when all marginals converge to a biased distribution as shown in the first column of Figure
In practice, we recommend users identify the source of errors and then tune the step size n or iterations K accordingly: reducing 7) may require more iterations. More specifically, if the value of K small, alternative diagnostic tools, such as trace plots, can be employed assess the convergence of the blocked Gibbs sampler. This corresponds the third column of Figure 4 If n relatively big, it becomes apparent that all marginals converge to common distribution, albeit one that is biased toward our target.
A.5.2 Quantitative analysis
is (1, In this section, we assume each is)
and the initial distribution for each node is exp(- (z)) is (0, I.). Also, following the Metropolis weights, we set ab (oo))) 1 if there is edge bet ween
18

---

Published in Transactions on Machine Learning Research (08/2025)
fi
fz
f3
f4
fz
Figure 3: Each local distribution exp(-fi(x) is 5-dimensional Gaussian
node and b. Here, ha is the degree (the number of neighbors) of node a. For these two network structures considered below, perfect binary trees (with layers more than 2) and circular graphs (each node connects lo its two neighbors), the non-zeros value of aab is 1/s. In this section, we repeat each our experiments under five different random seeds and show the 2-sigma error bar in all figures and tables. It supports that our findings are statistically significant.
Dependency on the number of nodes
In Proposition 5.5 we have proved the dependency of the mixing time K on the number of nodes n. Note that it is unclear if this upper bound is tight. To better understand the complexity of n, we conduct experiments on two graph structures, perfect binary trees and circular graphs. We run 100 independent chains for 40 iterations and then estimate the empirical mean and covariance matrix at cach itcration. Since the target distribution is Gaussian, we compute the W2 distance with the explicit formula of W₂ between two Gaussian distributions.
In Figure 5 run our sampler with layers ranging from 3 to 6 corresponding to 15,31, and 63, respectively. Then, we repeat our experiments on circular graphs with the same n. These figures show our sampler converges even when the graph is sparse and the number of nodes relatively large. We further analyze the curves from two perspectives: the slope after the logarithm transformation and the minimal distance along a chain. By Theorem 5.3 the estimated slope after applying logarithm transformation the convergence rate of the Gibbs sampler. In Table ! we observe that the convergence rate small for large n. Morcover, it may indicate faster convergence rate than lincar rates term discussed in Theorem 5.4 by the minimal W2 over each chain in Table 2 Again, we observe that the biased term is large for graphs with more nodes as indicated in Theorem 5.4 Furthermore, the coefficient
We also estimate the biased
of determination (Ii²) for fitting the distances and vn is approximately 0.940; this may indicate that the
dependency in this setting aligns with our theoretical analysis in Theorem 5.4
Table 1: Estimated slopes represented by the mean and 2-sigma error
Graphs
n 7
n 15
n 31
n 63
Perfect binary trees
-0.054 = 0.003
-0.047 + 0.002
-0.039 + 0.002
-0.034 + 0.001
Circular graphs
-0.056 = 0.003
-0.038 + 0.002
-0.028 + 0.002
-0.024 + 0.001
Table Minimal distances represented by the mean and 2-sigma error
Graphs
7
n 15
= 31
Yl 63
Perfect binary trees
0.170 + 0.043
0.270 + 0.020
0.376 + 0.024
0.457 + 0.035
Circular graphs
0.187 + 0.013
0.367 + 0.016
0.526 + 0.015
0.637 + 0.025
19

---

Published in Transactions on Machine Learning Research (08/2025)
Node 1
Mode 3
Dersity
100
1
3.0
15
2.5
10
3.0
200
19
-20
6.0
65
15
M Ch
1.4
Node
Node Demiity
Mode
Tue Density
True Density
12
12
C30
44
Ch
Nodz 4
Node
Node 4
Tue Density
Tue Denolty
Tue Denskiy
1
02
Walt
Node 3
1.0
Node 5
Node 5
Tus Densily
Puue Dersily
Tue Dersky
130
3.5
Figure 4: Each column in the figure represents the histogram of values on all five nodes with unique values. The columns are arranged from left to right, where the n) values are 0.01, 0.001, and 0.0001, respectively. In the first column, 77 is too large that all marginals converge to a biased distribution, while in the third column, 1j is too small that users need more iterations.
A.6 Comparison to D-ADMMS (Tzikas et al., 2024)
D-ADMM is a distributed MCMC variant of ADMM (Matcos et al.] 2010) that treats the primal variable of each agent as the sample and, at each iteration, performs noisy proximal update with neighbor averaging.
20

---

Published in Transactions on Machine Learning Research (08/2025)
2.5
n=7
no7
n-15
nw15
20-
3stance
1.5
1,0
0.5
0.5
0.0
10
15
20
25
15
40
0
10
15
20
30
35
40
Itarations
Beral kitt
(a) Convergence on perfect binary trees
(b) Convergence on circular graphs
Figure 5: The mean and 2-sigma error bar of estimated W2 distances under various nodes on trees (Left) and circular graphs (Right)
Table 3: Gaussian target on three-layer perfect binary tree.
Iterations
20
40
60
80
D-ADMMS with p=0.01
5.83 1: 0.06
13.37 1 0.30
13.52 1 0.01
13.57 1: 0.09
13.38 1: 0.06
D-ADMMS with p=0.1
5.81 0.09
9.75
0.14
9.65
0.13
9.57
0.12
9.53 0.01
D-ADMMS with 0=0.5
5.83 + 0.02
4.38 + 0.03
4.39 = 0.02
4.43 = 0.08
4.39 + 0.08
D-ADMMS with p=5
5.84 0.03
2.76 0.01
1.51 = 0.02
0.97 + 0.01
0.76 0.01
D-SGLD with 005
+.44
8.64 0.02
9.96 # 0.07
+ 10.26
10.31 + 0.13
D-SGLD with 00111
5.86 0.02
1.67 0.03
1.50 0.01
1.48 0.06
1.53 0.01
D-SGLA with 7=0.01
5.83 1: 0.06
4.71 0.02
3.86 0.02
3.17 0.03
2.63 0.03
Ours with y=0.5
5.83 0.06
2.11 1 0.02
2.05 0.01
2.10 1 0.01
2.09 0.06
Ours with -0001
5.83 0.06
3.03 0.03
1.63 0.02
0.98 0.04
0.76 0.01
To stress test robustness, we repeated the Gaussian experiment on the same three-layer perfect binary tree as in Figure [a] but increased the dimensionality from d-5 d-32 and replaced the Gaussian initialization with a uniform initialization. The penally parameter p D-ADMMS varied. We report mean + std over three trials in Table
Gaussian study
The results in Table 3 show a pronounced hyperparameter scnsitivity for D-ADMMS. D-SGLD performs worse overall: at 0.5 it even degrades over time and while 0.1 is more stable, it still plateaus higher contrast, our sampler robust across step sizes: both configurations converge without instability, with 7 = 0.01 achieving 0.76 at 80 iterations matching the best D-ADMMS setting and 17 = 0.5 remaining stable around 2.09. These trends indicate that our method attains competitive accuracy with substantially less hyperparameter sensitivity.
Non-Gaussian study We also evaluated D-ADMMS on the non-Gaussian target of Figure 2b and compared against sampler. The performance metric is the L2 distance between the estimated mean and the ground-truth mean. Results appear below in Table 4
Table shows that D-ADMMS again exhibits strong hyperparameter sensitivity: with a small penalty (p=0.2) the Le mean error oscillates and does not settle, whereas larger penalties improve monotonicity but still remain high at 25 iterations. contrast, our sampler is robust across step sizes: both 7=0.2 and n=2 reach low error quickly and stay low thereafter, with the best value 0.01 25 iterations. Overall, our method achieves lower error with markedly less tuning effort this non-Gaussian target.
21

---

Published in Transactions on Machine Learning Research (08/2025)
Table Mon-Gaussian target
Iterations
10
15
20
25
D-ADMMS with p=0.2
0.03 1: 0.01
0.07 1: 0.05
0.03 = 0.025
0.08 +: 0.06
0.06 1: 0.02
D-ADMMS with p=2
0.42 0.02
0.28 0.03
0.20 0.01
0.15 0.01
0.11 0.01
D-ADMMS with p=5
0.55 + 0.003
0.46 = 0.007
0.39 0.013
0.32 = 0.005
0.27 = 0.005
Ours with y=0.2
0.05 1: 0.006
0.02 + 0.011
0.02 = 0.003
0.02 1 0.009
0.01 0.002
Ours with 1
0.05 + 0.003
0.03 + 0.014
0.02 0.008
0.02 + 0.003
0.03 + 0.012
A.7 Revisiting the differences to Yuan et al. (2023)
Both this work and Yuan et al. (2023) employ Gibbs updates, but the problem setting and crucially the guarantees establish are different.
Scope of the target and augmented model. We focus the fully distributed composite target (2) exp( E==S(())) and analyze a client-only blocked Gibbs sampler over bipartite graphs for the augmented joint law
;(I a exp - Σ f((1))
aah ΣΣ aE Be
|xa
2n
In Yuan et al. 2023). the augmented distribution is itself the target of inference: their results establish mixing of a Gibbs chain for that augmented law, but do not relate it non-asymplotically to the composite objective exp(- E. f(()). In contrast, our augmented law is used only as an instrument: we prove that for sufficiently small the induced marginal distribution close to the composite target x see Theorems 4.3 and 5.4 thereby bridging augmented and original targets with explicit TV bounds.
New non-asymptotic bias control augmentation:
A central novelty of this paper is quantifying the bias induced by
Two-node composite: Theorem
4.3 gives an explicit TV(x,, x>) bound absent Yuan al.
2023)..
Networks: Theorem 5.4 bounds TV(#, m) for the average मे induced by â, with explicit dependence on the spectral gap 1 A the communication weights. This bridges the augmented sampler to the original composite target on graphs.
These results enable end-to-end itcration complexities (Propositions 4.4 and 5.5 were not available in Yuan et al. (2023).
in total variation, which
Sharper Gibbs mixing for the augmented chain. We revisit the block-Gile Gibbs analysis of Yuan et al. (2023) and obtain a lighter contraction constant by (i) imposing the natural weight constraints Σ. Tab and >n Jab < I, and (ii) tightening the bound on the intermediate matrix term. The resulting Theorem 5.3
improves the convergence rate constant by up O(n?) compared to Theorem 10 of Yuan et al. (2023 yielding faster mixing of the augmented chain and directly strengthening the overall complexity bounds.
22


Reviews:
[{"review_id": "pXTJgWWNCX", "reviewer": "Reviewer_rgxK", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Please find below my major comments:\n\n**Major comments**\n1) The augmented distribution $\\pi^{XY}$ and the discrepancy between its marginals and the initial distribution $\\pi$ has also been studied in previous works, see e.g. \n* https://jmlr.org/papers/v23/20-357.html\n* https://proceedings.mlr.press/v139/plassier21a.html\n\nCould the authors compare their bounds with these works? It is not clear to me at which point results in Theorem 4.3 and Proposition 4.4 are novel.\n\n2) Overall, there is a lack of rigor in the theoretical statements and proofs. As an example, statement and proof of Proposition 4.4 needs more rigor: you cannot just say that the second order term is supposed to vanished compared to the first-order team. I would like to see more quantitative results involving exact bounds on $\\eta$ and only at the end, considering asymptotic arguments to provide order of magnitudes. Same remark for Theorem 5.3, $k$ is not defined in the statement.\n\n3) The assumption requiring the potential functions to share the same minimizer $m$ is difficult to meet in a practical scenario as the local datasets of each client are probably different and hence the local minimizer will change. Even if the authors are stating that convergence holds without this assumption, it would be better for the paper quality to get rid of this assumption directly in the main paper.\n\n4) With the current paper writing, it is not clear to me what is the incremental contribution compared to Yuan et al. (2023), given that all the non-asymptotic results initially came from the latter paper. The authors are saying that the bounds are tighter but do not give any comparison or discussion regarding this.\n\n**Minor comments**\n1) Introduction $\\pi$ should be written $\\pi(x)$ to be consistent with the right-hand side. Same remark applies throughout the whole paper, see e.g. Equation (1) and Assumption 4.1.\n2) Notations are not consistent. For instance in Assumption 4.1., the common minimiser is denoted $m$ while $x^*$ is used before.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors are tackling the problem of sampling from a probability distribution having a composite potential, where each potential function comes from a likelihood defined locally on a given node of a network of clients.\nTo address this issue, they propose to rely on an augmented probability distribution which is then targeted using a block Gibbs sampler. Non-asymptotic bounds with the total variation distance are derived, mostly building on the previous work by Yuan et al. (2023).\nSome experiments are provided to illustrate the benefits of the proposed approach.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see my major comments.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "io9uWceLrF", "reviewer": "Reviewer_r5tu", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**:  \n1. The use of block Gibbs sampling on an augmented distribution enables true decentralization, a critical advance for privacy-sensitive applications (e.g., edge computing, sensor networks).  \n2. The non-asymptotic analysis is overall sound to me. It builds on strong convexity/smoothness assumptions and LSI to derive convergence rates. \n3. Experiments highlight the sampler’s robustness to large step sizes (unlike D-SGLD, which diverges) and its scalability to complex graph structures.  \n\n**Weaknesses**:  \n1. The introduction does not sufficiently explain why Gibbs sampling is uniquely suited for distributed settings compared to other MCMC methods (e.g., Metropolis-Hastings, Langevin Monte Carlo). The problem’s relevance to Bayesian learning and privacy-preserving inference is mentioned but not deeply motivated.  \n2. Section 2 lists numerous works but lacks critical analysis. There is no clear mapping of how the proposed method addresses the limitations of prior distributed MCMC.  \n3. Figure 2 compares metrics (Wasserstein distance, mean error) under fixed iterations but not runtime. Since Gibbs sampling may have higher per-iteration costs than SGLD, a comparison of performance vs. wall-clock time is missing.  \n4. The paper does not discuss how initial samples are generated (e.g., random initialization, prior knowledge) or their impact on convergence. The initial distribution $\\nu_0^X$ is mentioned in Proposition 4.4 but not validated in experiments.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This manuscript introduces a fully distributed Markov Chain Monte Carlo (MCMC) sampler for Bayesian inference in decentralized networks, which eliminates the need for centralized servers. The target distribution is defined as $\\pi \\propto \\exp\\left(-\\sum_{i=1}^n f_i(x)\\right)$, where each $f_i$ corresponds to local data at client $i$. The key innovation is a block Gibbs sampling approach on an augmented distribution that incorporates pairwise quadratic terms between clients on a bipartite graph, which enables decentralized communication. Non-asymptotic convergence guarantees in Total Variation (TV) distance for the distributed Gibbs sampler to address a gap in the analysis of fully decentralized samplers.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Add a comparative discussion of prior works, explaining their limitations (e.g., server dependence, convergence guarantees) and how the proposed method addresses these. Clarify the difference between \"fully distributed\" (no server) and \"decentralized\" frameworks used in other studies.  \n2. For experiments, include runtime comparisons between the Gibbs sampler and baselines (e.g., D-SGLD) to address potential efficiency concerns. Discuss initialization strategies in experiments, testing how random vs. informed initializations affect convergence (as in Figure 2).  \n3. In Equation (5) (page 5), the expectation $\\underset{x \\sim \\pi}{\\mathbf{E}}$ is not clearly linked to the variable $x$ in $\\nabla \\log \\frac{\\pi}{\\pi^X}$.", "broader_impact_concerns": "The work promotes privacy-preserving Bayesian inference in distributed systems, which is crucial for applications like healthcare, finance, and edge computing, where data cannot be centralized. The lack of a centralized server reduces single points of failure and enhances robustness, aligning with trends toward decentralized technologies.\n\nThe paper does not explicitly discuss potential downsides. For instance, in sparse graphs, the increased communication complexity could pose a limitation. The energy costs for edge devices also warrant consideration. A brief Broader Impact Statement acknowledging the trade-offs between decentralization and resource usage is advisable. Limitations in real-world deployment, such as graph connectivity requirements, should also be discussed to provide a balanced perspective.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "OoQID8s18Q", "reviewer": "Reviewer_GcEm", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n1. The inherent client-only communication pattern enhances privacy and robustness compared to server-dependent architectures.\n2. The theoretical analyses are rigorous.\n\n### Weaknesses\n1. The theoretical findings are incremental compared with Yuan et al. (2023). Although the authors claim they use the novel techniques in their non-asymptotic bound, I do not find where the authors discuss their novelty, even after reading the proofs of Theorem 4.3 and Theorem 5.4.\n2. The novelty and practical significance were questioned relative to existing distributed MCMC and optimization literature, where the discussion about the previous works is less clear. \n3. Experiments lack comparisons with a wider set of relevant baselines and do not explore sufficiently diverse scenarios (models, data, network structures beyond bipartite graphs) to fully demonstrate the claimed advantages.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the problem of sampling from a target distribution $\\pi(x) \\propto \\text{exp}(-\\sum_{i=1}^n f_i(x_i \\mid \\mathcal{D}_i))$, where each function $f_i$ depends on local data $\\mathcal{D}_i$ by client $i$. The key contribution in this work is to provide non-asymptotic analysis to an existing distributed MCMC algorithm (Yuan et al. 2023) without a central server, relying only on client communication in a two-node case and extension to bipartite graph. In particular, the authors claim that\n\n1. They propose a new distributed sampling algorithm that is fully operational on any bipartite graphs.\n2. They improve the existing non-asymptotic bound from Yuan et al. (2023) and provide the non-trivial upper bound between marginals $\\hat \\pi$ and $\\pi$.\n3. They conduct empirical comparison against D-SGLD and illustrate the enhanced stability and performance of the proposed algorithm under specific conditions.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The authors should provide a detailed comparison of their results with those presented by Yuan et al. (2023). It is crucial that they clearly indicate the necessity and significance of their findings, as Yuan et al. (2023) have already performed non-asymptotic analyses for both Algorithms 1 and 2, and established their rate of convergence. Without such clarity, the importance of the authors' theoretical contributions remains unclear.\n2. More discussion and comparison of earlier distributed MCMC algorithms is needed. Currently, the motivation for selecting Gibbs sampling is not adequately addressed, particularly when more advanced alternatives, such as SGLD or HMC, have been overlooked.\n3. The empirical evaluation needs to be strengthened, including state-of-the-art baselines beyond D-SGLD. The authors should test on more high-dimensional problems and analyze performance across different network topologies beyond bipartite graphs to numerically see the robustness of their algorithms.", "broader_impact_concerns": "No specific negative ethical implications or broader impact concerns requiring a dedicated statement were identified from the provided materials. The research is primarily algorithmic.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)