  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.
