Exact Inference with Latent Variables in an Arbitrary Domain
  We analyze the necessary and sufficient conditions for exact inference of a
latent model. In latent models, each entity is associated with a latent
variable following some probability distribution. The challenging question we
try to solve is: can we perform exact inference without observing the latent
variables, even without knowing what the domain of the latent variables is? We
show that exact inference can be achieved using a semidefinite programming
(SDP) approach without knowing either the latent variables or their domain. Our
analysis predicts the experimental correctness of SDP with high accuracy,
showing the suitability of our focus on the Karush-Kuhn-Tucker (KKT) conditions
and the spectrum of a properly defined matrix. As a byproduct of our analysis,
we also provide concentration inequalities with dependence on latent variables,
both for bounded moment generating functions as well as for the spectra of
matrices. To the best of our knowledge, these results are novel and could be
useful for many other problems.
