Stochastic Neighbor Embedding separates well-separated clusters
This addresses a theoretical gap for practitioners using SNE and t-SNE in dimensionality reduction, though it is incremental as it builds on existing methods.
The paper proves that Stochastic Neighbor Embedding (SNE) and its variants can quantitatively separate well-separated clusters when embedding from high dimensions to Euclidean space, providing the first theoretical results for these widely used methods.
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.