An Analysis of the t-SNE Algorithm for Data Visualization

By Sanjeev Arora, Wei Hu, Pravesh Kothari. 2018

212 citations recorded by the source corpus.

A first line of attack in exploratory data analysis is data visualization, i.e., generating a 2-dimensional representation of data that makes clusters of similar points visually identifiable. Standard Johnson-Lindenstrauss dimensionality reduction does not produce data visualizations. The t-SNE heuristic of van der Maaten and Hinton, which is based on non-convex optimization, has become the de facto standard for visualization in a wide range of applications. This work gives a formal framework for the problem of data visualization - finding a 2-dimensional embedding of clusterable data that correctly separates individual clusters to make them visually identifiable. We then give a rigorous analysis of the performance of t-SNE under a natural, deterministic condition on the "ground-truth" clusters (similar to conditions assumed in earlier analyses of clustering) in the underlying data. These are the first provable guarantees on t-SNE for constructing good data visualizations. We show that our deterministic condition is satisfied by considerably general probabilistic generative models for clusterable data such as mixtures of well-separated log-concave distributions. Finally, we give theoretical evidence that t-SNE provably succeeds in partially recovering cluster structure even when the above deterministic condition is not met.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

The art of using t-SNE for single-cell transcriptomics (2018, methodology): “When initialising with scaled PCA as in Figure 7c, we obtained much better results when using aggressive early exaggeration (Linderman and Steinerberger, 2017; Arora et al., 2018): we used α = 120 for 1000 iterations followed by another 1000 iterations with α = 4.”
A more globally accurate dimensionality reduction method using triplets (2018, background): “Also it has been proven theoretically (Arora et al., 2018) that if the clusters are separated far enough in higher dimension, then t-SNE separates them in the embedding 7.”
A Unifying Perspective on Neighbor Embeddings along the Attraction-Repulsion Spectrum (2020, methodology): “Prior work used ‘early exaggeration’ only as an optimisation trick (van der Maaten and Hinton, 2008) that allows to separate well-deﬁned clusters (Linderman and Steinerberger, 2019; Arora et al., 2018).”
T-SNE-CUDA: GPU-Accelerated T-SNE and its Applications to Modern Data (2018, methodology): “We redirect interested readers to Van der Maaten’s and Arora et al. ’s works [1], [15] for a thorough comparison between t-SNE and these visualization methods.”
Metric Learning for Adversarial Robustness (2019, background): “Figure 1 shows the visualization of the high dimensional latent representation of sampled CIFAR-10 images with t-SNE [40, 2].”
GPU accelerated t-distributed stochastic neighbor embedding (2019, methodology): “’s works [1], [25] for a thorough comparison between t-SNE and these visualization methods.”
Stochastic Neighbor Embedding under f-divergences (2018, background): “Only recently researchers showed that if the high-dimensional input data does contain prominent clusters then the 2D t-SNE visualization will be able to successfully capture the cluster structure [12, 3].”