  Stochastic Neighbor Embedding and its variants are widely used dimensionality
reduction techniques -- despite their popularity, no theoretical results are
known. We prove that the optimal SNE embedding of well-separated clusters from
high dimensions to any Euclidean space R^d manages to successfully separate the
clusters in a quantitative way. The result also applies to a larger family of
methods including a variant of t-SNE.
