On a Class of Gibbs Sampling over Networks

Authors Bo Yuan, Jiaojiao Fan, Jiaming Liang, Andre Wibisono, Yongxin Chen

Publication date 23 June 2023

Abstract: We consider the sampling problem from a composite distribution whose potential (negative log density) is

s u m_{i = 1}^{n} f_{i} (x_{i}) + s u m_{j = 1}^{m} g_{j} (y_{j}) + s u m_{i = 1}^{n} s u m_{j = 1}^{m} f r a c s i g m a_{i j} 2 e t a V e r t x_{i} - y_{j} V e r t_{2}^{2}

where each of

x_{i}

and

y_{j}

is in

m a t h b b R^{d}

,

f_{1}, f_{2}, l d o t s, f_{n}, g_{1}, g_{2}, l d o t s, g_{m}

are strongly convex functions, and

s i g m a_{i j}

encodes a network structure. % motivated by the task of drawing samples over a network in a distributed manner. Building on the Gibbs sampling method, we develop an efficient sampling framework for this problem when the network is a bipartite graph. More importantly, we establish a non-asymptotic linear convergence rate for it. This work extends earlier works that involve only a graph with two nodes cite{lee2021structured}. To the best of our knowledge, our result represents the first non-asymptotic analysis of a Gibbs sampler for structured log-concave distributions over networks. Our framework can be potentially used to sample from the distribution

p r o p t o e x p (- s u m_{i = 1}^{n} f_{i} (x) - s u m_{j = 1}^{m} g_{j} (x))

in a distributed manner.

This page was built for publication: On a Class of Gibbs Sampling over Networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6441317)