Learning Restricted Boltzmann Machines with Arbitrary External Fields
This work addresses a limitation in graphical model learning for researchers, as prior methods only handled consistent external fields, making it an incremental advance.
The authors tackled the problem of learning Restricted Boltzmann Machines with arbitrary external fields, presenting the first algorithm for this setting that achieves optimal dimension dependence in sample complexity and runtime, though with suboptimal parameter dependence.
We study the problem of learning graphical models with latent variables. We give the first algorithm for learning locally consistent (ferromagnetic or antiferromagnetic) Restricted Boltzmann Machines (or RBMs) with {\em arbitrary} external fields. Our algorithm has optimal dependence on dimension in the sample complexity and run time however it suffers from a sub-optimal dependency on the underlying parameters of the RBM. Prior results have been established only for {\em ferromagnetic} RBMs with {\em consistent} external fields (signs must be same)\cite{bresler2018learning}. The proposed algorithm strongly relies on the concavity of magnetization which does not hold in our setting. We show the following key structural property: even in the presence of arbitrary external field, for any two observed nodes that share a common latent neighbor, the covariance is high. This enables us to design a simple greedy algorithm that maximizes covariance to iteratively build the neighborhood of each vertex.