Provable Gaussian Embedding with One Observation
  The success of machine learning methods heavily relies on having an
appropriate representation for data at hand. Traditionally, machine learning
approaches relied on user-defined heuristics to extract features encoding
structural information about data. However, recently there has been a surge in
approaches that learn how to encode the data automatically in a low dimensional
space. Exponential family embedding provides a probabilistic framework for
learning low-dimensional representation for various types of high-dimensional
data. Though successful in practice, theoretical underpinnings for exponential
family embeddings have not been established. In this paper, we study the
Gaussian embedding model and develop the first theoretical results for
exponential family embedding models. First, we show that, under mild condition,
the embedding structure can be learned from one observation by leveraging the
parameter sharing between different contexts even though the data are dependent
with each other. Second, we study properties of two algorithms used for
learning the embedding structure and establish convergence results for each of
them. The first algorithm is based on a convex relaxation, while the other
solved the non-convex formulation of the problem directly. Experiments
demonstrate the effectiveness of our approach.
