Timezone: »
Poster
Learning Restricted Boltzmann Machines with Sparse Latent Variables
Guy Bresler · RaresDarius Buhai
Restricted Boltzmann Machines (RBMs) are a common family of undirected graphical models with latent variables. An RBM is described by a bipartite graph, with all observed variables in one layer and all latent variables in the other. We consider the task of learning an RBM given samples generated according to it. The best algorithms for this task currently have time complexity $\tilde{O}(n^2)$ for ferromagnetic RBMs (i.e., with attractive potentials) but $\tilde{O}(n^d)$ for general RBMs, where $n$ is the number of observed variables and $d$ is the maximum degree of a latent variable. Let the \textit{MRF neighborhood} of an observed variable be its neighborhood in the Markov Random Field of the marginal distribution of the observed variables. In this paper, we give an algorithm for learning general RBMs with time complexity $\tilde{O}(n^{2^s+1})$, where $s$ is the maximum number of latent variables connected to the MRF neighborhood of an observed variable. This is an improvement when $s < \log_2 (d1)$, which corresponds to RBMs with sparse latent variables. Furthermore, we give a version of this learning algorithm that recovers a model with small prediction error and whose sample complexity is independent of the minimum potential in the Markov Random Field of the observed variables. This is of interest because the sample complexity of current algorithms scales with the inverse of the minimum potential, which cannot be controlled in terms of natural properties of the RBM.
Author Information
Guy Bresler (MIT)
RaresDarius Buhai (ETH Zurich)
More from the Same Authors

2021 Poster: The staircase property: How hierarchical structure can guide deep learning »
Emmanuel Abbe · Enric BoixAdsera · Matthew S Brennan · Guy Bresler · Dheeraj Nagaraj 
2020 Poster: Sharp Representation Theorems for ReLU Networks with Precise Dependence on Depth »
Guy Bresler · Dheeraj Nagaraj 
2020 Poster: Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms »
Dheeraj Nagaraj · Xian Wu · Guy Bresler · Prateek Jain · Praneeth Netrapalli 
2020 Spotlight: Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms »
Dheeraj Nagaraj · Xian Wu · Guy Bresler · Prateek Jain · Praneeth Netrapalli 
2019 Poster: Sample Efficient Active Learning of Causal Trees »
Kristjan Greenewald · Dmitriy Katz · Karthikeyan Shanmugam · Sara Magliacane · Murat Kocaoglu · Enric BoixAdsera · Guy Bresler 
2018 Poster: Sparse PCA from Sparse Linear Regression »
Guy Bresler · Sung Min Park · Madalina Persu 
2017 : Community Detection and Invariance to Distribution »
Guy Bresler