On a Class of Gibbs Sampling over Networks
share
We consider the sampling problem from a composite distribution whose potential (negative log density) is ∑_i=1^n f_i(x_i)+∑_j=1^m g_j(y_j)+∑_i=1^n∑_j=1^mσ_ij/2η‖ x_i-y_j ‖^2_2 where each of x_i and y_j is in ℝ^d, f_1, f_2, …, f_n, g_1, g_2, …, g_m are strongly convex functions, and {σ_ij} encodes a network structure. 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 <cit.>. 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 ∝exp(-∑_i=1^n f_i(x)-∑_j=1^m g_j(x)) in a distributed manner.
READ FULL TEXT