A1129
Title: A phase transition in sampling from restricted Boltzmann machines
Authors: Youngwoo Kwon - University of Minnesota (Korea, South) [presenting]
Qian Qin - University of Minnesota (United States)
Guanyang Wang - Rutgers University (United States)
Yuchen Wei - Rutgers University (United States)
Abstract: Restricted Boltzmann machines are a class of undirected graphical models that play a key role in deep learning and unsupervised learning. The aim is to prove a phase transition phenomenon in the mixing time of the Gibbs sampler for a one-parameter restricted Boltzmann machine. Specifically, the mixing time varies logarithmically, polynomially, and exponentially with the number of vertices depending on whether the parameter c is above, equal to, or below a critical value $c_star = -5.87$. A key insight from the analysis is the link between the Gibbs sampler and a dynamical system, which are utilized to quantify the former based on the behavior of the latter. To study the critical case $c = c_star$, a new isoperimetric inequality is developed for the samplers stationary distribution by showing that the distribution is nearly log-concave.
