Skip to main content
Back

Researchers Prove t-SNE's Core Math Collapses High-Dimensional Data Into a Blob

A new arXiv paper by mathematicians Rupert Li and Elchanan Mossel proves that t-SNE's own objective function collapses high-dimensional data into a single point.

Paper, Full Access
  • Rupert Li (Stanford) and Elchanan Mossel (MIT) prove t-SNE's global optimum collapses high-dimensional data to a point.
  • For equidistant inputs or perplexity at least n-1, all output points coincide at one location.
  • For uniform sphere samples, the global minimizer squeezes almost every point into a vanishingly small ball.
  • Setting perplexity too close to the number of points is provably catastrophic, forcing bandwidths to infinity.
  • Experiments on spheres from d=2 to d=100,000 visually confirm the predicted collapse behavior.
  • Full paper on arXiv; practical t-SNE may work only because gradient descent finds good local minima.

t-SNE is the workhorse behind nearly every scatter plot you have ever seen of a neural network's embedding space, and has been the default technique for 2D visualizations of high-dimensional data since 2008. A new theoretical paper posted to arXiv by Rupert Li and Elchanan Mossel now formalizes something practitioners have long suspected: the algorithm's mathematical objective is fundamentally broken for certain natural data distributions, provably collapsing everything into a tiny blob.

The authors do not attack the practical heuristics that people run in scikit-learn. Their target is the theoretical ideal, the global minimum of the loss function that t-SNE is trying to reach with gradient descent. They show that this ideal is often a disaster.

What t-SNE is actually optimizing

t-SNE works by constructing two probability distributions over pairs of points. It computes a similarity measure between all pairs of points in the high-dimensional dataset, then considers a candidate mapping of that dataset into a lower-dimensional space, typically 2D or 3D. A second similarity measure is computed between the low-dimensional points, and the algorithm arranges them so the two distributions are as close as possible. The high-dimensional side uses a Gaussian kernel; the low-dimensional side uses a Student's t-distribution with one degree of freedom, whose heavy tails give t-SNE its name and its cluster-spreading behavior. KL divergence measures the gap between the two distributions.