On a Class of Gibbs Sampling over Networks

Bo Yuan; Jiaojiao Fan; Jiaming Liang; Andre Wibisono; Yongxin Chen

On a Class of Gibbs Sampling over Networks

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

Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5754-5780, 2023.

Abstract

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

$\sum_{i=1}^n f_i(x_i)+\sum_{j=1}^m g_j(y_j)+\sum_{i=1}^n\sum_{j=1}^m\nicefrac{\sigma_{ij}}{2\eta} \Vert x_i-y_j \Vert^2_2$ where each of

$x_i$ and

$y_j$ is in

$\Rd$ ,

$f_1, f_2, \ldots, f_n, g_1, g_2, \ldots, g_m$ are strongly convex functions, and

$\{\sigma_{ij}\}$ encodes a network structure. 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

$\propto \exp[-\sum_{i=1}^n f_i(x)-\sum_{j=1}^m g_j(x)]$ in a distributed manner.

Cite this Paper

BibTeX


@InProceedings{pmlr-v195-yuan23a,
  title = 	 {On a Class of Gibbs Sampling over Networks},
  author =       {Yuan, Bo and Fan, Jiaojiao and Liang, Jiaming and Wibisono, Andre and Chen, Yongxin},
  booktitle = 	 {Proceedings of Thirty Sixth Conference on Learning Theory},
  pages = 	 {5754--5780},
  year = 	 {2023},
  editor = 	 {Neu, Gergely and Rosasco, Lorenzo},
  volume = 	 {195},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {12--15 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v195/yuan23a/yuan23a.pdf},
  url = 	 {https://proceedings.mlr.press/v195/yuan23a.html},
  abstract = 	 {We consider the sampling problem from a composite distribution whose potential (negative log density) is $\sum_{i=1}^n f_i(x_i)+\sum_{j=1}^m g_j(y_j)+\sum_{i=1}^n\sum_{j=1}^m\nicefrac{\sigma_{ij}}{2\eta} \Vert x_i-y_j \Vert^2_2$ where each of $x_i$ and $y_j$ is in $\Rd$, $f_1, f_2, \ldots, f_n, g_1, g_2, \ldots, g_m$ are strongly convex functions, and $\{\sigma_{ij}\}$ encodes a network structure. 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 $ \propto \exp[-\sum_{i=1}^n f_i(x)-\sum_{j=1}^m g_j(x)]$ in a distributed manner. }
}

Endnote

%0 Conference Paper
%T On a Class of Gibbs Sampling over Networks
%A Bo Yuan
%A Jiaojiao Fan
%A Jiaming Liang
%A Andre Wibisono
%A Yongxin Chen
%B Proceedings of Thirty Sixth Conference on Learning Theory
%C Proceedings of Machine Learning Research
%D 2023
%E Gergely Neu
%E Lorenzo Rosasco	
%F pmlr-v195-yuan23a
%I PMLR
%P 5754--5780
%U https://proceedings.mlr.press/v195/yuan23a.html
%V 195
%X We consider the sampling problem from a composite distribution whose potential (negative log density) is $\sum_{i=1}^n f_i(x_i)+\sum_{j=1}^m g_j(y_j)+\sum_{i=1}^n\sum_{j=1}^m\nicefrac{\sigma_{ij}}{2\eta} \Vert x_i-y_j \Vert^2_2$ where each of $x_i$ and $y_j$ is in $\Rd$, $f_1, f_2, \ldots, f_n, g_1, g_2, \ldots, g_m$ are strongly convex functions, and $\{\sigma_{ij}\}$ encodes a network structure. 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 $ \propto \exp[-\sum_{i=1}^n f_i(x)-\sum_{j=1}^m g_j(x)]$ in a distributed manner.

APA


Yuan, B., Fan, J., Liang, J., Wibisono, A. & Chen, Y.. (2023). On a Class of Gibbs Sampling over Networks. Proceedings of Thirty Sixth Conference on Learning Theory, in Proceedings of Machine Learning Research 195:5754-5780 Available from https://proceedings.mlr.press/v195/yuan23a.html.

Related Material

Download PDF